6
$\begingroup$

This question already has an answer here:

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

The jailer will take you into a private cell. In the cell will be a chessboard and a jar containing 64 coins. The jailer will take the coins, one-by-one, and place a coin on each square on the board. He will place the coins randomly on the board. Some coins will be heads, and some tails (or maybe they will be all heads, or all tails; you have no idea. It's all at the jailers whim. He may elect to look and choose to make a pattern himself, he may toss them placing them the way they land, he might look at them as he places them, he might not …). If you attempt to interfere with the placing of the coins, it is instant death for you. If you attempt to coerce, suggest, or persuade the jailer in any way, instant death. All you can do it watch. Once all the coins have been laid out, the jailer will point to one of the squares on the board and say: “This one!” He is indicating the magic square. This square is the key to your freedom. The jailer will then allow you to turn over one coin on the board. Just one. A single coin, but it can be any coin, you have full choice. If the coin you select is a head, it will flip to a tail. If it is a tail it will flip to a head. This is the only change you are allowed to make to the jailers initial layout. You will then be lead out of the room. If you attempt to leave other messages behind, or clues for your friend … yes, you guessed it, instant death! The jailer will then bring your friend into the room. Your friend will look at the board (no touching allowed), then examine the board of coins and decide which location he thinks is the magic square. He gets one chance only (no feedback). Based on the configuration of the coins he will point to one square and say: “This one!” If he guesses correctly, you are both pardoned, and instantly set free. If he guesses incorrectly, you are both executed. The jailer explains all these rules, to both you and your friend, beforehand and then gives you time to confer with each other to devise a strategy for which coin to flip.

What strategy would you use to escape?

$\endgroup$

marked as duplicate by Glorfindel, Omega Krypton, hexomino, rhsquared, Rand al'Thor Feb 24 at 9:55

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ 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. $\endgroup$ – Rubio Aug 7 '17 at 18:40
  • $\begingroup$ I thought n would be finite for m=1. And so incrementing the number of flips increases the scope. $\endgroup$ – Nikhil Bhavar Aug 7 '17 at 18:52
  • $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it :) $\endgroup$ – Rubio Aug 14 '17 at 8:18
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

This is answered here

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 };
    int xor = heads[0];
    for(int i = 1; i < heads.Count; i++)
    {
        xor = heads[i] ^ xor;
    }
    Debug.WriteLine(xor);
    int target = 16;
    int j;
    for (j = 0; j < 64; j++)
    {
        if(target == (xor ^ j))
            break;
    }
    heads.Add(j);
    xor = heads[0];
    for (int i = 1; i < heads.Count; i++)
    {
        xor = heads[i] ^ xor;
    }
    Debug.WriteLine(xor);
}
$\endgroup$
  • $\begingroup$ But how does your friend know you used this math to get there ? :D $\endgroup$ – Overmind Aug 14 '17 at 9:01
  • $\begingroup$ your friend knows by pre-arrangement $\endgroup$ – Jasen Dec 19 '17 at 2:20
3
$\begingroup$

Updated answer

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<j<2^k$.

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ffao Aug 7 '17 at 22:37
  • $\begingroup$ @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. $\endgroup$ – Apep Aug 7 '17 at 23:34
  • $\begingroup$ 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!) $\endgroup$ – ffao Aug 7 '17 at 23:52
  • $\begingroup$ @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. $\endgroup$ – Apep Aug 8 '17 at 0:47
  • $\begingroup$ 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). $\endgroup$ – ffao Aug 8 '17 at 1:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.