Guess the number – a game theory puzzle

I came across a highly amusing puzzle in Impossible?: Surprising Solutions to Counterintuitive Conundrums.

What distinguishes this brain teaser from other “guess my number” puzzles is the method of solution. The answer is not an arithmetic trick or a mathematical sleight of hand like in your age by restaurant math.

The puzzle is plainly titled “consecutive integers” and appears in a chapter about the game theory concept of common knowledge. Here is my slightly modified retelling of the puzzle that appears in the text.

The puzzle – consecutive integers

On a game show, two people are assigned whole, positive numbers. Secretly each is told his number and that the two numbers are consecutive. The point of the game is to guess the other number.

Here are the rules of the game:

–The two sit in a room which has a clock that strikes every minute on the minute
–The players cannot communicate in any way
–The two wait in the room until someone knows the other person’s number. At that point, the person waits until the next strike of the clock and can announce the numbers
–The game continues indefinitely until someone makes a guess
–The contestants win $1 million if correct, and nothing if they are wrong

Can they win this game? If so, how?

Preliminary thoughts

At first it seems like the contestants can do no better than chance. If a contestant has the number 20, for instance, there is no way to tell if the other person has 19 or 21.

The naive strategy is to wait a bit and then take a guess at the other number, yielding a 50 percent chance of success.

But can they do better?

It turns out there is a nice trick, along the lines of the hat puzzle, that can help the contestants.

The solution

The answer lies in the subtle rule about announcing the number once the clock strikes. It turns out that two players who reason correctly can win every single time, if they think inductively.

To see why this is so, think about a case where the players can win for sure. If one of the players gets the number 1, then he can be sure the other player has the number 2. There is no other possibility because the two assigned numbers are consecutive and positive. Therefore, this player will immediately deduce the answer and announce the numbers during the first strike of the clock.

Now consider when the players are assigned the numbers 2 and 3. The player with 2 can reason as follows. “I know my partner can either have 1 or 3. But if he has 1, then he should know it and will announce it at the first strike of the clock. So if the clock strikes once and nothing happens, I can be sure that I have the lower number. Therefore our numbers must be 2 and 3.” So what will happen is this player will announce the numbers at the second strike of the clock.

This reasoning can naturally be extended by induction. The general statement is the player with the number k will realize the other has k + 1 and can announce this information at the kth strike of the clock.

They can win every time!

Final thought: the connection with common knowledge

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

Roughly speaking, an event is mutual knowledge if all players know it. Common knowledge also requires that 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 a player has the number 20, it is mutual knowledge that neither player has the number 1, or 2, or so on up to 18. But that deduction is not good enough to solve the game.

And that is where the clock provides a helping hand. When the clock strikes once, and no one answers, the fact that neither player has 1 transforms from mutual knowledge into common knowledge. This alone is trivial given the numbers are consecutive, but as shown above, this stronger set of knowledge can build up on consequent strikes of the clock. Each time the clock strikes the set of excluded numbers is included as common knowledge and eventually the players can win.