{"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":"

This holiday-themed Riddler problem<\/a> is about probability:<\/p>\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’s call $p$ the probability that at least one song gets played twice and let’s 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’t 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’ll go with that!<\/p>\n<\/div>\n","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":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2610","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2610"}],"version-history":[{"count":5,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2610\/revisions"}],"predecessor-version":[{"id":2617,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2610\/revisions\/2617"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2615"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2610"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2610"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2610"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}