My New Favorite Hat Puzzle

My new favorite hat puzzle was invented by Konstantin Knop and Alexander Shapovalov. It appeared (in a different wording) in March 2013 at the Tournament of the Towns:

A sultan decides to give 100 of his sages a test. The sages will stand in line, one behind the other, so that the last person in the line sees everyone else. The sultan has 101 hats, each of a different color, and the sages know all the colors. The sultan puts all but one of the hats on the sages. The sages can only see the colors of the hats on people in front of them. Then, in any order they want, each sage guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the sages cannot speak. They are not allowed to repeat a color that was already announced. Each person who guesses his color wrong will get his head chopped off. The ones who guess correctly go free. The rules of the test are given to them one day before the test, at which point they have a chance to agree on a strategy that will minimize the number of people who die during this test. What should that strategy be?

I loved it so much that I wrote a paper about it. You can find the solution there.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

8 Comments

  1. Sara:

    Hi Tanya, how are you?

    I like this puzzle very much! Thank you for sharing it!

    But I have a question:

    Where, in the “black/white” version of the puzzle, does it state that there is close to 1 : 1 proportion of black to white hats?

    “The sultan puts either a black or a white hat on each sage.”

    Odd or even counts do not mean anything if I have a much higher number of white hats as compared to black hats, for instance. Isn’t this so?

    Considering this, I like the “color” version better, because there you have this information:

    “The sultan has 101 hats, each of a different color, and the sages know all the colors.”

    Kind regards,

    Sara

  2. Anon:

    Does the head get chopped off immediately after the wrong guess? That is, do all the yet alive prisoners know that the guess was wrong or they have to guess blindly until in the end some of them get killed?

  3. Tanya Khovanova:

    Anon,

    They guess blindly.

  4. Aaron F.:

    Sara: In the black/white version I know, the proportion of black to white hats doesn’t matter. Just to make sure we’re on the same page, what version are you talking about?

  5. Richard Elwes – Carnival of Mathematics 100:

    […] two colours, and a line of people have to deduce their own hat type. (E.g..) Here, Tanya Khovanova presents a new twist: A sultan decides to give 100 of his sages a test. The sages will stand in line, one behind the […]

  6. George R.:

    Dear Tanya,
    Pardon my poor English.
    Congratulations on your excelent and highly entertaining (and thus EDUCATIONAL) blog!
    It is really a joy for me to read your thoughts.
    There is something I don’t really get about the hat puzzle, regarding the even permutation solution at the end. (of course ,this is just poor understanding by myself, and has nothing to do with your wonderfull paper!)
    Is the permutation (1,2,…,101) not always even? I mean whatever number from (1 to 101)let be asigned to the ghost-sage,thus changing the pair:ghost-“heroe” , what difference does it make for the futurous decisions of the other sages?
    Perhaps, you could elaborate (numerically) the method with let’s say 10 (or 8) sages (+ 1 ghost=11)?
    (Or anybody else ,if she could devote some time to a stupid’s (that’s me!:-) )question)
    Thanks,and keep up the good work!

  7. Tanya Khovanova:

    George R.

    Suppose there are two people. The first person sees color 1, so there are two colors left: 2 and 3. Out of two permutations 231 and 321, the first one is even. So the first person assigns color 2 to the ghost, and announces 3. Now the from person heard 3, so there are two permutations to choose from: 132 and 231, The second one is even, so he announces 1.

  8. George R.:

    Τhanks a lot Tanya! Now I’ve understood the consept!