Coin Puzzle

[Willtor]

I heard this puzzle from a friend a few weeks ago, and found it very challenging:

You and a friend are kidnapped by mercenaries. The boss offers you a test: if you pass, you'll be let go, but if you fail, you both die.

You (without your friend) will be brought into a room with a chess board with a coin on each square. Some will be heads and some will be tails, but you won't know the configuration until you're brought into the room. The boss will point to a square. You must then flip exactly one coin on the chess board. You will be removed from the room and your friend will be brought in. Your friend must correctly identify the square the boss pointed to.

Before it begins, you're allowed to confer with your friend to figure out the system of communication. Your only means of communication, once the test has begun, is the configuration of coins on the chess board.

What is the system?

 

[Soyeong]

This would work in theory, but not sure well it would work in practice. Agree that you'll flip over the lower left coin and when placing it back down place it so its left edge is 1-8 millimeters from the left side of the board and its bottom edge is 1-8 millimeters from the bottom of the board to correspond with x and y coordinates of where the boss pointed. Or if you can flip the coin end over end so that it's partially onto an adjacent square, then it becomes a lot easier to identify the coin that is out of place.

 

[Willtor]

This would work in theory, but not sure well it would work in practice. Agree that you'll flip over the lower left coin and when placing it back down place it so its left edge is 1-8 millimeters from the left side of the board and its bottom edge is 1-8 millimeters from the bottom of the board to correspond with x and y coordinates of where the boss pointed. Or if you can flip the coin end over end so that it's partially onto an adjacent square, then it becomes a lot easier to identify the coin that is out of place.

That's a good guess. It turns out there's a way to do it by simply flipping. You could even tell the boss which one to flip for you.

 

[brinny]

LOL! Huh?

 

[Willtor]

For simplicity, imagine it were a 2x2 board, rather than 8x8. How would you solve it then?

 

[brinny]

hahahaaaa! no, but thanks for the kind suggestion...

i'm terrible with numbers...

even on a chess board i cannot fathom the numbered moves, etc.

 

[Willtor]

LOL! Huh?

This is a sort of a fun, math-y problem. There are a lot of related problems in Computer Science that have neat solutions. If this isn't appropriate for this forum, I'll leave it alone. But if people are able to solve it, I've got a boatload more.

 

[brinny]

This is a sort of a fun, math-y problem. There are a lot of related problems in Computer Science that have neat solutions. If this isn't appropriate for this forum, I'll leave it alone. But if people are able to solve it, I've got a boatload more.

of COURSE it's appropriate...

i'm just math/numbers-phobic

 

[Willtor]

of COURSE it's appropriate...

i'm just math/numbers-phobic

The 2x2 one is not hard. And the 8x8 one will directly follow.

 

[brinny]

you think i surely understand that, don't you?

 

[Willtor]

Suppose there are only two coins: The boss is going to point at one of them, and you have to signal to your friend which one he pointed at. With two, you can enumerate the possibilities.

 

[Soyeong]

Suppose there are only two coins: The boss is going to point at one of them, and you have to signal to your friend which one he pointed at. With two, you can enumerate the possibilities.

With two, you could have the right coin be heads if he pointed to the one on the left and tails if he pointed to the one on the right, but that system falls apart even when you go to four coins. You would essentially be counting in binary, but with four coins, you would need two coins to indicate all the possibilities, but you wouldn't be able to guarantee that those two coins were in the correct position with only one coin flip.

 

[brinny]

what Soyeong said

 

[Willtor]

With two, you could have the right coin be heads if he pointed to the one on the left and tails if he pointed to the one on the right, but that system falls apart even when you go to four coins. You would essentially be counting in binary, but with four coins, you would need two coins to indicate all the possibilities, but you wouldn't be able to guarantee that those two coins were in the right position with only one coin flip.

That's on the right path! Think in binary (without loss of generality, heads = 1, tails = 0). With 2, you have the following configurations:

00
01
10
11

Simply masking the first bit gives you the freedom you need to identify the coin. Forget about 4 in a row, for a moment. Consider a 2x2 chess board. How would you do that?

 

[Soyeong]

That's on the right path! Think in binary (without loss of generality, heads = 1, tails = 0). With 2, you have the following configurations:

00
01
10
11

Simply masking the first bit gives you the freedom you need to identify the coin. Forget about 4 in a row, for a moment. Consider a 2x2 chess board. How would you do that?

One coin might indicate a row and another the column, but that still runs into the same problem if you need to flip both coins and can only flip one.

 

[Willtor]

One coin might indicate a row and another the column, but that still runs into the same problem if you need to flip both coins and can only flip one.

But now you have four coins to work with -- not just 2 -- and they're laid out in rows and columns.

 

[Soyeong]

But now you have four coins to work with -- not just 2 -- and they're laid out in rows and columns.

It seems to me that the more coins that you use to communicate information the less control you have about what they communicate.

 

[Willtor]

It seems to me that the more coins that you use to communicate information the less control you have about what they communicate.

Consider what happens if you read the rows and then xor them, and then read the columns and xor them. Then you have a column index and a row index, and see what you can do to change either one, neither, or both...

 

[Willtor]

Okay, here's the solution for the 2x2:

Read each row as a binary number and xor them. Do the same for the columns.

a b
c d

row value: ab ^ cd (index: b ^ d)
column value: ac ^ bd (index: c ^ d)
(using ^ as xor)

Now you have two indices. Each coin represents the ability to flip a bit in the resulting row and column index. For example, if you like both indices, you can flip the "a" coin to leave both indices as they are. If you like the first but not the second, you can flip the "c" coin. If you like neither, you can flip "d".

Now you can communicate with your friend on a 2x2 board. But observe! A 2x2 board is the same as a 4x1 board, if you simply think of it this way:

a b c d

rearranged from:

a b
c d

You can use the same trick for a 4x2 (or even 4x4, since it's been solved for 4) board as we used to expand the 2x1 to a 2x2 board:

a b c d
e f g h

One direction encodes the row and the other, the column.

But, of course, a 4x2 board is the same as an 8x1 board! And if you can do 8x1, you can do 8x8 with the same expansion technique.

Therefore, with a totally random initial configuration, you can encode the id of any square on the board.

 

[brinny]

Thanks! Even tho' i cannot fathom numbers (i'm phobic LOL)

it was great that you started this thread...

got any non-number puzzles?