{"id":3112,"date":"2021-10-30T10:33:25","date_gmt":"2021-10-30T15:33:25","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3112"},"modified":"2021-11-07T01:18:39","modified_gmt":"2021-11-07T06:18:39","slug":"squid-game","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/squid-game\/","title":{"rendered":"Squid game"},"content":{"rendered":"<p>This week&#8217;s <a href=\"https:\/\/fivethirtyeight.com\/features\/can-you-survive-squid-game-riddler\/\">Riddler Classic<\/a> is <a href=\"https:\/\/www.netflix.com\/title\/81040344\">Squid Game<\/a>-themed!<\/p>\n<blockquote><p>\nThere are 16 competitors who must cross a bridge made up of 18 pairs of separated glass squares. Here is what the bridge looks like from above:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/fivethirtyeight.com\/wp-content\/uploads\/2021\/10\/Screen-Shot-2021-10-27-at-10.05.55-PM.png?w=1400\" alt=\"\" \/><\/p>\n<p>To cross the bridge, each competitor jumps from one pair of squares to the next. However, they must choose one of the two squares in a pair to land on. Within each pair, one square is made of tempered glass, while the other is made of normal glass. If you jump onto tempered glass, all is well, and you can continue on to the next pair of squares. But if you jump onto normal glass, it will break, and you will be eliminated from the competition.<\/p>\n<p>The competitors have no knowledge of which square within each pair is made of tempered glass. The only way to figure it out is to take a leap of faith and jump onto a square. Once a pair is revealed \u2014 either when someone lands on a tempered square or a normal square \u2014 all remaining competitors take notice and will choose the tempered glass when they arrive at that pair.<\/p>\n<p>On average, how many of the 16 competitors will make it across the bridge?\n<\/p><\/blockquote>\n<p>Here is my solution.<br \/>\n<a href=\"javascript:Solution('soln_squidgame','toggle_squidgame')\" id=\"toggle_squidgame\">[Show Solution]<\/a><\/p>\n<div id=\"soln_squidgame\" style=\"display: none\">\n<p>Let&#8217;s consider a more general version of the game. Let $f(n,m)$ to be the expected number of competitors that make it across the bridge assuming there are $n$ total competitors and the bridge has $m$ unknown tiles remaining. If there are no competitors, then clearly none can make it across. Also, if there are no unknown tiles remaining, then all competitors make it through. This leads to the boundary conditions<br \/>\n\\begin{align}<br \/>\nf(0,m) &#038;= 0\\quad\\text{for }m=0,1,2,\\dots \\\\<br \/>\nf(n,0) &#038;= n\\quad\\text{for }n=0,1,2,\\dots<br \/>\n\\end{align}Now consider the general case with $n$ competitors and $m$ bridge tiles. Each time a competitor takes a turn, they will cross some number of tiles before they are eliminated. Let&#8217;s look at the possible cases for the first competitor.<\/p>\n<ul>\n<li> With probability $1\/2$, they are eliminated on the first tile. So the $n-1$ remaining competitors only have to contend with $m-1$ unknown tiles.\n<li> With probability $1\/4$, they are eliminated on the second tile. So the $n-1$ remaining competitors only have to contend with $m-2$ unknown tiles.\n<li> Continuing in this fashion, with probability $1\/2^m$, they are eliminated on the last (the $m^\\text{th}$) tile, and the $n-1$ remaining competitors have $0$ unknown tiles to deal with.\n<li> Finally, with the remaining probability of $1\/2^m$, the competitor guesses all tiles correctly, which means that all $n$ competitors will get across safely.\n<\/ul>\n<p>We can express these statements concisely in the following recursion.<br \/>\n\\[<br \/>\nf(n,m) = \\sum_{k=1}^m \\frac{1}{2^k} f(n-1,m-k) + \\frac{n}{2^m}<br \/>\n\\]One way to simplify this expression is to multiply both sides by $2^m$ and define $g_n(m) := 2^m f(n,m)$. Then, the recursion becomes<br \/>\n\\begin{align}<br \/>\ng_0(m) &#038;= 0 \\\\<br \/>\ng_n(m) &#038;= n + \\sum_{k=0}^{m-1} g_{n-1}(k)\\quad\\text{for }n=1,2,\\dots<br \/>\n\\end{align}Applying this recursion for the first several steps, we obtain<br \/>\n\\begin{align}<br \/>\ng_1(m) &#038;= 1\\\\<br \/>\ng_2(m) &#038;= 2+m\\\\<br \/>\ng_3(m) &#038;= \\tfrac{1}{2}(6+3m+m^2)\\\\<br \/>\ng_4(m) &#038;= \\tfrac{1}{6}(24+14m+3m^2+m^3)\\\\<br \/>\ng_5(m) &#038;= \\tfrac{1}{24}(120+70m+23m^2+2m^3+m^4)\\\\<br \/>\ng_6(m) &#038;= \\tfrac{1}{120}(720+444m+120m^2+35m^3+m^5)\\\\<br \/>\ng_7(m) &#038;= \\tfrac{1}{720}(5040+3108m+1024m^2+135m^3+55m^4-3m^5+m^6)\\\\<br \/>\ng_8(m) &#038;= \\dots<br \/>\n\\end{align}From there, we can recover the expected number of winners via $f(n,m) = g_n(m) \/2^m$. Although computing each subsequent function is straightforward, I could not find a closed-form expression for $g_n(m)$. Each is a polynomial of degree $n-1$, but beyond some obvious observation such as the constant term being $n$ and the common denominator being $(n-1)!$, I couldn&#8217;t find a general formula.<\/p>\n<p>For the specific instance ($n=16$ and $m=18$) described in the problem statement, we can obtain the exact expected number of winners, and it is<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\nf(16,18) = \\frac{458757}{65536} = 7.0000762939453125 \\text{ (exact)}<br \/>\n$<\/span><\/p>\n<p>which is slightly larger than $7$.<\/p>\n<h3>Approximate (asymptotic) solution<\/h3>\n<p>We can approximate $f(n,m)$ as follows. Each tile will eliminate on average $\\frac{1}{2}$ of a contestant. So if we start with $n$ contestants, roughly $n-\\frac{1}{2}m$ contestants will cross the bridge. This leads to the approximation<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\nf(n,m) \\approx n-\\tfrac{1}{2}m<br \/>\n$<\/span><\/p>\n<p>This approximation doesn&#8217;t work when the number of contestants is small. For example, if $n\\lt \\frac{1}{2}m$, it would lead to a negative number of contestants crossing the bridge, which is of course impossible. But the approximation turns out to be pretty good when $n$ is larger. Applying the approximation to the specific instance in the problem statement, we find $f(16,18) \\approx 16-\\tfrac{1}{2}\\cdot 18 = 7$, and this is <em>very<\/em> close to the true solution!<\/p>\n<p>Here are some plots that confirm the formula; I plotted $f(n,m)$ for fixed values of $n$ and $m$.<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2021\/10\/squid_game.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2021\/10\/squid_game-1024x363.png\" alt=\"\" width=\"840\" height=\"298\" class=\"aligncenter size-large wp-image-3128\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2021\/10\/squid_game-1024x363.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2021\/10\/squid_game-300x106.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2021\/10\/squid_game-768x272.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2021\/10\/squid_game-1536x544.png 1536w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2021\/10\/squid_game-2048x725.png 2048w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2021\/10\/squid_game-1200x425.png 1200w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a>\n<\/div>\n<p>And here is a much better solution!<br \/>\n<a href=\"javascript:Solution('soln_squidgame2','toggle_squidgame2')\" id=\"toggle_squidgame2\">[Show Solution]<\/a><\/p>\n<div id=\"soln_squidgame2\" style=\"display: none\">\n<p>This solution comes courtesy of comments by Guy D. Moore and MarkS.<\/p>\n<p>As in the previous solution, suppose we have $n$ contestants and $m$ bridge tiles. Suppose $b$ tiles are broken during the course of the game. This occurs with probability $\\frac{1}{2^m}\\binom{m}{b}$, since each tile has a probability of $\\frac{1}{2}$ of being guessed incorrectly. When $b$ tiles are broken, $n-b$ contestants cross the bridge. Finally, we can break at most $\\min(n,m)$ tiles, since there are only $m$ tiles, and each of the $n$ players can break at most one tile. Therefore, the expected number of competitors to make it across the bridge is:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\nf(n,m) = \\frac{1}{2^m}\\sum_{b=0}^{\\min(n,m)} \\binom{m}{b}(n-b)<br \/>\n$<\/span><\/p>\n<p>If the special case where $n\\geq m$, the sum will go up to $m$, and we can evaluate it exactly, by writing:<br \/>\n\\begin{align}<br \/>\n(1+x)^m &#038;= \\sum_{b=0}^m \\binom{m}{b} x^{m-b} \\\\<br \/>\nx^{n-m}(1+x)^m &#038;= \\sum_{b=0}^m \\binom{m}{b} x^{n-b} \\\\<br \/>\n(n-m)x^{n-m-1}(1+x)^m + m x^{n-m}(1+x)^{m-1} &#038;= \\sum_{b=0}^m \\binom{m}{b} (n-b)x^{n-b-1}<br \/>\n\\end{align}where in the last step, we differentiated both sides with respect to $x$. Now, setting $x=1$ on both sides and dividing by $2^m$, we obtain:<br \/>\n\\[<br \/>\n\\frac{1}{2^m}\\sum_{b=0}^m \\binom{m}{b} (n-b) = n-\\frac{1}{2}m<br \/>\n\\]So the &#8220;asymptotic&#8221; solution I found in my first solution isn&#8217;t just asymptotic; it&#8217;s exact when $n\\geq m$.<\/p>\n<p>When $n\\lt m$, there is no closed-form expression for the sum. However, we can be smart about how we evaluate it. Since we know the sum of all $m$ terms, we only have to evaluate $\\min(n,m-n)$ terms. This leads us to the complete solution:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 45px 10px 45px 10px;\">$\\displaystyle<br \/>\nf(n,m) = \\begin{cases}<br \/>\nn-\\frac{1}{2}m &#038; \\text{if }n \\geq m \\\\<br \/>\n\\frac{1}{2^m}\\sum_{b=0}^n \\binom{m}{b} (n-b) &#038; n\\lt m\\\\<br \/>\nn-\\frac{1}{2}m-\\frac{1}{2^m}\\sum_{b=n+1}^m \\binom{m}{b} (n-b) &#038; n \\lt m\\text{ (alt.)}<br \/>\n\\end{cases}<br \/>\n$<\/span><\/p>\n<h3>Interesting side-note<\/h3>\n<p>Guy D. Moore also pointed out that there is a simpler recurrence relation for $f(n,m)$, given by:<br \/>\n\\[<br \/>\nf(n,m) = \\frac{f(n,m-1) + f(n-1,m-1)}{2}<br \/>\n\\]Using this recurrence with the generating function<br \/>\n\\[<br \/>\nG(x,y) = \\sum_{n=0}^\\infty \\sum_{m=0}^\\infty f(n,m) x^n y^m,<br \/>\n\\]it is possible to show that:<br \/>\n\\[<br \/>\nG(x,y) = \\frac{x}{(1-x)^2}\\cdot \\frac{2}{2-y(x+1)}<br \/>\n\\]Therefore, $f(n,m)$ is the coefficient corresponding to the $x^n y^m$ term in the series expansion of $G(x,y)$ above! Here is an example of this working for $n=16$ and $m=18$ (as in the original problem) <a href=\"https:\/\/www.wolframalpha.com\/input\/?i2d=true&#038;i=SeriesCoefficient%5C%2891%29Divide%5Bx%2CPower%5B%5C%2840%291-x%5C%2841%29%2C2%5D%5DDivide%5B2%2C%5C%2840%292-y%5C%2840%29x%2B1%5C%2841%29%5C%2841%29%5D%5C%2844%29+%7Bx%2C0%2C16%7D%5C%2844%29+%7By%2C0%2C18%7D+%5C%2893%29\">using WolframAlpha<\/a>.\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>This week&#8217;s Riddler Classic is Squid Game-themed! There are 16 competitors who must cross a bridge made up of 18 pairs of separated glass squares. Here is what the bridge looks like from above: To cross the bridge, each competitor jumps from one pair of squares to the next. However, they must choose one of &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/squid-game\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Squid game&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":3128,"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":[6,8,15,2],"class_list":["post-3112","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-counting","tag-probability","tag-recursion","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3112","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=3112"}],"version-history":[{"count":20,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3112\/revisions"}],"predecessor-version":[{"id":3135,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3112\/revisions\/3135"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/3128"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=3112"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=3112"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=3112"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}