3 ms·
Just looking at the main puzzle, I don't think the author's solution of randomness works. He suggests using a coin flip between two colors, say red and blue, bu
by y7 5y ago
Just looking at the main puzzle, I don't think the author's solution of randomness works. He suggests using a coin flip between two colors, say red and blue, but it suffers the same problem as the other solutions that he shoots down, namely that you have to get consensus on the pair {red, blue} first. If the other person suggests the pair {green, yellow} in the same round, you're out of luck. If you can get consensus on a pair of colors, then you can also get consensus on one color.
I think using randomness to decide whether you send a message or you stay silent does work. For example: toss a coin, and if it's heads, you send "If didn't send a message this round, I will send the host 'Red' on the next round." (you could add one round asking them to confirm on the next round, to make sure you speak the same language, etc.) If it's tails you stay silent.
If you stay silent during a round and your partner says something, you can use their strategy. Basically, you need a round where only one of you says something. If your partner is equally logical, and therefore has an equally efficient solution, this ends the game in an expected 1 + sum(k/2^k for k=1..inf) = 3 rounds.
- mjmahone17 5y agoThe coin flip on the main puzzle is assuming each person proposes exactly one color: do you switch or stay the same. So there is guaranteed to be at most a pair of colors, and the goal is to eventually get agreement between those two options.
- y7 5y agoWhat do you do they come up with a different but equally compelling strategy at the same time? One of you is going to have to start following the other person's strategy, but what if you do so at the same time?
- mjmahone17 5y agoRight exactly. So long as at least one of you uses a coin flip to switch between the strategy they last suggested and the strategy you last suggested it will work.
- y7 5y agoHow will you know when you're in sync?
- totony 5y ago>But I have got a coin in my pocket, and from now on, I intend each round to flip the coin, sending the red message on heads and the blue message on tails. If you do likewise, then we are very likely in a few rounds to hit upon the same message, and then we shall win on the next round by following through, announcing the agreed-upon color. What if the other person says "But I have got a coin in my pocket, and from now on, I intend each round to flip the coin, sending the green message on heads and the orange message on tails. If you do likewise, then we are very likely in a few rounds to hit upon the same message, and then we shall win on the next round by following through, announcing the agreed-upon color." How do you choose the strategy? If both stick to theirs, then you have a deadlock