|
Posted by: stak
Tags:
Posted on: 2020-03-17 20:45:35
In a a previous post I described a puzzle. A couple of people I've talked to since have mentioned that they thought about it but couldn't figure out the answer, so here it is. (If you don't want spoilers, stop reading now!)
The "magic square" chosen by the Devil is one of 64 possibilities. Or, in information theory terms, it's 6 bits of information (since each bit encodes one of two possibilities, and 2^6 is 64). So we need to somehow convey 6 bits of information to our friend, yet do so by flipping at most one token on the board.
The way to do this is to define 6 "parity sets" such that each parity set gives you 1 bit of information, and overlap them such that with a single token flip you can control the bit produced by each parity set. A parity set is simply an area of the board where you count up the number of "up" tokens. The parity (even or odd) of that number produces the bit of information.
So for example, consider a parity set that is the top half of the board (the first four rows). If there are an odd number of "up" tokens in that half of the board, the bit produced by that parity set is a 1. If there are an even number, the bit produced is a 0. By flipping any token in the top half of the board, you can change the bit produced from 1 to a 0 or vice-versa. And now consider a second parity set that is the left half of the board (the first four columns). Likewise that parity set produces a 1 or a 0. Importantly, if you flip a token in the top-left quarter of the board, you will change the bits produced by both parity sets. If you flip a token in the top-right quarter of the board, you will change the bit of only the first parity set and not the second. Flipping a bit in the bottom-left quarter will change the bit of only the second parity set and not the first.
We can extend this concept to create the following six parity sets:
- rows 1,2,3,4
- rows 1,2,5,6
- rows 1,3,5,7
- columns 1,2,3,4
- columns 1,2,5,6
- columns 1,3,5,7
Flipping the token in row 1, column 1 will change the parity of all six sets, while (for example) changing the token in row 5, column 6 will change the parity of sets 2, 3, and 5.
So the complete solution is like so: with your friend beforehand, you decide on the 6 parity sets (the above is one possibility) and their interpretation. One interpretation is that you take a 1 for an odd number of "up" tokens in the set, or a 0 for an even number, and glue together those six bits into a 6-bit number (e.g. 011001). That number then encodes the position of the "magic square", as it can represent 64 different values. Then, when you are in the room with the Devil, and he selects the "magic square", you work backwards to figure out the 6-bit number you want to encode, and flip the appropriate token so that the six parity sets produce the bits you need. Ta-da!
|