# Brain Teasers/Smurfs and Gargamel

Gargamel has captured 100 Smurfs. Feeling confident he proposes the following game:

He will exchange the white hats of an undefined number of smurfs with red hats. No smurf knows his own color. All smurfs can see each other, but they have no other means of communication. Then, each Smurf (order selected by Gargamel) should say the color of his hat (loudly so that everyone can hear it). If it is correct, then he lives, otherwise he dies. After a short discussion the smurfs accept. They know that the first Smurf to be chosen might die, but all 99 other smurfs will survive.

## Answer #1

The smurfs can sort themselves by following a simple rule.

One smurf starts forming a line; he has either White or Red. Second smurf stand behind him. They may have same or different color. Other smurfs go to the line one by one, and each one find in the middle of two color group. If all have same color, he stands behind the end of the line. This way, they will be able to group themselves into two color group. When a smurf is called upon, it can say the color of the hat that a smurf is wearing right in front of him. He will be correct unless he is the first one starting a different color group (let call him S). When the smurf finds himself in the middle of different color group, he cannot know what the color of his hat is. But a smurf in the last of the line may rearrange his position. If he cut into the before S, S know S is the first in the new color group, otherwise, he is the end of first color group.

## Answer #2

Before the game start, the smurfs set a rule in following way.

Count how many smurfs are wearing white hat. If they see even number of white hat, say WHITE, otherwise say RED.

There are two cases.

Case 1: Gargamel replaces hats of even number of smurfs with red hats.

- 1a: If a smurf sees odd number of white hats, he is wearing white
- 1b: If a smurf sees even number of white hats, he is wearing red

Case 2: Gargamel replaces hats of odd number of smurfs with red hats.

- 2a: If a smurf sees odd number of white hats, he is wearing red
- 2b: If a smurf sees even number of white hats, he is wearing white

The problem is they do not know how many smurfs are actually wearing red hats.

One smurf is called up on. He wears either white or red, and he sees either even number of odd number of white hats. Based on the rule, he answers, and he is either right or wrong.

Case 1: The smurf sees even number of white hats

- He says WHITE and he is RIGHT: This means there are odd number of white hats. This is case 2b. So EVEN = WHITE, ODD = RED.
- He says WHITE and he is WRONG: So, there are even number of white hats, which is case 1b. Now all other smurfs switches to opposite answer. EVEN = RED, ODD = WHITE.

Case 2: The smurf sees odd number of white hats

- He says RED and he is RIGHT: Case 2a.
- He says RED and he is WRONG: Case 1a. Now everyone switch to opposite answer.