# Hats Off to the Ministers

#### Gokul43201

Staff Emeritus
Gold Member
A king wants to get rid of some of his ministers. So he calls them up and tells them his plan for the following day. "You will all be made to stand in a stright line, all facing the same way, along the direction of the line" he says. "I will randomly put hats on your heads which will be one of 2 colors : black or white. Then, starting at one end of the line (from the minister who can see all the others in front of him) I will ask each of you the color of his hat. Those that answer correctly will be spared."

The ministers all convene after this announcement to formulate a strategy that will minimize the number of deaths. What would be the best strategy and what is maximum number of deaths it allows ?

NOTE the following :

1. The first minister to be questioned can see all the hats except his own. The next can see all but 2, and so on...

2. When questioned, the minister is only allowed a one word answer which must be "black" or "white" and no special intonation is allowed.

3. Every minister can hear the answers provided by those preceding him.

Related General Discussion News on Phys.org

#### jcsd

Gold Member
If each minister says the colour of the hat of the minister infront of him then the maximum number of deaths is one.

#### Gokul43201

Staff Emeritus
Gold Member
But then, every minister gets his own hat color wrong. Remember, he is allowed only one answer.

#### Pattielli

Does this have anything realating to worst case best case in analyzing an algorithm ?
Anything related to probability ?

Give me hints, I don't know how to answer...

#### Hurkyl

Staff Emeritus
Gold Member
The best strategy can save all but one of the ministers. Try starting with simple cases and see if you can work out a general strategy.

#### Gokul43201

Staff Emeritus
Gold Member
Think of how an earlier minister can convey information about the hats to a later minister. What is the maximum information that can be conveyed by a single bit ?

How many colors are there ? Now think of residues modulo this number. How many sets of congruent numbers does this divide the N into ? What common name is given to these sets ?

No more hints for now...let the people think !

#### Gokul43201

Staff Emeritus
Gold Member
just one clarification, perhaps...

jcsd's suggested solution will be a possible strategy if implemented as follows :

Every alternate minister tells the color of the hat in front of him. These in-between ministers tell their own hat color, since they know this from the previous minister. So half the ministers will get it right. The other half - the ones doing the service - can only be right by luck. So this strategy definitely saves half the lives.

The optimal strategy does better, as Hurkyl suggests.

#### jcsd

Gold Member
God I can be so stupid so,mthimes.

This one is really hard, but obviously there can be no strategy assured of saving the first minister, so it is dependent on what the first minister says

Stragetegy for 3:

If the first minster says 'black' if both hats are the same and 'white' if they are not.

Strategy for 4:

If the last two minsters have the same coloured hats the first minster will tell the second minster the correct colour of his hat. If they are different the first minster will tell the second minister the incorrect colour of his hat.

I'll work out a general strategy later, but I've got a baby screaming in my ear at the moment.

Startegy for 5

The first minster will say the corrcet colour of the third minster's hat if the second minster is wearing a black hat and the last two minsters have the same coloured hats or if the second minsiter has a white hat and the last two misnisters have a different hat. The first minster will say the incorrect colour of the third minsters hat if the second minister's hat is black and the last two minster''s have differnt coloured hats or if the second minsiter has a black hat and the last two minister's have different coloured hats.

Last edited:

Three hats

http://www.greylabyrinth.com/Puzzles/puzzle007.htm [Broken] is a similar problem.

Last edited by a moderator:

#### Gokul43201

Staff Emeritus
Gold Member
I'm not sure Hurkyl's advise - I guess it worked for him - will be particularly helpful to the average problem solver. I find it hard to imagine that the general solution can be found by identifying a pattern within the simpler cases...but this may just be a limitation of my imagination.

Also, "three hats" is a very different problem, and (in my opinion) easier to crack.

EXTRA HINT : (This obviates the previous hint) Think "even" and "odd" !!

Last edited:

#### jcsd

Gold Member
Gokul43201 said:
I'm not sure Hurkyl's advise - I guess it worked for him - will be particularly helpful to the average problem solver. I find it hard to imagine that the general solution can be found by identifying a pattern within the simpler cases...but this may just be a limitation of my imagination.

Also, "three hats" is a very different problem, and (in my opinion) easier to crack.

EXTRA HINT : (This obviates the previous hint) Think "even" and "odd" !!
Yes, I'm defintely struggling working from the simpler cases up, though I've got a stategy for 5 , it's seems to get exponentially hardier the more people are intoduced and I haven't found a way of generalizing it yet.

I imagine the solution involves a self-recontsructing code, unfortunately discrete maths has always been one of my weakest areas.

#### Gokul43201

Staff Emeritus
Gold Member
Let me assure you that the simplicity of the solution is the reason I rate this puzzle among the cleverest of them.

Gokul43201 said:
Also, "three hats" is a very different problem, and (in my opinion) easier to crack.

EXTRA HINT : (This obviates the previous hint) Think "even" and "odd" !!
The first minister need only give the high-bit or low-bit arbitrary signal for the initial presentation of an arbitrary even or odd total-count condition of the arbitrary color. Then, only the first minister will die, no matter how many total ministers there are, because each minister down the line can simply subtract the number of hats of the arbitrary color that have up until then been spoken for and then compute his own hat color from the sacrificial testimony of the first minister.

For example, it was arbitrarily decided (as the ministers met to agree on the strategy) that the first minister is to say "white" if the number of total white hats he can see is even. If the first minister does say "white" (meaning, he sees an even number of white hats in front of him), then the second minister, being able to easily count the number of white hats in front of himself, can thereby compute whether his own hat must also be white in order to satisfy the condition for evenness. If the count is already even without his hat, then his hat must be black. If the count is odd without his hat, then his hat, conversely, must be white.

If the second minister then announces his hat as white, the third minister at that point knows that the remaining number of white hats must be shifted from even to odd. Conversely, if the second minister answers "black," the third minister then knows that the remaining number of white hats must still be even. With the same simple arithmetic, the third minister can then answer correctly the color of his own hat, just as the second minister did, and at the same time signal the correct hat color for the next minister down the line — also as the second minister did, respectively, for him.

This can continue indefinitely down the line, no matter how many ministers there are.

Hitssquad with the slam dunk point.

Last edited:

#### jcsd

Gold Member
Damn you hit squad!! the answer seems so simple now I know it! it was pretty simliar to those self-reconstructing codes too!!!!!!!!

#### Gokul43201

Staff Emeritus
Gold Member

Thank you, and thanks for the puzzle, Gokul.

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving