How long does it take to remove c ‘magical’ hats from n people

Problem:

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. 

Solution:

Consider a person A wearing the hat. A shall see C-1 hats as no one can tell other that he has a hat.

Let us denote P(n,c) as the number of days it takes to remove c hats from n people.

Case 1 - When c = 1
Also, Genie has said that atleast 1 man will have a hat, so at min will be 1.

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.

Case 2 - When c = 2
Now consider the case when C = 2. The two men with hats see one hat, and are unsure whether c = 1 or c = 2 They know, from the previous case, that if c = 1, the hats would be removed on Night #1 Therefore, if the other man still has a hat, he must deduce that c = 2, which means that he has a hat Both men would then remove the hats on Night #2

• P(2,2) = 2. Denote these two people as A and B. Let us pretend we are people A.
  
  1. We see B wears a hat.
  2. We know at least one people wears a hat. In this senario, we are not sure whether c = 1 or 2.
  3. 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.
  4. 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 them remove their 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.

Thanks

Answer:

              after c days, where c is number of magical hats.

Reference :
                    tian runhe,