Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hats Off to the Ministers

  1. May 24, 2004 #1

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    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.
     
  2. jcsd
  3. May 24, 2004 #2

    jcsd

    User Avatar
    Science Advisor
    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.
     
  4. May 24, 2004 #3

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    But then, every minister gets his own hat color wrong. Remember, he is allowed only one answer.
     
  5. May 24, 2004 #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...
     
  6. May 24, 2004 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  7. May 24, 2004 #6

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    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 !
     
  8. May 24, 2004 #7

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    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.
     
  9. May 25, 2004 #8

    jcsd

    User Avatar
    Science Advisor
    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.

    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: May 25, 2004
  10. May 25, 2004 #9
  11. May 25, 2004 #10

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    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: May 25, 2004
  12. May 25, 2004 #11

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  13. May 25, 2004 #12

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Let me assure you that the simplicity of the solution is the reason I rate this puzzle among the cleverest of them.
     
  14. May 25, 2004 #13
    Hitssquad with the point

    I now agree on both counts. I hadn't thought hard about this problem.



    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: May 25, 2004
  15. May 25, 2004 #14

    jcsd

    User Avatar
    Science Advisor
    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!!!!!!!!
     
  16. May 25, 2004 #15

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Nice one hitssquad
     
  17. May 25, 2004 #16
    Thank you, and thanks for the puzzle, Gokul.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Hats Off to the Ministers
  1. Aluminum foil hats (Replies: 9)

Loading...