Need help with HL Math question

[Chriscor]

So, I haven't actually started the IB yet, (I'm in PRE-IB, starting IB next year), and will be taking HL Maths. My maths teacher gave the the following question:

"A CD has 10 different songs on it.The CD is put on shuffle and repeat, so no matter which song plays, any one of the 10 songs could be up next. What is the probability that at least one of the songs will be played at least 3 times before all of the songs have been played at least once."

I NEED help with this question, or it will drive me crazy.

So, i thought working out the probability of this NOT happening would be easier, and then just subtract that from one.

So, for this not to happen, once all the songs have been played at least once, all the songs need to  have played either once or twice right? (No more, no less)

So, let the number of songs that play twice be x. We know that x ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

So, i just need to calculate the probability for x to be any of these values.

P(x=0) = ((10/10)(9/10)(8/10)...(1/10)¹) * (10!/(0!*(10-0)!)

P(x=1) = ((10/10)(9/10)(8/10)....(1/10)²) * (11!/(2!*(11-2)!)

P(x=2) = ((10/10)(9/10)(8/10)....(1/10)⁴) * (12!/(4!*(12-4)!)

etc.

Then I can calculate P(x=∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), and 1 - P(x=∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}) should be my answer, correct?

What i want to know is if this way of solving the problem is correct. If not, what's wrong?

Additionally, this will take a long time to calculate, is there (i assume there must be, but as I sad, I'm not in the IB yet, so i haven't learned any of the fancy techniques) an easier way to solve this?

Sincerely, 

A future IB student who is about to lose his sanity.

Edited January 1, 2017 by Chriscor
Typos and clarification

[kw0573]

I hope to share my thoughts so we could work as a team to solve this problem. Math SL and HL exams would either test a simpler probability/combinatorics problem(few related concepts), or longer questions with probability in conjunction with many other concepts, but never such a tedious problem of just probability. 

I think your logic is correct: find probability of when all songs have been played  that no song has been played more than twice. I lost you after that; please kindly explain further. 

This new probability is P(no threefold repetition AND all songs have been played), and similar to what you did, do this for 10-19 songs. 

For example at 11 songs

P(no threefold AND all played) = permutations of 11 songs that include all songs with only dublicates/ all permutations , which is arrangement with repetition, and is (11! / 2!) * 10C1/ 10^11. 10C1 because any of 10 cards could have been the duplicated card and with each choice there are 11!/2! ways of rearranging. For n songs this is (n! / ((n-10)*2!)) * 10C(n-10)/10^n. The desired probability of at least a threefold is 1 - sum of this expression for n from 10 to 19.

[kw0573]

Ah what I failed to consider is that the last song played must not be a duplicate ...

EDIT: So with this in mind, and once again considering 11 songs, the first 10 songs must contain the pair. The one remaining song can be any one of the single songs. We can modify the P(no triple AND all there, n = 11) = (10! / 2!) * (10C1) * 9C8 / 10^11, where 9C8 is to choose 8 out of the 9 unrepeated songs to appear in the first 10 songs. 

The generalized formula for n songs is thus (n - 1)! / ((n-10)*2!) * 10C(n-10) * (10 - (n-10))C(10 - (n-10) - 1) / 10^n

10 - (n - 10) = 20 - n is the number of songs played once, 19 - n must be chosen for the songs before the final song. 20 - n choose 19 - n is 20 - n

general probability = (n - 1)! / ((n-10)*2!) * 10C(n-10) * (20 - n) / 10^n

I get 1-0.050 or 0.950 chance of at least 1 song repeating at least 3 times. I will update my answer if a simulation proves likewise. 

EDIT: In a simulation of over 60000 "playlists", I got 0.978 chance. So it's quite possible that I made a mistake. If others have spot the mistakes please let me know.

 

Edited January 2, 2017 by kw0573