3
$\begingroup$

Suppose every friday night you like going in a lounge bar and drink some soft drinks. Usually you spend $t$ minutes (say, $120$) there and talking to the bartender you know that there are exactly $N$ songs (say, $100$), of $3$ minutes each, in the playlist that keeps the typical atmosphere. The algorithm of the player is made such that once a song is played, it can't be played until other $n$ (say, $20$) different songs are played, then the probability of the choice of that song returns uniform as before.

What is the probability that you'll listen to the same song twice?

Honestly I do not know how to attack this problem, I saw that this kind of problems can have solutions that are "very strange" but still beautiful.

$\endgroup$

1 Answer 1

2
$\begingroup$

Let's calculate the probability that all the songs played will be different. The probability of hearing at least one repeated song is then $1$ minus that probability.

The first $n+1$ songs will always be different because of the shuffle algorithm.

The next song cannot be any of the previous $n$ songs, but could be any one of the other $N-n$ songs, $1$ of which you have heard before. So the probability that song $n+2$ differs is $\frac{N-n-1}{N-n}$.

The song after that cannot be any of the previous $n$ songs, but could be any one of the other $N-n$ songs, $2$ of which you have heard before. So the probability that song $n+3$ differs is $\frac{N-n-2}{N-n}$.

The song after that cannot be any of the previous $n$ songs, but could be any one of the other $N-n$ songs, $3$ of which you have heard before. So the probability that song $n+4$ differs is $\frac{N-n-3}{N-n}$.

This continues until you have heard $T=\frac{t}{3}$ songs.

I'll leave you to finish this off.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.