Kelly Coin and Matrices

Let's play a game. The game consists of a row of 17+7 coins that all start face-up. Each turn involves flipping between one and seven coins so that the leftmost coin goes from heads to tail. You lose if there are no legal moves. Find the winning strategy.

Let ``1" denote a heads and ``0" denote tails. Playing the games a few times for experimentation, it is not hard to see that if a player is handed the game 11111111, a game with only 8 heads at the very end of the string, then they will lose. On their move, there will be at most 7 heads which can be flipped over on the next turn by their opponent, and since there are 8 heads, the player cannot flip all of them to tails. Thus, we want to give this case to our opponent at the end of the game. From here, we want to build up a strategy that allows us to convert any move our opponent makes into a winning position. Observing the number of coins each person can flip, between 1 and 7 inclusive, we see that no player can make 8 moves on their turn, but we can make exactly 8 moves on every other turn. Thus, we will be looking for an 8-move sequence that leads to the losing code.

We know from Daniel's realization that a code of length 23 with exactly three errors in each code gives us perfectly packed hogging spheres, however, this only gives us a distance of 7 between the two closest codes. Adding another digit, so that we now have 24 bits, allows for the desired distance of 8 between the two closest codes. We will construct the encoding matrix in the next part of this problem (technically, the next problem), but for now let's assume we have it. The first player begins on a codeword, and after making a move, cannot stay on the same codeword since they must change at least 1 digit, and they also cannot reach the next codeword, since that would require changing 8-bits. Thus, when player two receives the game, they will be between 1 and 7 moves away from the next codeword, and they can once again make the game a codeword.

Icosahedron Vertex Neighboring Matrix

Now, we need to find some encoding matrix that has a difference of exactly 8 between the two closest codewords. We know how to construct a 23 bit codeword that is error correcting for up to 3 errors, but it is not immediately clear how to construct the encoding such that they have 24 bits, and a distance of 8. We'll take the hint from problem 9 and construct the adjacency matrix for an icosahedron, which has 12 vertices, we get the following. \\

$$ \begin{bmatrix} 0&1&1&1&1&1&0&0&0&0&0&0\\ 1&0&1&0&0&1&1&0&0&0&1&0\\ 1&1&0&1&0&0&1&1&0&0&0&0\\ 1&0&1&0&1&0&0&1&1&0&0&0\\ 1&0&0&1&0&1&0&0&1&1&0&0\\ 1&1&0&0&1&0&0&0&0&1&1&0\\ 0&1&1&0&0&0&0&1&0&0&1&1\\ 0&0&1&1&0&0&1&0&1&0&0&1\\ 0&0&0&1&1&0&0&1&0&1&0&1\\ 0&0&0&0&1&1&0&0&1&0&1&1\\ 0&1&0&0&0&1&1&0&0&1&0&1\\ 0&0&0&0&0&0&1&1&1&1&1&0 \end{bmatrix} $$ Now, putting a 12 by 12 identity matrix next to the conjugate of the adjacency matrix, we get an encoding matrix which has the desired properties. $$ \begin{bmatrix} 1&0&0&0&0&0&0&0&0&0&0&0& 1&0&0&0&0&0&1&1&1&1&1&1\\ 0&1&0&0&0&0&0&0&0&0&0&0& 0&1&0&1&1&0&0&1&1&1&0&1\\ 0&0&1&0&0&0&0&0&0&0&0&0& 0&0&1&0&1&1&0&0&1&1&1&1\\ 0&0&0&1&0&0&0&0&0&0&0&0& 0&1&0&1&0&1&1&0&0&1&1&1\\ 0&0&0&0&1&0&0&0&0&0&0&0& 0&1&1&0&1&0&1&1&0&0&1&1\\ 0&0&0&0&0&1&0&0&0&0&0&0& 0&0&1&1&0&1&1&1&1&0&0&1\\ 0&0&0&0&0&0&1&0&0&0&0&0& 1&0&0&1&1&1&1&0&1&1&0&0\\ 0&0&0&0&0&0&0&1&0&0&0&0& 1&1&0&0&1&1&0&1&0&1&1&0\\ 0&0&0&0&0&0&0&0&1&0&0&0& 1&1&1&0&0&1&1&0&1&0&1&0\\ 0&0&0&0&0&0&0&0&0&1&0&0& 1&1&1&1&0&0&1&1&0&1&0&0\\ 0&0&0&0&0&0&0&0&0&0&1&0& 1&0&1&1&1&0&0&1&1&0&1&0\\ 0&0&0&0&0&0&0&0&0&0&0&1& 1&1&1&1&1&1&0&0&0&0&0&1 \end{bmatrix} $$ Let us now show that the code generated by this encoding matrix has the desired properties. We see that changing any bit in this our original 12-bit message changes exactly 8 bits in the encoded message. This means that, although they have the property that the two closest codes are more than 2(3)+1 apart, they are not error-correcting for more than 3 corrupted bits. However, since the distance is 8, errors in codes that are 4 away from the closest codewords cannot be corrected because they belong to the Hogging spheres of both adjacent codewords. This encoding allows us to finish the problem.

Recall that we defined the sequence of the 0's and 1's to correspond to a sequence of tails and heads. We begin the game with the sequence of twenty-four 1's, and end the game with a sequence of twenty-four 0's. Thus, if the both sequences are codewords, then player 2 always wins. Each code consists of the 12 message bits and 12 parity bits, which each correspond to the parity of 7 message bits. However, we also need to show that player 1 can reach the next codeword by flipping the first 1, as stated in the rules of the game.

We see that the first 12 digits of the code are the message bits, and the next 12 are the parity bits. Player 1 is forced to flip the leftmost 1 to a 0, which causes an error in exactly 7 of the parity bits.

Thus, both sequences are codewords and we can conclude that player 2 always wins.