What is the best strategy for the ministers to survive in the king's hat game?

  • Thread starter Gokul43201
  • Start date
In summary, the conversation discusses a problem in which a king wants to get rid of some of his ministers by randomly assigning black or white hats to them. The ministers must answer the color of their hat correctly to be spared. The discussion focuses on finding the best strategy to minimize the number of deaths, with hints provided to guide the thinking process. The solution involves thinking in terms of even and odd numbers, and ultimately results in a simple solution where only the first minister will die.
  • #1
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,220
24
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.
 
Physics news on Phys.org
  • #2
If each minister says the colour of the hat of the minister infront of him then the maximum number of deaths is one.
 
  • #3
But then, every minister gets his own hat color wrong. Remember, he is allowed only one answer.
 
  • #4
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...
 
  • #5
The best strategy can save all but one of the ministers. :smile: Try starting with simple cases and see if you can work out a general strategy.
 
  • #6
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 !
 
  • #7
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.
 
  • #8
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.

eited to add:

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:
  • #9
Three hats

http://www.greylabyrinth.com/Puzzles/puzzle007.htm [Broken] is a similar problem.
 
Last edited by a moderator:
  • #10
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:
  • #11
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.
 
  • #12
Let me assure you that the simplicity of the solution is the reason I rate this puzzle among the cleverest of them.
 
  • #13
Hitssquad with the point

Gokul43201 said:
Also, "three hats" is a very different problem, and (in my opinion) easier to crack.
I now agree on both counts. I hadn't thought hard about this problem.



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:
  • #14
Damn you hit squad! the answer seems so simple now I know it! it was pretty simliar to those self-reconstructing codes too!
 
  • #15
Nice one hitssquad
 
  • #16
Thank you, and thanks for the puzzle, Gokul.
 

What is "Hats Off to the Ministers"?

"Hats Off to the Ministers" is a phrase used to express admiration or praise for someone's achievement or accomplishment. It can also be used as a way to show respect or appreciation for a person's hard work or dedication.

Where did the phrase "Hats Off to the Ministers" originate from?

The phrase "Hats Off to the Ministers" is believed to have originated from the tradition of taking off one's hat as a sign of respect or greeting. It has since evolved to become a colloquial expression used to show appreciation or admiration for someone's success.

How is the phrase "Hats Off to the Ministers" used in modern society?

In modern society, the phrase "Hats Off to the Ministers" is commonly used in congratulatory or celebratory contexts. It can also be used sarcastically in a mocking or ironic manner to criticize someone's actions or decisions.

Are there any other variations of the phrase "Hats Off to the Ministers"?

Yes, there are a few variations of the phrase "Hats Off to the Ministers" such as "Hats Off to You" or "Take Your Hat Off." These variations still convey the same message of admiration or respect towards someone's achievements or hard work.

Is there any scientific significance to the phrase "Hats Off to the Ministers"?

No, the phrase "Hats Off to the Ministers" does not hold any scientific significance. It is simply a cultural expression that has been adapted and used in various contexts to convey praise or appreciation towards someone.

Similar threads

Replies
35
Views
4K
Replies
13
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
Replies
10
Views
3K
  • General Discussion
Replies
6
Views
14K
  • General Discussion
Replies
2
Views
5K
  • General Discussion
Replies
4
Views
2K
  • General Discussion
Replies
2
Views
1K
Replies
5
Views
4K
  • General Discussion
Replies
33
Views
2K
Back
Top