Puzzle: A bunch of men are on an island. A genie comes down and gathers everyone to-gather 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.
Ans:
Ans:
so let’s simplify it by looking at specific cases.
Case c = 1: Exactly one man is wearing a hat.
Assuming all the men are intelligent, the man with the hat should look around and realize
that no one else is wearing a hat. Since the genie said that at least one person is wearing
a hat, he must conclude that he is wearing a hat. Therefore, he would be able to remove it
that night.
Case c = 2: Exactly two men are wearing hats.
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
Case General: If c = 3, then each man is unsure whether c = 2 or 3. If it were 2, the hats would be removed on Night #2. If they are not, they must deduce that c = 3, and therefore they have a hat. We can follow this logic for c = 4, 5, ...
Case c = 2: Exactly two men are wearing hats.
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
Case General: If c = 3, then each man is unsure whether c = 2 or 3. If it were 2, the hats would be removed on Night #2. If they are not, they must deduce that c = 3, and therefore they have a hat. We can follow this logic for c = 4, 5, ...
There are c hats so it will take c nights to remove all of them.
No comments:
Post a Comment