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.
[...]
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?
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 willplace 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
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.
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.
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?
On Monday, November 21, 2022 at 4:03:16 AM UTC, glenn...@gmail.com wrote: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
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
prisoner will choose that row.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
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 magicrow.
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.
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?
Gabor Szabo to Anton Shepelev:
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
Gabor Szabo to Anton Shepelev:
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.
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..)
Mike Terry to 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.
Anton Shepelev <anton.txt@gmail.com> writes:
Mike Terry to 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.
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
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 440 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 23:36:43 |
| Calls: | 9,150 |
| Calls today: | 1 |
| Files: | 13,433 |
| Messages: | 6,043,104 |