can you solve it An Oxford University Admissions Question | mathematics
Today’s conundrum involves contestants on a fictional game show trying to win £1million. It was also once awarded to a different type of candidate competing for a different type of prize: candidates applying for a joint philosophy degree at Oxford University.
The teenagers wanted to study PPE (politics, philosophy and economics), mathematics and philosophy, and computer science and philosophy. The conundrum was posed to them in their admission interviews, as part of a back-and-forth discussion during which the interviewer may have offered clues and asked probing questions. The interviewer focused on both how the contestants solved the puzzle and the solutions they gave.
It’s a really interesting puzzle and – as we shall see – it relates to fundamental questions of logic and computer science.
The game show
You are a contestant on a game show with a prize pool of £1m. A second candidate is in another room. The game is cooperative, so you both win or you both lose. You’ve never met the other candidate before, but you can assume they’re just as logical as you are.
The game begins with round 1 and then continues with rounds 2, 3, etc. for as many rounds as necessary. In each round, each participant has two options:
EITHER Telling the host, “I’m ending the game,” and announcing a color (any color of the contestant’s choice).
OR To send a message (of any length) to the other party.
If you both choose to send a message, the messages will be sent simultaneously and will cross paths during transmission.
To win the game, you must both finish the game in the same round and bid the same suits. If only one of you finishes the game or you both finish by declaring different suits, you lose.
Round 1 is imminent. How are you?
Obviously you don’t end the game in turn 1. This is obviously a bad strategy. When you finish the game you would have to announce a color, let’s say red. To win the £1 million, the other contestant must also decide to finish in the first round (unlikely) and also bid red (also unlikely). Do not do it. The best strategy involves some sort of dialogue between you and the other participant.
Let’s briefly consider a simpler variant of the riddle, which will help us understand what the main riddle asks you to do. In this variant, the structure is exactly the same, except that in each round only one candidate sends a message. In round 1 you send a message, in round 2 the other contestant sends you a message and you keep switching between the two of you.
In this “alternating” version, a simple strategy suggests itself. Your message for Round 1 could be: “I will bid red in Round 2; if you do it too, we will win.” Or, if you are more cautious, you can say: “Let’s declare red in round 3, please confirm in round 2”. Remember that the other participant wants to cooperate and will therefore follow your lead. They will both win the £1 million by Round 3.
However, this strategy it does not work in the original puzzle when you both need to message at the same time. Imagine your message in Round 1 is “Let’s explain Red in round 3, please confirm in round 2”. The other contestant is just as smart and logical as you, so maybe they had the same idea but with a different color! Let’s say their message is, “Let’s explain blue in round 3, please confirm in round 2.” Where does that leave you two? Who Confirms Which Color in Round 2?
The crux of this puzzle is to understand that no matter what message you send to the other party, they may be sending you the exact same message at the same time, but in terms of a different color. You must find a strategy that breaks this impasse.
When this puzzle was used in Oxford admissions interviews, the candidate was not expected to come up with a perfect answer right away. First of all, there is no clearly defined “best message” in Round 1 as the effectiveness of each message depends on the message you receive and there is no way of knowing this in advance. Rather, the puzzle led to an open-ended discussion of the problems involved. There may not be a “best starting message,” but certain strategies are far better than others.
The tutor may have also introduced these two variants:
The collision variant: Participants have three choices in each round. He can either end the game and announce a suit, or he can send a message like in the standard version, or he can do nothing. If both players send a message, the messages will collide and not be delivered. In this case, each player will receive an error message that the message was not delivered. How are you?
The pigeon variant: Only one participant sends one message per round (like the simplified version mentioned above). You start in round 1, the other candidate sends in round 2 and you take turns moving on. Although this time they are far apart and the messages are sent by carrier pigeon, you can never be sure that the messages will get through. How are you?
These variations also begin to explain what the puzzle has to do with computer science: they are analogies to the problems that arise when computers talk to each other.
I’ll be back in the UK at 5pm with solutions to all three variations of the puzzle and a discussion
NO SPOILERS PLEASE Discuss your favorite game shows. Or suggest new game show based logic puzzles.
Thanks to Joel David Hamkins for writing today’s puzzles. He is the O’Hara Professor of Philosophy and Mathematics at the University of Notre Dame and was Professor of Logic and Sir Peter Strawson Fellow in Philosophy at University College, Oxford until last December, where he conducted many admissions interviews.
I rephrased the puzzle to make it more suitable for a newspaper column.
I post a riddle here every two weeks on a Monday. I’m always looking for great puzzles. If you want to suggest one, email me.
I am the author of several puzzle books, most recently The Language Lover’s Puzzle Book. I also give school lectures on math and puzzles (online and in person). If you are interested in your school, please contact us.
On Thursday April 21st I will be giving a puzzle workshop for Guardian Masterclasses. Here you can sign up.