## Friday, April 1, 2011

### Another Hat Color Problem

The Island - One puzzle a day - Puzzle Buddies
100 men were captured and prisoned in an island.the island is guarded by a genie.
Everyday genie takes prisoners out.genie places them in a circle so that everyone can see each other,then all the prisoners are blindfolded. Genie then places hats on prisoners head,some of them are white and some of them are red.their folds will be opened after the genie places hats.

On genie's command the prisoners with white hat should step forward.They will be set free if only the men with white hat steps forward.
If any one without white hat steps forward,genie executes all of them
If no one steps forward,the same game will be repeated the next day,if the game is repeated,each prisoner will get the same hat that they got on the first day

Prisoners are not allowed to communicate with each prisoner.if communicated all of them will be executed.prisoners are not allowed to see the hat that they are wearing
At least one white hat is given, and all prisoners are aware of this.

how many days did it take for the prisoners to get out if genie gave "n" white hats where 1<=n<=100, and how did they do it?

Solution:
Let us say there is one white hat,the answer is simple.the prisoner wearing white hat sees no other white hat and he steps forward.
Now let us take two white hats.No body comes forward on the first day,because the prisoners wearing white hat sees one white hat.On the second day since no body has come forward they both know there must be two white hats and one he can see and other must be his own.so they come forward on second day.
Similarly if there are three white hats they will not come out on second day.it will take three days.
and so on..for "n" it will take n days