CareerCup

100th person will speak the color of hat of 99 th person. Now he has 1/2 chance of dying, and all other persons from 99 to 2 will say scream there if it same as there next person hat's color other wise they will speak softly. This gives assurance of saving person from 99 to 1. we have assurity that we can atleast able to save 99 people.

Ans:99
Last person has 99 ppl in front.Total of one color will be even and of the other will be odd(Only even+odd=odd).He will shout the color with odd total(say red).The person at 99 hears the odd color.He will count no of caps of that color in front of him(red).If it is even,then his cap color is the same as spoken by previous(red),else other(blue).He will shout his answer(say blue).Person at 98 hears both the answers of 100 and 99.He now knows that 99 must hv seen odd number of red caps in front .98 will see the no. of reds in front of him and decide his answer(blue if odd otherwise red).It will continue in this manner till the first. Thus 99 lives saved!!

maximum can be fifty (n/2 in general)..
such that each person tells the color of hat of the person in front of him and so the person in front of him tells the right color of his hat......
hope this helps...

99 from the last to the first.

100th person will speak the color of hat of 99 th person. Now he has 1/2 chance of dying, and all other persons from 99 to 2 will say scream there if it same as there next person hat's color other wise they will speak softly. This gives assurance of saving person from 99 to 1. we have assurity that we can atleast able to save 99 people.

I dont understand how the color of the hat is related to the person being alive or dead.

The question doesn't seem to complete, can somebody amend it a little bit?

Please provide the complete question..not sure how first third people provided answer...

alternate prisoner can say the color of hat of the person who stands in front of him...atleast 50% prisoners will be saved...
For e.g. if hats are in order: R R W W R W R W...last person will shout red...he will die, next person will say red and survive, next person says red and dies...next person says red and survives...etc...

Complete 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?

Thanks Akash for the explanation.

Look at the problem probabilitcally, and work with the expectation of the number of colors.

Ans – Minimum 99 persons are saved for sure. Could be 100

Explanation :

Strategy – 100th person will count the number of white cap in front of him, if total is even he shouts white else he shouts red.
How it works – after 100th person’s shout, 99th person will count the number of white cap again. If his answer differs from 100th (red/white) it is sure that his own cap is white. If not his own cap is red.
Rest of them follow the same logic and will all save their life.

good solution ankur

All 100 can be saved

:O
can u xplain sourabh..at max u can save 99 with .5 probablity of 100th

From http://en.wikipedia.org/wiki/Prisoners_and_hats_puzzle

Ten-Hat Variant

In this variant there are 10 prisoners and 10 hats. Each prisoner is assigned a random hat, either red or blue, but the number of each color hat is not known to the prisoners. The prisoners will be lined up single file where each can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be "red" or "blue". If the word matches their hat color they are released, if not, they are killed on the spot. A friendly guard warns them of this test one hour beforehand and tells them that they can formulate a plan where by following the stated rules, 9 of the 10 prisoners will definitely survive, and 1 has a 50/50 chance of survival. What is the plan to achieve the goal?
[edit]Ten-Hat Solution
The prisoners can use a binary code where each blue hat = 0 and each red hat = 1. The prisoner in the back of the line adds up all the values and if the sum is even he says "blue" (blue being =0 and therefore even) and if the sum is odd he says "red". This prisoner has a 50/50 chance of having the hat color that he said, but each subsequent prisoner can calculate his own color by adding up the hats in front (and behind after hearing the answers [excluding the prisoner in the back]) and comparing it to the initial answer given by the prisoner in the back of the line. The total number of red hats has to be an even or odd number matching the initial even or odd answer given by the prisoner in back.

The counting of even and odd numbers of colored hats does not work.
Say ordering of hats is: (last)W,B,W,W,B,W(first) [W-White Hat;B-Black Hat]
The last prisoner counts # of Black Hats and sees it is even and says "Black"
The last-but-one prisoner sees odd # of hats and knows his is a black hat n says "Black"
The last-but-two prisoner uses the same logic and says "Black" which is clearly wrong!

Therefore only 50% of prisoners can be saved

With my logic I can save 75 out of 100. Consider 4 prisoners 4,3,2 and 1. When 4 is asked to speak out he will use the following logic,

if Color(3) == Color(2) then Say Color(1)
else if Color(3) != Color(2) then Say ~Color(1). As there are 2 colors ~B = W and ~W = B

Now after this the P(4) surviving is 0.5 but now 3 will see C(2) and C(1) and if 4 said ~C(1) , 3 will tell ~C(2) and 2 will say ~C(3) as 2 will also realize that what 4 said was ~C(1). Now when 1 hears two different colors from 3 and 4 it will realize that what 4 told was ~C(1) and hence he knows what the color he has.

So with this logic every 4th prisoner sacrifices his life for other 3.

Please let me kn

XOR of first 99 Cap!