{"id":1183,"date":"2020-08-30T21:28:14","date_gmt":"2020-08-30T21:28:14","guid":{"rendered":"http:\/\/blog.atlant.is\/?p=1183"},"modified":"2021-02-21T11:47:28","modified_gmt":"2021-02-21T09:47:28","slug":"tower-of-hats","status":"publish","type":"post","link":"https:\/\/blog.douzeb.is\/?p=1183","title":{"rendered":"Towers of hats (1\/3)"},"content":{"rendered":"\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" loading=\"lazy\" width=\"859\" height=\"972\" src=\"https:\/\/blog.atlant.is\/wp-content\/uploads\/2020\/09\/hats-towering-pillar.png\" alt=\"\" class=\"wp-image-1880\" srcset=\"https:\/\/blog.douzeb.is\/wp-content\/uploads\/2020\/09\/hats-towering-pillar.png 859w, https:\/\/blog.douzeb.is\/wp-content\/uploads\/2020\/09\/hats-towering-pillar-265x300.png 265w, https:\/\/blog.douzeb.is\/wp-content\/uploads\/2020\/09\/hats-towering-pillar-768x869.png 768w\" sizes=\"(max-width: 859px) 100vw, 859px\" \/><figcaption>A towering pillar of hats (number $4$)<\/figcaption><\/figure>\n\n\n\n<p>This is the first in a series of three <em>exercices de style<\/em> to show some interesting aspects of the <em>game of hats<\/em>: a puzzle which was initially proposed by Lionel Levine, and arose from his work with Tobias Friedrich on <span class=\"zp-InText-zp-ID--6833562-A7GHFPNK--wp1183 zp-InText-Citation loading\" rel=\"{ 'pages': 'np', 'items': '{6833562:A7GHFPNK}', 'format': '(%a%, %d%, %p%)', 'brackets': '', 'etal': '', 'separator': '', 'and': '' }\"><\/span><\/p>\n\n\n\n<!--more-->\n\n\n\n<ul><li><a href=\"https:\/\/blog.atlant.is\/?p=1893\">Second exercice<\/a><\/li><li><a href=\"https:\/\/blog.atlant.is\/?p=2817\">Third exercice<\/a><\/li><\/ul>\n\n\n\n<p>I borrow the introduction from <span class=\"zp-InText-zp-ID--6833562-APHK998J--wp1183 zp-InText-Citation loading\" rel=\"{ 'pages': 'np', 'items': '{6833562:APHK998J}', 'format': '(%a%, %d%, %p%)', 'brackets': '', 'etal': '', 'separator': '', 'and': '' }\"><\/span>:<\/p>\n\n\n\n<blockquote class=\"wp-block-quote\"><p><span class=\"has-inline-color has-accent-color\">Two players each have countably many hats put on their heads.<br>Each hat is either black or white with equal probability. Furthermore, the players are only able to see the hats on the other person\u2019s head. Simultaneously each player points to a hat on their own head. They win if both players pick out a white hat.<\/span><\/p><p>The question is what is the optimal strategy for this game? It should be noted that each individual player will pick a white hat with probability one half regardless of the strategy employed. The challenge then is to correlate their choices.<\/p><p>At a first glance, it may seem that there is no strategy with better than random ($1 \\over 4$) chance of winning. This can be quickly discounted by the following simple strategy: each player looks for the first white hat on the partner\u2019s head and chooses the corresponding hat on his or her own head.<\/p><p>Observe that if both players have a white hat first ($1 \\over 4$ chance) then they win, if the two first hats are different ( $1 \\over 2$ chance) then they lose, and if the two first hats are both black ($1 \\over 4$ chance) then effectively they replay the game with the first hat removed. So, we see that the chance of winning is $x = {1 \\over 4} + {1 \\over 4} \\cdot x$, so $x = {1 \\over 3}$.<\/p><\/blockquote>\n\n\n\n\n\n<h2>Finite case<\/h2>\n\n\n\n<h3>Definitions and notations<\/h3>\n\n\n\n<h4>Towers<\/h4>\n\n\n\n<p>Consider a <em>tower<\/em> of $n$ stacked hats ($n$ finite), each hat either black  or white. We refer to $n$ as the tower&rsquo;s <em>height<\/em>. By identifying each hat with a <em>bit<\/em> (value $0$ for black, $1$ for white), we can view the tower as the binary representation of a natural number, the first hat being the least significant bit.<\/p>\n\n\n\n<p>Let $\\mathbb{T}_n$ denote the set of all possible towers:<\/p>\n\n\n\n<p>\\begin{align}<br>\\mathbb{T}_n \\quad &amp;\\stackrel{\\text{def}}{=} \\quad \\{0, 1\\}^{[n]} \\\\<br>&amp;= \\quad [2^n], \\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>where $[n] = \\{0, &#8230;, n-1\\}$ is the set of natural numbers strictly smaller than $n$.<\/p>\n\n\n\n<p>Let $t$ be a tower in $\\mathbb{T}_n$.<\/p>\n\n\n\n<p>As an element of $[2^n]$, $t$ is a plain natural number, which provide a convenient way to name it. For instance, $4 \\in \\mathbb{T}_3$ is the tower consisting of one white hat on top of two black hats.<\/p>\n\n\n\n<p>$$<br>4 \\quad = \\quad<br>\\begin{array}{c}<br>\u25cb\\\\<br>\u25cf\\\\<br>\u25cf<br>\\end{array}<br>$$<\/p>\n\n\n\n<p>Alternately, as an element of $\\{0, 1\\}^{[n]}$, $t$ is a map: $[n] \\rightarrow \\{0, 1\\}$. Given a <em>position<\/em> $p$ in $[n]$, $t(p)$ tells us the color of the hat at position $p$ in the tower ($0$ for black or $1$ for white). $t(p)$ is also the value of the $p$<sup>th<\/sup> bit in the binary representation of $t$.<\/p>\n\n\n\n<p>To avoid confusing $t(p)$ (map application) with $t \\cdot (p)$ (multiplication of numbers), we write $\\overline{(t)}(p)$ (overlined) for the map application. Also, we extend the domain of $\\overline{(t)}$ to the set of integers:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\forall t \\in \\mathbb{T}_n, \\forall p \\in \\mathbb{Z}, \\quad<br>\\overline{(t)}(p) \\;\\stackrel{\\text{def}}{=}\\; (t \\gg p) \\mathbin{\\%} 2,<br>\\end{equation}<\/p>\n\n\n\n<p>(where $\\gg$ is the bitwise right shift operator and $\\mathbin{\\%}$ the remainder operator).<\/p>\n\n\n\n<h5>Example<\/h5>\n\n\n\n<p>\\begin{align*}<br>\\overline{(4)}(-1) &amp;= 0 \\\\<br>\\overline{(4)}(0) &amp;= 0 \\\\<br>\\overline{(4)}(1) &amp;= 0 \\\\<br>\\overline{(4)}(2) &amp;= 1 \\\\<br>\\overline{(4)}(3) &amp;= 0<br>\\end{align*}<\/p>\n\n\n\n<h4>Strategies<\/h4>\n\n\n\n<p>A (deterministic) <em>strategy<\/em> $s$ for the game of $n$ hats is a way for each player, when presented with the tower of hats on top of their partner&rsquo;s head, of choosing the position of a (hopefully white) hat on their own head. In other words: $s$ is a map from $\\mathbb{T}_n$ to $\\mathbb{Z}$.<\/p>\n\n\n\n<p>Note that we allow a strategy to choose a position outside of the tower ($\\ge n$ or $&lt; 0$).<\/p>\n\n\n\n<p>Let $\\mathbb{S}_n = \\mathbb{Z}^{\\mathbb{T}_n}$ denote the set of all possible strategies for towers of $n$ hats:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\mathbb{S}_n \\; \\stackrel{\\text{def}}{=} \\; \\mathbb{Z}^{\\mathbb{T}_n}.<br>\\end{equation}<\/p>\n\n\n\n<p>A natural way to name a strategy is to use a $2^n$-uple for enumerating the choices it makes.<\/p>\n\n\n\n<p>For instance if $s \\in \\mathbb{S}_2$ is such that:<\/p>\n\n\n\n<p>$$<br>\\left\\{<br>\\begin{array}{ll}<br>s\\left(\\begin{array}{c}<br>\u25cf\\\\<br>\u25cf<br>\\end{array}\\right) = s(0) = 0,\\\\<br>s\\left(\\begin{array}{c}<br>\u25cf\\\\<br>\u25cb<br>\\end{array}\\right) = s(1) = 0,\\\\<br>s\\left(\\begin{array}{c}<br>\u25cb\\\\<br>\u25cf<br>\\end{array}\\right) = s(2) = 1,\\\\<br>s\\left(\\begin{array}{c}<br>\u25cb\\\\<br>\u25cb<br>\\end{array}\\right) = s(3) = 0,<br>\\end{array}<br>\\right.<br>$$<\/p>\n\n\n\n<p>then we write:<\/p>\n\n\n\n<p>$$s = (0,0,1,0).$$<\/p>\n\n\n\n<p>When there is no ambiguity (e.g.: all positions are single digit), we shorten the notation: <\/p>\n\n\n\n<p>$$s = [0010].$$<\/p>\n\n\n\n<p>And for clarity, when $n$ gets too big, we use hyphens to separate groups of digits,  e.g.: write $[0100 \\text{-} 2123 \\text{-} 0100 \\text{-} 2120]$ for $[0100212301002120] \\in \\mathbb{S}_4$.<\/p>\n\n\n\n<h5>Hit score<\/h5>\n\n\n\n<p>A configuration for the game of $n$ hats is a pair of towers $t$ and $u$ in $\\mathbb{T}_n$: one for each player&rsquo;s head. Given a strategy $s$ in $\\mathbb{S}_n$, we denote by $\\eta_{t,u}(s)$ the outcome of applying strategy $s$ in the configuration $(t, u)$: $1$ for <em>hit<\/em> (win), $0$ for <em>miss<\/em> (loss).<\/p>\n\n\n\n<p>\\begin{equation}<br>\\eta_{t,u}(s) \\; \\stackrel{\\text{def}}{=} \\; \\overline{(t)}\\big(s(u)\\big) \\cdot \\overline{(u)}\\big(s(t)\\big)<br>\\end{equation}<\/p>\n\n\n\n<p>We call <em>hit score<\/em> of $s$, denoted by $\\eta(s)$, the sum of all such outcomes, i.e. the count of all game configurations where the team wins.:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\eta(s) \\; \\stackrel{\\text{def}}{=} \\; \\sum_{t,u \\in \\mathbb{T}_n}\\eta_{t,u}(s)<br>\\end{equation}<\/p>\n\n\n\n<h5>Win rate<\/h5>\n\n\n\n<p>Given a strategy $s$ in $\\mathbb{S}_n$, we denote by $\\mu(s)$ the <em>win rate<\/em> (or <em>measure<\/em>) of $s$, i.e. the probability that a team applying the strategy wins.<\/p>\n\n\n\n<p>\\begin{equation}<br>\\mu(s) \\; \\stackrel{\\text{def}}{=} \\; {1 \\over{4^n}} \\cdot \\eta(s)<br>\\end{equation}<\/p>\n\n\n\n<h5>Equivalence<\/h5>\n\n\n\n<p>We call two strategies $a$ and $b$ in $\\mathbb{S}_n$ <em>equivalent<\/em>, when they agree on the winning configurations:<\/p>\n\n\n\n<p>\\begin{equation}<br>a \\equiv b \\; \\stackrel{\\text{def}}{\\iff} \\; \\forall t,u \\in \\mathbb{T}_n, \\eta_{t,u}(a) = \\eta_{t,u}(b).<br>\\end{equation}<\/p>\n\n\n\n<p>Note that two strategies $a$ and $b$ in $\\mathbb{S}_n$ which differ only in the choice of $a(0) \\neq b(0)$ are equivalent. This is because they make different choices only when one of the players is presented with tower $0$ (all black hats), which is always a losing situation for the team.<\/p>\n\n\n\n<p>\\begin{equation}<br>\\big(\\forall t \\in \\mathbb{T}_n \\setminus \\{0\\}, \\;\\; a(t) = b(t)\\big) \\quad \\implies \\quad a \\equiv b.<br>\\end{equation}<\/p>\n\n\n\n<p>Of course, equivalent strategies have the same hit score and win rate:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\forall a, b \\in \\mathbb{S}_n, \\quad a \\equiv b \\implies \\eta(a) = \\eta(b).<br>\\label{EquivRate}<br>\\end{equation}<\/p>\n\n\n\n<h3>Examples of strategies<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table><thead><tr><th><strong><strong>Name<\/strong><\/strong><\/th><th>Tuple<\/th><th class=\"has-text-align-center\" data-align=\"center\">Height<\/th><th>Hit score<\/th><th>Win rate<\/th><\/tr><\/thead><tbody><tr><td>top<\/td><td>$\\mathbf{T}_0 = [-1]$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$0$<\/td><td>$0$<\/td><td>${0 \\over 1} = 0\\%$<\/td><\/tr><tr><td>top<\/td><td>$\\mathbf{T}_1 = [00]$ <\/td><td class=\"has-text-align-center\" data-align=\"center\">$1$<\/td><td>$1$<\/td><td>${1 \\over 4} = 25\\%$<\/td><\/tr><tr><td>lowest-white<\/td><td>$\\mathbf{W}_2 = [1010]$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$2$<\/td><td>$5$<\/td><td>${5 \\over 16} = 31.25\\%$ <\/td><\/tr><tr><td>lowest-black<\/td><td>$\\mathbf{B}_3 = [01020102]$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$3$<\/td><td>$21$<\/td><td>${21 \\over 64} \\approx 31.81\\%$<\/td><\/tr><\/tbody><\/table><figcaption>Examples of strategies<\/figcaption><\/figure>\n\n\n\n<h4>Constant strategies<\/h4>\n\n\n\n<p>We call <em>constant<\/em> a strategy $s \\in \\mathbb{S}_n$ which always chooses the same position:<\/p>\n\n\n\n<p>$$s \\text{ constant } \\;\\stackrel{\\text{def}}{\\iff}\\; \\forall t, u \\in \\mathbb{T}_n, \\; s(t) = s(u)$$<\/p>\n\n\n\n<p>Observe:<\/p>\n\n\n\n<ul><li>all constant strategies of height $0$ are equivalent,<\/li><li>a constant strategy which chooses position $p \\not\\in [n]$ has hit score and win rate $0$,<\/li><li>a constant strategy of height $&gt;0$ which chooses position $p \\in [n]$ has hit score $4^{n-1}$ and win rate of $1 \\over 4$.<\/li><\/ul>\n\n\n\n<p>In particular, we denote by $\\mathbf{T}_n$ (<em>top<\/em> $n$) the strategy in $\\mathbb{S}_n$ which chooses position $n-1$ (i.e. the top position in the tower, when the tower is not empty).<\/p>\n\n\n\n<p>\\begin{equation}<br>\\forall t \\in \\mathbb{T}_n, \\quad \\mathbf{T}_n(t) \\stackrel{\\text{def}}{=} n-1<br>\\end{equation}<\/p>\n\n\n\n<h4>Lowest-white strategies<\/h4>\n\n\n\n<p>We denote by $\\mathbf{W}_n$ (<em>white<\/em> n) the strategy in $\\mathbb{S}_n$ which chooses the position of the lowest white hat, or $n-1$ if there is no white hat.<\/p>\n\n\n\n<h5>Example<\/h5>\n\n\n\n<p>$\\mathbf{W}_2 = [1010]$ chooses position $1$ when the first hat is black, position $0$ otherwise.<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-regular\"><table><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\"><span class=\"has-inline-color has-primary-color\">$\\eta_{t_1,t_2}(\\mathbf{W}_2)$<\/span><\/td><td class=\"has-text-align-center\" data-align=\"center\">$\\mathbf{W}_2(t_2)$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$1$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$0$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$1$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$0$<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">$\\mathbf{W}_2(t_1)$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$\\downarrow\\!t1 \\quad t2\\!\\rightarrow$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$0 = \\begin{array}{c}\u25cf\\\\\u25cf\\end{array}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$1 = \\begin{array}{c}\u25cf\\\\\u25cb\\end{array}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$2 = \\begin{array}{c}\u25cb\\\\\u25cf\\end{array}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$3 = \\begin{array}{c}\u25cb\\\\\u25cb\\end{array}$<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">$1$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$0 = \\begin{array}{c}\u25cf\\\\\u25cf\\end{array}$&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<\/td><td class=\"has-text-align-center\" data-align=\"center\">0\u00d70<\/td><td class=\"has-text-align-center\" data-align=\"center\">0\u00d70<\/td><td class=\"has-text-align-center\" data-align=\"center\">0\u00d71<\/td><td class=\"has-text-align-center\" data-align=\"center\">0\u00d71<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">$0$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$1 = \\begin{array}{c}\u25cf\\\\\u25cb\\end{array}$&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<\/td><td class=\"has-text-align-center\" data-align=\"center\">0\u00d70<\/td><td class=\"has-text-align-center\" data-align=\"center\"><span style=\"color:#00a300\" class=\"has-inline-color\"><strong>1\u00d71<\/strong><\/span><\/td><td class=\"has-text-align-center\" data-align=\"center\"><span class=\"has-inline-color has-primary-color\">0\u00d70<\/span><\/td><td class=\"has-text-align-center\" data-align=\"center\"><span style=\"color:#00a300\" class=\"has-inline-color\"><strong>1\u00d71<\/strong><\/span><\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">$1$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$2 = \\begin{array}{c}\u25cb\\\\\u25cf\\end{array}$&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<\/td><td class=\"has-text-align-center\" data-align=\"center\">1\u00d70<\/td><td class=\"has-text-align-center\" data-align=\"center\"><span class=\"has-inline-color has-primary-color\">0\u00d70<\/span><\/td><td class=\"has-text-align-center\" data-align=\"center\"><span style=\"color:#00a300\" class=\"has-inline-color\"><strong>1\u00d71<\/strong><\/span><\/td><td class=\"has-text-align-center\" data-align=\"center\"><span class=\"has-inline-color has-primary-color\">0\u00d71<\/span><\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">$0$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$3 = \\begin{array}{c}\u25cb\\\\\u25cb\\end{array}$&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<\/td><td class=\"has-text-align-center\" data-align=\"center\">1\u00d70<\/td><td class=\"has-text-align-center\" data-align=\"center\"><span style=\"color:#00a300\" class=\"has-inline-color\"><strong>1\u00d71<\/strong><\/span><\/td><td class=\"has-text-align-center\" data-align=\"center\"><span class=\"has-inline-color has-primary-color\">1\u00d70<\/span><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong><span style=\"color:#00a300\" class=\"has-inline-color\">1\u00d71<\/span><\/strong><\/td><\/tr><\/tbody><\/table><figcaption>Hits for strategy $\\mathbf{W}_2 = [0010]$<\/figcaption><\/figure>\n\n\n\n<p>$\\mathbf{W}_2$ has hit score $5$ and win rate $5 \\over 16$.<\/p>\n\n\n\n<h4>Lowest-black strategies<\/h4>\n\n\n\n<p>We denote by $\\mathbf{B}_n$ (<em>black<\/em> n) the strategy in $\\mathbb{S}_n$ which chooses the position of the lowest black hat, or $n-1$ if there is no black hat.<\/p>\n\n\n\n<h5>Example<\/h5>\n\n\n\n<p>$\\mathbf{B}_3 = [01020102]$ chooses position $2$ when the lowest two hats are white, otherwise position $1$ when the lowest hat is white, otherwise position $0$.<\/p>\n\n\n\n<p>$\\mathbf{B}_3$ has hit score $21$ and win rate $21 \\over 64$.<\/p>\n\n\n\n<h3>Operations on strategies<\/h3>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-left\" data-align=\"left\">Name<\/th><th class=\"has-text-align-left\" data-align=\"left\">Example<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\">embedding<\/td><td class=\"has-text-align-left\" data-align=\"left\">$e_3([0100]) \\;=\\; [0100 \\text{-} 0100]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">left reset<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[0101] \\rightarrow [-1] \\;=\\; [0101]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><\/td><td class=\"has-text-align-left\" data-align=\"left\">$[0101] \\rightarrow [00] \\;=\\; [01 \\text{-} 02 \\text{-} 01 \\text{-} 02]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><\/td><td class=\"has-text-align-left\" data-align=\"left\">$[00] \\rightarrow [0000] \\;=\\; [2000 \\text{-} 2000]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><\/td><td class=\"has-text-align-left\" data-align=\"left\">$[1010] \\rightarrow [1010] \\;=\\; [3010 \\text{-} 2010 \\text{-} 3010 \\text{-} 2010]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">right reset<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[0101] \\leftarrow [-1] \\;=\\; [0101]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><\/td><td class=\"has-text-align-left\" data-align=\"left\">$[0101] \\leftarrow [00] \\;=\\; [0102 \\text{-} 0102]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><\/td><td class=\"has-text-align-left\" data-align=\"left\">$[0000] \\leftarrow [00] \\;=\\; [0002 \\text{-} 0002]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">double  reset<\/td><td class=\"has-text-align-left\" data-align=\"left\">$DR([0010], [0010]) \\;=\\; [2012 \\text{-} 2012 \\text{-} 3012 \\text{-} 2012]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">left shift<\/td><td class=\"has-text-align-left\" data-align=\"left\">$\\uparrow\\![0] \\;=\\; [0 \\text{-} 0]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><\/td><td class=\"has-text-align-left\" data-align=\"left\">$\\uparrow\\![00] \\;=\\; [00 \\text{-} 10]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">right shift<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[00]\\!\\uparrow \\;=\\; [01 \\text{-} 00]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">double shift<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[00]\\!\\Uparrow \\;=\\; [01 \\text{-} 00 \\text{&#8211;} 21 \\text{-} 20]$<\/td><\/tr><\/tbody><\/table><figcaption>Operations on strategies<\/figcaption><\/figure>\n\n\n\n<h4>Embedding<\/h4>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\">$e_1([-1]) = (-1, -1)$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$e_3([1010]) = [1010 \\text{-} 1010]$<\/td><\/tr><\/tbody><\/table><figcaption>Embedding examples<\/figcaption><\/figure>\n\n\n\n<p>Given a strategy $s$ in  $\\mathbb{S}_n$ and an integer $m &gt; n$, we can use $s$ to play the game of $m$ hats. Simply: do not\u00a0\u00bblooking\u00a0\u00bb at the hats above position $n$ ($n$ included). This defines an embedding $e_m: \\mathbb{S}_n \\rightarrow \\mathbb{S}_m$:<\/p>\n\n\n\n<p>\\begin{align*}<br>e_m: \\mathbb{S}_n \\rightarrow \\mathbb{S}_m\\\\<br>s \\mapsto e_m(s)<br>\\end{align*}<\/p>\n\n\n\n<p>\\begin{equation}<br>\\forall t \\in \\mathbb{T}_n, \\;\\; \\big(e_m(s)\\big)(t)  \\stackrel{\\text{def}}{=} s(t \\mathbin{\\%} 2^n)<br>\\end{equation}<\/p>\n\n\n\n<p>(where $\\mathbin{\\%}$ is the remainder operator).<\/p>\n\n\n\n<p>Win rate is invariant under embedding into $\\mathbb{S}_m$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\forall s \\in \\mathbb{S}_n, \\forall m &gt; n, \\;\\; \\mu(s) = \\mu(e_m(s))<br>\\end{equation}<\/p>\n\n\n\n<h4>Left reset<\/h4>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\">$[00] \\rightarrow [-1] = [00]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$[00] \\rightarrow [00] \\rightarrow [-1] = [10 \\text{-} 10]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$[00] \\rightarrow [00] \\rightarrow [00] \\rightarrow [-1] = [2010 \\text{-} 2010]$<\/td><\/tr><\/tbody><\/table><figcaption>Left-reset examples<\/figcaption><\/figure>\n\n\n\n<p>Given two strategies $a \\in \\mathbb{S}_m$ and $b \\in \\mathbb{S}_n$, we call \u00ab\u00a0$a$ <em>left-reset<\/em> by $b$\u00a0\u00bb, denoted by $LR(a,b)$, the following strategy in $\\mathbb{S}_{m+n}$: whenever the lowest $m$ hats in the tower are not all black, use strategy $a$; otherwise, use strategy $b$ on the remaining $n$ hats. Formally:<\/p>\n\n\n\n<p>\\begin{align}<br>LR(a,b): \\; &amp; \\mathbb{T}_{m+n} \\rightarrow [m+n] \\nonumber \\\\<br>\\nonumber \\\\<br>&amp; t \\stackrel{\\text{def}}{\\mapsto}<br>\\left\\{<br>\\begin{array}{l}<br>a(t) \\quad\\text{if } t \\not \\equiv 0 \\bmod 2^m\\\\<br>m + b(t \\gg m) \\quad\\text{otherwise}<br>\\end{array}<br>\\right.<br>\\end{align}<\/p>\n\n\n\n<p>(where $\\gg$ is the bitwise right shift operator).<\/p>\n\n\n\n<p>Left reset is associative:<\/p>\n\n\n\n<p>$$\\forall a, b, c, \\quad LR(a, LR(b, c)) \\,=\\, LR(LR(a, b), c)$$<\/p>\n\n\n\n<p>so we make it into a binary operator:<\/p>\n\n\n\n<p>\\begin{equation}<br>b \\rightarrow a \\;\\stackrel{\\text{def}}{=}\\; LR(a, b),<br>\\end{equation}<\/p>\n\n\n\n<p>and the following holds:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\forall a, b, c, \\;\\; (c \\rightarrow b) \\rightarrow a \\,=\\, c \\rightarrow (b \\rightarrow a) \\,=\\, c \\rightarrow b \\rightarrow a<br>\\end{equation}<\/p>\n\n\n\n<h4>Right reset<\/h4>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\">$[-1] \\leftarrow [00] = [00]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$[-1] \\leftarrow [00] \\leftarrow [00] = [01 \\text{-} 01]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$[-1] \\leftarrow [00] \\leftarrow [00] \\leftarrow [00] = [0102 \\text{-} 0102]$<\/td><\/tr><\/tbody><\/table><figcaption>Right-reset examples<\/figcaption><\/figure>\n\n\n\n<p>Given two strategies $a \\in \\mathbb{S}_m$ and $b \\in \\mathbb{S}_n$, we call \u00ab\u00a0$a$ <em>right-reset<\/em> by $b$\u00a0\u00bb, denoted by $RR(a,b)$, the following strategy in $\\mathbb{S}_{m+n}$: whenever the lowest $m$ hats in the tower are not all white, use strategy $a$; otherwise, use strategy $b$ on the remaining $n$ hats. Formally:<\/p>\n\n\n\n<p>\\begin{align}<br>RR(a,b): \\; &amp; \\mathbb{T}_{m+n} \\rightarrow [m+n] \\nonumber \\\\<br>\\nonumber \\\\<br>&amp; t \\stackrel{\\text{def}}{\\mapsto}<br>\\left\\{<br>\\begin{array}{l}<br>a(t) \\quad \\text{if } t \\not\\equiv -1 \\bmod 2^m\\\\<br>m + b(t \\gg m) \\quad \\text{otherwise,}<br>\\end{array}<br>\\right.<br>\\end{align}<\/p>\n\n\n\n<p>where $\\gg$ is the bitwise right shift operator.<\/p>\n\n\n\n<p>Right reset is associative:<\/p>\n\n\n\n<p>$$\\forall a, b, c, \\;\\; RR(a, RR(b, c)) \\,=\\, RR(RR(a, b), c)$$<\/p>\n\n\n\n<p>so we make it into a binary operator:<\/p>\n\n\n\n<p>\\begin{equation}<br>a \\leftarrow b \\;\\stackrel{\\text{def}}{=}\\; RR(a, b),<br>\\end{equation}<\/p>\n\n\n\n<p>and the following holds:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\forall a, b, c, \\;\\;  (a \\leftarrow b) \\leftarrow c \\,=\\, a \\leftarrow (b \\leftarrow c) \\,=\\, a \\leftarrow b \\leftarrow c<br>\\end{equation}<\/p>\n\n\n\n<h4>Double reset<\/h4>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\">$DR([00], [00]) = [1111]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$DR(DR([1010], [00]), [00]) = [30122013 \\text{-} 30122013]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$DR([1010], DR([00], [00])) = [30133013 \\text{-} 30133013]$<\/td><\/tr><\/tbody><\/table><figcaption>Double-reset examples<\/figcaption><\/figure>\n\n\n\n<p>Given two strategies $a \\in \\mathbb{S}_m$ and $b \\in \\mathbb{S}_n$, we call \u00ab\u00a0$a$ <em>double-reset<\/em> by $b$\u00a0\u00bb, denoted by $DR(a, b)$, the following strategy in $\\mathbb{S}_{m+n}$: whenever the lowest $m$ hats in the tower are not all black and not all white, use strategy $a$; otherwise, use strategy $b$ on the remaining $n$ hats. Formally:<\/p>\n\n\n\n<p>\\begin{align}<br>DR(a,b): \\; &amp; \\mathbb{T}_{m+n} \\rightarrow [m+n] \\nonumber \\\\<br>\\nonumber \\\\<br>&amp; t \\stackrel{\\text{def}}{\\mapsto}<br>\\left\\{<br>\\begin{array}{l}<br>a(t) \\quad \\text{if } t \\not\\equiv 0 \\text{ and } t \\not\\equiv -1 \\bmod 2^m \\\\<br>m + b(t \\gg m) \\quad \\text{otherwise,}<br>\\end{array}<br>\\right.<br>\\end{align}<\/p>\n\n\n\n<p>where $\\gg$ is the bitwise right shift operator.<\/p>\n\n\n\n<p>Double-reset is <em>not<\/em> associative.<\/p>\n\n\n\n<h4>Left shift<\/h4>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\">$\\uparrow\\![0] = [0 \\text{-} 0]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$\\uparrow\\![00] = [00 \\text{-} 10]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$\\uparrow\\![0000] = [0000 \\text{-} 2000]$<\/td><\/tr><\/tbody><\/table><figcaption>Left-shift examples<\/figcaption><\/figure>\n\n\n\n<p>Given a strategie $s \\in \\mathbb{S}_n$, we call \u00ab\u00a0$s$<em> left-shifted<\/em>\u00ab\u00a0, denoted by $\\uparrow\\!s$, the following strategy in $\\mathbb{S}_{n+1}$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\forall t \\in \\mathbb{T}_{n+1}, \\quad  (\\uparrow\\!s)(t) \\stackrel{\\text{def}}{=}<br>\\left\\{<br>\\begin{array}{ll}<br>n  &amp; \\text{if } t = 2^n\\\\<br>s(t \\mathbin{\\%} 2^n) &amp; \\text{otherwise,}<br>\\end{array}<br>\\right.<br>\\end{equation}<\/p>\n\n\n\n<p>where $\\mathbin{\\%}$ is the remainder operator.<\/p>\n\n\n\n<h4>Right shift<\/h4>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\">$[0]\\!\\uparrow = [0 \\text{-} 0]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$[00]\\!\\uparrow = [01 \\text{-} 00]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$[0000]\\!\\uparrow = [0002 \\text{-} 0000]$<\/td><\/tr><\/tbody><\/table><figcaption>Right-shift examples<\/figcaption><\/figure>\n\n\n\n<p>Given a strategie $s \\in \\mathbb{S}_n$, we call \u00ab\u00a0$s$<em> right-shifted<\/em>\u00ab\u00a0, denoted by $s\\!\\uparrow$, the following strategy in $\\mathbb{S}_{n+1}$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\forall t \\in \\mathbb{T}_{n+1}, \\quad (s\\!\\uparrow)(t) \\stackrel{\\text{def}}{=}<br>\\left\\{<br>\\begin{array}{ll}<br>n &amp; \\text{if } t = 2^n &#8211; 1\\\\<br>s(t \\mathbin{\\%} 2^n) &amp; \\text{otherwise,}<br>\\end{array}<br>\\right.<br>\\end{equation}<\/p>\n\n\n\n<p>where $\\mathbin{\\%}$ is the remainder operator.<\/p>\n\n\n\n<h4>Double shift<\/h4>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\">$[00]\\!\\Uparrow = [01 \\text{-} 00 \\text{&#8211;} 21 \\text{-} 20]$<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">$[0000]\\!\\Uparrow = [0002 \\text{-} 0000 \\text{&#8211;} 3001 \\text{-} 3000]$<\/td><\/tr><\/tbody><\/table><figcaption>Double-shift examples<\/figcaption><\/figure>\n\n\n\n<p>Given a strategie $s \\in \\mathbb{S}_n$, we call \u00ab\u00a0$s$<em> double-shifted<\/em>\u00ab\u00a0, denoted by $s\\!\\Uparrow$, the following strategy in $\\mathbb{S}_{n+2}$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\forall t \\in \\mathbb{T}_{n+2}, \\quad (s\\!\\Uparrow)(t) \\stackrel{\\text{def}}{=}<br>\\left\\{<br>\\begin{array}{ll}<br>n+1 &amp; \\text{if } t = 2^{n+1} + 2^n\\\\<br>\\big(\\uparrow\\!(s\\!\\uparrow)\\big)(t) &amp; \\text{otherwise.}<br>\\end{array}<br>\\right.<br>\\end{equation}<\/p>\n\n\n\n<h3>Win rate computation<\/h3>\n\n\n\n<p>Brute-force computing the win rate would be expensive for large values of $n$. In the remainder of this section, we give simple formulae for calculating the win rate of certain strategies.<\/p>\n\n\n\n<h4>Formulae<\/h4>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th>Operation<\/th><th>Condition<\/th><th class=\"has-text-align-left\" data-align=\"left\">Win rate<\/th><\/tr><\/thead><tbody><tr><td>left-reset<\/td><td>$a \\in \\mathbb{S}_n$,<br>$b \\in \\mathbb{S}_m$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$\\mu(b \\rightarrow a) = \\mu(a) + {\\mu(b) \\over 4^n}$<\/td><\/tr><tr><td>right-reset<\/td><td>$a \\in [n]^{\\mathbb{T}_n}$,<br>$b \\in [m]^{\\mathbb{T}_m}$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$\\mu(a \\leftarrow b) = \\mu(a) + {\\mu(b) \\over 4^n}$<\/td><\/tr><tr><td>double-reset<\/td><td>$a \\in [n]^{\\mathbb{T}_n}$,<br>$b \\in [m]^{\\mathbb{T}_m}$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$\\mu(DR(a, b)) = \\mu(a) + {{4 \\mu(b) &#8211; 1} \\over 4^n}$<\/td><\/tr><tr><td>left-shift<\/td><td>$s \\in {\\mathbb{S}_n}$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$\\mu(\\uparrow\\!s) = \\mu(s) + {1 \\over 4^{n+1}}$<\/td><\/tr><tr><td>right-shift<\/td><td>$s \\in [n]^{\\mathbb{T}_n}$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$\\mu(s\\!\\uparrow) = \\mu(s) + {1 \\over 4^{n+1}}$<\/td><\/tr><tr><td>double-shift<\/td><td>$s \\in [n]^{\\mathbb{T}_n}$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$\\mu(s\\!\\Uparrow) = \\mu(s) + {1 \\over 4^{n+1}}+ {2 \\over 4^{n+2}}$<\/td><\/tr><\/tbody><\/table><figcaption>Formulae for win rate calculation<\/figcaption><\/figure>\n\n\n\n<h4>Observations<\/h4>\n\n\n\n<p>Let $a$ be a strategy in $\\mathbb{S}_n$. Recall that the hit score of $a$ is $\\eta(a) = \\sum_{t,u \\in \\mathbb{T}_n}\\eta_{t,u}(a)$, where $\\eta_{t,u}(a)$ denotes $\\overline{(t)}(a(u)) \\cdot \\overline{(u)}(a(t))$.<\/p>\n\n\n\n<p>Let $\\sum\\mathcal{M}$ denote the sum of all coefficients of matrix $\\mathcal{M}$.<\/p>\n\n\n\n<p>Then $\\eta(a)$ can be written as:<\/p>\n\n\n\n<p>\\begin{align*}<br>\\sum<br>\\begin{pmatrix}<br>\\big(\\eta_{0,0}(a) &amp; \\eta_{0,1}(a) &amp; \\cdots &amp; \\eta_{0,2^n-2}(a) &amp; \\eta_{0,2^n-1}(a) \\\\<br>\\big(\\eta_{1,0}(a) &amp; \\eta_{1,1}(a) &amp; \\cdots &amp; \\eta_{1,2^n-2}(a) &amp; \\eta_{1,2^n-1}(a) \\\\<br>\\vdots &amp; \\vdots &amp; \\ddots&amp; \\vdots&amp; \\vdots \\\\<br>\\big(\\eta_{2^n-2,0}(a) &amp; \\eta_{2^n-2,1}(a) &amp; \\cdots &amp; \\eta_{2^n-2,2^n-2}(a) &amp; \\eta_{2^n-2,2^n-1}(a) \\\\<br>\\big(\\eta_{2^n-1,0}(a) &amp; \\eta_{2^n-1,1}(a) &amp; \\cdots &amp; \\eta_{2^n-1,2^n-2}(a) &amp; \\eta_{2^n-1,2^n-1}(a)<br>\\end{pmatrix}<br>\\end{align*}<\/p>\n\n\n\n<p>Which simplifies to:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\sum<br>\\begin{pmatrix}<br>0 &amp; 0 &amp; \\cdots &amp; 0 &amp; 0 \\\\<br>\\cdot &amp; \\eta_{1,1}(a) &amp; \\cdots &amp; \\eta_{1,2^n-2}(a) &amp; \\eta_{1,2^n-1}(a) \\\\<br>\\vdots &amp; \\vdots &amp; \\ddots&amp; \\vdots&amp; \\vdots \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\eta_{2^n-2,2^n-2}(a) &amp; \\eta_{2^n-2,2^n-1}(a) \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\cdot &amp; \\eta_{2^n-1,2^n-1}(a)<br>\\end{pmatrix}<br>\\end{equation}<\/p>\n\n\n\n<p>Which when $a \\in [n]^{\\mathbb{T}_n}$ further simplifies to:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\sum<br>\\begin{pmatrix}<br>0 &amp; 0 &amp; \\cdots &amp; 0 &amp; 0 \\\\<br>\\cdot &amp; \\eta_{1,1}(a) &amp; \\cdots &amp; \\eta_{1,2^n-2}(a) &amp; \\overline{(1)}\\big(a(2^n-1)\\big) \\\\<br>\\vdots &amp; \\vdots &amp; \\ddots&amp; \\vdots&amp; \\vdots \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\eta_{2^n-2,2^n-2}(a) &amp; \\overline{(2^n-2)}\\big(a(2^n-1)\\big) \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\cdot &amp; 1<br>\\end{pmatrix} <br>\\end{equation}<\/p>\n\n\n\n<p>Note that:<\/p>\n\n\n\n<ul><li>these matrices are symmetric<\/li><li>the coefficients of the first line add up to $0$<\/li><li>the coefficients of the last column add up to:<\/li><\/ul>\n\n\n\n<p>$\\quad\\quad<br>\\left\\{<br>\\begin{array}{ll}<br>2^{n-1} &amp; \\text{when } a(2^m-1) \\in [n]\\\\<br>0 &amp; \\text{otherwise}<br>\\end{array}<br>\\right.<br>$<\/p>\n\n\n\n<p>Consequence: two strategies $a$ and $b$ in $[n]^{\\mathbb{T}_n}$ which differ only in the choice of $a(2^n-1) \\neq b(2^n-1)$  have the same hit score and win rate:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\big(\\forall t \\in \\mathbb{T}_n \\setminus \\{2^n-1\\}, \\;\\; a(t) = b(t)\\big) \\;\\; \\implies \\;\\; \\eta(a) = \\eta(b).<br>\\label{SameRate}<br>\\end{equation}<\/p>\n\n\n\n<h4>Win rate after left reset<\/h4>\n\n\n\n<p>Let $a \\in \\mathbb{S}_n, b \\in \\mathbb{S}_m$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\mu(b \\rightarrow a) = \\mu(a) + {\\mu(b) \\over 4^n}<br>\\label{LeftResetRule}<br>\\end{equation}<\/p>\n\n\n\n<p>Proof:<\/p>\n\n\n\n<p>\\begin{align*}<br>&amp; {\\eta(b \\rightarrow a) \\over 4^m} \\\\<br><br>&amp; \\;\\;=\\;\\; \\sum<br>\\begin{pmatrix}<br>\\mu(b) &amp; 0 &amp; \\cdots &amp; 0 &amp; 0 \\\\<br>\\cdot &amp; \\eta_{1,1}(a) &amp; \\cdots &amp; \\eta_{1,2^n-2}(a) &amp; \\eta_{1,2^n-1}(a) \\\\<br>\\vdots &amp; \\vdots &amp; \\ddots&amp; \\vdots&amp; \\vdots \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\eta_{2^n-2,2^n-2}(a) &amp; \\eta_{2^n-2,2^n-1}(a) \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\cdot &amp; \\eta_{2^n-1,2^n-1}(a)<br>\\end{pmatrix} \\\\<br><br>&amp; \\;\\;=\\;\\; \\eta(a) + \\mu(b) \\\\<br><br>&amp; \\;\\;=\\;\\; 4^n \\cdot \\left(\\mu(a) + {\\mu(b) \\over 4^n}\\right) \\quad \\Box<br>\\end{align*}<\/p>\n\n\n\n<h4>Win rate after right reset<\/h4>\n\n\n\n<p>This formula works for strategies which choose positions within the tower.<\/p>\n\n\n\n<p>Let $a \\in \\mathbb{S}_n, b \\in \\mathbb{S}_m$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\left\\{<br>  \\begin{array}{l}<br>  a \\in [n]^{\\mathbb{T}_n} \\\\<br>  b \\in [m]^{\\mathbb{T}_m}<br>  \\end{array}<br>\\right. \\;\\; \\implies \\;\\; \\mu(a \\leftarrow b) = \\mu(a) + {\\mu(b) \\over 4^n}<br>\\label{RightResetRule}<br>\\end{equation}<\/p>\n\n\n\n<p>Proof:<\/p>\n\n\n\n<p>\\begin{align*}<br>&amp; {\\eta(a \\leftarrow b) \\over 4^m}<br>\\\\<br>&amp; \\;\\;=\\;\\; \\sum \\\\<br>&amp; \\begin{pmatrix}<br>0 &amp; 0 &amp; \\cdots &amp; 0 &amp; {1 \\over 4^m} \\sum_{t,u\\in\\mathbb{T}_m} \\big(\\overline{(t)}(b(u)) \\cdot \\overline{(2^n-1)}(a(0))\\big) \\\\<br>\\cdot &amp; \\eta_{1,1}(a) &amp; \\cdots &amp; \\eta_{1,2^n-2}(a) &amp; {1 \\over 4^m} \\sum_{t,u\\in\\mathbb{T}_m} \\big(\\overline{(t)}(b(u)) \\cdot \\overline{(2^n-1)}(a(1))\\big) \\\\<br>\\vdots &amp; \\vdots &amp; \\ddots&amp; \\vdots&amp; \\vdots \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\eta_{2^n-2,2^n-2}(a) &amp; {1 \\over 4^m} \\sum_{t,u\\in\\mathbb{T}_m} \\big(\\overline{(t)}(b(u)) \\cdot \\overline{(2^n-1)}(a(2^n-2))\\big) \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\cdot &amp; \\mu(b)<br>\\end{pmatrix} \\\\<br>\\\\<br>&amp; \\;\\;=\\;\\; \\sum \\\\<br>&amp; \\begin{pmatrix}<br>0 &amp; 0 &amp; \\cdots &amp; 0 &amp; {1 \\over 4^m} \\sum_{u\\in\\mathbb{T}_m}\\sum_{t\\in\\mathbb{T}_m} \\overline{(t)}(b(u)) \\\\<br>\\cdot &amp; \\eta_{1,1}(a) &amp; \\cdots &amp; \\eta_{1,2^n-2}(a) &amp; {1 \\over 4^m} \\sum_{u\\in\\mathbb{T}_m}\\sum_{t\\in\\mathbb{T}_m} \\overline{(t)}(b(u)) \\\\<br>\\vdots &amp; \\vdots &amp; \\ddots&amp; \\vdots&amp; \\vdots \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\eta_{2^n-2,2^n-2}(a) &amp; {1 \\over 4^m} \\sum_{u\\in\\mathbb{T}_m}\\sum_{t\\in\\mathbb{T}_m} \\overline{(t)}(b(u)) \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\cdot &amp; \\mu(b)<br>\\end{pmatrix}<br>\\end{align*}<\/p>\n\n\n\n<p>Now since $0 \\le b(u) &lt; m, \\quad \\sum_{t\\in\\mathbb{T}_m} (\\overline{(t)}(b(u)) = 2^{m-1}$.<br><\/p>\n\n\n\n<p>Hence:<\/p>\n\n\n\n<p>\\begin{align*}<br>{\\eta(a \\leftarrow b) \\over 4^m} \\;\\;<br>&amp;= \\;\\; \\sum<br>\\begin{pmatrix}<br>0 &amp; 0 &amp; \\cdots &amp; 0 &amp; {1 \\over 2} \\\\<br>\\cdot &amp; \\eta_{1,1}(a) &amp; \\cdots &amp; \\eta_{1,2^n-2}(a) &amp; {1 \\over 2} \\\\<br>\\vdots &amp; \\vdots &amp; \\ddots&amp; \\vdots&amp; \\vdots \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\eta_{2^n-2,2^n-2}(a) &amp; {1 \\over 2} \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\cdot &amp; \\mu(b)<br>\\end{pmatrix} \\\\<br><br>&amp;= \\;\\; \\eta(a) + \\mu(b) \\\\<br><br>&amp;= \\;\\; 4^n \\cdot \\left(\\mu(a) + {\\mu(b) \\over 4^n}\\right) \\quad \\Box<br>\\end{align*}<\/p>\n\n\n\n<h4>Win rate after double reset<\/h4>\n\n\n\n<p>This formula works for strategies which choose positions within the tower.<\/p>\n\n\n\n<p>Let $a \\in \\mathbb{S}_n, b \\in \\mathbb{S}_m$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\left\\{<br>\\begin{array}{l}<br>a \\in [n]^{\\mathbb{T}_n} \\\\<br>b \\in [m]^{\\mathbb{T}_m}<br>\\end{array}<br>\\right. \\;\\; \\implies \\;\\;<br>\\mu(DR(a, b)) = \\mu(a) + {{4 \\mu(b) &#8211; 1} \\over 4^n}<br>\\label{DoubleResetRule}<br>\\end{equation}<\/p>\n\n\n\n<p>Proof:<\/p>\n\n\n\n<p>\\begin{align*}<br>&amp; {\\eta(DR(a, b)) \\over 4^m} \\\\<br>\\\\<br>&amp; \\;\\;=\\;\\; \\sum \\\\<br>&amp; \\begin{pmatrix}<br>\\mu(b) &amp; 0 &amp; \\cdots &amp; 0 &amp; \\mu(b) \\\\<br>\\cdot &amp; \\eta_{1,1}(a) &amp; \\cdots &amp; \\eta_{1,2^n-2}(a) &amp; {1 \\over 4^m} \\sum_{t,u\\in\\mathbb{T}_m} \\big(\\overline{(t)}(b(u)) \\cdot \\overline{(2^n-1)}(a(1))\\big) \\\\<br>\\vdots &amp; \\vdots &amp; \\ddots&amp; \\vdots&amp; \\vdots \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\eta_{2^n-2,2^n-2}(a) &amp; {1 \\over 4^m} \\sum_{t,u\\in\\mathbb{T}_m} \\big(\\overline{(t)}(b(u)) \\cdot \\overline{(2^n-1)}(a(2^n-2))\\big) \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\cdot &amp; \\mu(b)<br>\\end{pmatrix} \\\\<br>\\\\<br>&amp; \\;\\;=\\;\\; \\sum \\\\<br>&amp; \\begin{pmatrix}<br>\\mu(b) &amp; 0 &amp; \\cdots &amp; 0 &amp; \\mu(b) \\\\<br>\\cdot &amp; \\eta_{1,1}(a) &amp; \\cdots &amp; \\eta_{1,2^n-2}(a) &amp; {1 \\over 2} \\\\<br>\\vdots &amp; \\vdots &amp; \\ddots&amp; \\vdots&amp; \\vdots \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\eta_{2^n-2,2^n-2}(a) &amp; {1 \\over 2} \\\\<br>\\cdot &amp; \\cdot &amp; \\cdots &amp; \\cdot &amp; \\mu(b)<br>\\end{pmatrix} \\\\<br>\\\\<br>&amp;= \\;\\; \\eta(a) + 4 \\mu(b) &#8211; 1 \\\\<br>\\\\<br>&amp;= \\;\\; 4^n\\left(\\mu(a) + {{4 \\mu(b) &#8211; 1} \\over 4^n}\\right) \\quad \\Box<br>\\end{align*}<\/p>\n\n\n\n<h4>Win rate after left shift<\/h4>\n\n\n\n<p>Let $s \\in \\mathbb{S}_n$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\mu(\\uparrow\\!s) = \\mu(s) + {1 \\over 4^{n+1}}<br>\\label{LeftShiftRule}<br>\\end{equation}<\/p>\n\n\n\n<p>Proof:<\/p>\n\n\n\n<p>Note that the strategy $(\\uparrow\\!s)$ is equivalent to $([00] \\rightarrow s)$.<\/p>\n\n\n\n<p>Hence $(\\ref{EquivRate})$ they have the same hit score and win rate. Applying $(\\ref{LeftResetRule})$ we get:<\/p>\n\n\n\n<p>\\begin{align*}<br>\\mu(\\uparrow\\!s) \\;\\;=\\;\\; \\mu([00] \\rightarrow s) \\;\\;=\\;\\; \\mu(s) + {\\mu([00]) \\over 4^n} \\quad \\Box<br>\\end{align*}<\/p>\n\n\n\n<h4>Win rate after right shift<\/h4>\n\n\n\n<p>This formula works for a strategy which chooses positions within the tower.<\/p>\n\n\n\n<p>Let $s \\in \\mathbb{S}_n$:<\/p>\n\n\n\n<p>\\begin{equation}<br>s \\in [n]^{\\mathbb{T}_n} \\;\\;<br>\\implies \\;\\; \\mu(s\\!\\uparrow) = \\mu(s) + {1 \\over 4^{n+1}}<br>\\label{RightShiftRule}<br>\\end{equation}<\/p>\n\n\n\n<p>Proof:<\/p>\n\n\n\n<p>Note that the strategies $(s\\!\\uparrow)$ and $(s \\leftarrow [00])$ make the same choices except when presented with a tower with only white hats.<\/p>\n\n\n\n<p>Hence $(\\ref{SameRate})$ they have the same hit score and win rate. Applying $(\\ref{RightResetRule})$ we get:<\/p>\n\n\n\n<p>\\begin{align*}<br>\\mu(\\uparrow\\!s) \\;\\;=\\;\\; \\mu(s \\leftarrow [00]) \\;\\;=\\;\\; \\mu(s) + {\\mu([00]) \\over 4^n} \\quad \\Box<br>\\end{align*}<\/p>\n\n\n\n<h4>Win rate after double shift<\/h4>\n\n\n\n<p>This formula works for a strategy which chooses positions within the tower.<\/p>\n\n\n\n<p>Let $s \\in \\mathbb{S}_n$:<\/p>\n\n\n\n<p>\\begin{equation}<br>s \\in [n]^{\\mathbb{T}_n} \\;\\;<br>\\implies \\;\\; \\mu(s\\!\\Uparrow) = \\mu(s) + {1 \\over 4^{n+1}}+ {2 \\over 4^{n+2}}<br>\\label{DoubleShiftRule}<br>\\end{equation}<\/p>\n\n\n\n<p>Proof:<\/p>\n\n\n\n<p>Consider $s_1 = \\uparrow\\!(s\\!\\uparrow)$ and $s_2 = s\\!\\Uparrow$:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-regular\"><table><thead><tr><th class=\"has-text-align-left\" data-align=\"left\">$s_1 = \\uparrow\\!(s\\!\\uparrow)$<\/th><th class=\"has-text-align-left\" data-align=\"left\">$s_2 = s\\!\\Uparrow$<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\">$s(0), s(1), \\!\\cdot\\cdot, s(2^n\\text{-}2), \\pmb{n},$<br>$s(0), s(1), \\!\\cdot\\cdot, s(2^n\\text{-}2), s(2^n\\text{-}1),$<br>$\\pmb{n}\\!\\pmb{+}\\!\\pmb{1}, s(1), \\!\\cdot\\cdot, s(2^n\\text{-}2), \\pmb{n},$<br>$\\pmb{s(0)}, s(1), \\!\\cdot\\cdot, s(2^n\\text{-}2), s(2^n\\text{-}1)$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$s(0), s(1), \\!\\cdot\\cdot, s(2^n\\text{-}2), \\pmb{n},$<br>$s(0), s(1), \\!\\cdot\\cdot, s(2^n\\text{-}2), s(2^n\\text{-}1),$<br>$\\pmb{n}\\!\\pmb{+}\\!\\pmb{1}, s(1), \\!\\cdot\\cdot, s(2^n\\text{-}2), \\pmb{n},$<br>$\\pmb{n}\\!\\pmb{+}\\!\\pmb{1}, s(1), \\!\\cdot\\cdot, s(2^n\\text{-}2), s(2^n\\text{-}1)$<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The only difference between $s_1$ and $s_2$ is the position they choose for tower $k = 2^{n+1} + 2^n$:<\/p>\n\n\n\n<p>$$s_2(k) = n + 1 \\neq s(0) = s_1(k)$$<\/p>\n\n\n\n<p>Let&rsquo;s compare the hit scores. Since the $\\eta_{t,u}$ are equal unless $t$ or $u$ equals $k$, we have:<\/p>\n\n\n\n<p>\\begin{align}<br>\\eta(s_2) &#8211; \\eta(s_1) \\;\\; &amp; =\\;\\; \\sum_{t,u \\in \\mathbb{T}_{n+2}} \\big(\\eta_{t,u}(s_2) &#8211; \\eta_{t,u}(s_1)\\big) \\nonumber \\\\<br><br>&amp; =\\;\\; 2 \\!\\!\\sum_{t \\in \\mathbb{T}_{n+2}, t \\neq k}\\!\\!<br>  \\big(\\eta_{t,k}(s_2) &#8211; \\eta_{t,k}(s_1)\\big) \\label{PartialDoubleShift}\\\\<br>&amp; \\;\\;\\;\\;\\;\\; + \\big(\\eta_{k,k}(s_2)\\big)^2. \\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>Now:<\/p>\n\n\n\n<p>\\begin{align}<br>&amp; \\sum_{t \\in \\mathbb{T}_{n+2}, t \\neq k}<br>  \\big(\\eta_{t,k}(s_2) &#8211; \\eta_{t,k}(s_1)\\big) \\nonumber \\\\<br><br>&amp; \\quad = \\!\\!\\sum_{t \\in \\mathbb{T}_{n+2}, t \\neq k}\\!\\!<br>  \\big(\\overline{(t)}(s_2(k))\\cdot\\overline{(k)}(s_2(t))<br>  &#8211; \\overline{(t)}(s_1(k))\\cdot\\overline{(k)}(s_1(t))\\big) \\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>Because $k = 2^{n+1} + 2^n$ (all bits null but the two most significant), for the terms in this sum it holds that:<\/p>\n\n\n\n<p>$$<br>\\left\\{<br>\\begin{array}{l}<br>\\overline{(k)}(s_2(t)) \\neq 0 \\implies s_2(t) \\ge n<br>  \\implies t \\in \\{2^n-1, 2^{n+1}, 2^{n+1}-1\\} \\\\<br>\\overline{(k)}(s_1(t)) \\neq 0 \\implies s_1(t) \\ge n<br>\\implies t \\in \\{2^n-1, 2^{n+1}, 2^{n+1}-1\\}<br>\\end{array}<br>\\right.<br>$$<\/p>\n\n\n\n<p>Hence:<\/p>\n\n\n\n<p>\\begin{align*}<br>&amp; \\sum_{t \\in \\mathbb{T}_{n+2}, t \\neq k}<br>\\big(\\eta_{t,k}(s_2) &#8211; \\eta_{t,k}(s_1)\\big) \\\\<br>\\\\<br>&amp; \\quad = \\;\\;\\; \\overline{(2^n-1)}(s_2(k)) \\,- \\overline{(2^n-1)}(s_1(k)) \\\\<br>&amp;\\quad \\;\\;\\; + \\overline{(2^{n+1})}(s_2(k)) \\,- \\overline{(2^{n+1})}(s_1(k)) \\\\<br>&amp;\\quad \\;\\;\\; + \\overline{(2^{n+1}-1)}(s_2(k)) \\,- \\overline{(2^{n+1}-1)}(s_1(k)) \\\\<br>\\\\<br>&amp; \\quad = \\;\\;\\; \\overline{(2^n-1)}(n+1) \\,- \\overline{(2^n-1)}(s(0)) \\\\<br>&amp;\\quad \\;\\;\\; + \\overline{(2^{n+1})}(n+1) \\,-\\overline{(2^{n+1})}(s(0)) \\\\<br>&amp;\\quad \\;\\;\\; + \\overline{(2^{n+1}-1)}(n+1) \\,- \\overline{(2^{n+1}-1)}(s(0))<br>\\end{align*}<\/p>\n\n\n\n<p>Finally since $0 \\le s(0) &lt; n$:<\/p>\n\n\n\n<p>\\begin{align*}<br>\\sum_{t \\in \\mathbb{T}_{n+2}, t \\neq k}<br>&amp; \\big(\\eta_{t,k}(s_2) &#8211; \\eta_{t,k}(s_1)\\big) \\\\<br>\\\\<br>= \\quad &amp; \\quad\\; 0 \\quad-\\quad 1 \\\\<br>   &amp; + 1 \\quad-\\quad 0 \\\\<br>   &amp; + 1 \\quad-\\quad 1 \\\\<br>\\\\<br>= \\quad &amp; \\quad\\; 0<br>\\end{align*}<\/p>\n\n\n\n<p>Going back to $(\\ref{PartialDoubleShift})$, we conclude:<\/p>\n\n\n\n<p>\\begin{align*}<br>\\eta(s_2) &#8211; \\eta(s_1) \\;\\; &amp; =\\;\\; \\big(\\eta_{k,k}(s_2)\\big)^2 \\;\\;=\\;\\; 1 \\\\<br>\\eta(s\\!\\Uparrow) \\;\\; &amp; =\\;\\; \\eta(\\uparrow\\!(s\\!\\uparrow)) + 1 \\\\<br>&amp; =\\;\\; \\big( 16 \\cdot \\eta(s) + 4 + 1\\big) + 1 \\\\<br>&amp; =\\;\\; 4^{n+2} \\cdot \\big(\\mu(s) + {1 \\over 4^{n+1}} + {2 \\over 4^{n+2}}\\big)<br>\\quad \\Box<br>\\end{align*}<\/p>\n\n\n\n<h3>Efficient strategies<\/h3>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th><strong><strong>Strategy<\/strong><\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\">Height<\/th><th>Win rate<\/th><th class=\"has-text-align-center\" data-align=\"center\">Optimal?<\/th><\/tr><\/thead><tbody><tr><td>$\\mathbf{T}_0 = [-1]$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$0$<\/td><td>$0$<\/td><td class=\"has-text-align-center\" data-align=\"center\">yes<\/td><\/tr><tr><td>$\\mathbf{T}_1 = [00]$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$1$<\/td><td>${1 \\over 4}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">yes<\/td><\/tr><tr><td>$\\mathbf{W}_2 = [1010]$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$2$<\/td><td>${5 \\over 16}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">yes<\/td><\/tr><tr><td>$\\mathbf{B}_2 = [0101]$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$2$<\/td><td>${5 \\over 16}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">yes<\/td><\/tr><tr><td>$\\mathbf{C}_2 = [0010]$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$2$<\/td><td>${5 \\over 16}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">yes<\/td><\/tr><tr><td>$\\mathbf{C}_3 = \\mathbf{R}_1 =$<br>$[01002120]$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$3$<\/td><td>${21 \\over 64}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">yes<\/td><\/tr><tr><td>$\\mathbf{C}_4 =$<br>$[01002123$<br>$01002120]$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$4$<\/td><td>${89 \\over 256}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">yes<\/td><\/tr><tr><td>$\\mathbf{C}_5 =$<br>$[01002123$<br>$01002120$<br>$41002123$<br>$41002120]$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$5$<\/td><td>${358 \\over 1024}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">yes<\/td><\/tr><tr><td>$\\mathbf{T}_n$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$n$<\/td><td>${1 \\over 4}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">no for $n&gt;1$<\/td><\/tr><tr><td>$\\mathbf{W}_n$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$n$<\/td><td>${1 \\over 3}\\big(1 &#8211; {1 \\over 4^n}\\big)$<\/td><td class=\"has-text-align-center\" data-align=\"center\">no for $n&gt;2$<\/td><\/tr><tr><td>$\\mathbf{B}_n$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$n$<\/td><td>${1 \\over 3}\\big(1 &#8211; {1 \\over 4^n}\\big)$<\/td><td class=\"has-text-align-center\" data-align=\"center\">no for $n&gt;2$<\/td><\/tr><tr><td>$\\mathbf{C}_{2n+1}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$2n+1$<\/td><td>${7 \\over 20} &#8211; {1 \\over 10 (16)^n}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">yes?<\/td><\/tr><tr><td>$\\mathbf{C}_{2n+2}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$2n+2$<\/td><td>${7 \\over 20} &#8211; {3 \\over 80 (16)^n}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">yes?<\/td><\/tr><tr><td>$\\mathbf{R}_n$<\/td><td class=\"has-text-align-center\" data-align=\"center\">$3n$<\/td><td>${7 \\over 20} &#8211; {1 \\over {10 (16)^n}}$<\/td><td class=\"has-text-align-center\" data-align=\"center\">no for $n&gt;1$<\/td><\/tr><\/tbody><\/table><figcaption>Efficiency of various strategies<\/figcaption><\/figure>\n\n\n\n<h4>Top strategies<\/h4>\n\n\n\n<p>The top strategies are obtained by repeatedly double-resetting the strategy $[00]$:<\/p>\n\n\n\n<p>\\begin{align}<br>\\mathbf{T}_0 \\;<br>&amp;\\stackrel{\\text{def}}{=} \\; [-1] \\\\<br>\\forall n \\in \\mathbb{N}, \\quad \\mathbf{T}_{n+1} \\;<br>&amp;\\stackrel{\\text{def}}{=} \\; DR([00], \\mathbf{T}_n) \\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>\\begin{align}<br>\\mu(\\mathbf{T}_0) &amp;= 0\\\\<br>\\forall n &gt; 0, \\quad \\mu(\\mathbf{T}_n) &amp;= {1 \\over 4}\\\\<br>\\end{align}<\/p>\n\n\n\n<h4>Lowest-white strategies<\/h4>\n\n\n\n<p>The lowest-white strategies are obtained by repeatedly left-resetting the strategy $[00]$:<\/p>\n\n\n\n<p>\\begin{align}<br>\\mathbf{W}_0 \\;<br>&amp;\\stackrel{\\text{def}}{=} \\; [-1] \\\\<br>\\forall n \\in \\mathbb{N}, \\quad \\mathbf{W}_{n+1} \\;<br>&amp;\\stackrel{\\text{def}}{=} \\; \\mathbf{W}_n \\rightarrow [00] \\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>Applying $(\\ref{LeftResetRule})$ we get:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\mu(\\mathbf{W}_n) = {1 \\over 3} \\cdot \\big(1 &#8211; {1 \\over 4^n}\\big).<br>\\end{equation}<\/p>\n\n\n\n<p>As the height of the towers goes to infinity, the win rate of the lowest-white strategies converges to $1 \\over 3$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\lim_{n \\to \\infty}\\mu(\\mathbf{W}_n) = {1 \\over 3} \\approx 33.33\\%.<br>\\end{equation}<\/p>\n\n\n\n<h4>Lowest-black strategies<\/h4>\n\n\n\n<p>The lowest-black strategies are obtained by repeatedly right-resetting the strategy $[00]$:<\/p>\n\n\n\n<p>\\begin{align}<br>\\mathbf{B}_0 \\;<br>&amp;\\stackrel{\\text{def}}{=} \\; [-1] \\\\<br>\\forall n \\in \\mathbb{N}, \\quad \\mathbf{B}_{n+1} \\;<br>&amp;\\stackrel{\\text{def}}{=} \\; [00] \\leftarrow \\mathbf{B}_n \\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>Applying $(\\ref{RightResetRule})$ we get:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\mu(\\mathbf{B}_n) = {1 \\over 3} \\cdot \\big(1 &#8211; {1 \\over 4^n}\\big).<br>\\end{equation}<\/p>\n\n\n\n<p>As the height of the towers goes to infinity, the win rate of the lowest-black strategies converges to $1 \\over 3$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\lim_{n \\to \\infty}\\mu(\\mathbf{B}_n) = {1 \\over 3} \\approx 33.33\\%.<br>\\end{equation}<\/p>\n\n\n\n<h4>Carter strategies<\/h4>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th>$\\mathbf{C}$<\/th><th>Win<br>rate<\/th><th class=\"has-text-align-left\" data-align=\"left\">Tuple<\/th><\/tr><\/thead><tbody><tr><td>$\\mathbf{C}_1$<\/td><td>$1 \\over 4$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[00]$<\/td><\/tr><tr><td>$\\mathbf{C}_2$<\/td><td>$5 \\over 16$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[0100]$<\/td><\/tr><tr><td>$\\mathbf{C}_3$<\/td><td>$22 \\over 64$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[01002120]$<\/td><\/tr><tr><td>$\\mathbf{C}_4$<\/td><td>$89 \\over 256$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[0100212\\text{-}01002120]$<\/td><\/tr><tr><td>$\\mathbf{C}_5$<\/td><td>$358 \\over 1024$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[01002123 \\text{-} 01002120 \\text{-} 41002123 \\text{-} 41002120]$<\/td><\/tr><tr><td>$\\mathbf{C}_6$<\/td><td>$1433 \\over 4096$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[01002123 \\text{-} 01002120 \\text{-} 41002123 \\text{-} 41002125$<br>$01002123 \\text{-} 01002120 \\text{-} 41002123 \\text{-} 41002120]$<\/td><\/tr><tr><td>$\\mathbf{C}_7$<\/td><td>$5734 \\over 16384$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[01002123 \\text{-} 01002120 \\text{-} 41002123 \\text{-} 41002125$<br>$01002123 \\text{-} 01002120 \\text{-} 41002123 \\text{-} 41002120$<br>$61002123 \\text{-} 01002120 \\text{-} 41002123 \\text{-} 41002125$<br>$61002123 \\text{-} 01002120 \\text{-} 41002123 \\text{-} 41002120]$<\/td><\/tr><\/tbody><\/table><figcaption>Carter strategies<\/figcaption><\/figure>\n\n\n\n<p><em>Carter<\/em> strategies are defined by repeatedly shifting and double-shifting the strategy $[00]$:<\/p>\n\n\n\n<p>\\begin{align}<br>\\mathbf{C}_1 \\quad &amp;\\stackrel{\\text{def}}{=} \\quad [00], \\nonumber \\\\<br>\\mathbf{C}_{2n+2} \\quad &amp;\\stackrel{\\text{def}}{=} \\quad \\mathbf{C}_{2n+1}\\!\\uparrow, \\\\<br>\\mathbf{C}_{2n+3} \\quad &amp;\\stackrel{\\text{def}}{=} \\quad \\mathbf{C}_{2n+1}\\!\\Uparrow. \\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>Applying $(\\ref{LeftShiftRule})$ &amp; $(\\ref{DoubleShiftRule})$ we get:<\/p>\n\n\n\n<p>\\begin{align}<br>\\mu(\\mathbf{C}_{2n+1}) \\quad &amp;= \\quad {7 \\over 20} &#8211; {1 \\over 10 \\cdot (16)^n}, \\\\<br>\\mu(\\mathbf{C}_{2n+2}) \\quad &amp;= \\quad {7 \\over 20} &#8211; {3 \\over 80 \\cdot (16)^n}.<br>\\end{align}<\/p>\n\n\n\n<p>As the height of the towers goes to infinity, the win rate of the Carter strategies converges to $7 \\over 20$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\lim_{n \\to \\infty}\\mu(\\mathbf{C}_n) = {7 \\over 20} = 35\\%.<br>\\end{equation}<\/p>\n\n\n\n<h4>Reyes strategies<\/h4>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th>$\\mathbf{R}$<\/th><th>Win<br>rate<\/th><th class=\"has-text-align-left\" data-align=\"left\">Tuple<\/th><\/tr><\/thead><tbody><tr><td>$\\mathbf{R}_1$<\/td><td>$22 \\over 64$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[21002122]$<\/td><\/tr><tr><td>$\\mathbf{R}_2$<\/td><td>$358 \\over 1024$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[51002125 \\text{-} 41002124 \\text{-} 31002123 \\text{-} 31002123$<br>$51002125 \\text{-} 41002124 \\text{-} 51002125 \\text{-} 51002125]$<\/td><\/tr><tr><td>$\\mathbf{R}_3$<\/td><td><br>$5734 \\over 16384$<\/td><td class=\"has-text-align-left\" data-align=\"left\">$[61002126 \\text{-} 41002124 \\text{-} 31002123 \\text{-} 31002123$<br>$51002125 \\text{-} 41002124 \\text{-} 51002125 \\text{-} 61002126$<br>$71002127 \\text{-} 41002124 \\text{-} 31002123 \\text{-} 31002123$<br>$51002125 \\text{-} 41002124 \\text{-} 51002125 \\text{-} 71002127$<br>$61002126 \\text{-} 41002124 \\text{-} 31002123 \\text{-} 31002123$<br>$51002125 \\text{-} 41002124 \\text{-} 51002125 \\text{-} 61002126$<br>$61002126 \\text{-} 41002124 \\text{-} 31002123 \\text{-} 31002123$<br>$51002125 \\text{-} 41002124 \\text{-} 51002125 \\text{-} 61002126$<br>$81002128 \\text{-} 41002124 \\text{-} 31002123 \\text{-} 31002123$<br>$51002125 \\text{-} 41002124 \\text{-} 51002125 \\text{-} 81002128$<br>$71002127 \\text{-} 41002124 \\text{-} 31002123 \\text{-} 31002123$<br>$51002125 \\text{-} 41002124 \\text{-} 51002125 \\text{-} 71002127$<br>$81002128 \\text{-} 41002124 \\text{-} 31002123 \\text{-} 31002123$<br>$51002125 \\text{-} 41002124 \\text{-} 51002125 \\text{-} 81002128$<br>$61002126 \\text{-} 41002124 \\text{-} 31002123 \\text{-} 31002123$<br>$51002125 \\text{-} 41002124 \\text{-} 51002125 \\text{-} 61002126]$<\/td><\/tr><\/tbody><\/table><figcaption>Reyes strategies<\/figcaption><\/figure>\n\n\n\n<p><em>Reyes<\/em> strategies are defined by repeatedly double-resetting the Carter strategy $\\mathbf{C}_3$:<\/p>\n\n\n\n<p>\\begin{align}<br>\\mathbf{R}_1 \\;<br>&amp;\\stackrel{\\text{def}}{=} \\; \\mathbf{C}_3 \\\\<br>\\forall n &gt; 0, \\quad \\mathbf{R}_{n+1} \\;<br>&amp;\\stackrel{\\text{def}}{=} \\; DR(\\mathbf{C}_3, \\mathbf{R}_n). \\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>Applying $(\\ref{DoubleResetRule})$ we get:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\mu(\\mathbf{R}_n) = {7 \\over 20} &#8211; {1 \\over {10 \\cdot (16)^n}}.<br>\\end{equation}<\/p>\n\n\n\n<p>As the height of the towers goes to infinity, the win rate of the Reyes strategies converges to $7 \\over 20$:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\lim_{n \\to \\infty}\\mu(\\mathbf{R}_n) = {7 \\over 20} = 35\\%.<br>\\end{equation}<\/p>\n\n\n\n<h2>Recap and Whereto?<\/h2>\n\n\n\n<p>I came across the game of hats through <a rel=\"noreferrer noopener\" href=\"https:\/\/www.youtube.com\/watch?v=laAtv310pyk\" target=\"_blank\">Numberphile&rsquo;s<\/a> <span class=\"zp-InText-zp-ID--6833562-J37FUJWX--wp1183 zp-InText-Citation loading\" rel=\"{ 'pages': 'np', 'items': '{6833562:J37FUJWX}', 'format': '(%a%, %d%, %p%)', 'brackets': '', 'etal': '', 'separator': '', 'and': '' }\"><\/span>. Then Google pointed to the interesting article by Stan Wagon <span class=\"zp-InText-zp-ID--6833562-NCUAUHGU--wp1183 zp-InText-Citation loading\" rel=\"{ 'pages': 'np', 'items': '{6833562:NCUAUHGU}', 'format': '(%a%, %d%, %p%)', 'brackets': '', 'etal': '', 'separator': '', 'and': '' }\"><\/span>.<\/p>\n\n\n\n<p>Wagon provides a state of the art as of 2014:<\/p>\n\n\n\n<ul><li>Gives a list of best known symmetric strategies due to Carter and Reyes, up to $n = 8$ (hence the christening of the $\\mathbf{C}_n$ and  $\\mathbf{R}_n$ strategies in this article). Carter and Reyes strategies are proven optimal by brute force for $n &lt; 5$. For $n = 5$ Wagon mentions an indirect proof by Jim Roche and him, further confirmed by a different proof by Rob Pratt. For $n &gt; 5$ we don&rsquo;t know.<\/li><li>Mentions a proof by Walter Stromquist that $15\\over40$ is an upper bound for the win rate of any symmetric strategy.<\/li><li>Tells about asymmetric strategies (it is believed that they do not lead to better the win rates than the symmetric strategies). <\/li><li>Tells about playing the game with more than two players.<\/li><li>Shows how to leverage the axiom of choice to define a strategy for the game with countably infinitely many hats.<\/li><\/ul>\n\n\n\n<p>Wagon&rsquo;s state of the art doesn&rsquo;t give the explicit value of the Carter strategies beyond $\\mathbf{C}_8$, nor does it give a procedural way to construct them. It even asks the question: \u00ab\u00a0What about n = 9 or larger?\u00a0\u00bb. By contrast this article provides an explicit construction of $\\mathbf{C}_n$ for all $n &gt; 0$.<\/p>\n\n\n\n<p>In the next article I plan to describe a \u00ab\u00a0hat calculator\u00a0\u00bb which implements the operations defined in this article and lets you play with strategies. It also implements an efficient brute-force algorithm to look for optimal strategies (other than Carter&rsquo;s).<\/p>\n\n\n\n<h2>References<\/h2>\n\n\n\n\n<div id='zp-InTextBib-zotpress-06c24d010ebb01dd73d2921b8c899b40' class='zp-Zotpress zp-Zotpress-InTextBib wp-block-group zp-Post-1183'>\r\n\t\t<span class=\"ZP_ITEM_KEY\" style=\"display: none;\">{6833562:A7GHFPNK};{6833562:APHK998J};{6833562:J37FUJWX};{6833562:NCUAUHGU}<\/span>\r\n\t\t<span class=\"ZP_STYLE\" style=\"display: none;\">apa<\/span>\r\n\t\t<span class=\"ZP_SORTBY\" style=\"display: none;\">default<\/span>\r\n\t\t<span class=\"ZP_ORDER\" style=\"display: none;\">asc<\/span>\r\n\t\t<span class=\"ZP_TITLE\" style=\"display: none;\">no<\/span>\r\n\t\t<span class=\"ZP_SHOWIMAGE\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_SHOWTAGS\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_DOWNLOADABLE\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_NOTES\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_ABSTRACT\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_CITEABLE\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_TARGET\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_URLWRAP\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_FORCENUM\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_HIGHLIGHT\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_POSTID\" style=\"display: none;\">1183<\/span><div class='zp-List loading'>\n<div class=\"zp-SEO-Content\"><div id=\"zp-ID-1183-6833562-APHK998J\" class=\"zp-Entry zpSearchResultsItem\"><div class=\"csl-bib-body\" style=\"line-height: 2; padding-left: 1em; text-indent:-1em;\">\n  <div class=\"csl-entry\">Kariv, J., van Alten, C., &amp; Yeroshkin, D. (2017). Computing optimal strategies for a cooperative hat game. <i>ArXiv:1407.4711 [Cs, Math]<\/i>. <a href='http:\/\/arxiv.org\/abs\/1407.4711'>http:\/\/arxiv.org\/abs\/1407.4711<\/a><\/div>\n<\/div><\/div><div id=\"zp-ID-1183-6833562-A7GHFPNK\" class=\"zp-Entry zpSearchResultsItem\"><div class=\"csl-bib-body\" style=\"line-height: 2; padding-left: 1em; text-indent:-1em;\">\n  <div class=\"csl-entry\">Friedrich, T., &amp; Levine, L. (2012). Fast simulation of large-scale growth models. <i>ArXiv:1006.1003 [Cond-Mat]<\/i>. <a href='http:\/\/arxiv.org\/abs\/1006.1003'>http:\/\/arxiv.org\/abs\/1006.1003<\/a><\/div>\n<\/div><\/div><div id=\"zp-ID-1183-6833562-J37FUJWX\" class=\"zp-Entry zpSearchResultsItem\"><div class=\"csl-bib-body\" style=\"line-height: 2; padding-left: 1em; text-indent:-1em;\">\n  <div class=\"csl-entry\">Buhler, J. (2020, July 6). <i>Hat Problems - Numberphile - YouTube<\/i>. <a href='https:\/\/www.youtube.com\/watch?v=laAtv310pyk'>https:\/\/www.youtube.com\/watch?v=laAtv310pyk<\/a><\/div>\n<\/div><\/div><div id=\"zp-ID-1183-6833562-NCUAUHGU\" class=\"zp-Entry zpSearchResultsItem\"><div class=\"csl-bib-body\" style=\"line-height: 2; padding-left: 1em; text-indent:-1em;\">\n  <div class=\"csl-entry\">Wagon, S. (2014, January 4). <i>MacPOW 1179: An Infinitely Puzzling Hat Problem<\/i>. Stan Wagon&#x2019;s Website. <a href='http:\/\/stanwagon.com\/potw\/fall13\/p1179.html'>http:\/\/stanwagon.com\/potw\/fall13\/p1179.html<\/a><\/div>\n<\/div><\/div><\/div><!-- .zp-zp-SEO-Content -->\n<\/div><!-- .zp-List --><\/div><!--.zp-Zotpress-->\n\n\n","protected":false},"excerpt":{"rendered":"<p>This is the first in a series of three exercices de style to show some interesting aspects of the game of hats: a puzzle which was initially proposed by Lionel Levine, and arose from his work with Tobias Friedrich on<\/p>\n","protected":false},"author":1,"featured_media":1880,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[16,19],"tags":[],"ppma_author":[76],"authors":[{"term_id":76,"user_id":1,"is_guest":0,"slug":"fred","display_name":"Fred","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/ec0326d654fdf9f66e9eb42bb34a9bc4?s=96&d=mm&r=g","description":"","first_name":"","last_name":"","user_url":""}],"_links":{"self":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/1183"}],"collection":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1183"}],"version-history":[{"count":672,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/1183\/revisions"}],"predecessor-version":[{"id":3705,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/1183\/revisions\/3705"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/media\/1880"}],"wp:attachment":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1183"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1183"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1183"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fppma_author&post=1183"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}