Problem of the Day
A new programming or logic puzzle every Mon-Fri

The Mad King

The mad king tells his 100 wisest men he is about to line them up and that he will place either a red or blue hat on each of their heads. Once lined up, they must not communicate among themselves. Nor may they attempt to look behind them or remove their own hat.

The king tells the wise men that they will be able to see all the hats in front of them. They will not be able to see the color of their own hat or the hats behind them, although they will be able to hear the answers from all those behind them.

The king will then start with the wise man in the back and ask "what color is your hat?" The wise man will only be allowed to answer "red" or "blue," no more no less. If the answer is incorrect then the wise man will be silently killed. If the answer is correct then the wise man may live but must remain absolutely silent.

The king will then move on to the next wise man and repeat the question. The king makes it clear that if anyone breaks the rules then all the wise men will die, then allows the wise men to consult before lining them up.

What is the maximum number of men they can be guaranteed to save?

Permalink: http://problemotd.com/problem/the-mad-king/

Comments:

  • Lasharn - 10 years, 6 months ago

    Assuming there are 50 blue and 50 red hats, if they all say the same answer then half of them are guaranteed to live. I haven't heard this riddle before so there's probably a much better answer :D

    reply permalink

  • Andreas - 10 years, 6 months ago

    since there is no information on the amount of hats of either color, I would say the amount of men they are guaranteed to save is technically zero.

    reply permalink

  • Andreas - 10 years, 6 months ago

    nvm, I disregarded the fact that they can consult beforehand... NargiT is right

    reply permalink

  • NargiT - 10 years, 6 months ago

    50, the first one says the color of the hat that is in front of him. the 2nd one repeat the color. the 3rd one do the same thing as the 1st...

    every odd wise man says the color of the one in front of him. every even wise man repeate the color said before.

    didn't find something better

    reply permalink

  • NargiT - 10 years, 6 months ago

    odd => even even => odd

    reply permalink

  • NargiT - 10 years, 6 months ago

    oops ! I meant odd = even, even = odd sorry mistape

    reply permalink

  • Anonymous - 10 years, 6 months ago

    99.

    The last person in line (first to be asked the question) just answers the hat color of the person in front of him. He may or may not live.

    Then, for each person in line, the king asks "what color is your hat" and he answers the color that was indicated by the previous man. However, if the man in front is wearing a red hat he answers in a comically girly voice. Otherwise, he answers using his usual wise manly voice.

    If executed successfully, 99 wise men are guaranteed to live.

    reply permalink

  • Ethan - 10 years, 6 months ago

    99

    https://gist.github.com/eglove/61e5e1a111c03df4ec72

    The first wise man counts the red hats he can see, and says red for an even amount, blue for an odd amount. He has a 50/50 chance of dying. But if every person counts the red hats themselves from then on, if it is still even/odd, they repeat what the guy behind them said. If it is the opposite, they say the opposite.

    reply permalink

  • Max Burstein - 10 years, 6 months ago

    Well done. This is indeed the correct solution

    reply permalink

  • Mre64 - 10 years, 6 months ago

    the biggest problem is that the king never said if he was alternating between colors.Wise men in line with alternating colors --> |R|B|R||B|R|B|R|B| <--. this would mean a guarantee 50 wise men still alive if they all say "Yes" or "No". However if the kind put hats on then randomly --> |R|R|R||B|R|B|B|R| <-- then god help them. Either way its a bad say to be a wise man in that kingdom.

    reply permalink

  • eskatrem - 10 years, 6 months ago

    50 wise men can be saved for sure. The first wise man has to answer the color of the hat of the next wise man before him, so the second one will answer his color since he knows it, the third one will answer the color of the fourth one, and so on.

    reply permalink

  • jimworm - 10 years, 6 months ago

    66 can be saved. The 1st wise man looks at the two in front of him. If the colours are the same then he says "blue", if not he says "red". The 2nd man then knows whether his hat is the same colour as the one that he sees in front, and the 3rd person will know by extension what colour he has by hearing the two answers that came before. The 100th person will have to guess.

    reply permalink

Content curated by @MaxBurstein