# Flip one of the 64 coins on chess board [duplicate]

I know the answer of this puzzle. I want to know does this puzzle works perfectly for every n × n chess board? Is there a upper bound to n? What is the upper bound for n, if m coins are allowed to flip?

Puzzle:

You and your friend are imprisoned. Your jailer offers a challenge. If you complete the challenge you are both free to go. The rules are

What strategy would you use to escape?

• For $m=1$ your question is a duplicate of The coolest checkerboard magic trick; an answer to that question shows how it generalizes to any $2^k \times 2^k$ board. I don't think an $n \times n$ board works for $n$ not a power of two. It's not clear what you mean by $m$ flips - do you mean the "you" of the puzzle is allowed to choose $m$, rather than 1, coin to flip? $m>1$ seems unnecessary as $m=1$ suffices, and I doubt that more flips make non-power-of-2 boards possible, as the solution depends on binary decomposition of the board.
– Rubio
Commented Aug 7, 2017 at 18:40
• I thought n would be finite for m=1. And so incrementing the number of flips increases the scope. Commented Aug 7, 2017 at 18:52

Okay, I'll just give a quick outline for a proof of why 1 flip is not always sufficient. This is just an outline for the 10x10 board case, with 1 flip. (Yes, I did copy it from here)

Consider a graph with $2^{100}$ nodes (these are the possible states of the board). Draw an edge between two nodes if it possible to get from one to the other by flipping a coin (This is a 100-cube, in a way). Now, we want to colour the vertices of this graph in 100 colours such that, given any node, there exists an adjacent node of each colour (that's pretty much the question, where each colour is a square). I'll expand on this in the note below. So for any colour $i$, there exist $2^{100}$ ordered (node, node) pairs where the first node has colour $i$. But, there exists a colour such that there are strictly less than $2^{100}/100$ nodes of that colour (since 100 is not a factor of $2^{100}$. Therefore there are strictly less than $2^{100}/100*100=2^{100}$ (node, node) ordered pairs where the first node has that colour, a contradiction.]

Basically a node is coloured colour $i$ if, when your friend sees the board at that node, then they choose the $i$th square on the board. This should clarify things up a bit.

I am proving that boards of size $2^n\times 2^n$ are possible in 1 flip
Example for a 8x8 board:
1. I will decide with my friend that we map the board from top-left to bottom-right from 0 to 63
2. I'll decide with him that we count only Tails (Heads also will work :-) )
3. Now what we'll do is XOR between all the positions of the Tails in binary and get a result
4. Flip the coin that's needed to fix the XoR to the wanted square - your penny

Example: lets say that there are tails only on 3,7,20,61 and the chosen sqare is 8: XoR on them {3,7,20,61} will be: 45. now what number XoR 45 will give us 8? 37!! I'll flip 37 :-)

It should work for any square board that is a power of 2.

in c#

public static void Chess()
{
List<int> heads = new List<int> { 3, 7, 20, 61 };
for(int i = 1; i < heads.Count; i++)
{
}
Debug.WriteLine(xor);
int target = 16;
int j;
for (j = 0; j < 64; j++)
{
if(target == (xor ^ j))
break;
}
for (int i = 1; i < heads.Count; i++)
{
}
Debug.WriteLine(xor);
}

• But how does your friend know you used this math to get there ? :D Commented Aug 14, 2017 at 9:01
• your friend knows by pre-arrangement Commented Dec 19, 2017 at 2:20

Thanks to @ffao's comments and from chat. 4 or more coins can be solved with exactly 2 flips, as long as the coins are ordered.

First, find the largest integer $$k$$ relative to the number of coins, $$c$$, such that $$2^k < c ≤ 2^{k+1}$$. Starting from the first coin, count $$2^k$$ coins, which will be subset A. Starting from the last coin, count $$2^k$$ coins backwards, which will be subset B.

If either of subsets A or B contains the magic square, it can be solved by flipping exactly one coin, as per the original solution.

If the coin exists in subset A:
• If the first coin is tails, flip it. Otherwise, flip any coin in subset B that is not in subset A.
• If the original solution would have you flip the first coin of subset A, flip a second coin in subset B that is not in subset A. Otherwise, solve subset A as per the original solution.

If the coin is in subset B:
• If the first coin of subset A is heads, flip it. Otherwise, flip the second coin in subset A.
• Solve subset B as per the original solution.

The solver will find the magic square by checking if the first coin is heads. If it is, they will check subset A as per the original solution as a $$2^k$$ sized set. If it is not, they will check subset B as per the original solution as a $$2^k$$ sized set.

# Original answer for 4 flips on a square board:

Any sized square non-$$2^k×2^k$$ board can be solve with exactly 4 flips.

This answer relies on the original problem and solution and the fact that the solution can be extended to any $$2^k×2^k$$ board.

Let the board be $$n×n$$ for any $$n=2^k+j$$ for $$0.

Sub-divide the board into four $$2^k×2^k$$ boards starting at squares $$(0,0)$$, $$(0, j)$$, $$(j,0)$$, and $$(j,j)$$. These four sub-boards will be labelled A, B, C, and D, respectively. They will cover the entire board.

Example 7x7 board:

The first individual will choose the first sub-board that the magic square is in, the chosen sub-board. They will use 1 flip to solve the chosen sub-board as per the original solution - except in the case that the solution is to flip the top-left coin of the chosen sub-board and it is already heads.

Next, they will flip the top-left coin of any preceding sub-boards that are currently heads. This uses at most 3 if the chosen sub-board is D and the top-left coins of A, B, and C are heads. If the chosen was not sub-board D, then they will flip the top-left coin of the chosen sub-board if it is tails. This will ensure that the chosen sub-board is the first one whose top-left coin is heads, or sub-board D is the chosen board. The top-left coin of preceding sub-boards are not part part of later sub-boards and changing the top-left coin on the chosen sub-board does not change its solution.

Including the one to solve the board, this is at most 4. The remaining flips can be used on any spaces that are not in the chosen sub-board and are not the top-left corner of other sub-boards.

The second individual will divide the board in the same manner. They will locate the first sub-board such that the top-left corner is heads, or board D if they are all tails. They will then locate the magic space on that sub-board as per the original solution.

• As I pointed out in chat, there's no special significance to the board layout -- you can divide your board in two arbitrary sets of 2^k and this still works in half the flips.
– ffao
Commented Aug 7, 2017 at 22:37
• @ffao Ah, I understand what you meant now. In that case, a 3-coin board should be solvable in 2 flips in the same way.
– Apep
Commented Aug 7, 2017 at 23:34
• Yes, I realized that this also solves the 3-coin case in 2 flips when I saw your answer :) You might want to edit this in, now we only need to show that non-powers of 2 can't be done in one flip (or find a way to do it!)
– ffao
Commented Aug 7, 2017 at 23:52
• @ffao Upon reviewing the 3-coin solution, it's seems to be impossible with 2 distinct forced flips. You have two disjoint sets {TTT, HHT, HTH, THH} and {HHH, TTH, THT, HTT}. Two flips from any of these can result in any other result in the same set, but never one from the other set. Unless you can flip the same coin a second time, it doesn't seem possible.
– Apep
Commented Aug 8, 2017 at 0:47
• Oh yes, it's easy to show that it's impossible if you can't flip the same coin twice, but upon seeing your answer I think it's much more elegant if you can (I see nothing to forbid you from doing so anyway).
– ffao
Commented Aug 8, 2017 at 1:44