Riddler Classic – 12/21/2018

This week’s Riddler Classic is about using probability to estimate the length of a playlist.

Santa’s elves are working in the workshop and listening to 100 songs each shift. About half of the time, there is at least one song that is repeated. The problem is to use the information above to find the length of Santa’s playlist.

The solution is below.

Santa’s playlist is 7175 songs long.

The key to solving the problem is to remember the famous birthday problem:

How many people need to be in a room to have a greater than 50% chance that two of them have the same birthday.

The solution to the birthday problem involves calculating the probability that everybody in the room has different birthdays, that is:

\frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \cdots \cdot \frac{365-n}{365}.

The solution is the smallest value of n that gives a probability less than \frac{1}{2}.

For the playlist problem, we know the number of songs that are played, which means there will be 100 total factors in the probability calculation. The probability of not repeating a song on a playlist of n songs is

\displaystyle \prod_{i=0}^{99} \frac{n-i}{n}.

The final challenge is to set the above expression equal to \frac{1}{2} and solve for n.

To solve the equation, I used the following R code.


# Define a function for the equation.
f <- function(x) {
product = 1
for(i in 1:99) product <- product * (x-i)/x
return (product - 0.5)
}

# Solve where the function is equal to 0.
answer <- uniroot(f, c(100, 12000))
# Print the solution.
print(answer$root)

For a sanity check, I calculated the probability of a repeat as a function of n and graphed the results below. The black dashed line represents the solution of 7175.

Santa - Probability vs Length

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s