{"id":3381,"date":"2022-06-25T13:11:29","date_gmt":"2022-06-25T18:11:29","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3381"},"modified":"2022-06-27T16:23:09","modified_gmt":"2022-06-27T21:23:09","slug":"tower-of-goats","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/tower-of-goats\/","title":{"rendered":"Tower of goats"},"content":{"rendered":"

This week’s Riddler classic<\/a> is a counting problem. Can the goats fit in the tower?<\/p>\n

\nA tower has 10 floors, each of which can accommodate a single goat. Ten goats approach the tower, and each goat has its own (random) preference of floor. Multiple goats can prefer the same floor. One by one, each goat walks up the tower to its preferred room. If the floor is empty, the goat will make itself at home. But if the floor is already occupied by another goat, then it will keep going up until it finds the next empty floor, which it will occupy. But if it does not find any empty floors, the goat will be stuck on the roof of the tower. What is the probability that all 10 goats will have their own floor, meaning no goat is left stranded on the roof of the tower?\n<\/p><\/blockquote>\n

My solution:
\n[Show Solution]<\/a><\/p>\n

\n

Suppose there are $n$ goats and the building has $n$ floors. Let $a_i$ be the floor preference of goat $i$, with $i=1,\\dots,n$. We will say a vector of floor preferences $v=(a_1,a_2,\\dots,a_n)$ is “crowded” if it leads to exactly one goat on each floor.<\/p>\n

Let $f(n)$ be the number of crowded floor preferences. Since there are $n^n$ total possible preference vectors (each of the $n$ goats can prefer $n$ different floors), the probability that each goat finds a floor is $f(n)\/n^n.$ Therefore, solving the problem amounts to finding $f(n)$.<\/p>\n

The following elegant counting argument is due to Pollak (1974). We start by considering a modified version of the problem:<\/p>\n

    \n
  1. Add one extra floor (the roof). The goats are allowed to pick this $(n+1)^\\text{st}$ floor as their preferred floor.\n
  2. Just like the other floors, the roof can accommodate at most one goat.\n
  3. If a goat ends up on the roof and there is no space for it, the goat “wraps around”; it takes the elevator back down to the first floor and continues its search for an open floor.\n<\/ol>\n

    In our modified version of the problem, each goat will eventually occupy a floor (possibly the roof), and there will be exactly one empty floor. If the empty floor is the roof, then no goat had the roof as its preferred floor, no goat ever visited the roof, and no goat ever had to take the elevator back down. Therefore, the vector of floor preferences was crowded according to our original definition. Conversely, if one of the other floors ends up empty, then a goat ended up on the roof, which means the original vector of floor preferences was either invalid (one of the goats picked the roof), or the preferences were valid but a goat nonetheless overflowed onto the roof.<\/p>\n

    So not only is $f(n)$ equal to the number of crowded preference vectors in the original problem, it is also equal to the number of preference vectors in the modified problem that lead to the roof being empty.<\/p>\n

    The final piece to this argument is to realize that there must be an equal number of preference vectors that lead to the $k^\\text{th}$ floor being empty, for $k=1,\\dots,n+1$. This follows because of the symmetry in the modified version of the problem. Specifically, if a particular preference vector $(a_1,\\dots,a_n)$ leads to floor $k$ being empty, then $(a_1+j,\\dots,a_n+j)$ leads to floor $k+j$ being empty (where we wrap all numbers around so they are in the range between $1$ and $n+1$).<\/p>\n

    Since there are $(n+1)^n$ total possible preference vectors for the modified problem (each of the $n$ goats can prefer $n+1$ different floors), and there are $n+1$ possible empty floors, we obtain
    \n\\[
    \nf(n) = \\frac{(n+1)^n}{n+1} = (n+1)^{n-1}
    \n\\]Converting this number into a probability as explained at the beginning of the solution, we find that the probability that $n$ goats have a crowded set of preferences is<\/p>\n

    $\\displaystyle
    \np(n) = \\frac{(n+1)^{n-1}}{n^n} = \\frac{1}{n+1}\\left(1+\\frac{1}{n}\\right)^n
    \n$<\/span><\/p>\n

    For the case $n=10$, we can calcluate:
    \n\\[
    \np(10) = \\frac{11^9}{10^{10}} = \\frac{2{,}357{,}947{,}691}{10{,}000{,}000{,}000} \\approx 23.58\\%
    \n\\]<\/p>\n

    Since $\\lim_{n\\to\\infty} \\left(1+\\frac{1}{n}\\right)^n = e$, it follows that in the asymptotic limit of large $n$, we have $p(n) \\sim \\frac{e}{n+1}$. Here is a plot comparing the true probability to this asymptotic approximation.<\/p>\n

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

    About this problem’s history<\/h3>\n

    This sort of counting problem, where you start with a preference and move to the next available open slot, is also known as a parking problem<\/em>, because its original formulation was about cars trying to park on a one-way street and taking the next available open spot. There are many other equivalent counting problems, which you can find more about in the entry A000272<\/a> in the Online Encyclopedia of Integer Sequences. For a wonderful explanation of the parking problem and other related counting problems, take a look at Richard Stanley’s slides on the topic<\/a>. The solution in my post above is based on the argument in Richard’s slides, which is due to Pollak (1974).<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

    This week’s Riddler classic is a counting problem. Can the goats fit in the tower? A tower has 10 floors, each of which can accommodate a single goat. Ten goats approach the tower, and each goat has its own (random) preference of floor. Multiple goats can prefer the same floor. One by one, each goat … Continue reading “Tower of goats”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":3388,"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":[29,6,8,2],"class_list":["post-3381","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-classics","tag-counting","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3381","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=3381"}],"version-history":[{"count":15,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3381\/revisions"}],"predecessor-version":[{"id":3392,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3381\/revisions\/3392"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/3388"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=3381"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=3381"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=3381"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}