Board Of Hamming

OK, I think the checkboard puzzle has been up for long enough now. Time for the solution.

Mark managed to find the solution much faster than I did, but thats because I managed to confuse myself for quite sometime with Hamming codes, because I have gotten far too used to that stuff doing these other puzzles. To construct the solution, let us assume that the geometry of the board will play no part, and that there simply are N squares that have stones (or not) on them. Alice must remove or add a stone to be able to communicate a single square to Bob. A solution seems possible at least, since Alice has N possible moves and must communicate one of N possible choices, so there is theoretically enough room, but there can be no room wasted from any position.

First let us try to solve the N=2 case. The board configuration is represented by an element of {00,01,10,11}, where "1" means that square has a stone and "0" means it does not. Bob must have a function that maps from that set to {A,B} where "A" is the square on the right and "B" is the square on the left. From any given configuration, Alice must perform exactly 1 bitflip and specify "A" or "B" to Bob. Alice needing this ability puts restrictions on Bobs possible functions.

A function that works for Bob is f(00)=f(10)=A, f(01)=f(11)=B. The first bit is ignored and the second bit specifies which square is being pointed at. Alice simply looks at the board, if it already pointing at the correct answer, flip the first bit, if instead it is pointing at the incorrect answer, flip the second bit. This will always give Alice a move to make. Note that Alice needed to reserve a move as the "nothing move" just in case The Adversary chose a position that she didn't want to move from.

Let us try the N=3 case. Now we need a function from {000,001,010,011,100,101,110,111} on to {A,B,C}. Let us assume that The Adversary has set up the board in position 000 and has pointed at one of the squares A,B, or C. Alice must change the board to one of {001, 010, 100}, so without loss of generality, we might as well assume f(001)=A, f(010)=B, and f(100)=C. Next, assume The Adversary has set up 110, meaning Alice must choose from {010,100,111}, since f(010)=B and f(100)=A we must have f(111)=C or The Adversary will defeat us. Next, assume The Adversary has set up 011, so Alice must choose from {111,001,010} since f(111)=C, f(001)=C, and f(010)=B, The Adversary can select square A in this case. This proves there cannot exist a function that solves the puzzle on a board with 3 squares.

The failure in the N=3 case is not surprising if you realize that f has to map from a set with 8 elements on to a set with 3 elements, and this cannot be done symmetrically to the set with 3 elements (3 does not divide 8, that is). In general, we will have to find a function from a set with 2^N elements to a set with N elements, so this will only divide evenly if N is a power of 2. For the full problem N=64, so there is still hope.

You can try out the N=4 case next if you like, just by explicitly constructing the function, it all works out if you do it right, but its not especially illuminating as it is difficult to see how to generalize it just from one particular function (at least it was difficult for me).

For general N, one can get a hint of the solution by remembering that from any position there must be a "dummy move", that is, suppose you have a strategy f (mapping from board positions to special squares). If the adversary set up a position x that has the feature f(x) is already the special square, Alice must be able to make a "nothing move", a move that does not change the value of f. Let us assume that there is one square on the board that f is not sensitive to, so Alice can always just toggle that one if she needs. Then there really are only N-1 squares on the board that f looks at, and Alice has the choice of if she wants to toggle one of the N-1 squares or not. The adversary still has N choices of special squares though. We suspect that N should be a power of 2 for a solution to exist, so N-1 is 1 less than a power of two, of course. This immediately made me think of Hamming codes, as those only exist of length M when M is 1 less than a power of 2.

Let us go over what Hamming codes are again. Consider the set of all binary strings of length M (call this set S). We want to construct a set H that is a subset of S with the following feature. For every element x in S there exists an element y in H such that y is no more than 1 bitflip away from x. In the Sam and Ray problem, this was used so that Sam could specify a member of S accurate to 1 bitflip by only specifying a member of H (and it took fewer bits of data to specify an element of H than to specify an element of S).

For our game, let us try the following strategy for Bob. Bob will look at the N-1 squares on the board (ignoring the agreed-upon "dummy square"), this specifies a binary string of length N-1, which will either be a hamming code exactly or be 1 bitflip away from one. If it is 1 bitflip away from one, then the location of that bit that needs to be flipped is the special square. If it is 0 bitflips away from a Hamming code, then the dummy square is the special square.

Can Alice always manage to communicate any square to Bob? If The Adversary sets up a Hamming code exactly, then it is trivial, Alice simply flips the bit on the special square. If The Adversary chooses the dummy square as the special square, the Alice can always do 1 bitflip to put the board into a Hamming code position (unless it is already in one, in which case she just flips the dummy square). The remaining cases (which are, admittedly, the majority of the cases) still need to be checked. First let us reexamine how the Hamming codes actually look.

Consider the set S, binary strings of length M, where M is one less than a power of two, so M+1=2^K. Number the bits 1 through M, and divide them into "parity bits" and "data bits" as follows: a parity bit is one whose number is a power of 2, all others are data bits. We can see that there are K parity bits and M-K data bits. We will construct the set of Hamming codes, H, by letting the data bits run over all possible values, and the parity bits will check the parities of the data bits. The parity bits are labeled with the powers of two, so they are bits 1,2,4,8,16,... The parity bit labeled 1 will check the parities of data bits 3,5,7,9,... (all the numbers with a 1 in the ones place of their binary expansion). The parity bit labeled 2 will check the parities of data bits 3,6,7,10,11... (all the numbers with a 1 in the twos place of their binary expansion). The parity bit labeled 4 will check the parities of data bits 5,6,7,12,13,14,15... (all the numbers with a 1 in the fours place of their binary expansion). The check the parities of a bunch of bits means to XOR them together.

To reuse a section of an earlier post, with some slightly changed notation..."for the case M=7, the set H looks like

0000000
1101001
0101010
1000011
1001100
0100101
1100110
0001111
1110000
0011001
1011010
0110011
0111100
1010101
0010110
1111111

Note that bits 3,5,6,7 run over all possible values. Bit 1 checks the parity of bits 3,5,7. Bit 2 checks the parity of bits 3,6,7. Bit 4 checks the parity of bits 5,6,7.

Further note that every bit is being checked by a unique combination of at least two parity bits. Bit 5 is being checked by 4 and 1 (because 5 in binary is represented as 4+1) and only bit 5 is being checked by bits 4 and 1 alone. This idea will hold in general."

"if we are given a binary string of length M, we can find an element of H that is different in no more than 1 spot through the following method: Find the element of H with the same data bits, it will differ in one or more parity bits. If it differs in one parity bit, we are done. If it differs in more than one parity bit, add of the values of those parity bits to find a value j. You will find that if you flip data bit j, all of the parity bits will now be correct and you will have exactly an element of H. Thus you either differ in only one parity bit, or the incorrect parity bits specify what data bit is off from an element of H."

Anyway, you can try this explicitly in the case N=4 and you will find it works out, great, Alice always has a bit she can flip to inform Bob of the special square, how do we prove it works in general? Well, first we need to look at the Hamming codes a bit differently.

Consider a typical Hamming string, like 0110011, this has ones at 2, 3, 6, and 7. the data bits {3,6,7} look like {011,110,111} in binary, their 1's place XORs to 0, their 2's place XORs to 1 and their 4s place XORs to 0, or more simply, they together XOR to 010. Actually, the full thing {2,3,6,7} is {010,011,110,111}, which XORs to 000. In general an element of H will do that, so that whole construction was a bit over the top.

Suppose you are given an element of S, to find the corresponding element of H you just XOR the values of all the 1's together, and flip that bit. For example 1101110 is {1,2,4,5,6} is {001,010,100,101,110} XORs to 100, thus you must flip bit 4 to get a hamming code, we can see that 1100110 does XOR to zero, it is a hamming code.

This gives us a more succinct strategy for Alice and Bob (and a proof that it works). Alice and Bob number the squares 0 through N-1 (0 will serve the job of the "dummy square"). Alice then looks at the squares where The Adversary places stones and XORs them together, getting a number y. She then XORs the value of the special square with y, and performs her bitflip on the result. Now the values of the squares with stones on them will XOR together to the special square, this works just by symmetry of XOR (that is, if A XOR B = C then A XOR C = B, even if A,B,C are binary strings). It is easy to see that the solution only works if N is one less than a power of two, suppose N was 45 or something. Then when Alice XORs everything together, she might get a result of 59 (or any number as high as 63 is possible) and she cannot flip that bit, it does not exist.

This more succinct wording of the strategy is actually the strategy that Mark found initially. I found it rather amusing that we both found the same solution, but had each had a rather different formulation of that solution.