Alice and Bob are on a game show. Each is secretly told a whole, positive number. They are told the two numbers are consecutive, but neither knows the other person’s number. For example, if Alice is told 20, she does not know if Bob was told 19 or 21. And if Bob is told 21, he does not know if Alice was told 20 or 22. The point of the game is to guess the other person’s number. The game works as follows.

• Alice and Bob cannot communicate with each other, and they are not allowed to plan their strategy either.
• The two are in a room where a clock rings every minute.
• After the clock rings, either player can call out a guess of the other player’s number, or they can stay silent.
• The game continues until Alice or Bob makes a guess. After the first guess is made, the game ends.
• Alice and Bob win $1 million each if the guess is correct, and they lose and get nothing if the guess is incorrect.

How should Alice and Bob play this game to have the best chance of winning? Each knows the other person is perfect at logical reasoning.

At first it seems like Alice and Bob can do no better than random chance. If Alice is told 20, for instance, there is no way to know if Bob has 19 or 21. But since Alice can limit Bob’s number to 2 possibilities, she can at least have a 50% chance of guessing correctly.

Bob has the same issue. If he is told a number N, then he cannot be sure if Alice was told N – 1 or N + 1. If Bob guesses between the 2 possibilities, then he also has a 50% chance of guessing correctly.

It would seem Alice and Bob are stuck. Neither person has can do better than random chance, so regardless of who guesses, it would seem they are limited to a 50% chance of winning.

But remarkably they can do much better than random chance! They can actually increase their odds of winning to 100%. That is, they can win the game for sure! The trick is that they can use logic and the ringing clock to coordinate which player guesses.

The strategy

The answer lies in the subtle rule that the clock rings every minute. The clock essentially serves as a signal between Alice and Bob that allows each person to reason inductively.

One key detail is the two are given positive consecutive numbers. When Alice gets a number N, she usually has to consider Bob has N – 1 or N + 1. But this is not always true. Suppose that Alice gets the number 1. She would have to consider that Bob got 0 or 2. But since 0 is not positive, she knows that Bob must have gotten 2.

So if Alice gets 1, then she would know Bob has 2 for sure, and she would answer on the first ring of the clock. Similarly, if Bob got the number 1, he would know Alice must have 2, and he would answer after the first ring of the clock.

Now consider instead that Alice was given 2 and Bob was given 3. Alice would be wondering if Bob has 1 or 3. But Alice would think, “If Bob has 1, he surely will answer after the first ring of the clock. Therefore, if the clock rings and he does not answer, he must surely have 3 instead.” So the clock will ring once, and then after it rings a second time Alice will answer and guess Bob has 3. (If instead Bob was given 2 and Alice was given 3, then Bob would answer after the second ring and guess Alice has 3.)

This reasoning can be extended inductively. If Alice and Bob are assigned N and N + 1, then the player with the lower number will answer in exactly N rings of the clock and correctly answer the other person has N + 1.

They win every single time!

The connection with common knowledge

The puzzle illustrates the game theory concept of common knowledge which is distinguished from mutual knowledge.

An event is mutual knowledge if each player knows the event. An event is instead common knowledge if all players know the event, all players know that all players know it, and so on ad infinitum.

Here is how the two concepts work in the game. When Alice is given the number 20 (and Bob could have 19 or 21), it is mutual knowledge that neither player has the number 1, neither player has the number 2, or so on, up to neither player has the number 18. But that deduction is not good enough to solve the game.

That is where the clock ringing provides a helping hand. When the clock rings the first time, and no one answers, the fact that neither player has 1 transforms from mutual knowledge into common knowledge. This seems like a trivial distinction, but it is an important one that allows for the building up of logical deductions. Each time the clock rings, the set of excluded numbers becomes common knowledge to both players, which eventually allows the players to win for sure.

(source)