Thursday, 11 October 2012

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

  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

Click Here To add Comment

Your feedback is always appreciated.
I will try to reply to your queries as soon as time allows.
Please do not spam Spam comments will be deleted immediately upon our review.

Blogger Widgets

Recent comments

Send Quick Massage

Name

Email *

Message *

Recent posts

Total Pageviews