This is what the Oxford University admissions interview is all about? Team up and choose a color? The logic behind this is very deep

Bo Wen from Aofei Temple
Quantum Bit Report | Public Account QbitAI

How to successfully get admitted to Oxford University?

Don't panic, choose a color first.

Recently, a professor of logic at Oxford University posted an admissions interview question, which attracted a large number of netizens to watch and discuss on major platforms.

The problem description is very simple:

This is a two-person collaboration program in which two contestants who have never met each other will stay in a completely closed room.

In a round, contestants have two possible actions:

1. Choose to end the game and tell the host a color;

2. Send a message (any content) to another contestant, and the recipient will receive it before the next round of the competition.

There are an unlimited number of rounds. Both contestants win when they both choose to end the game in the same round and tell the host the same color .

On the other hand, if only one person chooses to end the game and say the color, or the two people say different colors, both of them lose.

Now that you are one of the contestants, how can you win?

Endless “consensus”

I believe that many people will first think of: reaching a consensus with teammates through the operation of "sending messages".

For example, in the first round, send a message to your teammates saying "We will all declare red in the third round, and confirm each other once in the second round", and then success will come naturally.

But don’t be too naive. What if you both sent messages to each other in the first round ?

If they are a little more in sync and the information content happens to be the same, then they can win in the third round (even the "second round of confirmation" is just a formality).

But what if one person says “declare red” and one person says “declare blue”?

You might frown and choose:

1. Everyone insists on their own decision, and then the situation becomes deadlocked.

2. Both parties obey the other party’s decision, and the cycle continues indefinitely.

Well...like this comment says, this is essentially a question of "who is subordinate", and one side must stand up to break this unlimited "seeking consensus".

The professor who set the question said that in this very classic logic puzzle, there is a basic symmetry between the two contestants, who are also collaborators .

Specifically, "reaching consensus with teammates by sending messages in the shortest possible round" is the natural thought after seeing this puzzle.

When both parties think based on this logic, additional rounds of "debates" and "confirmations" can easily arise under the rule of receiving and sending information at the same time.

Breaking the “logical symmetry”

The professor who set the question proposed an idea: using "randomness" to break this "symmetry".

The simplest random game: coin toss.

The content of the information sent can be as follows:

From now on, I intend to flip a coin in each round, with heads being red and tails being blue, and to tell you the result of my coin flip in the next round.

If you do the same, then we should be able to throw the same side very quickly in one round, and then we can confirm it in the next round, and then win in the next round.

Transforming the question of “who will be subordinate” into a random probability problem sounds like it can break the cycle of “seeking consensus”, but someone soon pointed out the loophole:

To implement this method, both parties must first reach a consensus on the "red/blue combination" corresponding to the heads and tails of the coin . What if the other party also recommends the "green/yellow combination" in the same round based on this logic?

However, this commenter believes that the randomization strategy is still effective, but it can be slightly modified:

Flip a coin. If it’s heads, you will tell your teammates in the next round “I’m going to declare red, please confirm”. If it’s tails, you don’t have to do anything.

In other words, he believes that the most important thing in this puzzle is to keep "only one person speaking in each round." If teammates agree with this logic, the game can be over quickly.

In the real entrance test facing this puzzle, some interviewers also proposed this idea:

When the two parties choose different colors, they do not pursue randomness, but adopt all of them - mix the two colors as the new consensus color.

The professor who asked the question said that he was not listening because of lack of thinking, but red + blue is purple or violet? Are you going to use mixed light, mixed pigments, or RGB colors to produce new colors?

Logic puzzles can also test personality

After this puzzle was announced, many interesting ideas were born from the heated discussions among a large number of netizens.

For example, here’s how a logic puzzle is transformed into a computer model:

Convert the contestant to a virtual machine (VM) with a tuple (bool endGame, rgb agreed_color, string message). This message group from VM1 will be sent as input to VM2.

In the real 25-minute admission interview at Oxford University, the professor who set the questions also used this puzzle to simply understand the different personalities of the candidates.

For example, some candidates will follow the "leader strategy" and insist on persuading the other party's ideas to reach a consensus with their own.

Others are more inclined to "comply with the other party" and will first send a message to express their "agreement with whatever color the other party wants to use."

Another interesting result is that when choosing colors, 2/3 of the candidates will choose red, followed by blue which is far behind, and other colors such as orange, green, yellow and black are very rare.

In fact, there are three variations of the above problem:

1. Alternate sending
Two contestants can only send messages in alternating rounds, and only one person can send in one round

2. Collision problem
If two contestants send messages in the same round, the messages will collide. The contestant will know that the message was sent but the other party’s message will not be received.

3. Pigeons and pigeons
The rooms of the two contestants are quite far apart, and messages have to be sent by pigeons, so it takes a long time (perhaps hundreds or thousands of rounds) before they are received.

What new ideas do you have for solving the original problem and its variants?

Reference links:
[1] http://jdh.hamkins.org/coming-to-agreement-logic-puzzle/
[2] https://twitter.com/JDHamkins/status/1475088789701726208
[3] https://news.ycombinator.com/item?id=29707135