6
$\begingroup$

10 people in a circle and they are each given a red or blue hat. They can see each other's hats, but not their own. They are told that at least one red hat was assigned (we know that 3 red and 7 blue were assigned). They can't talk to each other. They are asked, "put your hand up if you know you are wearing a red hat" repeatedly and they have time to respond before being asked again. How many times do they need to be asked before those wearing a red hat have figured it out?

The answer to the question is as follows... If only one person was wearing a red hat, then they would see only blue hats on the others and on the first time of asking, would raise their hand as at least one red hat was assigned. If there were two people with red hats, consider one of them. They will see that the person wearing the other red hat didn't put up his hand on the first time of asking, can see the eight others are wearing blue, so deduces he is wearing red. Then both red hat people raise their hand on the second time of asking. With three red hats, consider one of them. They notice that both of the red hat people they can see don't raise their hand on the second time of asking, can see the other seven are wearing blue, so deduces he is wearing red. Then all three of them raise their hand on the third time of asking.

He's my question! The line in the question "they are told that at least one red hat was assigned" seems redundant because everyone in the circle can see a red hat since three were assigned. Yet without this line, the basis of the solution for the case "if only one person was wearing a red hat" is removed and the solution breaks down. Can someone clear this up for me please? Thank you!

$\endgroup$
2
$\begingroup$

Given that there are several hats, they all see at least one red hat, and hence they all know that there is at least one red hat. We could thus say that there is mutual knowledge that there is at least one red hat.

Even more, if there are three red hats (or more), then it is also true that they all know that they all know that there is at least one red hat, since they all know that everyone can see at least one red hat. This we could call shared knowledge

Neither mutual not shared knowledge is the same as common or public knowledge though: Common knowledge is the kind of knowledge that can go any number of levels deep. For example, if it is common knowledege that there is at least one red hat, then $A$ knows that $B$ knows that $C$ knows that $D$ knows that there is at least one red hat.

Now, if in a public setting the people are told that there is at least one red hat, then that becomes common knowledge, because they don't just all hear it, but given that this was said in a public setting, they also all know that they all heard it, and they also know that they all know that they know that ... they heard it.

However, if they are not told that there is at least one red hat, then we no longer have such common knowledge: with three hats we have the mutual knowledge that there is at least one hat (because they all see at least two red hats), and there is also the shared knowledge that there is at least one red hat (since they all know of any other person that that person must be seeing at least one red hat), but there is no common knowledge that there is at least one red hat: indeed, with exactly three red hats, and with $A$, $B$, and $C$ being the three different people wearing a red hat, $A$ does not know that $B$ knows that $C$ knows that there is at least one red hat.

Why does $A$ not know this? Well, $A$ looks around, and sees two red hats: on $B$ and on $C$. So: $A$ knows that $B$ knows that there is at least one red hat, since $A$ knows that $B$ can see $C$'s red hat. Likewise, $A$ knows that $C$ knows that there is at least one red hat ($B$'s!). Also, given that $A$ has a red hat, $b$ knows that $C$ knows that there is at least one red hat ($A$'s!). But, $A$ does not know that $B$ knows that $C$ knows that there is one red hat, because $A$ thinks: "Well, I may not have a red hat, and if that is so, then $B$ would be seeing exactly one red hat ($C$'s!), and so $B$ will say "Well, if I don't have a red hat, then $C$ is not seeing any red hats at all, and so $C$ does not know that there is at least one red hat", and so $B$ does not know that $C$ knows that there is at least one red hat". Again: $C$ of course know that there is at least one red hat, and $A$ knows that $C$ knows that there is at least one red hat, and $B$ knows that $C$ knows there is at least one red, but $A$ does not know that $B$ knows this about $C$.

Now, why is this important? Well, as you say, $A$ knowing that $B$ knows that $C$ knows that there is at least one red hat forms the very 'basis' of the reasoning: if no one raised their hand the first two times, then $A$ says:

"Now, wait a minute, I know that $B$ knows that $C$ knows there is at least one red hat, and so if I don't have a red hat, then given that the first time around no one raised their hand, $B$ should have realized to have a red hat, for $B$ should have thought "Well, I know that $C$ knows there is at least one red hat, and so if I don't have a red hat, then $c$ is the only one with a red hat, and so $C$ should have raised their hand the first time, but $C$ did not, and so I in fact do have a red hat" ... but $B$ did not raise their hand the second time around, and so I ($A$) in fact do have a red hat!"

So you see how important it is for $A$ to know that $B$ knows that $C$ knows that there is at least one red hat: $A$ uses that bit of information right at the very start. But if no one would have made a public announcement that there is at least one red hat, then, as explained above, $A$ would not know that $B$ knows that $C$ knows that there is at least one red hat.

By the way: it is extremely hard to ever get common knowledge in the real world if you think about it: I would have to know that you were paying attention when the public announcement was made ... and that you weren't deaf, and that you know of all the others that they aren't deaf and were actually paying attention, and we all need to know this of each other .. and know that .. and know that. In other words, there already needs to be a lot of public knowledge about people paying attention and not being deaf in order for the public announcement to become common knowledge about whatever the announcement was about. Moreover, if you know want to exploit this kind of common knowledge in any kind of reasoning, we also need to have the common knowledge that we are all capable of this kind of reasoning any number of levels deep (or whatever number of levels is needed for the issue at hand) ... but how would I know this? In fact, in real life I would suspect most people to get completely bewildered in their logical thinking if it goes any deeper than 2 levels. So, if I were to play this in real life with a real group of people, I wouldn't be sure at all that I would have a red hat if I see only two red hats around me and no one raised their hand any of the first two times.

$\endgroup$
  • $\begingroup$ Brilliant. Thank you. $\endgroup$ – Kristof Arnaldo Jul 22 at 21:25
  • $\begingroup$ @KristofArnaldo ... and that was before my edit to make it more clear yet :) ... well, at least I hope I made it more clear ... $\endgroup$ – Bram28 Jul 22 at 21:26
5
$\begingroup$

It's called meta information. Basically, it boils down to “I know that you know, what I know. But do you know that?”.

So if there is only one red hat and the intel about red hat was not given. I am looking at the person with red hat and think myself “I know that there is a red hat, but I don't know if the person in red hat knows about it”. With two hats, the chain of thought is a step longer: “I don't know if person in red hat #1 knows that person in red hat #2 knows that there is a red hat”.

With intel that not only everyone hears, but also everyone hears that everyone hears and so on (so called common knowledge), this ladder of meta-information can never end, so eventually everyone will guess their red hat. However, if everyone is given this intel secretly from everyone else, this no longer works.

P.S. There is an interesting speculation about meta-information and flirting/euphemisms. If man asks a woman to go home and listen to his collection of medieval music, they both understand that man suggests a night together. However, if a man asks woman directly, woman can be dis-pleasured and likely to say no. The idea is that meta-informational decay “I know that he suggests sex, but I am not sure if he knows that I know that” allows her to keep face and bail out if necessary (“I didn't know!”), whereas common knowledge (“Come with me for sexy time!”) doesn't leave room for that.

$\endgroup$
  • $\begingroup$ Thanks for your answer. You seem to be saying that it is necessary to include the line "they are told that at least one red hat was assigned" because then people gain the meta information. However, my point is that it is already obvious to all the people that at least one red hat has been assigned because they see either two or three red hats, and each knows that the rest can see at least two red hats, therefore it can't be any use to include this line. $\endgroup$ – Kristof Arnaldo Jul 22 at 17:07
1
$\begingroup$

In this kind of question the central idea is "who knows what when". You must distinguish between what "we know" and what the participants know at each stage.

The information "we know there are three red and seven blue" does not change the argument from the point of view of the participants. No one will raise his hand on the first round since each person sees at least one red had (some see two and some see three). The argument continues.

You could remove your confusion by rephrasing

How many times ... (we know that 3 red and 7 blue were assigned)?

as

When will the red hats declare themselves if 3 red and 7 blue are assigned?

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