A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads (i.e., at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those(and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat.

FOLLOW UP

Prove that your solution is correct.

**My initial thoughts:**

I thought this involves with recursion. Let us denote P(n,c) as the number of days it takes to remove c hats from n people. We start with simple case:

- P(1,1) = 1 since if there is only 1 people on the island and he knows there is one people who wears a hat, then that must be himself. So he will remove his hat on day 1.
- P(2,1) = 1 since the guy who wears a hat sees the other does not wear a hat, and he knows there is one people who is wearing a hat, so he can conclude that he wears the hat. So he will remove his hat on day 1.
- P(n,1) = 1 since the guy who wears a hat sees the other n-1 people do not wear a hat, following the same logic of above, he will remove his hat on day 1.
- P(2,2). This is where I’ve got wrong. I thought the people know how many people wear a hat. So I conclude P(2,2) = 1. Whereas they only know “at least one people wears a hat” but not the exact number.

**Solutions:**

- P(2,2) = 2. Denote these two people as A and B. Let us pretend we are people A.
- We see B wears a hat.
- We know at least one people wears a hat. In this senario, we are not sure whether c = 1 or 2.
- However we know if c = 1, then B sees us not wearing a hat, so B will figure out himself is wearing a hat then he will remove his hat on day 1.
- We wait for one day and we surprisingly notice, on day 2, B is still wearing the hat. So we ask, why? That must only because we are also wearing the hat and B is also not sure whether c = 1 or 2. Therefore, c = 2 and we and B are all wearing the hats. So both of us remove our hat on day 2.

- P(n,2) = 2. Denote those two people who wear hats as A and B and let us be A. So we see n – 2 people without a hat and one people (B) wears a hat. Again, we are not sure whether B is the only people who wears a hat or B and we are all wearing hats. So we wait for one night and we see B is still wearing a hat. Therefore we know c = 2 and B also knows. B and we will remove our hats on day 2.
- P(n,3) = 3. Denote those three people who wear hats as A, B and C and let us be A. So we see n – 3 people without a hat and 2 people (A and B) wears a hat. We know if c = 2, it takes 2 days for A and B to remove their hats, so we wait for 2 days. On day 3, we see A and B still wearing hats, so we know c = 3 and we will remove our hats on day 3.
- P(n,c) = c. Prove by induction. Let us assume P(n,c) = c is true and look at P(n,c+1). In this case, we see c people wearing hats. We know, by inductive hypothesis, that it takes c days for them to remove their hats, if there are exactly c hats. After c days, we see them still wearing hats, so we know ourselves also wearing a hat. Hence on day c+1, everyone with hats will remove their hats. That is, P(n,c+1) = c+1. By induction, P(n,c) = c holds.