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

Question

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$.

Answer 1

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.