{"id":2419,"date":"2018-08-27T11:37:15","date_gmt":"2018-08-27T16:37:15","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2419"},"modified":"2018-08-28T07:56:32","modified_gmt":"2018-08-28T12:56:32","slug":"hoop-hop-showdown","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/hoop-hop-showdown\/","title":{"rendered":"Hoop hop showdown"},"content":{"rendered":"<p>This <a href=\"https:\/\/fivethirtyeight.com\/features\/how-many-hoops-will-kids-jump-through-to-play-rock-paper-scissors\/\">Riddler puzzle<\/a> is a shout-out to this <a href=\"https:\/\/www.youtube.com\/watch?v=PcIord7RNAI\">YouTube video<\/a> of a game called &#8220;Hoop hop showdown&#8221;.<\/p>\n<blockquote><p>\nHere is an idealized list of its rules:<\/p>\n<ul>\n<li>Kids stand at either end of N hoops.\n<li>At the start of the game, one kid from each end starts hopping at a speed of one hoop per second until they run into each other, either in adjacent hoops or in the same hoop.\n<li>At that point, they play rock-paper-scissors at a rate of one game per second until one of the kids wins.\n<li>The loser goes back to their end of the hoops, a new kid immediately steps up at that end, and the winner and the new player hop until they run into each other.\n<li>This process continues until someone reaches the opposing end. That player\u2019s team wins!\n<\/ul>\n<p>You\u2019ve just been hired as the gym teacher at Riddler Elementary. You\u2019re having a bad day, and you want to make sure the kids stay occupied for the entire class. If you put down eight hoops, how long on average will the game last? How many hoops should you put down if you want the game to last for the entire 30-minute period, on average?\n<\/p><\/blockquote>\n<p>Here is a derivation of how I solved the problem:<br \/>\n<a href=\"javascript:Solution('soln_hoophop','toggle_hoophop')\" id=\"toggle_hoophop\">[Show Solution]<\/a><\/p>\n<div id=\"soln_hoophop\", style=\"display: none\">\n<p><strong>Note:<\/strong> The wording in the problem is a bit ambiguous with regards to a few details. e.g. Do the players start outside and jump into the first hoop when they start or do they start inside the first hoop? Does the game end when you win at the last hoop, or one second later when you jump out? I made assumptions that I thought were reasonable in formulating the problem. While slight changes in details regarding the problem could change the final answer, the same general solution approach should still apply.<\/p>\n<p>There are $N$ hoops but there are $k=1,2,\\dots,2N-1$ possible ways in which two kids can stop to have a rock-paper-scissors (RPS) match. This is because the two kids can land in the same hoop or in adjacent hoops. Here is a diagram for $N=3$ showing all possible pairs:<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown1.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown1-1024x815.png\" alt=\"\" width=\"840\" height=\"669\" class=\"aligncenter size-large wp-image-2422\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown1-1024x815.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown1-300x239.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown1-768x611.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown1-1200x955.png 1200w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown1.png 1498w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>Here is an example of how the game might play out in this simple scenario:<\/p>\n<ol>\n<li>When the game starts, both kids are outside the hoops. After 2 seconds, we end up in the $k=3$ case.\n<li>Suppose blue wins. Then 1 second later we are in $k=5$.\n<li>Suppose orange wins. Then 1 second later we are in $k=2$.\n<li>Suppose orange wins. Then 1 second later we are in $k=1$.\n<li>Suppose orange wins. Then the game ends.\n<\/ol>\n<p>Let&#8217;s generalize this process to any number of hoops. We&#8217;ll call $f(k)$ the expected number of seconds we have to wait for the game to end if we are currently in state $k$. If we are at state $k$, here are the options:<\/p>\n<ol>\n<li>If orange wins RPS, the next showdown occurs at state $\\left\\lfloor \\frac{k}{2} \\right\\rfloor$ after $\\left\\lfloor \\frac{k+2}{4} \\right\\rfloor$ seconds unless $k=1$, in which case the game ends.\n<li>If blue wins RPS, the next showdown occurs at state $\\left\\lfloor \\frac{2N+k+1}{2} \\right\\rfloor$ after $\\left\\lfloor \\frac{2N-k+2}{4} \\right\\rfloor$ seconds unless $k=2N-1$, in which case the game ends.\n<\/ol>\n<p>Note that we&#8217;re using the notation $\\left\\lfloor x \\right\\rfloor$ which is the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Floor_and_ceiling_functions\">floor function<\/a> (round $x$ down to the nearest integer). We must also account for how many seconds a game of RPS lasts on average. Let&#8217;s call this $r$. There are nine equally likely possible games, and one third of them end in a tie (so we must play again). So the game duration satisfies: $r = 1 + \\frac{1}{3}r$. In other words, we have $r=\\frac{3}{2}$. Putting everything together, the function $f(k)$ satisfies:<br \/>\n\\begin{multline}<br \/>\nf(k) = \\frac{3}{2} + \\frac{1}{2}\\left( \\left\\lfloor \\frac{k+2}{4} \\right\\rfloor + f\\biggl(\\left\\lfloor \\frac{k}{2} \\right\\rfloor\\biggr) \\right)\\\\<br \/>\n+ \\frac{1}{2}\\left( \\left\\lfloor \\frac{2N-k+2}{4} \\right\\rfloor + f\\biggl( \\left\\lfloor \\frac{2N+k+1}{2} \\right\\rfloor \\right) \\biggr)<br \/>\n\\end{multline}with the boundary conditions $f(0)=f(2N)=0$. These are in fact linear equations in the variables $f(k)$ for $k=0,1,\\dots,2N$. Ultimately, we want to know the average duration of a game. The first showdown always occurs at state $N$ and is preceded by $\\left\\lfloor\\frac{N+1}{2}\\right\\rfloor$ hops. So we&#8217;re ultimately looking to find:<br \/>\n\\[<br \/>\nT_\\text{avg} = \\left\\lfloor\\frac{N+1}{2}\\right\\rfloor + f(N)<br \/>\n\\]Here is how you would solve the problem in the $N=3$ case. The equations that relate the different $f(k)$ can be written out in matrix-vector form:<br \/>\n\\[<br \/>\n\\begin{bmatrix}<br \/>\n  1 &#038;   0 &#038;  0 &#038;  -\\tfrac{1}{2} &#038;   0 \\\\<br \/>\n -\\tfrac{1}{2} &#038;   1 &#038;  0 &#038;  -\\tfrac{1}{2} &#038;   0 \\\\<br \/>\n -\\tfrac{1}{2} &#038;   0 &#038;  1 &#038;   0 &#038;  -\\tfrac{1}{2} \\\\<br \/>\n  0 &#038;  -\\tfrac{1}{2} &#038;  0 &#038;   1 &#038;  -\\tfrac{1}{2} \\\\<br \/>\n  0 &#038;  -\\tfrac{1}{2} &#038;  0 &#038;   0 &#038;   1<br \/>\n\\end{bmatrix}<br \/>\n\\begin{bmatrix}<br \/>\nf(1)\\\\ f(2) \\\\ f(3) \\\\ f(4)\\\\ f(5)<br \/>\n\\end{bmatrix}<br \/>\n=\\begin{bmatrix}<br \/>\n2\\\\\\tfrac{5}{2}\\\\\\tfrac{5}{2}\\\\\\tfrac{5}{2}\\\\2<br \/>\n\\end{bmatrix}<br \/>\n\\]Solving these equations produces $f(3)=11.5$ and therefore $T_\\text{avg} = 13.5\\text{ sec}$. As we add more hoops (increase $N$), the procedure is analogous, and we can write code that rapidly solves these equations for a wide range of $N$ values&#8230; But we can do better!<\/p>\n<p>Note that we don&#8217;t actually care about the other values of $f(k)$. We only need to know the middle one, $f(N)=f(3)$. Also note that the columns of the matrix all sum to zero except the middle one&#8230; So if we sum all columns (equivalent to summing all our equations together), we obtain:<br \/>\n\\[<br \/>\nf(3) = 2+\\tfrac{5}{2}+\\tfrac{5}{2}+\\tfrac{5}{2}+2 = 11.5<br \/>\n\\]which is the same answer as we found by solving the whole system! In fact, this pattern persists for all $N$. Our matrix will always have dimensions $(2N-1)\\times(2N-1)$ and all columns will sum to zero except the middle one! So in general, we can write the solution for the case of $N$ hoops as:<br \/>\n\\begin{align}<br \/>\nT_\\text{avg} &#038;= \\left\\lfloor\\frac{N+1}{2}\\right\\rfloor + f(N) \\\\<br \/>\n&#038;= \\left\\lfloor\\frac{N+1}{2}\\right\\rfloor+\\sum_{k=1}^{2N-1} \\left( \\frac{3}{2} + \\frac{1}{2}\\left\\lfloor \\frac{k+2}{4} \\right\\rfloor + \\frac{1}{2}\\left\\lfloor \\frac{2N-k+2}{4} \\right\\rfloor  \\right) \\\\<br \/>\n&#038;= \\frac{3}{2}(2N-1) + \\left\\lfloor\\frac{N+1}{2}\\right\\rfloor+\\sum_{k=1}^{2N-1} \\left( \\frac{1}{2}\\left\\lfloor \\frac{k+2}{4} \\right\\rfloor + \\frac{1}{2}\\left\\lfloor \\frac{2N-k+2}{4} \\right\\rfloor  \\right) \\\\<br \/>\n&#038;= \\frac{3}{2}(2N-1) + \\sum_{k=1}^{2N} \\left\\lfloor \\frac{k+2}{4} \\right\\rfloor \\\\<br \/>\n&#038;= \\frac{3}{2}(2N-1) + \\sum_{m=1}^{N} \\left( \\left\\lfloor \\frac{2m+1}{4} \\right\\rfloor + \\left\\lfloor \\frac{2m+2}{4} \\right\\rfloor \\right) \\\\<br \/>\n&#038;= \\frac{3}{2}(2N-1) + \\sum_{m=1}^{N} m \\\\<br \/>\n&#038;= \\frac{3}{2}(2N-1) + \\frac{1}{2}N(N+1) \\\\<br \/>\n&#038;= \\frac{1}{2}(N^2+7N-3)<br \/>\n\\end{align}The simplification in the third last step follows by letting $m = 2q+r$ where $r\\in\\{0,1\\}$. Then we may write:<br \/>\n\\begin{align}<br \/>\n\\left\\lfloor \\frac{2m+1}{4} \\right\\rfloor + \\left\\lfloor \\frac{2m+2}{4} \\right\\rfloor<br \/>\n&#038;=\\left\\lfloor \\frac{4q+2r+1}{4} \\right\\rfloor + \\left\\lfloor \\frac{4q+2r+2}{4} \\right\\rfloor \\\\<br \/>\n&#038;=2q+\\left\\lfloor \\frac{2r+1}{4} \\right\\rfloor + \\left\\lfloor \\frac{2r+2}{4} \\right\\rfloor\\\\<br \/>\n&#038;=2q+r\\\\<br \/>\n&#038;=m<br \/>\n\\end{align}\n<\/p><\/div>\n<p>And if you just want to see the solutions:<br \/>\n<a href=\"javascript:Solution('soln_hoophop2','toggle_hoophop2')\" id=\"toggle_hoophop2\">[Show Solution]<\/a><\/p>\n<div id=\"soln_hoophop2\", style=\"display: none\">\n<p>The average duration (in seconds) of a game of Hoop hop showdown is given by:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\nT_\\text{avg} = \\frac{1}{2}(N^2+7N-3)<br \/>\n$<\/span><\/p>\n<p>Here is a plot showing the expected duration of the game as a function of the number of hoops.<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown2.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown2.png\" alt=\"\" width=\"900\" height=\"500\" class=\"aligncenter size-full wp-image-2430\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown2.png 900w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown2-300x167.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2018\/08\/hoop_hop_showdown2-768x427.png 768w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>So we need about 57 hoops in order to ensure that the average duration of a game of game of Hoop hop showdown lasts 30 minutes.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>This Riddler puzzle is a shout-out to this YouTube video of a game called &#8220;Hoop hop showdown&#8221;. Here is an idealized list of its rules: Kids stand at either end of N hoops. At the start of the game, one kid from each end starts hopping at a speed of one hoop per second until &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/hoop-hop-showdown\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Hoop hop showdown&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2430,"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":[18,8,2],"class_list":["post-2419","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-linearity-of-expectation","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2419","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=2419"}],"version-history":[{"count":10,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2419\/revisions"}],"predecessor-version":[{"id":2435,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2419\/revisions\/2435"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2430"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2419"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}