[psyang]

Originally Posted by psyang

I haven't heard this problem before, but my initial instinct is it is a parity problem, and probably closely related to hamming codes. I'll try to take some time this weekend to work it out.

Ok, I figured it out, but I had a bit of help. It had been a while since I learned about hamming codes - I just remembered it was a clever way to do parity-based error checking while also being able to identify the location of the error bit.

But reviewing the specifics of how hamming codes work clued me into the solution.

Quick solution + example

Spoiler!

Consider heads as 0s and tails as 1s and the chessboard as a 64 bit long bitstring.

Mentally (not physically) flip the quarter with the token. Using this new bitstring, you can always convert it to a "well prepared bitstring" by flipping one bit. That is the quarter to physically flip.

A well prepared bitstring is one where, if you take all the positions in the bitstring that have a 1, and xor those positions, the result is 0.

As an example, I'll use 16 bits for brevity. Let's say the 16 bits are:

1001001011110100

and the token is under position 5 (using positions 0-based indexing, so position 5 is the 6th bit):

Mentally, I flip 5 to get:
1001011011110100

Now I make it well-prepared. To do this it is easier to think of the bitstring as a 4x4 block:

1001
0110
1111
0100

Now I look at the parity of bits in all the indexes where the 4th (last) bit is 1 (2nd and 4th column). Then do the same for where the 3rd bit is 1 (3rd and 4th column), 2nd bit is 1 (2nd and 4th row), and 1st bit is 1 (3rd and 4th row). I am interested only in the value where the parity is odd.

In the above example the parities are:
4th bit=1: odd
3rd bit=1: even
2nd bit=1: odd
1st bit=1: odd

Since 1st, 2nd, and 4th bit is odd, I have to flip the bit in position 1101 which is position 13. That is the quarter I physically flip.

1001011011110000

The second prisoner comes in and sees:

1001001011110000

which looks like

1001
0010
1111
0000

Now he does the same thing - get the parity of all indexes that have a one, grouping by whether the position's 4th bit is 1, 3rd bit, etc. He gets:

4th bit=1: odd
3rd bit=1: even
2nd bit=1: odd
1st bit=1: even

That converts to the bitstring 0101 which is 5 which is where the token is.

More detail

Spoiler!

Hamming codes are like magic, which is why this problem seems so impossible at the outset.

The core idea of hamming codes is in addition to the bit itself, its position within the string is important information.

The 64 bits have position
0, 1, 2, ..., 62, 63
or in binary
000000, 000001, 000010, ..., 111110, 111111

When you see the chessboard, if you number so that top-left is 0, and bottom right is 63, moving left-to-right only, then the positions where:
-6th bit is 1: every other column (cols 1,3,5).
-5th bit is 1: every other group of two columns (cols 2+3, 6+7).
-4th bit is 1: last four columns (cols 4-7).
-3rd bit is 1: every other row (row 1,3,5).
-2nd bit is 1: every other group of two rows (rows 2+3, 6+7).
-1st bit is 1: last four rows (rows 4-7).

By computing parity of each group, and storing it in positions 1, 2, 4, 8, 16, and 32, you have a block of 64 bits whose parity of all 6 groups will always be even. Another way of putting it is that the xor of all the positions that have a 1 will end up with 0 (if parity is even, # of 1s is even, so xor'ing those 1s will always result in 0).

After doing this, if you flip any bit (quarter), the xor of all the positions that have a 1 will always give the position in the bitstring that was flipped. This is the magic of the hamming code. It not only detects the error, but the location of the error. It does this because, by flipping one quarter, you are changing the parity of one or more of those 6 groups. But since those 6 groups represent the index of the bits' binary positions, the groups you are changing necessarily form the binary representation of the position that you flipped.

Another way to look at it is, if you flip position 38, its binary representation is 100110. That means you have changed the parity for the groups where the 1st, 4th, and 5th bit is 1. So when the second prisoner computes those parities, he will see that groups for bits 1, 4, and 5 are odd, which gives 100110 which gives location 38.

There are some great resources on hamming codes. I was introduced to them a while back from this 2-parter:



It was after the python code example in the second video was shown that everything clicked for me.