The Kings Coins

Hopefully you will find the third question challenging. This game has no strings attached.

The king likes to invent games for his 2 logicians to play. He invented a coin game: Logician 1 has 1 coin, call it A, the King has 2 coins, call them 1,2 and Logician 2 is in a room isolated from Logician 1 and the king. Logician 2 will have no contact with Logician 1 during the game under penalty of being beheaded. The King has generously provided a $10,000 reward if they win. To play the game 1) King places #1 on the table choosing either heads or tails 2) Logician 1 places A on the table choosing either heads or tails 3) King places #2 on the table choosing either heads or tails 4) Logician 1 is given the option of reversing any coin (A, 1 or 2) 5) The King is given the option of reversing any coin, including the one Logician 1 just reversed 6) The King then presents the coins to Logician 2 in order A12. 7) To win, Logician 2 must identify the coin the King turned over. Before the game starts, the King allows Logician 1 and Logician 2 to devise the best strategy to win the game but they must inform the King what the strategy is before the game starts. If there is any lying, the logicians will be beheaded. Now for an easy question, what is a simple strategy to win with 3 coins?

The King is disappointed that his game is so easy to defeat so he generalizes to 5 coins, Logician 1 is given A, B and the King has 1, 2, 3. Same rules: still with each player reversing only one coin and Logician 2 is presented with AB123. Again another easy question, what is a simple strategy to win?

The King is disappointed again, so he generalizes to 7 coins, Logician 1 is given A, B, C and the King has 1, 2, 3, 4. ALMOST the same rules, except Logician 1 CAN ONLY reverse A, B, C and the King can reverse ANY COIN (he is the king). Logician 2 is presented with ABC1234. What is the best strategy in this case? Does this problem remind you of another puzzle that has appeared in rec.puzzles?

This seemed like something for error correcting codes, so I dug up my copy of Fraleigh, and it looks like it can be done with the Hamming (7,4) code. The procedure goes something like this, I think, translating the coins into binary:

First coin doesn't matter. If the second coin of the king is the same as his first, make your coin the opposite as your first and vice versa. Third coin is the sum of all the kings coins so far mod 2. Finally, after the king's last coin, it should be possible to flip one of your coins (A or so that you get one of the code words as follows:

1234CBA 0000000 0001011 0010111 0011100 0100101 0101110 0110010 0111001 1000110 1001101 1010001 1011010 1100011 1101000 1110100 1111111

These are at least three changes away from each other, so after the king chooses one to flip, the logician can tell which code word it's next to and see which coin was flipped.

[puzzle as spoiler space]

1) K puts down 1. 2) Whatever value K put down, L1 puts down A with the opposite value. 3) K puts down 2.

4) There are either two heads and one tail, or two tails and one head. In either case, L1 flips the odd man out.

5) There are either three heads or three tails. K flips one. Obviously, L2 will be able to tell which one.

I assume that the coins are put down (prior to the reversals) in the order 1A2B3.

Lemma 1: After L1's reversal, there must not be four heads and one tail, or four tails and one head. (K could reverse the odd man out, and L2 would not know which one it had been.)

Damned if I see how this one is easy, though. It seems to be analogous to error-correcting codes.

Let S1 be the set of possible sets-of-five-values after L1's reversal. Let S2 be the set of possible sets-of-five-values after K's reversal.

Lemma 2: S1 must be arranged such that each value in S2 could only have come from one value in S1.

Let S3 be the set of possible sets-of-four-values after B is laid down.

Lemma 3: S3 must be arranged such that, no matter what value K assigns to 3, L1 can reverse exactly one coin to produce a value in S1.

spoilers

Prearrange a setup for your coins with your partner. When the King is done putting down his coins, switch one of his (or not) so they're either all heads or all tails.

You must also agree that, if the King's coins are already 3H or 3T, then you will switch A rather than B. (Without such an agreement, the king could undo your switch, and your partner wouldn't be able to tell which one you switched.)

Given that, this does work. You present the king with one of the combos on the left, and the king can produce any of the combos on the right:

AB123 AB123

No. Just do nothing.

That's exactly right Aaron. Can you find an easy rule for Logistician1's coin flip so that Logician1 doesn't have to memorize a table? Can you find an easy rule for Logician2's decision, so that Logician2 doesn't have to memorize a table?

* Alan Sagan

I don't know if it matters, but do the King and Logican 1 place their coins alternately?

Could you simplify this procedure?

One could solve this problem by dragging out the old error-correcting codes book and copy down the hamming codes. But can you find a simple solution that doesn't require tables?

I don't think either L1 or K has that option, otherwise the original puzzle would have asked L2 'which coin, _if any_, did the king reverse'.

ObFollowup1: Which of the original three puzzles are solvable if both L1 and K have the option of not reversing anything?

ObFollowup2: Which of the original three puzzles are solvable if K has the option of not reversing anything, but L1 does not?

[puzzle as spoiler space]

Spoiler Spoiler Spoiler Spoiler Spoiler Spoiler

Actually, as Aaron pointed out, for the 3 and 5 coin game, Logician1 can always pick heads BEFORE the game starts and then let the King place his coins.