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:

Figure_1.png

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")

 

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