An Impossible Sounding Puzzle with an Elegant Solution

[Glenn Rhoads]

Two people are being held prisoner by a king. The king brings the pair into a room and explains that their fate depends on the following task to be given tomorrow. The floor of the room is tiled by 64 identical squares in an 8x8 pattern. The king will place a penny on each square tile. You will not know ahead of time which pennies have heads facing up and which have tails facing up. The king may use any procedure to determine which are heads and which are tails, including flipping some or all of the coins randomly. Tomorrow the king will bring one prisoner into the room. The king will point to some square saying that this is the magic square. The person in the room picks exactly one penny and flips it over (changes heads to tails or tails to heads). The person can pick any penny they like. The person exits the room on the opposite side from which they entered. The second person enters the room and gets to point at any square of their choosing and claim that this is the magic square. If he is right, they both go free, otherwise they will both be executed. The room has been constructed so that the two prisoners cannot communicate in any way during this procedure. But until tomorrow, they are held together in the same jail cell so that they can devise a strategy to maximize their chances of escape.

What strategy maximizes their chance of being set free? As hard as it is to initially believe, the prisoners can always escape! Describe such a strategy.

[Anton Shepelev]

Post by Glenn Rhoads
Two people are being held prisoner by a king. The king
brings the pair into a room and explains that their fate
depends on the following task to be given tomorrow. The
floor of the room is tiled by 64 identical squares in an
8x8 pattern.
[...]

The subject mentions "An Impossible Sounding Puzzle," so
that I thought it contained a puzzle that cannot be
pronounced. This puzzle is, in fact, *very* good, and I
used to act it live on several persons with a smaller board.
A colleage and I were the prisoners that left the dungeons
of several surprised kings.

[Richard Tobin]

A vague hint: to identify one of 64 (2^6) squares you need 6 bits of
information. How could you reliably convey a single bit by turning
over one coin?

-- Richard

[Anton Shepelev]

Post by Richard Tobin
A vague hint: to identify one of 64 (2^6) squares you need
6 bits of information. How could you reliably convey a
single bit by turning over one coin?

Only a single bit? I see it so, that the board encodes a
number in the range 1..64, and the task is to find an
encoding scheme that allows, by flip a coin, encode any
desired number, which the other prisoner should decode.

[Richard Tobin]

Post by Anton Shepelev

Post by Richard Tobin
A vague hint: to identify one of 64 (2^6) squares you need
6 bits of information. How could you reliably convey a
single bit by turning over one coin?

Only a single bit?

It's a hint, not a solution.

-- Richard

[Anton Shepelev]

Post by Richard Tobin
It's a hint, not a solution.

I thought I should abstain from posting my solution, because I had
solved it a long time ago, rather than specially for this newsgroup.
Shall I post it now, that a more beautiful solution has already
been provided?

[Jonathan Dushoff]

Two people are being held prisoner by a king. The king brings the pair into a room and explains that their fate depends on the following task to be given tomorrow. The floor of the room is tiled by 64 identical squares in an 8x8 pattern. The king will place a penny on each square tile. You will not know ahead of time which pennies have heads facing up and which have tails facing up. The king may use any procedure to determine which are heads and which are tails, including flipping some or all of the coins randomly. Tomorrow the king will bring one prisoner into the room. The king will point to some square saying that this is the magic square. The person in the room picks exactly one penny and flips it over (changes heads to tails or tails to heads). The person can pick any penny they like. The person exits the room on the opposite side from which they entered. The second person enters the room and gets to point at any square of their choosing and claim that this is the magic square. If he is right, they both go free, otherwise they will both be executed. The room has been constructed so that the two prisoners cannot communicate in any way during this procedure. But until tomorrow, they are held together in the same jail cell so that they can devise a strategy to maximize their chances of escape.
What strategy maximizes their chance of being set free? As hard as it is to initially believe, the prisoners can always escape! Describe such a strategy.

Spoiler space

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

The second prisoner needs to choose based only on an observed configuration. So we need a map from configurations to magic squares.

We handle rows and columns of the chessboard separately (easier for a human to compute).

Number the rows in binary from 000 to 111. Calculate the parity of each row as 0 if there is an even number of heads (and thus tails) or 1 otherwise.

Calculate a magic row bitwise: the parity of each binary digit of the row is 1 if an odd number of rows where that digit is 1 have parity 1. In other words, take the exclusive-or sum of the product of the row numbers and the row parities. The second prisoner will choose that row.

For any given starting configuration of row parities, the first prisoner can find the one row which switches the bits that we want switched and leaves the bits we want left. So the prisoner can flip any coin in that row to correctly indicate the magic row.

The same logic applies to columns. The first prisoner will then flip the coin at the intersection of the found row and found column to indicate the magic square at the intersection of the magic row and magic column.

[Gabor Szabo]

Thank you for the solution.
How would you do it in real time?

I tested it with my son, we wanted to do it at a birthday party but it seems a very long/hard calculation, especially in the head.

I used to act it live on several persons with a smaller board. A colleage and I were the prisoners that left the dungeons of several surprised kings.

Anton, how long did it take?

Two people are being held prisoner by a king. The king brings the pair into a room and explains that their fate depends on the following task to be given tomorrow. The floor of the room is tiled by 64 identical squares in an 8x8 pattern. The king will place a penny on each square tile. You will not know ahead of time which pennies have heads facing up and which have tails facing up. The king may use any procedure to determine which are heads and which are tails, including flipping some or all of the coins randomly. Tomorrow the king will bring one prisoner into the room. The king will point to some square saying that this is the magic square. The person in the room picks exactly one penny and flips it over (changes heads to tails or tails to heads). The person can pick any penny they like. The person exits the room on the opposite side from which they entered. The second person enters the room and gets to point at any square of their choosing and claim that this is the magic square. If he is right, they both go free, otherwise they will both be executed. The room has been constructed so that the two prisoners cannot communicate in any way during this procedure. But until tomorrow, they are held together in the same jail cell so that they can devise a strategy to maximize their chances of escape.
What strategy maximizes their chance of being set free? As hard as it is to initially believe, the prisoners can always escape! Describe such a strategy.

Spoiler space
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
The second prisoner needs to choose based only on an observed configuration. So we need a map from configurations to magic squares.
We handle rows and columns of the chessboard separately (easier for a human to compute).
Number the rows in binary from 000 to 111. Calculate the parity of each row as 0 if there is an even number of heads (and thus tails) or 1 otherwise.
Calculate a magic row bitwise: the parity of each binary digit of the row is 1 if an odd number of rows where that digit is 1 have parity 1. In other words, take the exclusive-or sum of the product of the row numbers and the row parities. The second prisoner will choose that row.
For any given starting configuration of row parities, the first prisoner can find the one row which switches the bits that we want switched and leaves the bits we want left. So the prisoner can flip any coin in that row to correctly indicate the magic row.
The same logic applies to columns. The first prisoner will then flip the coin at the intersection of the found row and found column to indicate the magic square at the intersection of the magic row and magic column.

[Anton Shepelev]

Post by Gabor Szabo

I used to act it live on several persons with a smaller
board. A colleage and I were the prisoners that left the
dungeons of several surprised kings.

Anton, how long did it take?

I hoped this would not transpire, but we did it with a 2x2
board, which is elementary. With Jonathan's two-dimensional
decomposition, 3x3 seems possible as well, after a little
drilling.

[Gabor Szabo]

I see :) Thanks.

Post by Anton Shepelev

Post by Gabor Szabo

I used to act it live on several persons with a smaller
board. A colleage and I were the prisoners that left the
dungeons of several surprised kings.

Anton, how long did it take?

I hoped this would not transpire, but we did it with a 2x2
board, which is elementary. With Jonathan's two-dimensional
decomposition, 3x3 seems possible as well, after a little
drilling.
--
() ascii ribbon campaign -- against html e-mail
/\ www.asciiribbon.org -- against proprietary attachments

[Mike Terry]

Post by Anton Shepelev

Post by Gabor Szabo

I used to act it live on several persons with a smaller
board. A colleage and I were the prisoners that left the
dungeons of several surprised kings.

Anton, how long did it take?

I hoped this would not transpire, but we did it with a 2x2
board, which is elementary. With Jonathan's two-dimensional
decomposition, 3x3 seems possible as well, after a little
drilling.

You mean 4x4? (The method works for sides 2,4,8, etc..)

To perform the method on a chess board should be possible with practice, but requires holding some
data in memory, like one of those short-term memory tests, so probably easier for the youngsters
among us (that's not me!) :)

How much data do we have to hold in your head? Having worked out the column, we need to remember
that column while we're working out the row - so that's one number 1-8. Also, to then work out the
row, we need to keep in mind a running number 1-8 (or the binary equivalent), and manipulate that
number as we go along. So if you can remember two numbers 1-8 there's a good chance you could make
the method work, with practice. Also you have to be ok with the binary aspect, translating to/from
binary for 3 binary digits (while not forgetting our two numbers). Hmm, that's probably the hardest
bit - while working through the binary you suddenly realised you've forgotten the running total, or
you've forgotten the previously worked out column.

Of course it's much easier if you have paper and pen handy... Or if you were allowed to place
markers next to rows/columns that would help...

Mike

[Anton Shepelev]

Post by Mike Terry

Post by Anton Shepelev
I hoped this would not transpire, but we did it with a
2x2 board, which is elementary. With Jonathan's two-
dimensional decomposition, 3x3 seems possible as well,
after a little drilling.

You mean 4x4? (The method works for sides 2,4,8, etc..)

You are right. It is time I gave my solution, which works
with a linear array of 2^n cells, with C(i) denoting the
cell value -- zero or unity. I index the cells from 0 to
n-1, and consider the resulting bit array as encoding an
integer K:

K = XOR( C(i) * i ), for i = 0 to n-1

where XOR is, well, the bit-wise exclusinve OR operation
upon a binary number. K is of the same size, and takes the
same values, as the array indices. It can be changed to any
other value by iversion of the cell at the index whose
binary value has zeros where the corresponding bits of K
should be preserved and unities where they should be
inverted. Inverting the cell as index zero does not affect
K.

[Phil Carmody]

Post by Anton Shepelev

Post by Mike Terry

Post by Anton Shepelev
I hoped this would not transpire, but we did it with a
2x2 board, which is elementary. With Jonathan's two-
dimensional decomposition, 3x3 seems possible as well,
after a little drilling.

You mean 4x4? (The method works for sides 2,4,8, etc..)

You are right. It is time I gave my solution, which works
with a linear array of 2^n cells, with C(i) denoting the
cell value -- zero or unity. I index the cells from 0 to
n-1, and consider the resulting bit array as encoding an
K = XOR( C(i) * i ), for i = 0 to n-1
where XOR is, well, the bit-wise exclusinve OR operation
upon a binary number. K is of the same size, and takes the
same values, as the array indices. It can be changed to any
other value by iversion of the cell at the index whose
binary value has zeros where the corresponding bits of K
should be preserved and unities where they should be
inverted. Inverting the cell as index zero does not affect
K.

8x8 is a lot to remember, but the binary decomposition does
mean that you can keep the calculations mostly trivial. Does
a subset of the board have odd or even parity? Repeat for the
various different subsets. 6 in the case of 8x8. If you can
remember 7 separate parity values, then you can perform the
3 calculations even more easily.

For 4x4, the 4 subsets are

YYYY
YYYY
....
....

YYYY
....
YYYY
....

YY..
YY..
YY..
YY..

Y.Y.
Y.Y.
Y.Y.
Y.Y.

As you can see, you only need the parity value of 3 rows to create 2 of
the decision values.

If the parity of the subset is 1, then the coin you're interested in
is in that subset. So when setting up the board and selecting which
coin to flip, if the interesting cell is in a subset, ensure that subset
has odd parity. If it already has the right parity, flip something in the
complement of that subset instead.

So if the parity values of all the subsets start in the perfect
configuration such that they identify the appropriate grid location,
then you flip this coin:

....
....
....
...X

because it doesn't take part in any of the parity calculation, and so
won't change the communicated square.

I really wouldn't want to do it on 8x8, to be honest, in particular as I
have terrible short term memory, but 4x4 seems easy, as you can see each
subset in one glance - if you forget anything, you can work it out again
instantly. Cognitively, 32 is a way bigger number than 8.

Phil

[Mike Terry]

Post by Phil Carmody

Post by Anton Shepelev

Post by Mike Terry

Post by Anton Shepelev
I hoped this would not transpire, but we did it with a
2x2 board, which is elementary. With Jonathan's two-
dimensional decomposition, 3x3 seems possible as well,
after a little drilling.

You mean 4x4? (The method works for sides 2,4,8, etc..)

You are right. It is time I gave my solution, which works
with a linear array of 2^n cells, with C(i) denoting the
cell value -- zero or unity. I index the cells from 0 to
n-1, and consider the resulting bit array as encoding an
K = XOR( C(i) * i ), for i = 0 to n-1
where XOR is, well, the bit-wise exclusinve OR operation
upon a binary number. K is of the same size, and takes the
same values, as the array indices. It can be changed to any
other value by iversion of the cell at the index whose
binary value has zeros where the corresponding bits of K
should be preserved and unities where they should be
inverted. Inverting the cell as index zero does not affect
K.

8x8 is a lot to remember, but the binary decomposition does
mean that you can keep the calculations mostly trivial. Does
a subset of the board have odd or even parity? Repeat for the
various different subsets. 6 in the case of 8x8. If you can
remember 7 separate parity values, then you can perform the
3 calculations even more easily.
For 4x4, the 4 subsets are
YYYY
YYYY
....
....
YYYY
....
YYYY
....
YY..
YY..
YY..
YY..
Y.Y.
Y.Y.
Y.Y.
Y.Y.
As you can see, you only need the parity value of 3 rows to create 2 of
the decision values.
If the parity of the subset is 1, then the coin you're interested in
is in that subset. So when setting up the board and selecting which
coin to flip, if the interesting cell is in a subset, ensure that subset
has odd parity. If it already has the right parity, flip something in the
complement of that subset instead.
So if the parity values of all the subsets start in the perfect
configuration such that they identify the appropriate grid location,
....
....
....
...X
because it doesn't take part in any of the parity calculation, and so
won't change the communicated square.
I really wouldn't want to do it on 8x8, to be honest, in particular as I
have terrible short term memory, but 4x4 seems easy, as you can see each
subset in one glance - if you forget anything, you can work it out again
instantly. Cognitively, 32 is a way bigger number than 8.

That seems more complicated than the "brute force" approach. I use thumb and first two fingers on
my left hand to track the 3 parity bits for the rows, and then similarly on my right hand but
tracking the columns. So there is no extra "remembering" required and at each step in the
calculations, just a straight observation + (possibly) binary calculation to make, then adjust the
appropriate fingers/thumbs. (Hm, ok I suppose you also have to remember which column/row you're
currently working on, so you can advance to the correct next column/row afterwards. That's easily
forgotten if you're interrupted... And you have to be ok with xor-ing 3 bit numbers but that's no
problem for me...)

On test Excel spreadsheets randomly generated with 0 or 1 entries it takes me around 90 seconds in
all for 8x8. I think using coins as in the puzzle would slow things down, as considerably more
visual attention is required to distinguish even/odd parity - but as there's no short-term memory
involved, I reckon it would just slows things down rather than making them genuinely harder... The
most common error for me is remembering to count row/column numbers starting from zero rather than one!

Mike.

Post by Phil Carmody
Phil