4
$\begingroup$

Imagine there is a hat sitting on the table. And there are two contestants. You, Tommy, will be one of the contestants, and we'll call the other one Vinnie.

You reach into the hat, and pull out a number. Then, Vinnie does the same. Now, the reason this hat is magical is that, no matter what number you pull out, Vinnie will always pull out a number that is either one above or one below your number. For example, if you pull out a two, you know Vinnie has pulled out either a one or a three.

To make it simple, we'll limit the numbers to between one... and infinity.

So, each of you pulls out a number. Let's say you pick three and Vinnie picks two. I'm the moderator, and I ask Tommy, "Do you know what number Vinnie has?" Tommy looks at his number, which is 3, and says, "No, I don't."

I then ask Vinnie, "Do you know what number Tommy has?" He looks at his number two and says, "Yes." He knows Tommy has to have a 3.

Regardless of the numbers that are picked, and assuming that both contestants answer truthfully, if I keep asking the question of both of them, eventually one contestant will know what number the other contestant has.

In other words, if I ask Tommy, then ask Vinnie, then Tommy again... then Vinnie again... eventually one of them will know the other's number.

The question is this:

How can this be proven in a mathematically rigorous fashion?

This question was taken from the Car Talk Puzzler Archive and is located at http://www.cartalk.com/content/magic-hat-0?question

$\endgroup$
  • $\begingroup$ Drat. Why can't /I/ be Vinnie? $\endgroup$ – Doc Nov 20 '13 at 1:27
4
$\begingroup$

This is known as Conway's Paradox, and you can find a mathematically rigorous solution here.

$\endgroup$
  • $\begingroup$ I have selected this as the answer despite reading the solution. I'm trusting it's correct. $\endgroup$ – math wannabe Nov 20 '13 at 23:41
4
$\begingroup$

This is similar to the Blue Eyed Islanders problem (originally called Muddy Children and other names), where every islander knows that the number of blue-eyed persons is either $n$ or $n-1$, and a certain number of rounds of "I don't know" leads to everyone knowing which is the correct value, by repeatedly incrementing the minimum $k$ that islander $1$ can consistently believe that islander $2$ might believe that islander $3$ thinks (...) islander $n$ might suppose is the number of blue-eyes on the island.

Blue eyes: a logic puzzle

$\endgroup$
1
$\begingroup$

I know you asked for a rigorous mathematical proof but since this is the only popular thread with this question (which I found) I am going to give a solution which helped me think of this. It is a pseudo game theoretic set up for the problem

Set up: There are 2 players - A and B. The payoffs are symmetric and the game is a simultaneous game where at each stage both players are asked if they know the other's player's draw, and each player has the set of actions {yes, no} (as the answer to "do you know which number the other player has?"). Payoffs are just 1 if 1 player gets the correct answer, 0 if both players say "no" and -1 if they get the wrong answer (payoffs aren't necessary to fully understand this)

Okay the key portion: this is where I kind of modify the question. The question I am asking is (and what I believe that the actual question is also effectively asking in the end) is: There is a game where two players draw a card identically, and they get numbers such that the difference between the numbers is 1 (think of this as nature's move). The numbers are drawn from a set of positive integers. What is the optimal NE strategy that they can use two effectively find out what their numbers are?

Before we go ahead, for simplicity a payoff (a, b) is same as (b, a). Also, we name states of the world as 1 if the state is (1,2), 2 if the state is (2, 3), etc. Basically state = a

Okay so I'm going to outline the strategy here. Generally a player's response will be determined by i) the other players action in $timeperiod_{t-1}$ and the draw of the player. How the other player's action determines the strategy is to see how consistent the other player's strategy is to the optimal strategy if the state had been $state_{n-1}$.

Also also, when going from state to state and checking for consistency, player i puts himself in player j's shoes had the state been $state_{n-1}$. i.e. if we are in state 3, and player A is checking for consistency with state 2, he thinks of himself as player B.

Let's explore the strategy:

  1. If player i's number is 1, answer "Yes" in time period 1. The other player has 2. This is trivial. Given that the other player's number is 1 plus/minus 1, which makes it either {0, 2}, combined with the fact that we draw from positive integers, (0 can't be possible), the other player has to have 2.

  2. Let's go to state 2 (i. e. (2,3)).

    • Both players start with prior beliefs of ((1, 3), (2, 4)). Now since neither player has 1, both answer No in the first time period.
    • But in time period 2, player A realizes that player B's actions in period 1 weren't consistent with the strategy developed for state 1. Given this, he eliminates the belief that the player B has 1.
    • Player A hence now knows the other player has to have 3. In period 2, he says "Yes" [and player B says "No"] and states that player B has 2. Player B says "No".
  3. Let's go to state III (i.e. (3,4)). Players start with prior beliefs of ((2,4),(3,5)).

    • Player A and B say "NO" in period 1 since neither drew the number "1".
    • Player A and B notice the other player's actions in period 1, to be inconsistent with state 1. Therefore neither player has drawn "1" (both players knew this).
    • So what stops player A from saying "YES" in this period [as he would've done we were in state 2]? Notice that in state II, even when player 1 ended the game with a yes, player B, who had his apriori beliefs as the same as player A in this situation didn't call out yes. He infact calls out a "No".
    • Time period 3, "belief update" wise (vague idea alert) both players are in state III. Now each player checks for consistency with strategy if we were in state II. Player A immediately notices that period 2's play wasn't consistent with the optimal strategy for state II, hence he narrows his solution set from {2, 4} to just {4}.
    • He proceeds to say "yes" is period 3, and says that the other person's number is 4.

We can use this method of reasoning to every single possible state of the world.

In generic notation here is the strategy more explicitly:

  1. If time period is 1, check if you have drawn the number 1. If yes, end the game and call out the other player's number as 2. If no, say "No"
  2. If time period != state, say "No". (A longform way to write this would be to explicitly condition the answer on the apriori beleifs and the time period, but this is easier)
  3. If time period == state, check for consistency of player j's actions with the optimal strategy of $state_{n-1}$. If inconsistent, update beliefs, call out other player.

I once again apologize for the psuedo maths/game theory. I explored this in order to make myself understand the solution (what does it mean that both players know each other is "extremely logical")? This is basically what I came up with. Also apologies for inconsistent notation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.