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?
PS: I have an answer, using which we can save 99 people with 100% assurance and 1 person with 50% assurance. Let's see how many people you can save.
How can we save 99 people with 100% assurance and 1 person with 50% assurance.
Give value '0' to RED hat and '1' to BLACK hat. Now first person will count the numbers of all the persons in front of him and if it is odd say BLACK else say RED. He has 50% chance of survival.
Now next person know what his previous person said. He should add the numbers of all the persons in front of him(i.e. 98 persons for 99th person) Now there may be 4 cases:
1. If count comes odd and earlier person said BLACK: say RED
2. If count comes odd and earlier person said RED: say BLACK
3. If count comes even and earlier person said RED: say RED
4. If count comes even and earlier person said BLACK: say BLACK
now 98th person knows the answer of 99th person and of first person, he can easily determine the color of his hat. In the same manner everyone else can determine the color of his hat.