<p>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 $&gt; k$ white hats can tell that they all have white hats <em>without any hesistation</em>, but it proves that $k+1$ people with $(k, &gt;k+1)$ hats can tell <em>with</em> hesitation.</p>

<p>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,&gt;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".</p>

<p>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?</p>

CC BY-SA 3.0
2012-12-17T14:34:34.523Z
2012-12-17T14:34:34.523Z
usul
<p>The following question was first presented in <a href="https://math.stackexchange.com/q/258692/51434">MATHEMATICS of StackExchange</a>. With a simple description at first sight, it has far-reaching consequences on plenty of recent and advanced theories, such as <a href="http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29" rel="nofollow noreferrer">Knowledge and Common Knowledge</a> 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. </p>

<p><strong>Below is the original source from MATHEMATICS for your convenience.</strong></p>

<p>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.</p>

<blockquote>
  <p><strong>Hat-Guessing Puzzle:</strong> 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 <em>white</em> hat, while the other two <em>black</em> 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. <strong>After a hesitation</strong>, they say that "the hat on my own hat is white" with one voice. The question is how do they make it?</p>
</blockquote>

<p>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$:</p>

<ul>
<li>When $n$ is 2, the situation is trivial because there is only one black hat. If <em>I</em> am wearing the black one, then the other person can tell that the hat on his head is white, <em>without any hesitation</em>. However, he does hesitate. Contradiction. </li>
<li>Suppose that we have solved the puzzle with $n = k$.</li>
<li>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, <em>without any hesitation</em>. Contradiction.</li>
</ul>

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

<blockquote>
  <p><strong>My Problem:</strong> How to <em>formally</em> model the <strong>hesitation</strong> in the hat-guessing puzzle?</p>
</blockquote>

<p><strong>Now, I will give an account of my confusion (after the discussion with MATHEMATICS users).</strong></p>

<ol>
<li>Is it suitable to model the hesitation in terms of <strong>rounds</strong>? Just like the <a href="http://sierra.nmsu.edu/morandi/coursematerials/MuddyChildren.html" rel="nofollow noreferrer">Muddy Children Puzzle</a>, the teacher can broadcast the following question <em>over and over</em>: 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, <em>and</em> in the $n$th round, they all say it is white simultaneously"?</li>
<li>I think the statement "If someone is wearing the black hat" given in the original proof is based on the <em>unjustified</em> 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", <em>before</em> proving the thing in the $n$th round? If it is, how to prove the $n-1$ part?</li>
</ol>

<p>Thank you very much for any suggestions.</p>

CC BY-SA 3.0
2012-12-17T19:09:49.417Z
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.)
Novak
<lo.logic><dc.distributed-comp><gt.game-theory><puzzles>
How to formally model the “hesitation” in the hat-guessing puzzle and prove it by mathematical induction?
hengxin
# How to formally model the “hesitation” in the hat-guessing puzzle and prove it by mathematical induction?

(Asked by: username_0 on 2012-12-17)

The following question was first presented in [MATHEMATICS of StackExchange](https://math.stackexchange.com/q/258692/51434). 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](http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29) 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](http://sierra.nmsu.edu/morandi/coursematerials/MuddyChildren.html), 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.

**Tags:** lo.logic, dc.distributed-comp, gt.game-theory, puzzles
> **Comments:**
> **username_1**: 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.)  

---

## 1 answers

### Answer by username_2 on 2012-12-17. Score: 2

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?


---

