How to formally model the “hesitation” in the hat-guessing puzzle and prove it by mathematical induction?

Question

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.

Answer 1

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?