{"id":2610,"date":"2018-12-21T23:06:21","date_gmt":"2018-12-22T05:06:21","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2610"},"modified":"2018-12-22T01:24:34","modified_gmt":"2018-12-22T07:24:34","slug":"elf-music","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/elf-music\/","title":{"rendered":"Elf music"},"content":{"rendered":"

<\/p>This holiday-themed Riddler problem<\/a> is about probability:\n

\nIn Santa\u2019s 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.<\/p>\n

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\u2019s sodden outbursts. So Mathy decides to use what he knows to figure out how large Santa\u2019s playlist actually is.<\/p>\n

Help Mathy out: How large is Santa\u2019s playlist?<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

This problem is short and sweet. The probability in question seems complicated, because there are so many different ways in which a song (or several songs) could repeat. This is made much easier by using complementarity. Namely:
\n\\[
\n\\mathrm{Prob}(\\text{at least one song repeats}) = 1-\\mathrm{Prob}(\\text{no songs repeat})
\n\\]And the probability that no songs repeat is simply the probability that all songs are different. This is much easier to calculate! Let\u2019s call $p$ the probability that at least one song gets played twice and let\u2019s say there are $n$ different songs on the playlist. Then we have:
\n\\begin{align}
\np &= 1-\\mathrm{Prob}(\\text{all }100\\text{ songs are different})\\\\
\n&= 1-\\frac{(\\text{number of ways of picking }100\\text{ different songs})}{(\\text{number of ways of picking }100\\text{ songs})}\\\\
\n&= 1-\\frac{n(n-1)(n-2)\\cdots(n-99)}{n^{100}} \\\\
\n&= 1-\\binom{n}{100}\\frac{100!}{n^{100}}
\n\\end{align}Of course, this formula is only valid if $n\\ge 100$. If there aren\u2019t at least $100$ songs, then by the Pigeonhole Principle<\/a>, a song getting picked twice is inevitable. The formula for the probability $p$ of hearing at least one repeated song as a function of the number of different songs $n$ is therefore:<\/p>\n

$\\displaystyle
\np = \\begin{cases}
\n1 & \\text{if }1 \\le n \\le 99\\\\
\n1-\\binom{n}{100}\\frac{100!}{n^{100}} & \\text{if }n \\ge 100
\n\\end{cases}
\n$<\/span><\/p>\n

We can make a plot of this function to see how it changes as a function of $n$:<\/p>\n

\"\"<\/a><\/p>\n

As expected, the probability remains at or near $1$ for awhile, and then drops once the number of songs on the playlist gets very large. Searching near $p=0.5$ as stated in the problem, the closest candidate $n$ values are:
\n\\begin{align}
\nn=7174\\quad&\\implies\\quad p=0.50002836 \\\\
\nn=7175\\quad&\\implies\\quad p=0.49997983
\n\\end{align}The closest to $p=0.5$ is attained by $n=7175$, so we\u2019ll go with that!<\/p>\n<\/div>\n

<\/p>\n<\/body>","protected":false},"excerpt":{"rendered":"

This holiday-themed Riddler problem is about probability: In Santa\u2019s 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 … Continue reading “Elf music”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2615,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[9,6,8,2],"class_list":["post-2610","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-binomial","tag-counting","tag-probability","tag-riddler"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t