Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Remove 'c' hats from 'n' people

Puzzle: N people in a room are wearing C hats where C > 0.
A person wearing the hat cannot know that he is wearing a hat but can see the others if they have hat or not.
If hat can be removed only at 12:00 noon, how many days it would take for all people to get rid of C hats?

Solution: Let us say C = 1.
The only person wearing the hat can see that no one else is wearing a hat and he also knows that C > 0
Hence he can easily conclude that the only person wearing the hat is himself and C = 1.
So he can remove the hat on first day itself.

For C = 2, there will be two people wearing hats (Let us call them Jack and Jill).
Both Jack and Jill see the other person wearing the hat and since they only know C > 1 (not the exact value of C),
each one will assume that they themselves are not wearing hat, thinking C is indeed 1.
So both of them will not remove the hat on first day.
Let us see from Jack's perspective on second day.
On seeing that Jill is still wearing her hat, Jack comes to realize that she did not remove her hat
because she was also seeing someone with a hat. But Jack can see that there is no one except Jill that is
wearing a hat. This means that Jill must be seeing Jack wearing a hat and so he should be removing his hat on day 2.

The same argument applies to Jill and she also realizes on day 2 that she is also wearing a hat because of which Jack
assumed on day 1 that he was not wearing any hat.
So she also removes her hat on day 2 itself.

For C = 3, three people are wearing hats.
By same logic as C=2, they do not remove hats either on day 1 or day 2.
On day 3, each one of them realizes that the 2 hat wearers they see did not remove their hats on day 2 because
they were also seeing two hat wearers on day 2.
This will help those 3 people understand that they are themselves putting a hat too and that C=3.
So all 3 would remove their hats on day 3.

Continuing in this fashion, for C hats, the day on which all hats will be removed is day C.

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: