# Communicate square on a 3-by-3 grid by flipping precisely one of 13 coins

A coin is placed on each of the $$13$$ squares in the following diagram:

Each coin may be showing heads or tails arbitrarily. An adversary points to a square in the $$3\times 3$$ grid. You must communicate this position to your ally, by flipping precisely $$1$$ coin.

Standard Devil's Chessboard rules apply:

1. The arrow is there to unambiguously label all the squares.
2. Every coin has a head on one side and a tail on the other.
3. You must flip a coin.
4. You and your ally are shown the diagram and have the problem explained to you in advance. You may then agree a strategy beforehand. The only things you do not know in advance are which coins are showing heads and which are showing tails, and the square which needs to be communicated.
5. Your ally has to deduce the position of the square, only from looking at the diagram with its configuration of coins showing heads and tails, after you made your flip.

No knowledge of the original Devil's Chessboard problem or solution is required.

Motivation The solution to the original Devil's Chessboard problem allows you to communicate a number between $$1$$ and $$n$$ with $$m$$ coins whenever $$n\leq 2^k\leq m$$, for an integer $$k$$. It is also well known that there is no solution when $$n=m$$ unless $$n=2^k$$. This frequently leads people to conjecture that there is only a solution if $$n\leq 2^k\leq m$$. This elementary puzzle disproves that conjecture, as there are no powers of $$2$$ between $$9$$ and $$13$$.

• I'm attempting to solve this with the original solution (dividing into overlapping groups) and have so far shown that four groups is insufficient. Unfortunately, the 5-cube is a little too complex for me, so I might just wait until someone comes along with a more elegant solution. Commented May 30 at 0:06
• @Auride Once you have solved or seen the solution to the original problem, it is just too tempting to try to adapt it. I think that is why people (including myself) find/found it so difficult to find a counterexample to the conjecture. 20 years ago all the maths PhD students at UCL spent a week trying to think of a counterexample and could not. I have seen other groups of similarly smart people come up with the same conjecture in online discussions, and fail to find a counterexample too. I only found this one by reading a research paper on the topic. Once I understood the theory ...
– tkf
Commented May 30 at 0:38
• .... I realised that if you phrase it this way, there is an elementary solution that requires no knowledge of the original problem, or any of the related theory (in fact not knowing is probably an advantage).
– tkf
Commented May 30 at 0:41
• I have a pretty clean solution if there are 5 squares outside the 3x3 grid, or if there are 4 coins outside the 3x3 grid and flipping a coin is optional. Still working on a solution to the original problem. Commented May 30 at 19:17
• @isaacg Brilliant - I would love to see your solution. Given the context, I think anything less than 7 extra coins deserves to be posted as an answer and upvoted (but not technically accepted).
– tkf
Commented May 30 at 19:37

We have 13 coin positions, which I'm going to give the following names (it doesn't matter which position is given which name, it can be selected arbitrarily as long as I and my ally agree on the assignment, so just pick one that's easy to remember):

1. N
2. S
3. E
4. W
5. NE
6. SW
7. NW
8. SE
9. N/S reverse (controls coins 1/2)
10. E/W reverse (controls coins 3/4)
11. NE/SW reverse (controls coins 5/6)
12. NW/SE reverse (controls coins 7/8)
13. spare coin

(tkf drew a picture of an example arrangement in this image.)

In order to identify a grid square, my ally starts in the centre, then moves in all the compass directions corresponding to coins 1-8 that are heads, wrapping around from one side of the board to the other if necessary (e.g. if moving north-west from the central north square, they arrive at the south-west corner). However, if any of the "reverse" coins are heads, any movement performed by the controlled coin is done backwards (e.g. if coin 11 is heads, then coin 5 actually moves south-west and coin 6 moves north-east rather than the other way round). My ally doesn't look at the position of the spare coin at all when identifying the square.

It turns out that no matter how the coins are arranged, there's always a coin I can flip to get my ally to select any of the nine squares. Here's how I do it:

• First, I work out what position my ally would select if I didn't flip any coins. If that's the square I need to communicate, I flip the spare coin and I'm done.
• Otherwise, I look at the square I need to communicate and the square my ally would select without flips. They must be in the same column, or row, or (possibly wrapping around the board) diagonal, because that's true of any two different squares on a 3×3 grid. This solution always flips one of the three coins that controls movement along the row, column, or diagonal in question (e.g. if the two squares in question are on the same NW-SE diagonal, I am going to flip coin 7, 8, or 12).
• If the relevant coins in the 1-8 range are both showing the same side (both heads or both tails), then flipping one of them will move my ally one direction along the relevant line, and the other will move my ally in the other direction. As such, flipping the appropriate one of those two coins will cause my ally to select the desired square.
• If the relevant coins are showing different sides, then flipping either of them will cause my ally to do the same thing (e.g. moving one more square north has the same effect as moving one less square south). If that happens to go to the desired square, I can flip either of those coins and my ally will end up in the right place.
• In the remaining case, I can flip the appropriate reverse-control coin. That causes the coin that was showing heads to start doing the same thing as the coin showing tails previously would have done, and vice versa – and thus it has the same effect as flipping both of the coins would. Flipping either of the coins would have moved my ally one square in the wrong direction; as such, effectively flipping both moves my ally two squares in the wrong direction, and (because we are wrapping around the grid) this has the same effect as moving one square in the correct direction.

As such, in every situation, there's at least one coin I can flip in order to get my ally to select the desired square.

• Perfect solution. Another way of describing the same algorithm: Instead of following the direction coin whenever they show heads, follow the direction coin whenever it shows different to its control coin. Then you do not need to bring in reversing.
– tkf
Commented May 31 at 21:44
• I added a picture to illustrate your points 1-13 (subject to approval). Feel free to get rid if you do not like it.
– tkf
Commented May 31 at 21:51