The first one is an old classic hat puzzle; I’ve put it here as a warm-up for the second one which is a tad more challenging.
Puzzle #1 Three wise men are told to stand in a straight line, one in front of the other. A hat is put on each of their heads. They are told that each of these hats was selected from a group of five hats: two black hats and three white hats. The first man, standing at the front of the line, can’t see either of the men behind him or their hats. The second man, in the middle, can see only the first man and his hat. The last man, at the rear, can see both other men and their hats.
None of the men can see the hat on his own head. They are asked to deduce its color. Some time goes by as the wise men ponder the puzzle in silence. Finally the first one, at the front of the line, makes an announcement: “My hat is white.”
He is correct. How did he come to this conclusion?
Puzzle #2 One hundred persons will be lined up single file, facing north. Each person will be assigned either a red hat or a blue hat. No one can see the color of his or her own hat. However, each person is able to see the color of the hat worn by every person in front of him or her. That is, for example, the last person in line can see the color of the hat on 99 persons in front of him or her; and the first person, who is at the front of the line, cannot see the color of any hat.
Beginning with the last person in line, and then moving to the 99th person, the 98th, etc., each will be asked to name the color of his or her own hat. If the color is correctly named, the person lives; if incorrectly named, the person is shot dead on the spot. Everyone in line is able to hear every response as well as hear the gunshot; also, everyone in line is able to remember all that needs to be remembered and is able to compute all that needs to be computed.
Before being lined up, the 100 persons are allowed to discuss strategy, with an eye toward developing a plan that will allow as many of them as possible to name the correct color of his or her own hat (and thus survive). They know all of the preceding information in this problem. Once lined up, each person is allowed only to say “Red” or “Blue” when his or her turn arrives, beginning with the last person in line.
Your assignment: Develop a plan that allows as many people as possible to survive. [Source: TienrneyLab ]
I’ll provide answers in the Comments section next week.
Blank Slate 
“Challenge accepted!” (The Barney way, from HIMYM)
Will try and work it out before you give the answers….
I will post hints for both puzzles tomorrow then.
Oh, and I have actually never watched that show, so I missed the reference! Is it any good?
Hints
Puzzle #1: The delay is informative. The fact that the other two wise men were not able deduce the colors of their hats helped the first man (at the front of the line) to correctly guess the color of his hat.
Puzzle #2: It is possible develop a strategy that will definitely save the lives of 99. And the likelihood that the remaining one person survives is 50/50.
I did solve the first one without the hint. Still mulling over the second.
As soon as I wrote the last comment, an idea popped into my head 🙂 Not sure if the puzzle forbids it, but essentially, for #2, a person (X) speaking just needs to communicate an additional bit of info to the person (X-1) ahead, that tells him whether X-1 has the same colour as X or not. One way to do this is for X to incorporate a pause before speaking if there is a difference. Illustration:
if X:red, X-1: red, X-2: blue
X: red!
X-1: red
X-2: blue (with a pause before “blue” depending on X-3’s hat
and so on.
Of course, Person #100 simply guesses, hence the 50% prob of survival.
(comments didn’t show “pause” as I’d used angular brackets, so read it thus:)
if X:red, X-1: red, X-2: blue
X: red!
X-1: [pause] red
X-2: blue (with a pause before “blue” depending on X-3′s hat
Ramanand,
I should have mentioned that there are no tricks outside the stated bounds of the problem. Each person is allowed to say either “Blue” or “Red”, and nothing else. They can’t cough, use Blue and Red in different tones or variations, use any other vocal signals, or add a pause etc. Since I didn’t mention it explicitly, I can’t say that your solution is incorrect! 🙂
However, there’s another, more elegant solution to this, which I’ll post tonight/tomorrow.
Here’s the solution to Puzzle #2:
Let’s start with two persons (instead of 100). If there were only two persons in the line, the last person in line (who has to go first) can call out the color of the hat worn by the person ahead of him. That way, the last person in line has a 50/50 shot at being correct about his own hat color, but the first person in line is saved because he will correctly identify the color of his hat.
Next, let’s assume that there are three persons in the line. The last person in the line, let’s call him X, will either see two blue hats, two red hats or one blue and one red hat. There are three different scenrios here, but he has only two options (either say ‘Blue’ or ‘Red’). So the question is: how can we reduce those three scenarios into two? Even and odds!
Let’s focus on red. X either sees zero, one or two red hats. The number of red hats has to be either odd or even. If the number of red hats is odd, he will say “Red”. Now if Y sees a red hat in front of him, he will deduce that the color of his hat must not be red, because otherwise X would have seen even number of red hats (and would have said “Blue”). And if Y sees a blue hat in front of him then he’ll deduce that the color of his hat must be red. Thus, Y will always be able to infer the color of his hat, and survive. Z will simply remember what X said (there are odd number of red hats among Y and Z) and add the information that Y gave (i.e the color of Y’s hat). And he will be able to correctly guess the color of his hat as well!
This logic works for any number of persons. (And obviously they don’t necessarily have to pick red+odd. The same logic applies to any combination of red/blue and odd/even.)
Heh, I didn’t take my solution too seriously because I assumed such snarkiness would be unfair 🙂
Thanks for the solution!
Loved the puzzle# 2 🙂
I am glad you enjoyed this puzzle.
I came across another related puzzle (on this blog):
The sultan decides to test his hundred wizards. Tomorrow at noon he will randomly put a red or a blue hat — for both of which he has an inexhaustible supply — on every wizard’s head. Each wizard will be able to see every hat but his own. The wizards will not be allowed to exchange any kind of information whatsoever. At the sultan’s signal, each wizard needs to write down the color of his own hat. Every wizard who guesses wrong will be executed. The wizards have one day to decide on a strategy to maximize the number of survivors. Suggest a strategy for them.
I haven’t figured out this one yet — it seems unlikely that the number of expected survivors can be more than 50…. (The hats are assigned randomly, so every wizard has a 50/50 chance of being right — not matter what color they see on the other hats.)
How about for #1?
Balie,
The delay is informative.
Suppose the wise man in the rear, let’s call him C, saw two black hats before him. Then he would immediately know that he is wearing a white hat (because there are only 2 black hats). As a result, there would be no delay. But since C was not able to determine the color of his hat, the wise man in the middle, B, and the wise man in the front front, A, know that there must be at least one white hat between them. Now suppose that B saw a black hat on A. Then he would immediately know that he was wearing a white hat, and again there would be no delay.
But since there is a delay (both C and B were unable to determine the colors of their hats), A is able to conclude that he’s wearing a white hat.
Makes sense?
trry doing puzzle number 2 , with 3 colours of hats 🙂
[I came to this blog today to find this post, and re-read and re-liked some others. You do really have a great blog]
I was trying to make my 6 yr old nephew sit at some place for some time, and not just run around the house. So, I was giving him puzzles to solve. I thought the second puzzle here will make him think (and think (and think ….)). (Btw, I made the 100 people as captured INA soldiers and the captors as British soldiers – red & blue caps suit the story)
But he came out with this ‘solution’ quickly (I’m not saying it’s good, but just interesting): The first one calls the second one’s color (say, “red”). Irrespective of whether he is shot, the second one will say “red”. But he will say a quick “red” if #3 has red, and a longish “rrred” if #3 has blue.
That is a tough puzzle for a 6-year old! But it’s nice that your nephew at least tried to solve it. Sometimes the willingness/curiosity to solve a puzzle matters more than the ability to solve it.
Poster’s solution for no.2 is too hard when N is large besides put another burden on the last unlucky poor person’s chance, he has to count them ALL and for many guys in front of him.
For what I think of, using unspeakable language such time (people need to practice and assume they work perfectly), Start with last person speaks of the hat’s color of a guy in front of him, if he was lucky enough to wear the same color hat with the guy in front of him, he’ll survive by 1/no.of color
The next key is for the rest, 99th person shout his color from what he’d told within 5 secs if the guy in front of him wear color 1, 5 – 10 secs if the guy in front of him wear color 2, 11 – 15 secs for color 3 and so on. When the guy in front of him has heard, time count shall start.
With this method, people challenge on timing rather than counting hats on their large N heads, which one do you prefer?
A guy from Bangkok