Catégories
Draft Friandises Math

Infinitely Many Hats (3/3)

Countably infinitely many hats
Countably infinitely many hats

This is the last 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.

Here we look at case where each player has a tower of countably infinitely many hats on their head and try constructing efficient strategies from the results of the first exercice.

Definitions and notations

Towers and strategies

We use notations inspired by .

Let $\mathbb{T}_{<\mathbb{N}}$ denote the set of all towers of finite height and $\mathbb{T}_{\mathbb{N}}$ the set of towers of countably infinite height.

\begin{align}
\mathbb{T}_{<\mathbb{N}}
&\stackrel{\text{def}}{=}\bigcup_{n\in\mathbb{N}} \mathbb{T}_n\\
\mathbb{T}_{\mathbb{N}}
&\stackrel{\text{def}}{=}[2]^{\mathbb{N}}
\end{align}

$\mathbb{T}_{<\mathbb{N}}$ is countable but $\mathbb{T}_{\mathbb{N}}$ has the cardinality of the real line. $\mathbb{T}_{\mathbb{N}}$ is also known as the Cantor space.

Let $\mathbb{S}_{\mathbb{N}}$ denote the set of strategies for the game of hats with towers of countably infinite height. A (symmetric) strategy maps a tower to a chosen position:

\begin{align}
\mathbb{S}_{\mathbb{N}}
&\stackrel{\text{def}}{=}{\mathbb{Z}}^{\mathbb{T}_{\mathbb{N}}}
\end{align}

$\mathbb{S}_{\mathbb{N}}$ has cardinality strictly greater than the real line.

Hit set and win rate

With infinite towers we can still use $\eta_{t,u}(s)$ to denote the outcome of applying strategy $s\in\mathbb{S}_{\mathbb{N}}$ to the configuration $(t,u)$, however it is no longer possible to calculate the hit score as a sum and the win rate as a mean value.

We substitute with $\eta(s)$, the hit set of strategy $s$:

\begin{equation}
\eta(s)\stackrel{\text{def}}{=}\{(t,u)\in\mathbb{T}_{\mathbb{N}}\times\mathbb{T}_{\mathbb{N}}\mid\eta_{t,u}(s)=1\},
\end{equation}

and write $\mu(s)$ for the win rate of strategy $s$, defined as the Baire/Borel measure of $\eta(s)$ in the space $\mathbb{T}_{\mathbb{N}}\times\mathbb{T}_{\mathbb{N}}$ (when it is measurable).

\begin{equation}
\mu(s)\stackrel{\text{def}}{=}\mu(\eta(s)).
\end{equation}

Embedding

For convenience we identify the towers in $\mathbb{T}_n$ with towers in $\mathbb{T}_{\mathbb{N}}$ (by completing with black hats) and the strategies in $s\in\mathbb{S}_n$ with strategies in $s\in\mathbb{S}_{\mathbb{N}}$ (by discarding hats at position $n$ and beyond).

Thus we loosely write $s(t)$ and $eta_{t,u}(s)$ even when $s$, $t$ and $u$ are a mix of finite/infinite strategies and towers.

\begin{align}
\forall i<j, \;\;
\left\{
\begin{array}{l}
\mathbb{T}_i
\subset \mathbb{T}_j
\subset \mathbb{T}_{<\mathbb{N}}
\subset \mathbb{T}_{\mathbb{N}}\\
\mathbb{S}_i
\subset \mathbb{S}_j
\subset \mathbb{S}_{\mathbb{N}}\\
\end{array}
\right.
\end{align}

Limits

Infinite towers as limits of finite towers

Every tower $t\in\mathbb{T}_{\mathbb{N}}$ is the limit of a sequence of towers in $\mathbb{T}_{<\mathbb{N}}$ (with the topology of the Cantor space).

Proof: if $s\!\mid\!k$ denotes the initial segment of $s$ of size $k\in\mathbb{N}$, then:

\begin{equation}
s = \lim_{n\to\infty} s\!\mid\!n
\end{equation}

In fact, we can view $t\in\mathbb{T}_{\mathbb{N}}$ as the Cauchy completion of $t\in\mathbb{T}_{<\mathbb{N}}$.

Finite strategies are continuous

A finite strategy $s\in\mathbb{S}_n$, embedded into $\mathbb{S}_{\mathbb{N}}$ as a mapping $s: \mathbb{T}_{\mathbb{N}} \to \mathbb{Z}$, is continuous.

Limits of strategies

Here we allow strategies as functions $s: \mathbb{T}_{\mathbb{N}} \to \mathbb{Z}$ with partial domain.

Given a sequence $s_n\in\mathbb{S}_{\mathbb{N}}$ we define its pointwise limit:

\begin{align}
\lim (s_n):\; &\big\{t\mid \lim_{n\to\infty} s_n(t)\text{ exists}\big\} \to \mathbb{Z}\\
&\;t \mapsto \lim_{n\to\infty} s_n(t) \nonumber
\end{align}

It is natural to try constructing efficient infinite strategies as limits of finite strategies.

Type      Win
rate
DomainComputable
$0_\omega$Constant$1 \over 4$$\mathbb{T}_{\mathbb{N}}$on $\mathbb{T}_{\mathbb{N}}$
$\mathbf{W}_\omega$Lowest white$1 \over 3$$\mathbb{T}_{\mathbb{N}}\setminus\{(0,0,\cdots)\}$on its domain
$\mathbf{B}_\omega$Lowest black$1 \over 3$$\mathbb{T}_{\mathbb{N}}\setminus\{(1,1,\cdots)\}$on its domain
$\mathbf{C}_\omega$Carter$7 \over 20$$\mathbb{T}_{\mathbb{N}}$on $\mathbb{T}_{\mathbb{N}}\setminus$ $\{(0,0,\cdots),$ $(1,1,\cdots)\}$
$\mathbf{R}_\omega$Reyes$7 \over 20$$\big\{t\in\mathbb{T}_{\mathbb{N}}\mid\exists k,$ $\text{ card}\{t_{3k},t_{3k+1},$ $\:t_{3k+2}\}\neq1\big\}$on its domain
Sample of infinite strategies

Infinite lowest-white strategy

Consider the infinite lowest-white strategy $\mathbf{W}_\omega$:

\begin{equation}
\mathbf{W}_\omega \stackrel{\text{def}}{=} \lim_{n\to\infty} \mathbf{W}_n
\end{equation}

$\mathbf{W}_\omega$ has win rate $1\over3$.

Proof

Considering all towers in $\mathbb{T}_{\mathbb{N}}$, let’s represent the combined output of the $\mathbf{W}_n$ strategies as a tree, as shown in the picture below:

Output of the $\mathbf{W}_n$ strategies

Let’s denote in gray the points where the pointwise limit is reached:

Pointwise limit of the $\mathbf{W}_n$ strategies

We see that $\mathbf{W}_\omega=\lim(\mathbf{W}_n)$ is defined almost everywhere1 with respect to the Baire/Borel measure, and we can squeeze its hit set the following way:

\begin{equation}
I_k \subset \eta(\mathbf{W}_\omega) \subset S_k
\end{equation}

where:

$$
\left\{
\begin{array}{l}
I_k = \eta(\mathbf{W}_k) \setminus U_k\\
S_k = \eta(\mathbf{W}_k) \cup U_k\\
U_k = \big\{(t,u)\mid \text{ card}\bigcup_{i\geq k}\{\mathbf{W}_i(t)\}\neq1
\text{ or card}\bigcup_{i\geq k}\{\mathbf{W}_i(u)\}\neq1\big\}
\end{array}
\right.
$$

$I_k$ is an increasing sequence of sets and $S_k$ is a decreasing sequence, with $\lim_{k\to\infty} \mu(U_k) = 0$, $\lim_{k\to\infty} \mu(I_k) = 1/3$, $\lim_{k\to\infty} \mu(S_k) = 1/3$, hence $\mu(\mathbf{W}_\omega) = 1/3$. $\quad \Box$

Note (as shown in the picture below) that $\mathbf{W}_\omega$ is a computable function and can be written as a finite automaton that processes the stream of hats from $t\in\mathbb{T}_{\mathbb{N}}$:

$\mathbf{W}_\omega$ as a finite automaton

Infinite Carter strategy

Consider the infinite Carter strategy $\mathbf{C}_\omega$:

\begin{equation}
\mathbf{C}_\omega \stackrel{\text{def}}{=} \lim_{n\to\infty}
\mathbf{X}_n,
\end{equation}

where:

$$
\left\{
\begin{array}{l}
\mathbf{X}_{2k-1} = \mathbf{C}_k\!\mid\!(2k-1)\\
\mathbf{X}_{2k} = \mathbf{C}_k\!\mid\!(2k)
\end{array}
\right.
$$

$\mathbf{W}_\omega$ has win rate $7\over20$.

Proof

Considering all towers in $\mathbb{T}_{\mathbb{N}}$, let’s represent the combined output of the $\mathbf{X}_n$ strategies as a tree, as shown in the picture below:

Output of the Carter $\mathbf{X}_n$ strategies

Let’s denote in gray the points where the pointwise limit is reached:

Pointwise limit of the Carter $\mathbf{X}_n$ strategies

We see that $\mathbf{C}_\omega=\lim(\mathbf{X}_n)$ is defined everywhere, and we can squeeze its hit set the following way:

\begin{equation}
I_k \subset \eta(\mathbf{C}_\omega) \subset S_k
\end{equation}

where:

$$
\left\{
\begin{array}{l}
I_k = \eta(\mathbf{X}_k) \setminus U_k\\
S_k = \eta(\mathbf{X}_k) \cup U_k\\
U_k = \big\{(t,u)\mid \text{ card}\bigcup_{i\geq k}\{\mathbf{X}_i(t)\}\neq1
\text{ or card}\bigcup_{i\geq k}\{\mathbf{X}_i(u)\}\neq1\big\}
\end{array}
\right.
$$

$I_k$ is an increasing sequence of sets and $S_k$ is a decreasing sequence, with $\lim_{k\to\infty} \mu(U_k) = 0$, $\lim_{k\to\infty} \mu(I_k) = 7/20$, $\lim_{k\to\infty} \mu(S_k) = 7/20$, hence $\mu(\mathbf{C}_\omega) = 7/20$. $\quad \Box$

Note (as shown in the picture below) that $\mathbf{C}_\omega$ is a computable function almost everywhere2 and can be written as a finite automaton that processes the stream of hats from $t\in\mathbb{T}_{\mathbb{N}}$:

$\mathbf{C}_\omega$ as a finite automaton

Infinite Reyes strategy

Consider the infinite Reyes strategy $\mathbf{R}_\omega$:

\begin{equation}
\mathbf{R}_\omega \stackrel{\text{def}}{=} \lim_{n\to\infty}
\mathbf{X}_n,
\end{equation}

where:

$$
\left\{
\begin{array}{ll}
\mathbf{X}_{3k-2} &= \mathbf{C}_k\!\mid\!(3k-2)\\
\mathbf{X}_{3k-1} &= \mathbf{C}_k\!\mid\!(3k-1)\\
\mathbf{X}_{3k} &= \mathbf{C}_k\!\mid\!(3k)
\end{array}
\right.
$$

$\mathbf{W}_\omega$ has win rate $7\over20$.

Proof

Considering all towers in $\mathbb{T}_{\mathbb{N}}$, let’s represent the combined output of the $\mathbf{X}_n$ strategies as a tree, as shown in the picture below:

Output of the Reyes $\mathbf{X}_n$ strategies

Let’s denote in gray the points where the pointwise limit is reached:

Pointwise limit of the Reyes $\mathbf{X}_n$ strategies

We see that $\mathbf{R}_\omega=\lim(\mathbf{X}_n)$ is defined almost everywhere3, and we can squeeze its hit set the following way:

\begin{equation}
I_k \subset \eta(\mathbf{C}_\omega) \subset S_k
\end{equation}

where:

$$
\left\{
\begin{array}{l}
I_k = \eta(\mathbf{X}_k) \setminus U_k\\
S_k = \eta(\mathbf{X}_k) \cup U_k\\
U_k = \big\{(t,u)\mid \text{ card}\bigcup_{i\geq k}\{\mathbf{X}_i(t)\}\neq1
\text{ or card}\bigcup_{i\geq k}\{\mathbf{X}_i(u)\}\neq1\big\}
\end{array}
\right.
$$

$I_k$ is an increasing sequence of sets and $S_k$ is a decreasing sequence, with $\lim_{k\to\infty} \mu(U_k) = 0$, $\lim_{k\to\infty} \mu(I_k) = 7/20$, $\lim_{k\to\infty} \mu(S_k) = 7/20$, hence $\mu(\mathbf{R}_\omega) = 7/20$. $\quad \Box$

Note (as shown in the picture below) that $\mathbf{R}_\omega$ is a computable function on its definition domain and can be written as a finite automaton that processes the stream of hats from $t\in\mathbb{T}_{\mathbb{N}}$:

$\mathbf{R}_\omega$ as a finite automaton

References

Kechris, A. S. (2012). Classical descriptive set theory. Springer.
Catégories
Friandises Math

0! = 1

La fonction factorielle est souvent définie comme le produit : $$n!=\prod_{k=1}^n k\text{,}$$ ou bien par récurrence : $$n!=n\cdot(n-1)!\text{,}$$ en prenant par convention : $0!=1$. Mais pourquoi cette convention ?

Bien sûr c’est assez pratique pour la formule des combinaisons, car ainsi on peut écrire : $$C_n^k=\left(\begin{array}{c}n\\k\end{array}\right)={n!\over k!(n-k)!}$$ même quand $k=n$, et vérifier qu’il y a bien une seule façon de choisir $n$ éléments parmi $n$ 🙂

On peut trouver une explication plus satisfaisante en revenant au sens ensembliste de la factorielle : $n!$ c’est le nombre de permutations d’un ensemble à $n$ éléments, c’est à dire le nombre de bijections possibles entre cet ensemble et lui-même.

Du coup la question devient : quelles sont les bijections entre l’ensemble vide $\emptyset$ et lui-même ? Quel est leur nombre ?

Pour revenir aux bases, une application $f$ d’un ensemble $A$ vers un ensemble $B$ est une relation entre $A$ et $B$ — autrement dit une partie $f\subset A\times B$ — qui vérifie : $$\forall x\in A, \exists! y\in B, (x,y)\in f\text{.}$$ Et dans le cas où $(x,y)\in f$ on écrit : $y=f(x)$.

On observe que $\emptyset\times\emptyset=\emptyset$, que donc $\emptyset$ est la seule partie de $\emptyset\times\emptyset$, et on vérifie que $\forall x\in \emptyset, \exists! y\in \emptyset, (x,y)\in \emptyset$, ce qui démontre que $\emptyset$ est la seule application de $\emptyset$ vers $\emptyset$. On remarque que le domaine de (l’application) $\emptyset$ est vide, et que donc on n’a jamais l’occasion d’écrire $\emptyset(x)=y$.

Pour finir, on constate que (l’application) $\emptyset:\emptyset\to\emptyset$ est à la fois injective (son domaine est vide) et surjective (son ensemble d’arrivée est vide), ce qui démontre que $\emptyset$ est une bijection.

Il est temps de conclure : $\emptyset$ est l’unique bijection entre $\emptyset$ et $\emptyset$…

$0!=1$.$\quad \Box$

Catégories
Friandises Math

Classic 15 Puzzle

15-puzzle by Mark Rohlich

Genesis

The Fifteen Puzzle consists of fifteen numbered square tiles in a 4×4 square grid, with one position empty or blank. Any tile horizontally or vertically adjacent to the blank can be moved into the blank position. The task is to rearrange the tiles from some random initial configuration into a desired goal configuration, ideally or optimally using the fewest moves possible.

The Fifteen Puzzle was invented by Sam Loyd1 in the 1870s , and appeared in the scientific literature shortly thereafter . The editor of the journal added the following comment to the paper: “The ‘15’ puzzle for the last few weeks has been prominently before the American public, and may safely be said to have engaged the attention of nine out of ten persons of both sexes and of all ages and conditions of the community.”

One reason for the world-wide Fifteen Puzzle craze was that Loyd offered a $1000 cash prize to transform a particular initial state to a particular goal state. Johnson and Story proved that it wasn’t possible, that the entire state space was divided into even and odd permutations, and that there is no way to transform one into the other by legal moves.

Loyd’s impossible goal state with a \$1000 cash prize

Proof of insolvability

The classical proof2 for the insolvability of the puzzle involves an argument on:

  • the parity3 of the permutation of the squares on the grid,
  • versus the parity of the taxicab distance (number of rows plus number of columns) traveled by the blank square

A summertime conversation with G.R., who was not aware of the question or the proof, lead to his suggesting a subtle and interesting variant which fully dispenses with the blank square. Here it goes…

Variant

The classical insolvability proof works by identifying the set of possible puzzle states with the group $\mathcal{S}_{16}$ of permutations of the squares on the puzzle grid. Instead for the variant we work with the group $\mathcal{S}_{18}$ of permutations of the fifteen tiles plus three fictitious elements $a$, $b$, $c$, which represent the horizontal separations between the rows of the puzzle.

Puzzle states

As shown in the picture below, the initial state of the puzzle is represented by the identity permutation in $\mathcal{S}_{18}$:

$$\text{Id} =
\left(
\begin{array}{l}
1\;2\;3\;4\;a\;5\;6\;7\;8\;b\;9\;10\;11\;12\;c\;13\;14\;15\\
1\;2\;3\;4\;a\;5\;6\;7\;8\;b\;9\;10\;11\;12\;c\;13\;14\;15
\end{array}
\right)$$

Initial puzzle state Element of $\mathcal{S}_{18} $

Note that moving a tile horizontally does not change the representation in $\mathcal{S}_{18}$, but moving a tile vertically does:

After moving tile $11$ down Element of $\mathcal{S}_{18} $

After tile $11$ has been moved down, the representation of the puzzle becomes:

\begin{align*}
&\left(
\begin{array}{l}
1\;2\;3\;4\;a\;5\;6\;7\;8\;b\;9\;10\;11\;12\;c\;\;13\;14\;15\\
1\;2\;3\;4\;a\;5\;6\;7\;8\;b\;9\;10\;12\;\;c\;13\;14\;11\;15
\end{array}
\right)\\
\\
=&(11\;12\;c\;13\;14)\quad \text{(cycle of length 5)}
\end{align*}

Let $\mathcal{P} \subset \mathcal{S}_{18}$ be the set of (representations of) all possible puzzle states, legal and non-legal. Then $\mathcal{P}$ is precisely:

$$\mathcal{P} = \left\{s\in\mathcal{S}_{18}\quad
\left|\quad
\begin{array}{ll}
&\big(s(4)=a\;\text{and}\;s(8)=b\;\text{and}\;s(12)=c\big)\\
\text{or}&\big(s(4)=a\;\text{and}\;s(8)=b\;\text{and}\;s(c)=c\big)\\
\text{or}&\big(s(4)=a\;\text{and}\;s(b)=b\;\text{and}\;s(c)=c\big)\\
\text{or}&\big(s(a)=a\;\text{and}\;s(b)=b\;\text{and}\;s(c)=c\big)
\end{array}
\right.
\;
\right\}
$$

Tile moves

We sort tile moves according to their type, where there are exactly 24 types as shown in the following picture:

$2\cdot3\cdot4=24$ types of moves

For instance, type $\downarrow_{c3}$ gather all moves like so:

  • downwards,
  • crossing separator $c$,
  • in column $3$.
This is move type $\downarrow_{c3}$

Let $\mathcal{M}\subset\mathcal{P}\times\mathcal{P}$ be the set of (representations of) all possible tile moves, where $(s, e)\in\mathcal{M}$ is the move starting at $s$ and ending at $e$. Finally let us split $\mathcal{M}$ along move types:

$$\mathcal{M}\quad=\;\;\bigcup_{\text{all types }t}\mathcal{M}_t$$

Tile moves are cycles

Lemma: all moves in $\mathcal{M}$ are cycles of length $5$.

We verify this by considering every move type in turn.

For example, $\forall (s, e)\in\mathcal{M}_{\downarrow_{c3}}$:

$$\begin{array}{l}
e&=\left(
\begin{array}{l}
\;\;1\;\;\;\;2\;\;\;\;3\;\;\;\;4\;\;\;\;\,a\;\;\;\;5\;\;\;\;6\;\;\;\;7\;\;\;\;8\;\;\;b \\
s(1) s(2) s(3) s(4) \;a\;s(5) s(6) s(7) s(8) b
\end{array}
\right. \\
&\\
&\quad\quad\left.
\begin{array}{l}
\;\;\;9\;\;\;\;10\;\;\;\;11\;\;\;12\;\;\;\;c\;\;\;\;\;13\;\;\;\;14\;\;\;\;15 \\
s(9) s(10) s(12)\;\;c\;s(13) s(14) s(11) s(15)
\end{array}
\right) \\
&\\
&=\;\; (11\;\;12\;\;c\;\;13\;\;14)\circ s,
\end{array}$$

which gives $e \circ s^{-1} = (11\;\;12\;\;c\;\;13\;\;14)$.

And so on4… Hence all moves are cycles of length $5$ and even parity:

$$
\forall (s, e) \in \mathcal{M}, \quad \pi(e \circ s^{-1}) = 1
$$

Conclusion

Consider a legal puzzle state $s\in\mathcal{P}$. There exists a sequence of moves $(s_0,e_0), \cdots, (s_n,e_n)$ in $\mathcal{M}$, such that:

$$
\left\{
\begin{array}{l}
s_0=\text{Id}\\
\forall i < n,\quad s_{i+1}=e_i\\
e_n=s
\end{array}
\right.
$$

It follows that:

\begin{align*}
s&=e_n\circ(s_n^{-1}\circ e_{n-1})\circ\cdots\circ(s_1^{-1}\circ e_0)\circ\text{Id}\\
&=(e_n\circ s_n^{-1})\circ(e_{n-1}\circ s_{n-1}^{-1})\circ\cdots\circ (e_1\circ s_1^{-1})\circ(e_0\circ s_0^{-1})
\end{align*}

is a permutation with even parity.

Hence Loyd’s \$1000-cash puzzle goal state is not legal.$\quad\Box$

References

Gardner, M. (Ed.). (1960). More mathematical puzzles of Sam Loyd. Dover Publ.
Johnson, Wm. W., & Story, W. E. (1879). Notes on the “15” Puzzle. American Journal of Mathematics, 2(4), 397–404. JSTOR. https://doi.org/10.2307/2369492
Korf, R. E. (2000). Recent Progress in the Design and Analysis of Admissible Heuristic Functions. In B. Y. Choueiry & T. Walsh (Eds.), Abstraction, Reformulation, and Approximation (pp. 45–55). Springer. https://doi.org/10.1007/3-540-44914-0_3

Permutations cheatsheet

A permutation of the set $\{1, 2, \cdots, n\}$ is a bijection of $\{1, 2, \cdots, n\}$ with itself. The set of permutations of $\{1, 2, \cdots, n\}$5 is denoted by $\mathcal{S}_n$.

One usual way of writing a permutation $p$ is by providing the exhaustive list of $x \mapsto p(x)$ mappings, in a rectangular matrix like so:

$$p=\left(\begin{array}{cccccc}
1&2&3&4&5&6&7\\
7&3&5&2&4&6&1
\end{array}\right)$$

A more concise way is by specifying $p$ as a combination of cycles. For example:

$$p = (1\;\;7) (2\;\;3\;\;5\;\;4)$$

A permutation that consists of a single length-2 cycle is called a transposition. Every permutation in $\mathcal{S}_n$ can be expressed as a composition of tranpositions. For example:

$$(1\;\;7) (2\;\;3\;\;5\;\;4) = (1\;\;7)\circ(2\;\;3)\circ(3\;\;5)\circ(5\;\;4)$$

The operation of composition gives the set $\mathcal{S}_n$ a structure of group. There is a unique group morphism from $\big(\mathcal{S}_n, \circ\big)$ to $\big(\{-1,1\},\cdot\big)$ which maps transpositions to the value -1. This morphism is called parity (denoted by $\pi$ in this article).

$$\pi: \mathcal{S}_n \rightarrow \{-1,1\}$$

$$\forall x, y \in \mathcal{S}_n, \;\;\pi(y\circ x) = \pi(y)\cdot\pi(x)$$

A cycle of length even (respectively odd) has parity odd (respectively even).

Catégories
Friandises

AlphaGo

AlphaGo versus Lee Sedol Game 2 – March 10th 2016
Catégories
Friandises

Colors

Colors are beautiful. Colors have names. Get to know them.

Catégories
Coding Friandises Geek

Hats Calculator (2/3)

The hats medic
The hats medic

This is the second 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.

Here we introduce the hats calculator: a toy application which implements the operations introduced in the first exercice.

Try it yourself

Installing the hats calculator

The hats calculator is a single file JavaScript application.

Clone it from the repository on GitHub:

Use the D8 JavaScript shell to run in from the terminal.

Evaluating strategies

The syntax for evaluating strategy expressions is as follows:

<expr> can be a strategy or a call to an operation on strategies. Strategies are keyed in as arrays, strings (shortened notation), or using predefined constant names.

Predefined constants include:

  • T0: Top strategy $\mathbf{T}_0$
  • W0, $\cdots$, W9: Lowest-white strategies $\mathbf{W}_n$
  • B0, $\cdots$, B9: Lowest-black strategies $\mathbf{B}_n$
  • C1, $\cdots$, C9: Carter strategies $\mathbf{C}_n$
  • R0, $\cdots$, R3: Reyes strategies $\mathbf{R}_n$

Available operations include:

  • lr(a, b): a left-reset by b ($b \rightarrow a$)
  • rr(a, b): a right-reset by b ($a \leftarrow b$)
  • dr(a, b): a double-reset by b ($DR(a, b)$)
  • ls(a): a left-shifted ($\uparrow\!a$)
  • rs(a): a right-shifted ($a\!\uparrow$)
  • ds(a): a double-shifted ($a\!\Uparrow$)
  • emb(a, n): a embedded in $\mathbb{S}_\text{n}$ ($e_n(a)$)
  • crush(a): a transform of a with the same hit score but such that $\forall t, \; a(t) \le t$.

Searching for optimal strategies

The syntax for searching for optimal strategies is as follows:

  • -n: specifies the height of the strategies (defaults to $1$)
  • -s: limits the search to strategies close to a seed strategy (defaults to the constant zero strategy)
  • -d: limits the search to strategies within a specified hamming distance of the seed strategy (defaults $0$ which means no limit)
  • -a: displays all occurrences of optimal strategies, not just the first one
  • -q: works quietly, displays only a summary line
  • -c: don’t actually perform the search; instead: prints the optimized JavaScript code which performs the search

Performance

Measured on chrome on a MacBook Pro 2015.

For $n = 4$, the search for the optimal strategy takes about $0.8$ second and compares $100\,663\,296$ strategies.

# of strategies compared$100\,663\,296$
Processing time$0.82$ s
Duration per strategy rating$8.15$ ns
# of processor cycles per rating$25$
Search performance for $n = 4$ (chrome on MacBook Pro 2015, 3.1 GHz)

For $n = 5$ the search for the optimal strategy would theoretically take $\approx 113\,000$ years and would compare $178\,813\,934\,326\,171\,875\,000$ strategies!

# of strategies compared$178\,813\,934\,326\,171\,875\,000$
Processing time$\approx 113\,000$ years
Duration per strategy rating$\approx20$ ns
# of processor cycles per rating$\approx62$
Search performance for $n = 5$ (chrome on MacBook Pro 2015, 3.1 GHz)

Implementation tips

hats.js implements several optimizations to increase the performance of the search.

  1. Uses the fact that the hit score is independent on the choice a strategy makes for a tower all black or all white. For $n = 5$ this decreases the cardinality of the problem by a factor of $25$.
  2. Uses an argument on « positions permutation » which allows to consider only crushed strategies (for which $\forall s, \; s(t) \le t$). For $n = 5$ this decreases the cardinality of the problem by an additional factor of $6$.
  3. Computes the hit score incrementally, changing one strategy choice at a time. For $n = 5$ this decreases the execution time by an additional factor of $32$.
  4. Uses a smart representation of strategy choices as bit patterns, which enables a faster computation of the incremental hit score.
  5. Eliminates most loops, indices, and array accesses by automatically generating « unfolded specialized » search code, optimized for each specific search query1. To have a look at the generated code, try e.g.: search -n 4 -c in the Try it yourself window.
  6. Tries to keep code and data of the search algorithm as much as possible within the processor cache. (Significant performance decrease is observed with less concise code.)
Automatically generated code pattern for the search algorithm

Unfortunately, these optimization do not make the $114\,000$ years computation time for $n = 5$ any more accessible. Different methods than brute force are definitely needed.

What’s next

In the next article I plan to go back to the theory of the game of hats and tackle the problem of playing with infinite towers.

Catégories
Friandises Math

Towers of hats (1/3)

A towering pillar of hats (number $4$)

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

I borrow the introduction from :

Two players each have countably many hats put on their heads.
Each hat is either black or white with equal probability. Furthermore, the players are only able to see the hats on the other person’s head. Simultaneously each player points to a hat on their own head. They win if both players pick out a white hat.

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.

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’s head and chooses the corresponding hat on his or her own head.

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}$.

Finite case

Definitions and notations

Towers

Consider a tower of $n$ stacked hats ($n$ finite), each hat either black or white. We refer to $n$ as the tower’s height. By identifying each hat with a bit (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.

Let $\mathbb{T}_n$ denote the set of all possible towers:

\begin{align}
\mathbb{T}_n \quad &\stackrel{\text{def}}{=} \quad \{0, 1\}^{[n]} \\
&= \quad [2^n], \nonumber
\end{align}

where $[n] = \{0, …, n-1\}$ is the set of natural numbers strictly smaller than $n$.

Let $t$ be a tower in $\mathbb{T}_n$.

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.

$$
4 \quad = \quad
\begin{array}{c}
○\\
●\\

\end{array}
$$

Alternately, as an element of $\{0, 1\}^{[n]}$, $t$ is a map: $[n] \rightarrow \{0, 1\}$. Given a position $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$th bit in the binary representation of $t$.

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:

\begin{equation}
\forall t \in \mathbb{T}_n, \forall p \in \mathbb{Z}, \quad
\overline{(t)}(p) \;\stackrel{\text{def}}{=}\; (t \gg p) \mathbin{\%} 2,
\end{equation}

(where $\gg$ is the bitwise right shift operator and $\mathbin{\%}$ the remainder operator).

Example

\begin{align*}
\overline{(4)}(-1) &= 0 \\
\overline{(4)}(0) &= 0 \\
\overline{(4)}(1) &= 0 \\
\overline{(4)}(2) &= 1 \\
\overline{(4)}(3) &= 0
\end{align*}

Strategies

A (deterministic) strategy $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’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}$.

Note that we allow a strategy to choose a position outside of the tower ($\ge n$ or $< 0$).

Let $\mathbb{S}_n = \mathbb{Z}^{\mathbb{T}_n}$ denote the set of all possible strategies for towers of $n$ hats:

\begin{equation}
\mathbb{S}_n \; \stackrel{\text{def}}{=} \; \mathbb{Z}^{\mathbb{T}_n}.
\end{equation}

A natural way to name a strategy is to use a $2^n$-uple for enumerating the choices it makes.

For instance if $s \in \mathbb{S}_2$ is such that:

$$
\left\{
\begin{array}{ll}
s\left(\begin{array}{c}
●\\

\end{array}\right) = s(0) = 0,\\
s\left(\begin{array}{c}
●\\

\end{array}\right) = s(1) = 0,\\
s\left(\begin{array}{c}
○\\

\end{array}\right) = s(2) = 1,\\
s\left(\begin{array}{c}
○\\

\end{array}\right) = s(3) = 0,
\end{array}
\right.
$$

then we write:

$$s = (0,0,1,0).$$

When there is no ambiguity (e.g.: all positions are single digit), we shorten the notation:

$$s = [0010].$$

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$.

Hit score

A configuration for the game of $n$ hats is a pair of towers $t$ and $u$ in $\mathbb{T}_n$: one for each player’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 hit (win), $0$ for miss (loss).

\begin{equation}
\eta_{t,u}(s) \; \stackrel{\text{def}}{=} \; \overline{(t)}\big(s(u)\big) \cdot \overline{(u)}\big(s(t)\big)
\end{equation}

We call hit score of $s$, denoted by $\eta(s)$, the sum of all such outcomes, i.e. the count of all game configurations where the team wins.:

\begin{equation}
\eta(s) \; \stackrel{\text{def}}{=} \; \sum_{t,u \in \mathbb{T}_n}\eta_{t,u}(s)
\end{equation}

Win rate

Given a strategy $s$ in $\mathbb{S}_n$, we denote by $\mu(s)$ the win rate (or measure) of $s$, i.e. the probability that a team applying the strategy wins.

\begin{equation}
\mu(s) \; \stackrel{\text{def}}{=} \; {1 \over{4^n}} \cdot \eta(s)
\end{equation}

Equivalence

We call two strategies $a$ and $b$ in $\mathbb{S}_n$ equivalent, when they agree on the winning configurations:

\begin{equation}
a \equiv b \; \stackrel{\text{def}}{\iff} \; \forall t,u \in \mathbb{T}_n, \eta_{t,u}(a) = \eta_{t,u}(b).
\end{equation}

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.

\begin{equation}
\big(\forall t \in \mathbb{T}_n \setminus \{0\}, \;\; a(t) = b(t)\big) \quad \implies \quad a \equiv b.
\end{equation}

Of course, equivalent strategies have the same hit score and win rate:

\begin{equation}
\forall a, b \in \mathbb{S}_n, \quad a \equiv b \implies \eta(a) = \eta(b).
\label{EquivRate}
\end{equation}

Examples of strategies

NameTupleHeightHit scoreWin rate
top$\mathbf{T}_0 = [-1]$$0$$0$${0 \over 1} = 0\%$
top$\mathbf{T}_1 = [00]$ $1$$1$${1 \over 4} = 25\%$
lowest-white$\mathbf{W}_2 = [1010]$$2$$5$${5 \over 16} = 31.25\%$
lowest-black$\mathbf{B}_3 = [01020102]$$3$$21$${21 \over 64} \approx 31.81\%$
Examples of strategies

Constant strategies

We call constant a strategy $s \in \mathbb{S}_n$ which always chooses the same position:

$$s \text{ constant } \;\stackrel{\text{def}}{\iff}\; \forall t, u \in \mathbb{T}_n, \; s(t) = s(u)$$

Observe:

  • all constant strategies of height $0$ are equivalent,
  • a constant strategy which chooses position $p \not\in [n]$ has hit score and win rate $0$,
  • a constant strategy of height $>0$ which chooses position $p \in [n]$ has hit score $4^{n-1}$ and win rate of $1 \over 4$.

In particular, we denote by $\mathbf{T}_n$ (top $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).

\begin{equation}
\forall t \in \mathbb{T}_n, \quad \mathbf{T}_n(t) \stackrel{\text{def}}{=} n-1
\end{equation}

Lowest-white strategies

We denote by $\mathbf{W}_n$ (white 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.

Example

$\mathbf{W}_2 = [1010]$ chooses position $1$ when the first hat is black, position $0$ otherwise.

$\eta_{t_1,t_2}(\mathbf{W}_2)$$\mathbf{W}_2(t_2)$$1$$0$$1$$0$
$\mathbf{W}_2(t_1)$$\downarrow\!t1 \quad t2\!\rightarrow$$0 = \begin{array}{c}●\\●\end{array}$$1 = \begin{array}{c}●\\○\end{array}$$2 = \begin{array}{c}○\\●\end{array}$$3 = \begin{array}{c}○\\○\end{array}$
$1$$0 = \begin{array}{c}●\\●\end{array}$              0×00×00×10×1
$0$$1 = \begin{array}{c}●\\○\end{array}$              0×01×10×01×1
$1$$2 = \begin{array}{c}○\\●\end{array}$              1×00×01×10×1
$0$$3 = \begin{array}{c}○\\○\end{array}$              1×01×11×01×1
Hits for strategy $\mathbf{W}_2 = [0010]$

$\mathbf{W}_2$ has hit score $5$ and win rate $5 \over 16$.

Lowest-black strategies

We denote by $\mathbf{B}_n$ (black 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.

Example

$\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$.

$\mathbf{B}_3$ has hit score $21$ and win rate $21 \over 64$.

Operations on strategies

NameExample
embedding$e_3([0100]) \;=\; [0100 \text{-} 0100]$
left reset$[0101] \rightarrow [-1] \;=\; [0101]$
$[0101] \rightarrow [00] \;=\; [01 \text{-} 02 \text{-} 01 \text{-} 02]$
$[00] \rightarrow [0000] \;=\; [2000 \text{-} 2000]$
$[1010] \rightarrow [1010] \;=\; [3010 \text{-} 2010 \text{-} 3010 \text{-} 2010]$
right reset$[0101] \leftarrow [-1] \;=\; [0101]$
$[0101] \leftarrow [00] \;=\; [0102 \text{-} 0102]$
$[0000] \leftarrow [00] \;=\; [0002 \text{-} 0002]$
double reset$DR([0010], [0010]) \;=\; [2012 \text{-} 2012 \text{-} 3012 \text{-} 2012]$
left shift$\uparrow\![0] \;=\; [0 \text{-} 0]$
$\uparrow\![00] \;=\; [00 \text{-} 10]$
right shift$[00]\!\uparrow \;=\; [01 \text{-} 00]$
double shift$[00]\!\Uparrow \;=\; [01 \text{-} 00 \text{–} 21 \text{-} 20]$
Operations on strategies

Embedding

$e_1([-1]) = (-1, -1)$
$e_3([1010]) = [1010 \text{-} 1010]$
Embedding examples

Given a strategy $s$ in $\mathbb{S}_n$ and an integer $m > n$, we can use $s$ to play the game of $m$ hats. Simply: do not »looking » at the hats above position $n$ ($n$ included). This defines an embedding $e_m: \mathbb{S}_n \rightarrow \mathbb{S}_m$:

\begin{align*}
e_m: \mathbb{S}_n \rightarrow \mathbb{S}_m\\
s \mapsto e_m(s)
\end{align*}

\begin{equation}
\forall t \in \mathbb{T}_n, \;\; \big(e_m(s)\big)(t) \stackrel{\text{def}}{=} s(t \mathbin{\%} 2^n)
\end{equation}

(where $\mathbin{\%}$ is the remainder operator).

Win rate is invariant under embedding into $\mathbb{S}_m$:

\begin{equation}
\forall s \in \mathbb{S}_n, \forall m > n, \;\; \mu(s) = \mu(e_m(s))
\end{equation}

Left reset

$[00] \rightarrow [-1] = [00]$
$[00] \rightarrow [00] \rightarrow [-1] = [10 \text{-} 10]$
$[00] \rightarrow [00] \rightarrow [00] \rightarrow [-1] = [2010 \text{-} 2010]$
Left-reset examples

Given two strategies $a \in \mathbb{S}_m$ and $b \in \mathbb{S}_n$, we call « $a$ left-reset by $b$ », 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:

\begin{align}
LR(a,b): \; & \mathbb{T}_{m+n} \rightarrow [m+n] \nonumber \\
\nonumber \\
& t \stackrel{\text{def}}{\mapsto}
\left\{
\begin{array}{l}
a(t) \quad\text{if } t \not \equiv 0 \bmod 2^m\\
m + b(t \gg m) \quad\text{otherwise}
\end{array}
\right.
\end{align}

(where $\gg$ is the bitwise right shift operator).

Left reset is associative:

$$\forall a, b, c, \quad LR(a, LR(b, c)) \,=\, LR(LR(a, b), c)$$

so we make it into a binary operator:

\begin{equation}
b \rightarrow a \;\stackrel{\text{def}}{=}\; LR(a, b),
\end{equation}

and the following holds:

\begin{equation}
\forall a, b, c, \;\; (c \rightarrow b) \rightarrow a \,=\, c \rightarrow (b \rightarrow a) \,=\, c \rightarrow b \rightarrow a
\end{equation}

Right reset

$[-1] \leftarrow [00] = [00]$
$[-1] \leftarrow [00] \leftarrow [00] = [01 \text{-} 01]$
$[-1] \leftarrow [00] \leftarrow [00] \leftarrow [00] = [0102 \text{-} 0102]$
Right-reset examples

Given two strategies $a \in \mathbb{S}_m$ and $b \in \mathbb{S}_n$, we call « $a$ right-reset by $b$ », 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:

\begin{align}
RR(a,b): \; & \mathbb{T}_{m+n} \rightarrow [m+n] \nonumber \\
\nonumber \\
& t \stackrel{\text{def}}{\mapsto}
\left\{
\begin{array}{l}
a(t) \quad \text{if } t \not\equiv -1 \bmod 2^m\\
m + b(t \gg m) \quad \text{otherwise,}
\end{array}
\right.
\end{align}

where $\gg$ is the bitwise right shift operator.

Right reset is associative:

$$\forall a, b, c, \;\; RR(a, RR(b, c)) \,=\, RR(RR(a, b), c)$$

so we make it into a binary operator:

\begin{equation}
a \leftarrow b \;\stackrel{\text{def}}{=}\; RR(a, b),
\end{equation}

and the following holds:

\begin{equation}
\forall a, b, c, \;\; (a \leftarrow b) \leftarrow c \,=\, a \leftarrow (b \leftarrow c) \,=\, a \leftarrow b \leftarrow c
\end{equation}

Double reset

$DR([00], [00]) = [1111]$
$DR(DR([1010], [00]), [00]) = [30122013 \text{-} 30122013]$
$DR([1010], DR([00], [00])) = [30133013 \text{-} 30133013]$
Double-reset examples

Given two strategies $a \in \mathbb{S}_m$ and $b \in \mathbb{S}_n$, we call « $a$ double-reset by $b$ », 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:

\begin{align}
DR(a,b): \; & \mathbb{T}_{m+n} \rightarrow [m+n] \nonumber \\
\nonumber \\
& t \stackrel{\text{def}}{\mapsto}
\left\{
\begin{array}{l}
a(t) \quad \text{if } t \not\equiv 0 \text{ and } t \not\equiv -1 \bmod 2^m \\
m + b(t \gg m) \quad \text{otherwise,}
\end{array}
\right.
\end{align}

where $\gg$ is the bitwise right shift operator.

Double-reset is not associative.

Left shift

$\uparrow\![0] = [0 \text{-} 0]$
$\uparrow\![00] = [00 \text{-} 10]$
$\uparrow\![0000] = [0000 \text{-} 2000]$
Left-shift examples

Given a strategie $s \in \mathbb{S}_n$, we call « $s$ left-shifted« , denoted by $\uparrow\!s$, the following strategy in $\mathbb{S}_{n+1}$:

\begin{equation}
\forall t \in \mathbb{T}_{n+1}, \quad (\uparrow\!s)(t) \stackrel{\text{def}}{=}
\left\{
\begin{array}{ll}
n & \text{if } t = 2^n\\
s(t \mathbin{\%} 2^n) & \text{otherwise,}
\end{array}
\right.
\end{equation}

where $\mathbin{\%}$ is the remainder operator.

Right shift

$[0]\!\uparrow = [0 \text{-} 0]$
$[00]\!\uparrow = [01 \text{-} 00]$
$[0000]\!\uparrow = [0002 \text{-} 0000]$
Right-shift examples

Given a strategie $s \in \mathbb{S}_n$, we call « $s$ right-shifted« , denoted by $s\!\uparrow$, the following strategy in $\mathbb{S}_{n+1}$:

\begin{equation}
\forall t \in \mathbb{T}_{n+1}, \quad (s\!\uparrow)(t) \stackrel{\text{def}}{=}
\left\{
\begin{array}{ll}
n & \text{if } t = 2^n – 1\\
s(t \mathbin{\%} 2^n) & \text{otherwise,}
\end{array}
\right.
\end{equation}

where $\mathbin{\%}$ is the remainder operator.

Double shift

$[00]\!\Uparrow = [01 \text{-} 00 \text{–} 21 \text{-} 20]$
$[0000]\!\Uparrow = [0002 \text{-} 0000 \text{–} 3001 \text{-} 3000]$
Double-shift examples

Given a strategie $s \in \mathbb{S}_n$, we call « $s$ double-shifted« , denoted by $s\!\Uparrow$, the following strategy in $\mathbb{S}_{n+2}$:

\begin{equation}
\forall t \in \mathbb{T}_{n+2}, \quad (s\!\Uparrow)(t) \stackrel{\text{def}}{=}
\left\{
\begin{array}{ll}
n+1 & \text{if } t = 2^{n+1} + 2^n\\
\big(\uparrow\!(s\!\uparrow)\big)(t) & \text{otherwise.}
\end{array}
\right.
\end{equation}

Win rate computation

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.

Formulae

OperationConditionWin rate
left-reset$a \in \mathbb{S}_n$,
$b \in \mathbb{S}_m$
$\mu(b \rightarrow a) = \mu(a) + {\mu(b) \over 4^n}$
right-reset$a \in [n]^{\mathbb{T}_n}$,
$b \in [m]^{\mathbb{T}_m}$
$\mu(a \leftarrow b) = \mu(a) + {\mu(b) \over 4^n}$
double-reset$a \in [n]^{\mathbb{T}_n}$,
$b \in [m]^{\mathbb{T}_m}$
$\mu(DR(a, b)) = \mu(a) + {{4 \mu(b) – 1} \over 4^n}$
left-shift$s \in {\mathbb{S}_n}$$\mu(\uparrow\!s) = \mu(s) + {1 \over 4^{n+1}}$
right-shift$s \in [n]^{\mathbb{T}_n}$$\mu(s\!\uparrow) = \mu(s) + {1 \over 4^{n+1}}$
double-shift$s \in [n]^{\mathbb{T}_n}$$\mu(s\!\Uparrow) = \mu(s) + {1 \over 4^{n+1}}+ {2 \over 4^{n+2}}$
Formulae for win rate calculation

Observations

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))$.

Let $\sum\mathcal{M}$ denote the sum of all coefficients of matrix $\mathcal{M}$.

Then $\eta(a)$ can be written as:

\begin{align*}
\sum
\begin{pmatrix}
\big(\eta_{0,0}(a) & \eta_{0,1}(a) & \cdots & \eta_{0,2^n-2}(a) & \eta_{0,2^n-1}(a) \\
\big(\eta_{1,0}(a) & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & \eta_{1,2^n-1}(a) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\big(\eta_{2^n-2,0}(a) & \eta_{2^n-2,1}(a) & \cdots & \eta_{2^n-2,2^n-2}(a) & \eta_{2^n-2,2^n-1}(a) \\
\big(\eta_{2^n-1,0}(a) & \eta_{2^n-1,1}(a) & \cdots & \eta_{2^n-1,2^n-2}(a) & \eta_{2^n-1,2^n-1}(a)
\end{pmatrix}
\end{align*}

Which simplifies to:

\begin{equation}
\sum
\begin{pmatrix}
0 & 0 & \cdots & 0 & 0 \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & \eta_{1,2^n-1}(a) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & \eta_{2^n-2,2^n-1}(a) \\
\cdot & \cdot & \cdots & \cdot & \eta_{2^n-1,2^n-1}(a)
\end{pmatrix}
\end{equation}

Which when $a \in [n]^{\mathbb{T}_n}$ further simplifies to:

\begin{equation}
\!\!\!\!\!\!\!\!\!\!\!\!\sum
\begin{pmatrix}
0 & 0 & \cdots & 0 & 0 \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & \overline{(1)}\big(a(2^n-1)\big) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & \overline{(2^n-2)}\big(a(2^n-1)\big) \\
\cdot & \cdot & \cdots & \cdot & 1
\end{pmatrix}
\end{equation}

Note that:

  • these matrices are symmetric
  • the coefficients of the first line add up to $0$
  • the coefficients of the last column add up to:

$\quad\quad
\left\{
\begin{array}{ll}
2^{n-1} & \text{when } a(2^m-1) \in [n]\\
0 & \text{otherwise}
\end{array}
\right.
$

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:

\begin{equation}
\big(\forall t \in \mathbb{T}_n \setminus \{2^n-1\}, \;\; a(t) = b(t)\big) \;\; \implies \;\; \eta(a) = \eta(b).
\label{SameRate}
\end{equation}

Win rate after left reset

Let $a \in \mathbb{S}_n, b \in \mathbb{S}_m$:

\begin{equation}
\mu(b \rightarrow a) = \mu(a) + {\mu(b) \over 4^n}
\label{LeftResetRule}
\end{equation}

Proof:

\begin{align*}
& {\eta(b \rightarrow a) \over 4^m} \\

& \;\;=\;\; \sum
\begin{pmatrix}
\mu(b) & 0 & \cdots & 0 & 0 \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & \eta_{1,2^n-1}(a) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & \eta_{2^n-2,2^n-1}(a) \\
\cdot & \cdot & \cdots & \cdot & \eta_{2^n-1,2^n-1}(a)
\end{pmatrix} \\

& \;\;=\;\; \eta(a) + \mu(b) \\

& \;\;=\;\; 4^n \cdot \left(\mu(a) + {\mu(b) \over 4^n}\right) \quad \Box
\end{align*}

Win rate after right reset

This formula works for strategies which choose positions within the tower.

Let $a \in \mathbb{S}_n, b \in \mathbb{S}_m$:

\begin{equation}
\left\{
\begin{array}{l}
a \in [n]^{\mathbb{T}_n} \\
b \in [m]^{\mathbb{T}_m}
\end{array}
\right. \;\; \implies \;\; \mu(a \leftarrow b) = \mu(a) + {\mu(b) \over 4^n}
\label{RightResetRule}
\end{equation}

Proof:

\begin{align*}
& {\eta(a \leftarrow b) \over 4^m}
\\
& \;\;=\;\; \sum \\
& \begin{pmatrix}
0 & 0 & \cdots & 0 & {1 \over 4^m} \sum_{t,u\in\mathbb{T}_m} \big(\overline{(t)}(b(u)) \cdot \overline{(2^n-1)}(a(0))\big) \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & {1 \over 4^m} \sum_{t,u\in\mathbb{T}_m} \big(\overline{(t)}(b(u)) \cdot \overline{(2^n-1)}(a(1))\big) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & {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) \\
\cdot & \cdot & \cdots & \cdot & \mu(b)
\end{pmatrix} \\
\\
& \;\;=\;\; \sum \\
& \begin{pmatrix}
0 & 0 & \cdots & 0 & {1 \over 4^m} \sum_{u\in\mathbb{T}_m}\sum_{t\in\mathbb{T}_m} \overline{(t)}(b(u)) \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & {1 \over 4^m} \sum_{u\in\mathbb{T}_m}\sum_{t\in\mathbb{T}_m} \overline{(t)}(b(u)) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & {1 \over 4^m} \sum_{u\in\mathbb{T}_m}\sum_{t\in\mathbb{T}_m} \overline{(t)}(b(u)) \\
\cdot & \cdot & \cdots & \cdot & \mu(b)
\end{pmatrix}
\end{align*}

Now since $0 \le b(u) < m, \quad \sum_{t\in\mathbb{T}_m} (\overline{(t)}(b(u)) = 2^{m-1}$.

Hence:

\begin{align*}
{\eta(a \leftarrow b) \over 4^m} \;\;
&= \;\; \sum
\begin{pmatrix}
0 & 0 & \cdots & 0 & {1 \over 2} \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & {1 \over 2} \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & {1 \over 2} \\
\cdot & \cdot & \cdots & \cdot & \mu(b)
\end{pmatrix} \\

&= \;\; \eta(a) + \mu(b) \\

&= \;\; 4^n \cdot \left(\mu(a) + {\mu(b) \over 4^n}\right) \quad \Box
\end{align*}

Win rate after double reset

This formula works for strategies which choose positions within the tower.

Let $a \in \mathbb{S}_n, b \in \mathbb{S}_m$:

\begin{equation}
\left\{
\begin{array}{l}
a \in [n]^{\mathbb{T}_n} \\
b \in [m]^{\mathbb{T}_m}
\end{array}
\right. \;\; \implies \;\;
\mu(DR(a, b)) = \mu(a) + {{4 \mu(b) – 1} \over 4^n}
\label{DoubleResetRule}
\end{equation}

Proof:

\begin{align*}
& {\eta(DR(a, b)) \over 4^m} \\
\\
& \;\;=\;\; \sum \\
& \begin{pmatrix}
\mu(b) & 0 & \cdots & 0 & \mu(b) \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & {1 \over 4^m} \sum_{t,u\in\mathbb{T}_m} \big(\overline{(t)}(b(u)) \cdot \overline{(2^n-1)}(a(1))\big) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & {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) \\
\cdot & \cdot & \cdots & \cdot & \mu(b)
\end{pmatrix} \\
\\
& \;\;=\;\; \sum \\
& \begin{pmatrix}
\mu(b) & 0 & \cdots & 0 & \mu(b) \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & {1 \over 2} \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & {1 \over 2} \\
\cdot & \cdot & \cdots & \cdot & \mu(b)
\end{pmatrix} \\
\\
&= \;\; \eta(a) + 4 \mu(b) – 1 \\
\\
&= \;\; 4^n\left(\mu(a) + {{4 \mu(b) – 1} \over 4^n}\right) \quad \Box
\end{align*}

Win rate after left shift

Let $s \in \mathbb{S}_n$:

\begin{equation}
\mu(\uparrow\!s) = \mu(s) + {1 \over 4^{n+1}}
\label{LeftShiftRule}
\end{equation}

Proof:

Note that the strategy $(\uparrow\!s)$ is equivalent to $([00] \rightarrow s)$.

Hence $(\ref{EquivRate})$ they have the same hit score and win rate. Applying $(\ref{LeftResetRule})$ we get:

\begin{align*}
\mu(\uparrow\!s) \;\;=\;\; \mu([00] \rightarrow s) \;\;=\;\; \mu(s) + {\mu([00]) \over 4^n} \quad \Box
\end{align*}

Win rate after right shift

This formula works for a strategy which chooses positions within the tower.

Let $s \in \mathbb{S}_n$:

\begin{equation}
s \in [n]^{\mathbb{T}_n} \;\;
\implies \;\; \mu(s\!\uparrow) = \mu(s) + {1 \over 4^{n+1}}
\label{RightShiftRule}
\end{equation}

Proof:

Note that the strategies $(s\!\uparrow)$ and $(s \leftarrow [00])$ make the same choices except when presented with a tower with only white hats.

Hence $(\ref{SameRate})$ they have the same hit score and win rate. Applying $(\ref{RightResetRule})$ we get:

\begin{align*}
\mu(\uparrow\!s) \;\;=\;\; \mu(s \leftarrow [00]) \;\;=\;\; \mu(s) + {\mu([00]) \over 4^n} \quad \Box
\end{align*}

Win rate after double shift

This formula works for a strategy which chooses positions within the tower.

Let $s \in \mathbb{S}_n$:

\begin{equation}
s \in [n]^{\mathbb{T}_n} \;\;
\implies \;\; \mu(s\!\Uparrow) = \mu(s) + {1 \over 4^{n+1}}+ {2 \over 4^{n+2}}
\label{DoubleShiftRule}
\end{equation}

Proof:

Consider $s_1 = \uparrow\!(s\!\uparrow)$ and $s_2 = s\!\Uparrow$:

$s_1 = \uparrow\!(s\!\uparrow)$$s_2 = s\!\Uparrow$
$s(0), s(1), \!\cdot\cdot, s(2^n\text{-}2), \pmb{n},$
$s(0), s(1), \!\cdot\cdot, s(2^n\text{-}2), s(2^n\text{-}1),$
$\pmb{n}\!\pmb{+}\!\pmb{1}, s(1), \!\cdot\cdot, s(2^n\text{-}2), \pmb{n},$
$\pmb{s(0)}, s(1), \!\cdot\cdot, s(2^n\text{-}2), s(2^n\text{-}1)$
$s(0), s(1), \!\cdot\cdot, s(2^n\text{-}2), \pmb{n},$
$s(0), s(1), \!\cdot\cdot, s(2^n\text{-}2), s(2^n\text{-}1),$
$\pmb{n}\!\pmb{+}\!\pmb{1}, s(1), \!\cdot\cdot, s(2^n\text{-}2), \pmb{n},$
$\pmb{n}\!\pmb{+}\!\pmb{1}, s(1), \!\cdot\cdot, s(2^n\text{-}2), s(2^n\text{-}1)$

The only difference between $s_1$ and $s_2$ is the position they choose for tower $k = 2^{n+1} + 2^n$:

$$s_2(k) = n + 1 \neq s(0) = s_1(k)$$

Let’s compare the hit scores. Since the $\eta_{t,u}$ are equal unless $t$ or $u$ equals $k$, we have:

\begin{align}
\eta(s_2) – \eta(s_1) \;\; & =\;\; \sum_{t,u \in \mathbb{T}_{n+2}} \big(\eta_{t,u}(s_2) – \eta_{t,u}(s_1)\big) \nonumber \\

& =\;\; 2 \!\!\sum_{t \in \mathbb{T}_{n+2}, t \neq k}\!\!
\big(\eta_{t,k}(s_2) – \eta_{t,k}(s_1)\big) \label{PartialDoubleShift}\\
& \;\;\;\;\;\; + \big(\eta_{k,k}(s_2)\big)^2. \nonumber
\end{align}

Now:

\begin{align}
& \sum_{t \in \mathbb{T}_{n+2}, t \neq k}
\big(\eta_{t,k}(s_2) – \eta_{t,k}(s_1)\big) \nonumber \\

& \quad = \!\!\sum_{t \in \mathbb{T}_{n+2}, t \neq k}\!\!
\big(\overline{(t)}(s_2(k))\cdot\overline{(k)}(s_2(t))
– \overline{(t)}(s_1(k))\cdot\overline{(k)}(s_1(t))\big) \nonumber
\end{align}

Because $k = 2^{n+1} + 2^n$ (all bits null but the two most significant), for the terms in this sum it holds that:

$$
\left\{
\begin{array}{l}
\overline{(k)}(s_2(t)) \neq 0 \implies s_2(t) \ge n
\implies t \in \{2^n-1, 2^{n+1}, 2^{n+1}-1\} \\
\overline{(k)}(s_1(t)) \neq 0 \implies s_1(t) \ge n
\implies t \in \{2^n-1, 2^{n+1}, 2^{n+1}-1\}
\end{array}
\right.
$$

Hence:

\begin{align*}
& \sum_{t \in \mathbb{T}_{n+2}, t \neq k}
\big(\eta_{t,k}(s_2) – \eta_{t,k}(s_1)\big) \\
\\
& \quad = \;\;\; \overline{(2^n-1)}(s_2(k)) \,- \overline{(2^n-1)}(s_1(k)) \\
&\quad \;\;\; + \overline{(2^{n+1})}(s_2(k)) \,- \overline{(2^{n+1})}(s_1(k)) \\
&\quad \;\;\; + \overline{(2^{n+1}-1)}(s_2(k)) \,- \overline{(2^{n+1}-1)}(s_1(k)) \\
\\
& \quad = \;\;\; \overline{(2^n-1)}(n+1) \,- \overline{(2^n-1)}(s(0)) \\
&\quad \;\;\; + \overline{(2^{n+1})}(n+1) \,-\overline{(2^{n+1})}(s(0)) \\
&\quad \;\;\; + \overline{(2^{n+1}-1)}(n+1) \,- \overline{(2^{n+1}-1)}(s(0))
\end{align*}

Finally since $0 \le s(0) < n$:

\begin{align*}
\sum_{t \in \mathbb{T}_{n+2}, t \neq k}
& \big(\eta_{t,k}(s_2) – \eta_{t,k}(s_1)\big) \\
\\
= \quad & \quad\; 0 \quad-\quad 1 \\
& + 1 \quad-\quad 0 \\
& + 1 \quad-\quad 1 \\
\\
= \quad & \quad\; 0
\end{align*}

Going back to $(\ref{PartialDoubleShift})$, we conclude:

\begin{align*}
\eta(s_2) – \eta(s_1) \;\; & =\;\; \big(\eta_{k,k}(s_2)\big)^2 \;\;=\;\; 1 \\
\eta(s\!\Uparrow) \;\; & =\;\; \eta(\uparrow\!(s\!\uparrow)) + 1 \\
& =\;\; \big( 16 \cdot \eta(s) + 4 + 1\big) + 1 \\
& =\;\; 4^{n+2} \cdot \big(\mu(s) + {1 \over 4^{n+1}} + {2 \over 4^{n+2}}\big)
\quad \Box
\end{align*}

Efficient strategies

StrategyHeightWin rateOptimal?
$\mathbf{T}_0 = [-1]$$0$$0$yes
$\mathbf{T}_1 = [00]$$1$${1 \over 4}$yes
$\mathbf{W}_2 = [1010]$$2$${5 \over 16}$yes
$\mathbf{B}_2 = [0101]$$2$${5 \over 16}$yes
$\mathbf{C}_2 = [0010]$$2$${5 \over 16}$yes
$\mathbf{C}_3 = \mathbf{R}_1 =$
$[01002120]$
$3$${21 \over 64}$yes
$\mathbf{C}_4 =$
$[01002123$
$01002120]$
$4$${89 \over 256}$yes
$\mathbf{C}_5 =$
$[01002123$
$01002120$
$41002123$
$41002120]$
$5$${358 \over 1024}$yes
$\mathbf{T}_n$$n$${1 \over 4}$no for $n>1$
$\mathbf{W}_n$$n$${1 \over 3}\big(1 – {1 \over 4^n}\big)$no for $n>2$
$\mathbf{B}_n$$n$${1 \over 3}\big(1 – {1 \over 4^n}\big)$no for $n>2$
$\mathbf{C}_{2n+1}$$2n+1$${7 \over 20} – {1 \over 10 (16)^n}$yes?
$\mathbf{C}_{2n+2}$$2n+2$${7 \over 20} – {3 \over 80 (16)^n}$yes?
$\mathbf{R}_n$$3n$${7 \over 20} – {1 \over {10 (16)^n}}$no for $n>1$
Efficiency of various strategies

Top strategies

The top strategies are obtained by repeatedly double-resetting the strategy $[00]$:

\begin{align}
\mathbf{T}_0 \;
&\stackrel{\text{def}}{=} \; [-1] \\
\forall n \in \mathbb{N}, \quad \mathbf{T}_{n+1} \;
&\stackrel{\text{def}}{=} \; DR([00], \mathbf{T}_n) \nonumber
\end{align}

\begin{align}
\mu(\mathbf{T}_0) &= 0\\
\forall n > 0, \quad \mu(\mathbf{T}_n) &= {1 \over 4}\\
\end{align}

Lowest-white strategies

The lowest-white strategies are obtained by repeatedly left-resetting the strategy $[00]$:

\begin{align}
\mathbf{W}_0 \;
&\stackrel{\text{def}}{=} \; [-1] \\
\forall n \in \mathbb{N}, \quad \mathbf{W}_{n+1} \;
&\stackrel{\text{def}}{=} \; \mathbf{W}_n \rightarrow [00] \nonumber
\end{align}

Applying $(\ref{LeftResetRule})$ we get:

\begin{equation}
\mu(\mathbf{W}_n) = {1 \over 3} \cdot \big(1 – {1 \over 4^n}\big).
\end{equation}

As the height of the towers goes to infinity, the win rate of the lowest-white strategies converges to $1 \over 3$:

\begin{equation}
\lim_{n \to \infty}\mu(\mathbf{W}_n) = {1 \over 3} \approx 33.33\%.
\end{equation}

Lowest-black strategies

The lowest-black strategies are obtained by repeatedly right-resetting the strategy $[00]$:

\begin{align}
\mathbf{B}_0 \;
&\stackrel{\text{def}}{=} \; [-1] \\
\forall n \in \mathbb{N}, \quad \mathbf{B}_{n+1} \;
&\stackrel{\text{def}}{=} \; [00] \leftarrow \mathbf{B}_n \nonumber
\end{align}

Applying $(\ref{RightResetRule})$ we get:

\begin{equation}
\mu(\mathbf{B}_n) = {1 \over 3} \cdot \big(1 – {1 \over 4^n}\big).
\end{equation}

As the height of the towers goes to infinity, the win rate of the lowest-black strategies converges to $1 \over 3$:

\begin{equation}
\lim_{n \to \infty}\mu(\mathbf{B}_n) = {1 \over 3} \approx 33.33\%.
\end{equation}

Carter strategies

$\mathbf{C}$Win
rate
Tuple
$\mathbf{C}_1$$1 \over 4$$[00]$
$\mathbf{C}_2$$5 \over 16$$[0100]$
$\mathbf{C}_3$$22 \over 64$$[01002120]$
$\mathbf{C}_4$$89 \over 256$$[0100212\text{-}01002120]$
$\mathbf{C}_5$$358 \over 1024$$[01002123 \text{-} 01002120 \text{-} 41002123 \text{-} 41002120]$
$\mathbf{C}_6$$1433 \over 4096$$[01002123 \text{-} 01002120 \text{-} 41002123 \text{-} 41002125$
$01002123 \text{-} 01002120 \text{-} 41002123 \text{-} 41002120]$
$\mathbf{C}_7$$5734 \over 16384$$[01002123 \text{-} 01002120 \text{-} 41002123 \text{-} 41002125$
$01002123 \text{-} 01002120 \text{-} 41002123 \text{-} 41002120$
$61002123 \text{-} 01002120 \text{-} 41002123 \text{-} 41002125$
$61002123 \text{-} 01002120 \text{-} 41002123 \text{-} 41002120]$
Carter strategies

Carter strategies are defined by repeatedly shifting and double-shifting the strategy $[00]$:

\begin{align}
\mathbf{C}_1 \quad &\stackrel{\text{def}}{=} \quad [00], \nonumber \\
\mathbf{C}_{2n+2} \quad &\stackrel{\text{def}}{=} \quad \mathbf{C}_{2n+1}\!\uparrow, \\
\mathbf{C}_{2n+3} \quad &\stackrel{\text{def}}{=} \quad \mathbf{C}_{2n+1}\!\Uparrow. \nonumber
\end{align}

Applying $(\ref{LeftShiftRule})$ & $(\ref{DoubleShiftRule})$ we get:

\begin{align}
\mu(\mathbf{C}_{2n+1}) \quad &= \quad {7 \over 20} – {1 \over 10 \cdot (16)^n}, \\
\mu(\mathbf{C}_{2n+2}) \quad &= \quad {7 \over 20} – {3 \over 80 \cdot (16)^n}.
\end{align}

As the height of the towers goes to infinity, the win rate of the Carter strategies converges to $7 \over 20$:

\begin{equation}
\lim_{n \to \infty}\mu(\mathbf{C}_n) = {7 \over 20} = 35\%.
\end{equation}

Reyes strategies

$\mathbf{R}$Win
rate
Tuple
$\mathbf{R}_1$$22 \over 64$$[21002122]$
$\mathbf{R}_2$$358 \over 1024$$[51002125 \text{-} 41002124 \text{-} 31002123 \text{-} 31002123$
$51002125 \text{-} 41002124 \text{-} 51002125 \text{-} 51002125]$
$\mathbf{R}_3$
$5734 \over 16384$
$[61002126 \text{-} 41002124 \text{-} 31002123 \text{-} 31002123$
$51002125 \text{-} 41002124 \text{-} 51002125 \text{-} 61002126$
$71002127 \text{-} 41002124 \text{-} 31002123 \text{-} 31002123$
$51002125 \text{-} 41002124 \text{-} 51002125 \text{-} 71002127$
$61002126 \text{-} 41002124 \text{-} 31002123 \text{-} 31002123$
$51002125 \text{-} 41002124 \text{-} 51002125 \text{-} 61002126$
$61002126 \text{-} 41002124 \text{-} 31002123 \text{-} 31002123$
$51002125 \text{-} 41002124 \text{-} 51002125 \text{-} 61002126$
$81002128 \text{-} 41002124 \text{-} 31002123 \text{-} 31002123$
$51002125 \text{-} 41002124 \text{-} 51002125 \text{-} 81002128$
$71002127 \text{-} 41002124 \text{-} 31002123 \text{-} 31002123$
$51002125 \text{-} 41002124 \text{-} 51002125 \text{-} 71002127$
$81002128 \text{-} 41002124 \text{-} 31002123 \text{-} 31002123$
$51002125 \text{-} 41002124 \text{-} 51002125 \text{-} 81002128$
$61002126 \text{-} 41002124 \text{-} 31002123 \text{-} 31002123$
$51002125 \text{-} 41002124 \text{-} 51002125 \text{-} 61002126]$
Reyes strategies

Reyes strategies are defined by repeatedly double-resetting the Carter strategy $\mathbf{C}_3$:

\begin{align}
\mathbf{R}_1 \;
&\stackrel{\text{def}}{=} \; \mathbf{C}_3 \\
\forall n > 0, \quad \mathbf{R}_{n+1} \;
&\stackrel{\text{def}}{=} \; DR(\mathbf{C}_3, \mathbf{R}_n). \nonumber
\end{align}

Applying $(\ref{DoubleResetRule})$ we get:

\begin{equation}
\mu(\mathbf{R}_n) = {7 \over 20} – {1 \over {10 \cdot (16)^n}}.
\end{equation}

As the height of the towers goes to infinity, the win rate of the Reyes strategies converges to $7 \over 20$:

\begin{equation}
\lim_{n \to \infty}\mu(\mathbf{R}_n) = {7 \over 20} = 35\%.
\end{equation}

Recap and Whereto?

I came across the game of hats through Numberphile’s . Then Google pointed to the interesting article by Stan Wagon .

Wagon provides a state of the art as of 2014:

  • 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 < 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 > 5$ we don’t know.
  • Mentions a proof by Walter Stromquist that $15\over40$ is an upper bound for the win rate of any symmetric strategy.
  • Tells about asymmetric strategies (it is believed that they do not lead to better the win rates than the symmetric strategies).
  • Tells about playing the game with more than two players.
  • Shows how to leverage the axiom of choice to define a strategy for the game with countably infinitely many hats.

Wagon’s state of the art doesn’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: « What about n = 9 or larger? ». By contrast this article provides an explicit construction of $\mathbf{C}_n$ for all $n > 0$.

In the next article I plan to describe a « hat calculator » 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’s).

References

Kariv, J., van Alten, C., & Yeroshkin, D. (2017). Computing optimal strategies for a cooperative hat game. ArXiv:1407.4711 [Cs, Math]. http://arxiv.org/abs/1407.4711
Friedrich, T., & Levine, L. (2012). Fast simulation of large-scale growth models. ArXiv:1006.1003 [Cond-Mat]. http://arxiv.org/abs/1006.1003
Buhler, J. (2020, July 6). Hat Problems - Numberphile - YouTube. https://www.youtube.com/watch?v=laAtv310pyk
Wagon, S. (2014, January 4). MacPOW 1179: An Infinitely Puzzling Hat Problem. Stan Wagon’s Website. http://stanwagon.com/potw/fall13/p1179.html
Catégories
Friandises Math Tips

Schizo: a different sudoku solving technique

Over the years, several tips and techniques have been developed to help solve sudoku puzzles with logic rather than brute force. To name a few, sudoku9x9 mentions (among others) hidden single, naked single, x-wing.

At least one solution

These techniques are all based on a common principle: they work « ad absurdum », by eliminating moves that would lead to an invalid grid: a puzzle with zero solution. For example, the grid below illustrates the hidden single technique:

Hidden single example
2
1 3
2

Number 2 cannot be placed in any of the red cells because this would lead to a grid with no solution. Therefore it must be placed in the green cell, leading to the next step:

The hidden single is revealed
2
1 2 3
2

At most one solution

Here is a (novel?) technique based on the opposite principle: it works by eliminating a move that would lead to a grid with more than one solution. (By current rules, well formed sudoku puzzles must have a single solution.)

The grid below illustrates this technique, which we call schizo (as in schizophrenia):

Schizo example
3 6 1 2
2 5 1 48 478 9 3 6
6 3 2 478 5 1 9
2 48 48 7 1
7 1 9 5 3 6 2 8 4
1 9 2
4 2 7 1 3 5
1 9 5 8 2
5 6 2 4 1

Number 7 cannot be placed in the red cell because this would eventually lead to two equally valid solutions:

Eventual solution 1
3 6 1 2
2 5 1 4 8 9 3 6
6 3 2 7 5 1 9
2 8 4 7 1
7 1 9 5 3 6 2 8 4
1 9 2
4 2 7 1 3 5
1 9 5 8 2
5 6 2 4 1
Eventual solution 2
3 6 1 2
2 5 1 8 4 9 3 6
6 3 2 7 5 1 9
2 4 8 7 1
7 1 9 5 3 6 2 8 4
1 9 2
4 2 7 1 3 5
1 9 5 8 2
5 6 2 4 1

Therefore 7 must be placed in the green cell, leading to the next step:

Schizophrenia is avoided
3 6 1 2
2 5 1 48 7 9 3 6
6 3 2 48 5 1 9
2 48 48 7 1
7 1 9 5 3 6 2 8 4
1 9 2
4 2 7 1 3 5
1 9 5 8 2
5 6 2 4 1

$\Box$

Catégories
Friandises La vie

Shepard Fairey

By Mozilla – Mozilla, CC BY 3.0
Obey x Zumiez à l’Aérosol (high def picture here)

Counterpoint in blue: paintings by Alexandre Motte (Dinard)

Catégories
Friandises Poésie

Ce que nous sommes

We are such stuff
        Nous sommes l’étoffe
As dreams are made on; and our little life
        dont sont faits les rêves ; et nos petites vies
Is rounded with a sleep.
        sont bordées de sommeil.
— Prospero, The Tempest, William Shakespeare


Wir sind eine Masse, die jede Form annimmt, in die sie auf die eine oder die andere Weise hineingerät!
        Nous sommes une matière qui épouse toujours la forme du premier monde venu !
— Ulrich, Der Mann ohne Eigenschaften, Robert Musil