Earlier today I set you the following puzzle about a game show, which has been used during Oxford university admissions interviews for joint philosophy courses. The puzzle has three versions and I will discuss the solutions to all of them below, as well as how they relate to basic issues in computer science.
1. The standard version
You are a contestant on a game show with a £1m prize. A second contestant is in another room. The game is cooperative, so either you both win, or you both lose. You have never met the other contestant before, but you can assume they are just as logical as you are.
The game begins with round 1, then proceeds with rounds 2, 3, and so on, for as many rounds as need be. On each round, each contestant has two choices:
EITHER To tell the host: “I end the game” and announce a colour (any colour, of the contestant’s choice.)
OR To send a message (of any length) to the other contestant.
If you both choose to send a message, the messages are sent simultaneously, crossing in transit.
To win the game you must both end the game on the same round, announcing the same colours. If only one of you ends the game, or you both end it announcing different colours, you lose.
Round 1 is about to begin. What do you do?
Solution
As I mentioned in the earlier post, a bad strategy is to end the game by announcing a colour on round 1, since it is very unlikely the other contestant will do the same with the same colour. Instead, you and the other contestant should message each other to plan when to end the game, and with which colour.
Here’s a sensible-sounding candidate for your first message: “let’s declare red in round 3, please confirm in round 2”. The game is cooperative, so the other contestant will follow your lead if they think it is in both of your best interests. Indeed, this strategy would work if only you sent a message in round 1, and only they responded (to confirm the plan) in round 2. You would win in round 3.
However, this strategy does not work for this puzzle because your messages are sent simultaneously. Since the other contestant is as logical as you, maybe they are thinking of sending a similar message. In fact, they may send exactly the same message, in which case, you will both announce red on round 3 and win. Hurrah! But then again, they may make the proposal with a different colour.
For example, let’s say you send “let’s declare red in round 3, please confirm in round 2”, as suggested above, and you receive the message: “let’s declare blue in round 3, please confirm in round 2”? Where does that leave you both? Do you stick with red or do you defer to the other contestant and announce blue? They will be struggling with the same dilemma.
Indeed, you may come to the realisation that whatever message you send the other contestant, they may simultaneously send you exactly the same message but concerning a different colour. To solve the problem you need to find a way to break the symmetry.
The quick answer is to flip a coin. A very good idea is to introduce an element of randomisation.
For example, let’s say your first message is “I suggest we both announce red next round. I will do so if you also suggest this.” And let’s say that you receive the message “I suggest we both announce blue next round. I will do so if you also suggest this.” A sensible course of action would be to flip a coin each round, and send the “red” message on heads and the “blue” message on tails. If the other contestant does the same, then in a few rounds you will send each other the same message, and win on the following round.
There are other ways to introduce randomness depending on what message you send (or receive). For example, you could flip a coin to send a message about who will lead the process. Heads, you send: “let’s say red next round, if your message indicates you will follow my suggestion.” Tails, you send: “I am going to follow your plan of action if you send one this round.” Within a few rounds you will have established a leader.
Provided you send (and receive) a workable plan, any deadlock between you can be broken by introducing randomness. Flip a coin to determine whether to be insistent on your plan, or amenable to theirs, and eventually an agreement will be reached.
In computer science, a similar problem comes up in an issue called contention resolution. For example, just say you connect identical computers together on a network. If the computers are identical, they will all want to talk to each other at the same time. But if they do talk at the same time they will garble each other. In order to break the symmetry, the computers do the equivalent of flipping an internal coin, so that an order of priority emerges.
2. The collision variation: The contestants have three choices each round. Either they can end the game and announce a colour, or they can send a message, as in the standard version, or they can do nothing. If both players send a message, the messages collide and are not delivered. In this case, an error message is generated. What do you do?
Again, randomness comes to the rescue. Flip a coin to decide whether to send a message or stay silent. On heads, send the message “Announce red on next round, if this message gets through.” On tails, do nothing, and plan to follow whatever is suggested on the message that might be received. It is very likely that in a few rounds a message gets through one way or the other, with a quick win straight afterward.
3. The pigeon variation: Only one contestant sends a message per round. You start in round 1, the other contestant sends in round 2, and you continue alternating between you. Although this time, you are a long distance from each other and the messages are sent via carrier pigeon, which means you can never be sure that the messages arrive. What do you do?
The pigeon variation is a version of the two-generals problem, a well-known problem in computer science about communication between two parties where a failure in communication is possible.
Since no messages you send may reach the other contestant (and vice versa), you cannot guarantee winning the prize. However, you can attain a very high degree of confidence with the following plan.
On round 1 you send the message, “We shall say red on round 1000, please confirm.” On each subsequent round, you send this message again, together with a complete record of all prior messages sent/received.
The other contestant, if receiving the message on round 1 should simply follow along and send confirmations. If they don’t receive anything, they should reply with “sorry, no message received; please resend.” Most importantly, they should not start a competing plan, which would only reintroduce the priority issue of the main puzzle. Eventually, messages are likely to get through and the two players will be on track to win with high probability.
Today’s puzzles were written by Joel David Hamkins, who used them on admissions candidates when he was Professor of Logic and the Sir Peter Strawson Fellow in Philosophy at University College, Oxford. “In the admissions interviews, which were generally less than 25 minutes, we were happy if a candidate got to the realisation of the symmetry issue in the main puzzle, before going on to the alternating version [in which one message is sent per round], which most students got quickly, and then the collision version, where the randomness idea seemed to arise more naturally. The best candidates were then able to realize how to apply the randomness idea to the main version. With the pigeon version of the puzzle, successful candidates realized the need to achieve confirmation and confirmation of confirmation, and a few put this together to mount the impossibility argument for the case of certainty, and most realized how to increase the likelihood of success by picking a distant round and repeating messages.”
Hamkins is currently the O’Hara Professor of Philosophy and Mathematics at the University of Notre Dame. For further discussion of this puzzle, please see his blog.
I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.
I’m the author of several books of puzzles, most recently the Language Lover’s Puzzle Book. I also give school talks about maths and puzzles (online and in person). If your school is interested please get in touch.
On Thursday 21 April I’ll be giving a puzzles workshop for Guardian Masterclasses. You can sign up here.
