There is a coins games that called "Turning Turtles".
I'd like like to know if there is a winning strategy for this game.
From the written above I understand how to calculate the Nim-Value of it:
H=1, T=0
$HTTHTTHTHT = 1001001010$, and Nim-Value of it is: $(100)\oplus(100)\oplus(10)\oplus(10)=0$ – this is loosing situation (if I understand right…).
So my question is:
How can I bring from loosing situation to a winning situation? (if it's possible)
And I don't understand something: lets say that this is the board $HTTHTTHTHT = 1001001010$ – and it's my turn. I'm at loosing position (Nim-Val is $0$), and I can do a move that make the next player at loosing position also:
$HTTHTT\boldsymbol {T}T\boldsymbol {T}T$ – and the next player is at Nim-Val of $0$ (loosing position).
Where is my mistake here?
Thank you!
Best Answer
You need to understand two things:
How to translate Turning Turtles to Nim, and back.
What the winning strategy is in Nim.
Turning Turtles $\iff$ Nim
A coin with the Head side up at position $i$ is equivalent to a Nim heap of size $i$. That is, $\mathrm{H\,T\,T\,H\,T\,T\,H\,T\,H\,T}$ is equivalent to a Nim position with heaps of size $1,4,7$ and $9$.
Flipping coins numbered $i$ and $j$, where $i<j$, so that coin number $j$ was originally heads, is equivalent to reducing the Nim heap of size $j$ to a Nim heap of size $i$. For example, from $\mathrm{H\,T\,T\,H\,T\,T\,H\,T\,H\,T}$, you could flip coins number $2$ and $7$, resulting in $\mathrm{H}\,\bf{H}\,\mathrm{T\,H\,T\,T}\,\bf{T}\,\mathrm{T\,H\,T}$. If you translate both to Nim positions, this looks like $$ (1,4,7,9)\longrightarrow (1,2,4,9), $$ which is indeed like reducing a Nim heap of size $4$ to one of size $2$.
The exception to this correspondence is when both coins are turned from heads to tails. For example, moving from $\mathrm{H\,H,H}$ to $\mathrm{T\,H\,T}$. In this case, the first Nim position was $(1,2,3)$, and it seems like the result should be $(1,1,2)$, since we flipped coins $3$ and $1$. Here, we have to mentally delete any repeated heaps, so instead of $(1,1,2)$, we just get a single Nim heap of size $2$. These repeated heaps do not affect the Nim outcome.
Now that you know how Turning Turtles positions and moves correspond to Nim, all you need to know is$\dots$
Winning Strategy in Nim
To find a winning move in a Nim position with heap size $n_1,\dots,n_k$, all you need to do is the following:
Compute the Nim sum of the heap sizes: $m=n_1\oplus \dots \oplus n_k$. A winning move exists iff $m\neq 0$.
Compute $n_i\oplus m$ for each $i\in \{1,\dots,k\}$. If $n_i\oplus m$ is a smaller number than $n_i$, then reducing the $n_i$ heap to $n_i\oplus m$ is a winning move.
Example
Let's find all winning moves starting from $\mathrm{H\,T\,T\,H\,T\,T\,H\,T\,H\,T}$. The corresponding Nim position is $(1,4,7,9)$, whose Nim sum is $1\oplus 4\oplus 7\oplus 9=11$. Then,
$11\oplus 1=10$, so there is no winning move on the $1$ heap.
$11\oplus 4=15$, so there is no winning move on the $4$ heap.
$11\oplus 7=12$, so there is no winning move on the $7$ heap.
$11\oplus 9=2$, so reducing the $9$ heap to $2$ is a winning move.
Translating this back to Turning Turtles, the only winning move is to flip over coins $2$ and $9$.