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$:
Prove 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?
Thank you for any suggestions.