# Knowledge about common knowledge (hats puzzle)

$n$ villagers wear either black or white hats. The truth is that all the hats are black, but this is not known. They sit in a line, so that each villager can see all the hats in front of them, but not the hats behind them. If a villager ever deduces the fact that all the villagers (including himself) know that their hats are black, then he leaves at noon on the next day (without anyone in front noticing).

One day, a light is installed where all villagers can see it. The light remains on as long as at least one villager in the line has a black hat.

Will anyone ever leave? If so, after how long?

• I assume it is sacrilegious for these villagers to communicate under the Sacred Light? – Hackiisan Sep 23 '15 at 7:32
• And all villagers know how many villagers there are and what their place in line is? – Warkgnall Sep 23 '15 at 7:37
• @Warkgnall Yes, they know. All knowledge apart from the hat colors and departures is common knowledge. – ghosts_in_the_code Sep 23 '15 at 7:40
• Can they communicate with one another? – S.C. Sep 23 '15 at 7:41
• @SeraphCheng No, otherwise they would just leave on Day 1. – ghosts_in_the_code Sep 23 '15 at 7:42

I think that only for $n=1$ a villager can leave because that is the trivial case. In any other case the villager at the back of the line can never deduce his own color, even for $n=2$.

• I was trying to find a puzzle similar to the answer by @f" in puzzling.stackexchange.com/questions/22500/… Why does that puzzle work and not mine? – ghosts_in_the_code Sep 23 '15 at 7:49
• The major difference is that f"'s answer says that someone can leave when they know their own color. You require that someone can leave when everyone knows their color – Ivo Beckers Sep 23 '15 at 7:51
• I don't think it works even in the variation where "someone can leave when they know their own color". The fundamental problem is that the villagers in front of the line can't see the hat colours behind them. Because of this, for the $n = 2$ case, the first villager still can't leave on day 1 if the second villager's hat is white. – Hackiisan Sep 23 '15 at 8:19
• @Hackiisan. I actually think that it would work in that case. There are only three scenarios: BB, WB and BW. In the case of WB, the one in the back will leave in 1 day and the light will go off and the next day the first one knows he's white. In the other two cases the first one will know after one day that he's black for the fact that the light didn't went off. After that the second one can leave the day after because you then have a $n=1$ case – Ivo Beckers Sep 23 '15 at 8:32
• You are right! I had discounted the information of the WB case right off the bat =) – Hackiisan Sep 23 '15 at 8:41

I am very frequently very incorrect when it comes to Blue Eyes puzzles, but since you must make deductions about your hat color based on the light and the light cannot go out until someone leaves and no one can leave until everyone knows their hat color, I postulate that for $n > 1$ no one will ever leave. I swear I typed most of this up before Ivo posted his similar answer.

• I think you mean "$n > 1$"? Anyway, I agree so far. It would probably be more interesting to think about the case where someone can leave if they know their own colour, but even then... – Hackiisan Sep 23 '15 at 7:52
• Yes, thank you. I really need to go to sleep. – Warkgnall Sep 23 '15 at 7:57

Even if they don't all have to gain knowledge and leave at the same time, nobody can leave for $n>1$ because your condition for leaving is that an individual knows that everyone is wearing a black hat. How can the person at the front ever work out if he is wearing a white hat or if there are any white hats anywhere behind him? Consider the BW case. The person at the back can only see a white hat so he knows he is wearing a black hat but cannot leave the line because at least one person is not wearing a black hat, so the light stays on. The person at the front would therefore be wrong to assume that he is wearing a black hat however long he waits.