| Question: There are a hundred people lined up on the steps of a stadium, each on a different step, all looking down toward the field so that they can see everyone in front of them, but can't see anyone behind them. Each person will be given either a red or black hat. We know nothing about the total number of red or black hats. Each person will not be able to see the color of his own hat (or the ones behind him), but will be able to see the colors of all the hats in front of him. Starting in the back, the last person will be asked what color hat he is wearing. If he guesses correctly, he will live; if he guesses incorrectly, he will be shot immediately. We will then proceed to the person second from the back, and so on, until we have reached the person on the bottom step. Each person will be able to hear what all the people behind him say, and will also be able to hear which people behind him were shot. Before we begin this process, the 100 people may meet to discuss a strategy. They can plan whatever they want, but once the line-up begins, they may no longer confer. At each person's turn, he may only say "black" or "red," and no other words -- if he says anything else, all 100 people will be executed. He may also not use tone of voice, volume, etc., to convey any meaning -- this will be detected and they will all be shot. What strategy will guarantee saving the maximum number of people? What is this number? Answer: We can save 99 people with 100% assurance and 1 person with 50% assurance. |
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
How about the case in which there are three different colored hats. Like WHITE,BLACK and BLUE. I was recently asked this in an interview, first I was asked with 2 colors and then with three colors.
@Ranganath This is true for any number of colors; assign 0, 1 and 2 to White, Black and Blue respectively. Now 100th person will count the numbers in front of him and divide by 3. Say count comes 158; he will say 158%3 = 2 (Blue). His probability of being correct is 1/3.
Now 99th person will count all the number in front of him, say it comes 157. Coz he know that last person say Blue(2), he must got the count 158 so his hat must be 158-157=1 i.e. Black.
So on other persons can guess the colors of their hats correctly.
So for n colors, one person will have the probability of 1/n and all other have 100% probability of living.
Actually, this method is too complicated and it assumes that there will not be any calculation errors on the part of the people. An easier method is described below:
Let's say that the person at the back is person n. Then he could guess his hat color by saying "White" or "Black".
BUT, if person n-1 is wearing a white hat, then person n says his guess loudly.
If person n-1 is wearing a black hat, then person n says his guess softly (loud enough for person n-1 to hear).
In this way, person n-1 would immediately know what color his own hat is.
From here, the solution applies recursively all the way till person 1, who simply says the color of his own hat.
This solution was formulated by looking at how bits are transferred across a link: +ve voltage for 1 and -ve voltage for 0.
I think the solution is not explained completely well. I was misled a bit. Let the first person who can see everyone count the number of black hats.
If he sees an odd number in front of him he will say black, otherwise he will say red. Now everyone knows how many black hats there should be: even or odd.
It is up to each one of the people in row to count how many people say black (excluding the first one). In this way each person will have to only count the number of black hats in front of him and add it to the number of people who have said black.
Now we just consider the four cases explained in the original answer.
If there are an odd number of black hats and the person counted an odd number of black hats in total (behind him and in front) that means that he is red.
If there are an odd number of black hats and the person counted an even number of black hats in total that means that he is black.
The key here is to also count the number of people who have said black (not just the one behind him).