3
$\begingroup$

The following question was first presented in MATHEMATICS of StackExchange. With a simple description at first sight, it has far-reaching consequences on plenty of recent and advanced theories, such as Knowledge and Common Knowledge in game theory, logic, and distributed computing. With many excellent answers from MATHEMATICS (with my gratitude), it is still somewhat mysterious to me. So, I am here for more illumination.

Below is the original source from MATHEMATICS for your convenience.

Hua Luogeng (in Chinese, 华罗庚) took a hat-guessing puzzle as an illustration in a booklet focusing on mathematical induction. The following description is a literal translation from Chinese.

Hat-Guessing Puzzle: A teacher wants to identify the most smartest one from his three students by the following methods: 5 hats are shown, in which 3 of them are white and the other two are black, to the three students. With eyes closed, each student is put on a white hat, while the other two black ones are hidden. Once the permissions of opening eyes are granted, the three students open their eyes simultaneously and are allowed to look at the hats of others without any communication. After a hesitation, they say that "the hat on my own hat is white" with one voice. The question is how do they make it?

The puzzle can be easily generalized to the version with $n$ persons, $n-1$ black hats, and $\ge n$ white hats and be solved by induction on $n$:

  • When $n$ is 2, the situation is trivial because there is only one black hat. If I am wearing the black one, then the other person can tell that the hat on his head is white, without any hesitation. However, he does hesitate. Contradiction.
  • Suppose that we have solved the puzzle with $n = k$.
  • When $n = k + 1$, the reason goes in the following way: If someone is wearing the black hat, all the other people will know that and the problem is reduced to a version with $k$ person, $k-1$ black hats and $\ge k+1$ white hats. According to the inductive hypothesis, the $k$ persons should tell that the hats on their heads are all white, without any hesitation. Contradiction.

While both the puzzle and proof sound very simple, I am very confused with the informal keyword "hesitation" in them. I even cannot tell the vagueness of hesitation clearly. For example, is the hesitation itself a suitable object which can be used in mathematical induction? Informally, my problem can be stated as follows.

My Problem: How to formally model the hesitation in the hat-guessing puzzle?

Now, I will give an account of my confusion (after the discussion with MATHEMATICS users).

  1. Is it suitable to model the hesitation in terms of rounds? Just like the Muddy Children Puzzle, the teacher can broadcast the following question over and over: What is the color of your hat? If the modeling is OK, is it still on the right way to prove the following statement (for the version with $n$ students) "in the first $n−1$ rounds they all say I don't know, and in the $n$th round, they all say it is white simultaneously"?
  2. I think the statement "If someone is wearing the black hat" given in the original proof is based on the unjustified assumption about the first $n−1$ rounds. In other words, is it necessary to prove first "in the first $n-1$ rounds they all say I don't know", before proving the thing in the $n$th round? If it is, how to prove the $n-1$ part?

Thank you very much for any suggestions.

$\endgroup$
  • 2
    $\begingroup$ You've pinpointed the reasons why these questions make me uncomfortable: Not only do the participants need to model the processes of their co-participants, they also need to model the speed of those other process. I think in this case, since they all give the same answer at the same time, we are being coached toward the idea that they are identical agents with identical models of each other. (Sometimes the puzzles are phrased carefully enough, in terms of discrete rounds, such that we might gloss over those details. Other times, now.) $\endgroup$ – Novak Dec 17 '12 at 19:09
2
$\begingroup$

This isn't really an answer to your questions, but I think it would help in understanding the problem (or the way to answer your questions is) to write out a formal statement and proof of the solution. The proof you've presented doesn't say what is being proven, and as written is certainly incorrect. It states (final bullet point) that the inductive hypothesis is that $k$ people with $k-1$ black hats and $> k$ white hats can tell that they all have white hats without any hesistation, but it proves that $k+1$ people with $(k, >k+1)$ hats can tell with hesitation.

Writing out a more formal proof would also make it clear what modeling assumptions you require for it to work. For example, you would probably end up needing to prove "$k$ people with $(k-1,>k)$ hats can all tell if they have white hats after $k$ moments of hesistation". If so, that means you would need some formal, common-knowledge notion of "moment of hesitation".

I hope that helps a little bit with question #1. (Also, the answers at math.stackexchange seem very good on this topic as well....) It might also help with #2, but I'm not sure what exactly you're asking -- I think the proof by induction would take care of this?

$\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.