Heads I win

I am characterizing each starting position by the number of "piles", where a pile is a group of adjacent heads. For example the state $\{2,3\}$ means the positions HHTTHHH, HHTHHHT, HHHTTHH, HHHTHHT, THHTHHH, THHHTHH.

There's two stages to the solution: deciding which states are winning, and then counting how many positions in total make up the winning states.

Here are the possible states divided into winning and losing ones (I'll justify this in a moment).

Losing: $\{0\}, \{1,1\} \{2,2\} \{3,3\} \{1,4\} \\ \{1,1,1,1\}$ Winning: $\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{7\} \\ \{1,2\}, \{1,3\}, \{2,3\}, \{2,4\}, \{1,5\} \\ \{1,1,1\}, \{1,1,2\}, \{1,2,2\}, \{1,1,3\}$

The states that can be broken down into two identical halves are losing states because the second player wins by copying the first player's move on the other half.

Any state that consists of a losing state plus any one of the following operations must be a winning state (with the winning move being converting that state to the losing state):

• add $1$ or $2$ coins to a pile
• create a new pile with $1$ or $2$ coins
• combine two piles and add $1$ or $2$ coins to the combined pile

Applying all of these steps to each of the losing states $\{0\}, \{1,1\}, \{2,2\}, \{3,3\}, \{1,1,1,1\}$ gives all of the above winning states except $\{1,5\}$ .

We determine that $\{1,4\}$ must be a losing state because we have considered all states derivable from it in one move and they are all winning. From this we conclude that $\{1,5\}$ is winning because it can be reduced to $\{1,4\}$ in one move.

Now to add up the number of combinations for each of the above. We can encode the concept that the piles must have blank spaces between them by representing a pile of size $n$ as $n$ heads followed by one tail, and imagine we have $8$ slots to fill. So for example $p(\{1,2\})$ is the number of permutations of $\{HT, HHT, T, T, T\}$ , i.e. $5! / 3! = 20$ .

It's a bit shorter to add up the number of losing positions and then subtract them from $128$ :

$\begin{aligned} p(1,1) &= 6! / (4!2!) = 15 \\ p(2,2) &= 4! / (2!2!) = 6 \\ p(3,3) &= 1\\ p(1,4) &= 3! = 6\\ p(0) &= 1\\ p(1,1,1,1) &= 1\\ \end{aligned}$ which add up to $30$ , so the number of winning positions is $\boxed{98}$ .

Reading the discussion about the Sprague-Grundy function will be useful.

This is a Nim-type game, where the stacks on the Nim board are the sizes of the consecutive strings of heads. At each go, the player can remove one or two heads from one of the strings, which may divide the string into two pieces. The Grundy function for this game is $\begin{array}{rcl} g(0) & = & 0 \\ g(1) & = & \mathrm{mex}\{g(0)\} = 1 \\ g(2) & = & \mathrm{mex}\{g(0),g(1)\} = 2 \\ g(3) & = & \mathrm{mex}\{g(1),g(2),g(1)\oplus g(1)\} \\ & = & \mathrm{mex}\{1,2,0\} = 3 \\ g(4) & = & \mathrm{mex}\{g(2),g(3),g(1)\oplus g(2),g(1)\oplus g(1)\} \\ & = & \mathrm{mex}\{2,3,3,0\} = 1 \\ g(5) & = & \mathrm{mex}\{g(3),g(4),g(1) \oplus g(3),g(2)\oplus g(2),g(1)\oplus g(2)\} \\ & = & \mathrm{mex}\{3,1,2,0,3\} = 4 \\ g(6) & = & \mathrm{mex}\left\{ \begin{array}{l} g(4),g(5),g(1)\oplus g(4),g(2)\oplus g(3), \\ g(1) \oplus g(3),g(2)\oplus g(2)\end{array} \right\} \\ & = & \mathrm{mex}\{1,4,0,1,2,0\} = 3 \\ g(7) & = & \mathrm{mex}\left\{ \begin{array}{l} g(5),g(6),g(1)\oplus g(5),g(2)\oplus g(4),\\ g(3)\oplus g(3),g(1)\oplus g(4),g(2) \oplus g(3)\end{array}\right\} \\ & = & \mathrm{mex}\{4,3,5,3,0,0,1\} = 2 \end{array}$ We need to calculate the Nim score for each starting position of the board, and count the number of losing positions for the first player.

• If there are $7$ tails, then the first player loses. This gives us a count of $1$ losing position.

• If there are $6$ tails, then there is just one head, so the Nim score of the board is $g(1)=1$ . This is a winning position for the first player.

• If there are $5$ tails, we could have one sequence of $2$ heads, or two sequences of $1$ head. Since $g(2) = 2$ and $g(1)\oplus g(1)=0$ , the losing positions for the first player are the ones with two sequences of $1$ head. There are ${}^6C_2 = 15$ such positions.

• If there are $4$ tails we could have one sequence of $3$ heads, a sequence of $2$ heads and a sequence of $1$ head, or else three sequences of $1$ head. Since $g(3)=3$ , $g(2)\oplus g(1) = 3$ and $g(1)\oplus g(1) \oplus g(1) = 1$ , these are all winning positions for the first player, and so we get no more losing positions.

• If there are $3$ tails then since $g(4) = 1$ , $g(3)\oplus g(1) = 2$ , $g(2)\oplus g(2) = 0$ , $g(2) \oplus g(1) \oplus g(1) = 2$ and $g(1)\oplus g(1) \oplus g(1) \oplus g(1) = 0$ , the losing positions for the first player are the ones where there are two sequences of $2$ heads, or where there are four sequence of $1$ head each. There are ${}^4C_2 = 6$ for the first type, and $1$ of the second type. This adds another $7$ to our tally.

• If there are two tails, then since $g(5)=4$ , $g(4)\oplus g(1)=0$ , $g(3)\oplus g(2) = 1$ , $g(3)\oplus g(1) \oplus g(1) = 3$ , $g(2)\oplus g(2) \oplus g(1) = 1$ , the only losing positions for the first player are when there is one sequence with $4$ heads and one sequence with $1$ head. There are $6$ such boards.

• If there is just one tail, then since $g(6)=3$ , $g(1)\oplus g(5) = 5$ , $g(2) \oplus g(4) = 3$ , $g(3) \oplus g(3)=0$ , the only losing positions for the first player are those where there are two sequences of $3$ heads. There is just one such board.

• If there are no tails then, since $g(7)=2$ , this is a winning position for the first player.

Thus there are $1+15+7+6+1 = 30$ losing boards for the first player, and hence $98$ winning boards.

In any particular arrangement, suppose we remove some tails between two heads maintaining the following restrictions:
i) If there were a positive number of tails between two heads, after the transformation, there exists exactly $1$ tail between two heads.
ii) If there were no tails between two heads, after the transformation, there are still no tails between two heads.

Then, note that the state (winning or losing) of the transformed arrangement must be identical to the state of the original arrangement: it is obvious that the number of tails between two heads doesn't matter. All what matters is whether two heads are consecutive or not. Also, note that the number of coins of the transformed arrangement must be $\leq$ the number of coins in the original arrangement.

We call this transformation the reduced arrangement of the original arrangement. Note that the ends of the reduced arrangement of any arrangement must be heads.

Next, suppose in some arrangement we consider each block of few consecutive heads as a single block, and we permute these single blocks in such a way that no two blocks appear consecutive. We call two such arrangements friends of each other. As an explicit example, the arrangements $HHTH$ and $HTHH$ are friends of each other. Note that the states of two friends must be identical: we can consider the game as a combination of those blocks, the order obviously doesn't matter.

Now, note that to the end of any reduced arrangement if we append a $H$ , the resultant arrangement will be winning iff atleast one of the following conditions are satisfied:
i) The original reduced arrangement is losing.
ii)) If we remove the last head from the original arrangement, the resultant is a losing arrangement.
Also note that to the end of any winning arrangement if we append a $TH$ , the resultant arrangement in losing, and to the end of any losing arrangement if we append a $TH$ , the resultant will be winning.

The proof of the sufficient condition is trivial: if either one of the conditions hold, the first player has a move which pushes the second player to a losing position. If none of the conditions hold, the first player has no move that pushes the second player to a losing position, so he makes a move within the original arrangement, which is winning. The second player then flips the last head, and now the first player is in a losing position. This establishes our claim. The same proof holds for the latter claim.

Note that $H$ and $HH$ are both winning positions, whereas $HTH$ is a losing position. Starting from these three positions, we keep on appending $H$ s keeping in mind our above algorithm. This generates the following losing reduced arrangements (note: in the following list we ignore two arrangements which are friends of each other, and the sum of the number of $H$ s and $T$ s is at most $7$ ).
$HTH, HHH, HHHHTH, HTHTHTH$ $HTHTHHH, HHHHHH, HHHHHTH$ $HHHTHHH$

Note that if any reduced arrangement has $f$ friends and can be arranged in $t$ ways in a $7$ coin game, then that reduced arrangement will actually contribute $tf$ losing arrangements. We compute $t$ and $f$ individually for each reduced arrangement. I am not showing it for each of the arrangements individually, but I am just giving a sketch. Take the arrangement $HHHHHTH$ . To find its number of friends, consider the block $HHHHH$ as a single block $X$ , and the block $H$ as another block $Y$ . This has two permutations (note: $XY$ cannot be consecutive): $XTY$ and $YTX$ , so this reduced arrangement has two friends. To find the number of possibilities each friend of this reduced arrangement has, say there are $a+1$ $T$ s in place of the $T$ , $b$ $T$ s before the first $H$ , and $c$ $T$ s after the last *H), where $a,b,c$ are non-negative integers. The equation is then $a+b+c+1= 1 \implies a+b+c= 0$ . We can find its number of solutions by the ball and bars method. Below we tabulate the analysis of each the reduced arrangements.

$\text{Arrangement} \ \ \text{\#Friends} \ \ \text{\#Total arrangements for each friend}$ $HTH \ | \ 1 | \ | \ {6 \choose 4} = 15$ $HHH \ | \ 1 \ | \ {5 \choose 4}= 5$ $HTHTHTH \ | \ 1 | \ | \ {3 \choose 3} = 1$ $HTHHTHH \ | \ 2 | \ | \ 1$ $HHHHTH \ | \ 2 \ | \ 3$ $HHHHHHH \ | \ 2 \ | 1$ $HHHHHTH \ | 2 \ | 1$ $HHHTHHH \ | 1 \ | 1$ Adding these, we get $30$ losing positions, so the number of winning positions is $128-30= \boxed{98}$ .