Today’s puzzle concerns contestants in a fictitious game show trying to win £1m. It was also once given to a different sort of contestant competing for a different sort of prize: candidates applying to study joint philosophy degrees at Oxford university.
The teenagers were hoping to study PPE (politics, philosophy and economics), Maths and Philosophy, and Computer Science and Philosophy. They were set the puzzle in their admissions interviews, as part of a back-and-forth discussion in which the interviewer may have given hints and asked probing questions. The interviewer was focussed on how the candidates went about solving the puzzle as much as the solutions they gave.
It’s a really interesting puzzle, and – as we will see - relates to fundamental issues in logic and computer science.
The game show
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?
Clearly, you don’t end the game on round 1. That’s a self-evidently bad strategy. If you end the game, you would have to announce a colour, let’s say red. To win the £1m, the other contestant must also decide to end on the first round (unlikely) and also announce red (also unlikely). Don’t do it. The best strategy will involve some kind of dialogue between you and the other contestant.
Let’s briefly consider a simpler variation of the puzzle, which will help us understand what the main puzzle is asking you to do. In this variation, the set-up is exactly the same, except that in each round only one contestant sends a message. In round 1 you send a message, in round 2 the other contestant sends you a message, and you continue alternating between the two of you.
In this ‘alternating’ version, a simple strategy presents itself. Your round 1 message could be: “I will declare red on round 2; if you also do we will win.” Or, if you are more cautious, you may say: “let’s declare red in round 3, please confirm in round 2”. Remember, the other contestant wants to cooperate, and so will follow your lead. You will both win the £1m by round 3.
This strategy, however, does not work in the original puzzle, when both of you must send messages simultaneously. Imagine your round 1 message is “let’s declare red in round 3, please confirm in round 2”. The other contestant is just as smart and logical as you, so they may have had the same idea, but with another colour! Let’s say their message is: “let’s declare blue in round 3, please confirm in round 2.” Where does that leave you both? Who confirms what colour in round 2?
The crux of this puzzle is to understand that whatever message you send the other contestant, they may simultaneously send you exactly the same message but concerning a different colour. You must find a strategy that breaks this impasse.
When this puzzle was used in Oxford admissions interviews, the contestant was not expected to come up with a perfect answer straight away. For a start, there is no clear-cut, “best message” to ask in round 1, since the effectiveness of any message will depend on the message you receive, and there is no way that you can know that in advance. Rather, the puzzle led to an open-ended discussion of the issues involved. There may be no “best initial message” but certain strategies are vastly better than others.
The tutor may also have introduced these two variations:
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, each player gets an error message saying the message was not delivered. What do you do?
The pigeon variation: Only one contestant sends a message per round (like the simplified version mentioned above). 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?
These variations also begin to explain what the puzzle has got to do with computer science: they are analogies of the problems that arise when computers talk to each other.
I’ll be back at 5pm UK with solutions to all three variations of the puzzle, and a discussion
PLEASE NO SPOILERS Discuss your favourite game shows. Or suggest new game show-based logic puzzles.
UPDATE: The solutions can be read here.
Thanks to Joel David Hamkins, who wrote today’s puzzles. He is the O’Hara Professor of Philosophy and Mathematics at the University of Notre Dame, and until last December was Professor of Logic and the Sir Peter Strawson Fellow in Philosophy at University College, Oxford, where he conducted many admissions interviews.
I rephrased the puzzle to make it more suitable for a newspaper column.
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.
