**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