Another week, another riddler. Here is this week’s problem:
In Santa’s workshop, elves make toys during a shift each day. On the overhead radio, Christmas music plays, with a program randomly selecting songs from a large playlist.
During any given shift, the elves hear 100 songs. A cranky elf named Cranky has taken to throwing snowballs at everyone if he hears the same song twice. This has happened during about half of the shifts. One day, a mathematically inclined elf named Mathy tires of Cranky’s sodden outbursts. So Mathy decides to use what he knows to figure out how large Santa’s playlist actually is.
Help Mathy out: How large is Santa’s playlist?
So to do this we used minimized N for the following
Each term represents the chance that the song is not a repeat — so the first song has a 0/N chance, so the chance that it is not that song is 1. This gets multiplied by the (1-1/N) for the second song, etc. etc.
This results in 7176 when our shift length is 100. Next, we vary the shift length and find the resulting playlist length:
This, interestingly, follows the following equation for a playlist length of l and playlist length of N:
Now we know why the shift length is 100, its likely the total number of Christmas songs 🙂
import matplotlib.pyplot as plt
prob = 0
songs_in_playlist = 200
while prob < goal_prob:
prob = 1
for i in range(shift_len_in_songs): prob = (1-(i/songs_in_playlist)) * prob
songs_in_playlist += 1
x = [i for i in range(50,200)]
y = [num_songs_in_playlist(0.5,i) for i in range(50,200)]
plt.xlabel("Shift Length (songs)")
plt.title("Santa's playlist length to ensure repeating\n probability 0.5 over various shift lengths")