Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Without having worked it out before; I imagine you can model the guessing as a game, where every hat-wearer is required to answer, but they are allowed to say "I don't know". Then "to conclude after /hesitation/..." would mean that "in some finite number of rounds it is possible to conclude...". –  Eric Stucky Dec 14 '12 at 14:13
    
@Eric Stucky Actually, this puzzle reminds me of the muddy children puzzle, which proceeds in rounds as you suggested. However, a father is involved and playing a subtle part in "muddy children puzzle". In the hat-guessing one, different rounds may make no difference. hesitation is still there. I am not sure. Can you explain it a bit more? –  hengxin Dec 14 '12 at 14:29
    
Heard this with 1 black and 2 whites way back in my childhood. it isn't a new puzzle. –  ashley Dec 15 '12 at 2:06
    
@ashley Yes, it is not new. The booklet, written by Hua Luogeng focusing on mathematical induction, is targeted at the middle school students. Nevertheless, it may mean a lot when you are exploring it with advanced mathematics more formally. See the answer given by gnometorule. –  hengxin Dec 15 '12 at 3:27
    
@hengxin "introduced a hat-guessing puzzle" in your first phrase giving all the credit to Luogeng which he doesn't deserve. the problem is interesting enough-- which apparently is one reason it's been around for so long. –  ashley Dec 15 '12 at 3:49
show 1 more comment

3 Answers 3

up vote 4 down vote accepted

The puzzle is older than its mathmaical formalizations and a version of it cates back to the fifties. The most common way to model such a situation is by using the partitional model introduced by Robert Aumann. There is a finite set (can be somewhat generalized) $\Omega$ of states. A state describes everything relevant that could be the case. In the puzzle, a state could describe who wears what hat, so there are seven states $$\Omega=\{www,wwb,wbw,bww,bbw,bwb,wbb\},$$ where for example $wbw$ stands for kid $1$ wearing a white hat, kid $2$ wearing a black hat, and kid $3$ wearing a white hat. Now we have to model what the kids know. We do this the following way: A person is able to different between certain states, but not others. We model this by that person having a partition of $\Omega$ and the person gets informed in which element in the partition the true state lies but not the precise state. In the puzzle, a kid is unable to differentiat states in which everyone else wears the same hat. For example, kid $2$ has the partition $$P_2=\big\{\{www,wbw\}, \{bww,bbw\},\{wwb,wbb\},\{bwb\}\big\}.$$

Note that kid $2$ knows the color of her hat only if the true state is $bwb$. Kid $1$ knows it if the true state is $wbb$ and kid $3$ know it if it is $bbw$. Generally, let $P_i$ be the information partition of a person $i$. If the true state is $\omega$, we let $P_i(\omega)$ be the element of the partition that contains $\omega$ and we interpret it as the set of states $i$ deems possible. An event is simply a set of states. We say that $i$ knows the event $E$ at state $\omega$, if $P_i(\omega)\subseteq E$. We let $K_i(E)$ be the set of states at which $i$ knows $E$. Note that $K_i(E)$ is an event itself. So, one can write things like $K_1(K_2(K_1(E)))$, which can be interpreted as $1$ knowing that $2$ knows that $1$ knows $E$.

Now in the puzzle, the true state is $www$. But a kid seeing two white hats does not tell her anything about the color of her own hat. Nobody knows the color of her hat, for otherwise she would say it. The event that nobody knows the color of her hat is $$E=\{www,wwb,wbw,bww\},$$ which is exactly the set of states at which no two kids wear a black hat. Everyone knows this and gets therefore a new partition in which this knowlege is incorporated. For example, $$P_2'=\big\{\{www,wbw\}, \{bww\},\{bbw\},\{wwb\},\{wbb\},\{bwb\}\big\}.$$ Formally, this is the coarsest partition that is at least as fine as the two partitions $P_2$ and $\{E,E^C\}$ and this is how e model learning. Even with this partition, no kid knows the color of her hat. Everyone knows this, and this allows her to deduce that the state is not on in which the other two kids have white heads and she has black hats, for the other kids could then deduce that they have white hats and they did not. From this, every kid can deduce that the true state is $www$, or more formally $P''_i(www)=\{www\}$ for $i=1,2,3$, so this becomes a formal statement.

A survey of this kind of modeling has bee written by John Geanakoplos for the Handbook of Game Theory and Economic Applcations. The survey can be found here. It also discusses essentially the same puzzle. The article is somewhat technical, and a slightly simplified version can be found here.

share|improve this answer
    
Very appreciated for your formal argument and rich material covered. Just for some confirmations. Do the transitions from $P$ to $P'$ and $P'$ to $P''$ proceed in rounds? Because I think it is related to the formal meaning of hesitation. Second, how to generalize this argument to the version with $n$ students, $n-1$ black hats, and $\ge n$ white hats effectively? Does mathematical induction work well with this formal argument? Third, your argument on 3 students has shown no one knows her color in rounds 1 and 2. Can it be generalized to the $n$ version, proving $n-1$ rounds impossible? –  hengxin Dec 15 '12 at 13:37
    
Yes, to everything. Genakoplos shows how to generalize these things to more players. –  Michael Greinecker Dec 15 '12 at 13:39
    
It seems difficult for me to follow the whole formal statements in Genakoplos just now. Back to the version with $n$ students, is it on the right way to prove using mathematical induction the statement: "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" to the question "what is the color of your hat" broadcast by the teacher _over and over_? If so, how to prove the part of "I don't know"? I think the "If someone is wearing the black hat" given in the original proof is based on the _unjustified_ assumption about the first $n-1$ rounds. –  hengxin Dec 15 '12 at 14:49
add comment

The variations of this question that I've seen fall into two types:

  • Time is very carefully quantized (e.g. every day at noon they gather to say something if possible), so that it is possible to make inferences of the sort "Nobody said anything during the last unit of time".
  • The knowledge that the other people couldn't say anything with the knowledge immediately given is all that one needs, so one can patiently wait long enough that any reasonable person would have given an answer if they could to gain that information.

The question you state, I believe, is a bad one (at least as translated). Hesitation is, as you put it, too vague; without knowledge of how quickly the other people can make deductions (and knowledge of how quickly they think you can make deductions, et cetera), it becomes difficult to impossible to make reliable statements as the number of people grows.

share|improve this answer
    
Is it suitable to model the hesitation in terms of rounds? Just like the Muddy Children Puzzle and the way mentioned in the comment given by Eric Stucky, the teacher can broadcast the following question over and over: What is the color of your hat? If the modeling is OK, then what we should prove may be reduced to (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". So, what is your opinion? @Michael Greinecker –  hengxin Dec 15 '12 at 13:53
add comment

These type of questions are analyzed in game theory/microeconomics and typically rely on probability filtrations (discrete or continuous time information updating) or algebraic topological methods. The hesitation, as suggested by comment above, is updated information over time; and it results from inaction as a different information set would have led to action. This is surprisingly hard stuff, but analyzing a similar problem made someone from my school his year's job market superstar (Sherlock Holmes - Dr. Moriarity puzzle, using hierarchies of beliefs)

This isn't truly helpful to help you see how to model your particular problem. But you seem genuinely interested in understanding this better, and googling any of the above keywords (also Repeated Games; Bounded Rationality) should help.

P.S.: The muddied children problem, say, would probably be modeled using hierarchies of beliefs, which are sequences of reasoning "You know x", "I know that you know x", "You know that I know that you know x"...., which are then (often) examined for fix points.

share|improve this answer
    
Is there some working paper or something like that about the hierarchies of belief stuff in and the Holmes -Moriatity puzzle? –  Michael Greinecker Dec 15 '12 at 4:45
    
@MichaelGreinecker I know a paper about the hierarchy of knowledge (similar to but different from belief in subtle ways), including common knowledge, in a distributed environment written by Joseph Y. Halpern and Yoram Moses. This paper was awarded the Godel Prize (maybe the most honorable prize in theoretical computer science) in 1997. You can check Godel Prize for the announcement and the paper. –  hengxin Dec 15 '12 at 12:59
    
@hengxin Thank you, but I mostly know the literature. I was more interested what the paper on the Holmes-Moriarty situation does that is not covered by standard material. –  Michael Greinecker Dec 15 '12 at 13:01
    
@MG: it might be standard now - guy graduated in the late '90s, and is now teaching at Northwestern I think. This gets a it close to home, but name is Marciano Siniscalchi (if I spelled that right), and it was - from memory! - his job market paper. I know Robert Wilson still writes frequently papers in this area, vaguely; but for what I remember to be the HM puzzle, that was Marciano. –  gnometorule Dec 15 '12 at 16:38
    
@hengxin: Yes, Common Knowledge obviously is another big word in this area; and I remember Halpern. I didn't do research in game theory myself, so only know it from class work and talks I watched, etc. –  gnometorule Dec 15 '12 at 16:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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