# Elf Playlist

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

#### $P_{N} = \prod_{i=1}^{100}(1-\frac{i}{N})\approx0.5$

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:

#### $N = 0.7214l^2 - 1.8316l+2.6343$

Now we know why the shift length is 100, its likely the total number of Christmas songs 🙂

import matplotlib.pyplot as plt

def num_songs_in_playlist(goal_prob,shift_len_in_songs):
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
return songs_in_playlist

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.ylabel("Playlist Length")
plt.scatter(x,y)
plt.title("Santa's playlist length to ensure repeating\n probability 0.5 over various shift lengths")