Puzzle : The Stark Raving Mad King

[reddy]

A stark raving mad king tells his 100 wisest men he is about to line them up and place either a red or blue hat on each head. Once lined up, they must not communicate amongst themselves nor attempt to look behind them nor 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," nothing more. 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.

Before they are lined up, the king makes it clear that if anyone breaks the rules then all the wise men will die. The king listens in while the wise men consult each other to make sure they don't devise a plan to communicate anything more than their guess of red or blue.

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

Solution : http://technical-interviews-questions.blogspot.in/2007/07/puzzle-stark-raving-mad-king_09.html

[mallika...@vanguardbschool.com]

99, Just ask the last guy to tell the color of hat the guy in front of him is wearing.

The guy in the last will have 50% probability to survive, while the rest have probability of 100% to survive.

[James Dow Allen]

Was this question really ignored for two years? All but one of the men can be saved. Note that this is true even when there are many different colors instead of 2 (as long as the set of colors is known in advance).

More amazing is that, supposedly*, all but a finite number of countably infinite number of prisoners will survive in this game EVEN IF the prisoners cannot hear each others' guesses! For a spoiler see
https://en.wikipedia.org/wiki/Prisoners_and_hats_puzzle#Countably_Infinite-Hat_Variant_without_Hearing

* I write "supposedly" because the solution assumes the Axiom of Choice. Results like this may make one disbelieve that Axiom. :-)

James Dow Allen

[James Dow Allen]

On Thursday, August 28, 2014 1:02:28 PM UTC+7, James Dow Allen wrote:

> > Before they are lined up, the king makes it clear that if anyone breaks the rules then all the wise men will die. The king listens in while the wise men consult each other to make sure they don't devise a plan to communicate anything more than their guess of red or blue.

Sorry for the excess line lengths. Groogle Goofs seems to have
changed its M.O.

Speaking of the company which has forgotten its
"Do No Evil" motto, here's the latest annoyance
with gmail: Some features no longer work with
Basic View; you have to switch to Standard View just
to view certain long messages.
But how do you then switch back to Basic View?

Answer: THERE IS NO EASY WAY.
AFAIK, you have to access the account deliberately
using a slow Internet connection! With the
Slow connection a "Switch to Basic" option will
appear briefly. Click quickly before the
option disappears from the screen ... and
remember to "Make Basic the Default" if/when
you get in with Basic Mode.

James

[ken]

On Thursday, August 28, 2014 4:56:41 AM UTC+10, mallika...@vanguardbschool.com wrote:
> 99, Just ask the last guy to tell the color of hat the guy in front of him is wearing.
> The guy in the last will have 50% probability to survive, while the rest have probability of 100% to survive.

not really. 100 tells 99 that 99 is Red. But if 98 is Blue what will 99 say?

The expected answer is 99.
100 says 'Red' if he sees an even number of Red hats. He may or may not live.
Each man then knows the even-odd parity of Reds remaining, and the rearmost can deduce his own colour. Whenever the rearmost says 'Red', the rest know that parity has been reversed. All 99 can survive.

Even though each man says only 'Red' or 'Blue', the king may execute the lot because he knows they have a plan and are passing information forward. This not only breaks the rules, but the king is aware of it.

"The king listens in while the wise men consult each other to make sure they don't devise a plan to communicate anything more than their guess of red or blue."

So they must devise this plan in silence. Technically they are still breaking the rules but all is fair when the king is stark raving mad.

-ken

[michaelal...@gmail.com]

How exactly do the men know the remaining even-odd parity. They died silently after all. All they can do is count the # of red hats in front of them and know what the person behind them answered.

[ken]

They didn't die silently. Each one said "red" or "blue" when his turn came up, and all those in front reverse the parity of reds remaining whenever they hear "red"

[anujk...@gmail.com]

Ans --- 99