Solution: People`s hat puzzle on Island..(awesome logic)

Tweet

Solution: This problem seems hard, 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 hat. The two men with hat see one crown, and are unsure where c = 1 or c = 2. They know, from the previous case, that if c = 1, the crowns 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 crown 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, … Proof by Induction Using induction to prove a statement P(n) If (1) P(1) = TRUE (eg, the statement is true when n = 1) AND (2) if P(n) = TRUE -> P(n+1) = TRUE (eg, P(n+1) is true whenever P(2) is true). THEN P(n) = TRUE for all n >= 1. Explanation: - Condition two sets up an infinite deduction chain: P(1) implies P(2) implies P(3) implies ... P(n) implies P(n+1) implies .... - Condition one. (P(1) is true) ignites this chain, with truth cascading off into infinity. Base Case: c = 1 (See previous page). Assume true for c hats. Eg, if there are c hats, it will take c nights to remove all of them. Prove true for c+1 hats. Each man with a hat sees c hat, and can not be immediately sure whether there are c hats or c+1 hats. However, he knows that if there are c hats, it will take exactly c nights to remove them. Therefore, when c nights have passed and everyone still has a hats, he can only conclude that there are c+1 hats. He must know that he is wearing a hats. Each man makes the same conclusion and simultaneously removes the hats on night c+1. Therefore, we have met our principles of induction. We have proven that it will take c nights to remove c hats. POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

  Adjust the font size     Reset ↕

Solution:

This problem seems hard, 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 hat.
The two men with hat see one crown, and are unsure where c = 1 or c = 2. They know, from
the previous case, that if c = 1, the crowns 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 crown 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, …
Proof by Induction
Using induction to prove a statement P(n)
If (1) P(1) = TRUE (eg, the statement is true when n = 1)
AND (2) if P(n) = TRUE -> P(n+1) = TRUE (eg, P(n+1) is true whenever P(2) is true).
THEN P(n) = TRUE for all n >= 1.

Explanation:
- Condition two sets up an infinite deduction chain: P(1) implies P(2) implies P(3) implies ...
P(n) implies P(n+1) implies ....
- Condition one. (P(1) is true) ignites this chain, with truth cascading off into infinity.
Base Case: c = 1 (See previous page).
Assume true for c hats. Eg, if there are c hats, it will take c nights to remove all of them.
Prove true for c+1 hats.
Each man with a hat sees c hat, and can not be immediately sure whether there are c hats
or c+1 hats. However, he knows that if there are c hats, it will take exactly c nights to remove
them. Therefore, when c nights have passed and everyone still has a hats, he can only conclude
that there are c+1 hats. He must know that he is wearing a hats. Each man makes the
same conclusion and simultaneously removes the hats on night c+1.
Therefore, we have met our principles of induction. We have proven that it will take c nights
to remove c hats.

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION