There are three people, A, B and C, a 8x8 board with cells labelled 1 to 64, and 64 coins. A and C first goes into a room out of B’s sight. A places a coin on each of the 64 cells on the board. C can flip any number of coins as she pleases and when she is done, she points to one cell on the board. A then flips exactly one coin and C then takes the board out of the room and show it to B. B takes a look at the board, and points to a cell which C originally pointed out in A’s presence. The puzzle is to figure out how that is done.
Source: http://ioi2017.org/tasks/practice/coins.pdf.
The practice question had other sub parts, presumably to be completed before this part and should hint to the solution.
The subparts are:
- C will only choose from the first two cells, A flips exactly 1 coin.
- C will only choose from the first three cells, A flips exactly 1 coin.
- C chooses any cells, and A flips at most 8 coins.
If you want to think about it, you should stop reading here and come back when you have a solution or when you have given up.
Failed attempt No. 1
My first thought was to try to prove it was even possible, and hope that it will trigger a way to solve it.
Effectively, A is trying to encoded the numbers 1-64 in a 8x8 grid of coins. The grid has 2^64 possible states. Suppose A and B agrees on a mapping from each of these state to a number from 1-64, then if A can encoded the coin C chosen in the state that B sees, then the problem is solved.
This reminds me of hypercubes. If each state was a vertex of the hypercube, an edge would represent a transition by flipping exactly one coin. So the problem can be solved if there was a way to colour the vertices such that from any vertex, it is possible to transition into a vertex of a given colour.
2 cells, 1 flip
1 - 1
| |
2 - 2
For 2 cells, there are 4 states, the numbers denote the colour of the vertex. C can choose a starting state, and can point to cell 1 or 2. Regardless of which state C chooses, A can transition into the state that is coloured 1 or 2, effectively conveying that information to B.
3 cells, 1 flip
Doing the same exercise for 2^3 = 8 states (in a 3D cube) reveals that it is not possible to colour it in a way that it is possible to get to all other colours. This is also alluded by the fact that 8 does not divide evenly into the 3 colours. However, because we can flip a coin outside the 3 cells, we can effectively perform a no-op. So if the starting state is already the correct colour, A just needs to flip an unrelated coin to stay in that state.
All cells, 1 flip
From the previous sub problem, we guessed that if the colours doesn’t divide evenly into the possible states, we might not get a solution. So the next smallest case to get our hands dirty with is 4 cells, 2^16 states. This can be represented in a 4D hypercube:
1 + + + + + + + + + + + 1 3 + + + + + + + + + + + 3
+\ +\ +\ +\
| \ | \ | \ | \
| \ | \ | \ | \
| \ | \ | \ | \
| 4 + + + + + + + + +-+ + 4 | 2 + + + + + + + + +-+ + 2
| + | + | + | +
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
+ | + | + | + |
2 + +-+ + + + + + + + + 2 | 4 + +-+ + + + + + + + + 4 |
\ | \ | \ | \ |
\ | \ | \ | \ |
\ | \ | \ | \ |
\+ \+ \+ \+
3 + + + + + + + + + + + 3 1 + + + + + + + + + + + 1
There seems to be a pattern happening here, the cubes can be coloured via grey’s encoding. At this point, I was rather confident it can be extended to 2^64 states. However, since this was a coding task, the question was how to encode this mapping into code.
I thought for a while and concluded that there’s no way IOI contestents are asked to come up with such a complex mapping. There has to be a simpler way.
Failed attempt No. 2
Since I skipped sub problem 3, I thought maybe that holds the crux. In sub problem 1 and 2, we manage to transfer 2 and 3 bits of information with 1 flip. We want to transmit 6 bits of information (to encode a number from 1-64) with at most 8 flips. This seems easy, we use the top 2x6 array to transmit 6 bits using the technique in subproblem 1. That is, for each 2x1 array, if the first coin is chosen, it represents 0, otherwise it represents 1.
This solves the third sub problem. However, I couldn’t see how this could help solve the original problem.
I gave up
After thinking about this for a few days, I finally gave up and searched for the solution. I found a post on quora describing this problem, giving it the name “Devil’s chessboard”.
It turns out I was indeed overthinking it. Each cell represents the number 0 - 63, whatever state C sets the board 2, there is a XOR sum, A just needs to flip the cell that when XORed with the current sum, will prodice the number pointing to the cell chosen.