How Many Can You Save ?
One hundred prisoners are lined up, one behind the other, all facing forward. On each prisoner's head is a hat, either red or black. Each prisoner can see the hats of all the people in front of him, but he cannot see his own hat and he cannot see the hats of the people behind him. Starting with the prisoner in the back of the line (the one that can see all 99 other prisoners), the prison warden asks the prisoner what color hat he is wearing. Each prisoner can hear the guesses of all of the prisoners behind him. If a prisoner correctly guesses his hat color, he is set free. If he guesses wrong, he is executed.
The prisoners are allowed to agree in advance on an algorithm to use, and you can assume that they all agree to follow the agreed-upon algorithm. The prisoners are NOT allowed to provide each other with any additional clues once the hats are placed on their heads. (For example, tapping shoulders or modulating their voices are not allowed.) The only information each prisoner has is the guesses for the prisoners behind them, and the hats on the prisoners in front of them. Design an algorithm for the prisoners to follow that saves the most prisoners from execution. What is the maximum number of prisoners you can guarantee to save?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
9 solutions
It doesn't mention there being an equal number of red and black hats though.
Log in to reply
This would work if there where 2 black hats an 97 red in front of him one odd and one even
Yea. This questions wording broke the whole objective.
Prisoner Nr.100 says the color of the guy in front of him
Log in to reply
This doesn't work either, if they say the hat color of those in front of them, then they'll all die if it's alternated.
This may be incomplete. Take the case of 50 blacks and 50 reds. Suppose the pattern for 100-98 is RBB.
Case A: 100 says black cause he sees 50 Blacks, 49 reds. 99 says black because he sees 49 blacks, 49 reds (odd number of blacks). 98 says red beacuse he sees 48 Blacks, 49 reds (even number of blacks) <wrong, should be black>
Even if you switch the parity rules for the second step every other person(odd number of blacks = red. Even number of blacks= black), it will fail on the RRB pattern:
Case B: 100 says black (sees 50 blacks, 49 reds) 99 says red(sees 50 blacks, 48 reds, original rule) 98 says red (sees 49 blacks, 48 reds, reverse parity) <wrong, should be black>
Prisoners 98 and below must follow an additional step : they must account for the guesses of everyone before them except for 100's guess then apply the second step to the sum. In case A, since 99 said black, 98 must add that result to what he sees. (49 blacks, 49 reds). Since there are odd blacks, according to step 2, the result is black.
In case B, since 99 said red, 98 accounts for it (49 blacks, 49 reds) and gets black when step 2 is applied.
Log in to reply
If there are 67Red and 33black hats, and the hats are randomly distributed like first 8 person has black, your approach fails.
Log in to reply
No because 67+33= 100 the last man can not see his hat so he sees 66 red and 33 black then the guy in front of him sees 65 black and 33 red so forth and so on
the last person has to sacrifice himself and by telling red or black he can divide the whole front pattern into 2 parts......the next person can identify which particular pattern he is in because he can see the front hats.... the next parson can also divide the half pattern again into 2 half's and identify in which he is in.............this continues.....and thus all the rest can be saved......
for example in case of three prisoners....the last person can see the front two peoples hat which can be in 4 pattern.... R-R.........B-B........R-B..........or B-R.........they can assign 2 pattern for each answer...Red( R-R......B-B) and Black (R-B.......B-R)...
by hearing his answer the next 2 person can easily identify in which 2 cases they are in.....
* If Red is the answer...they both know for sure either it's R-R or B-B......if the 2 person sees red in front of him he shouts red cause he knows he is red for sure and the next person also knows re is red.........this is the same case if he sees black....
* If Black is the answer the next 2 person knows it's B-R or R-B .....whatever he sees in front he says the opposite and thus the next 2 person is saved...
I explained this as an example of 3....in that case there can be only 4 combination for 2 guy(B-B,R-R,B-R,R-B).......for an example of 4 there will be 8 combination (B-B-B...........R-R-R...........B-B-R..........B-R-B...........R-B-B..........R-R-B........R-B-R....B-R-R)......in case of 100 there will be much more combination.
In this process only 1 has to die and the next 99 prisoners can be saved.......:D
I don't suppose by this process 99 persons can be saved it may be that 99 persons will know what color hat they are wearing but they wont' be able to save themselves.
Masun Bi Alam, There seems to be an error in your reasoning. How can saying "Black" signify both the color of your hat and a clue to the colors of the 2 hats ahead of you?
Here is my paradigm for your perusal.
Let " Black " be the sign that # of black hats seen by the last man is odd, and "Red" signify that the # of black hats seen by the last man is even. Every prisoner takes note of this fact. Let's suppose that #100 sees an odd number of black hats and yells out "Black".
#99 counts the number of black hats ahead of him. If the number is even he concludes that he has a black hat,(to keep the total black odd). If he sees an odd number of hats then he concludes that he has a red hat.
#98 counts the number of black hats ahead of him. Knowing what #99 had, then he can conclude the color of his hat and he yells it out.
The same reasoning holds for everyone ahead of him. All each person has to do is count the # of black hats correctly and to remember how many black hats were worn by the men preceding him.
The initial paradigm is used only by the last prisoner whose fate is 50/50 whether he lives or dies. Therefore there is a guarantee of at least 99 saved.
By the above process, lets say say the first prisoner sees R-R in front of him and says Red. then 2nd prisoner would say Red, since he is seeing a Red cap(3rd Guy) in front of him. What if the 3rd guy sees a B-R, in front of him. 3rd guy knows that he is wearing Red cap. But according to the algorithm, he should say Black. Whatever answer he says, either he dies ( by saying Black, according to algorithm) or another prisoner gets killed (by saying Red, 4th prisoner would think that he and the guy in front of him wear same color. But that is wrong) So I guess in this way, 99 prisoners cannot be saved.
Log in to reply
if the third guy see B-R OR R-B....he will say Black...then the next 2 person will know that it's B-R or R-B .....the the 2nd person whatever he sees in front he says the opposite and the 1st person says the opposite of 2nd persons answer thus the next 2 person is saved..... And this is only the example of three...means the last guy can save all the persons in front of him.....it can be done with 4,5.6,7....,99...,n
Log in to reply
If the third guy says Black, then he will be executed. Because he is wearing a Red cap. And this confusion will come for every third guy. First guy says Same color or opposite. Second guy will answer based on third guy's hat color and what first guy has told. Third guy will come to know the color of his hat from third guy. These are all fine. But the third guy has to say one color, which should be his hat color as well as based on the guys in front of him. The problem arises there.
Log in to reply
@Vignesh Dhandayuthapani – you didn't get it..I explained this as an example of 3....in that case there can be only 4 combination for 2 guy(B-B,R-R,B-R,R-B).......for an example of 4 there will be 8 combination (B-B-B...........R-R-R...........B-B-R..........B-R-B...........R-B-B..........R-R-B........R-B-R....B-R-R)......in case of 100 there will be much more combination.
The process doent say that the colors will have a pattern? The guy has to tell the color of his cap only but not allowed to tell the color of the person who are in front so he only guesses his color........ so 99 doesnt seem to be correct, might be 49?
I think this algorithm is not clear. How do you extend this to more than 3 people and save 99?
(a) you find the patterns for 3+n and divide it into 2 groups. This algorithm will only reveal the color of the hat for every even numbered person for n>0. Consider 4 people (the first person sees RRR, RRB, RBR, RBB, BRR, BRB, BRR, BBB - the only way to divide these patterns into 2 is to consider the first color). So for 100, only 50 is surely saved.
(b) You divide the whole group into 3 prisoners each - where you only have 66 saved (as Subhrajyoti Sinha pointed out)
(c) If you divide the whole group by more than 3 each, you save even less as implied by (a).
according to this algorithm 2 persons are saved from three. that means 66 out of 99 (or 100) can be saved. NOT 99 COZ 4TH PERSON HAS TO SACRIFICE HIS LIFE AGAIN TO USE THIS ALGORITHM
99 prisoners cannot be saved. For example if the patter 100th,99th,98th,97th is B,R,R,B then yes the 100th prisoner would safe the 99th because the 99th would say Red, but because the 99th prisoner said Red, then it means that the 98th prisoner will say black, and he dies. That is, the right answer must be 50. Because each prisoner can tell the prisoner in front of him what hat color the prisoner in front of him are using. The 100th can safe the 99th by shouting the 99th hat color, the 98th could safe the 97th by shouting the 97th hat color and so on. So 50 of them sacrifice themselves and 50 of them are saved.
Log in to reply
I think 66 prisoners can be saved.because each prisoner have two option he can render two information thus saving two prisoners. Like, First person will say red if 2nd and 3rd person wears the same color of hats,otherwise he will say black. Now,hearing first persons answer and watching 3rd persons hat color,2nd person can identify his hat color and thus save himself.and 3rd person will identfiy his color using his previous two guesses. thus in worst case,every 3n+1 th prisoner will be executed.but rest will be saved,thats how 66 prisoners can be saved.
i can't translate it -_- my english so bad :(
First guy is a coin toss - let's wish him good luck. His job is to establish the parity of black hats visible to him. He says "Black" if he sees an odd number of black hats; "Red" otherwise. By paying attention to what has been said, each prisoner will know his hat's color.
Example: Second to speak hears "Black" and sees an even number of black hats. He knows his hat is black [odd changed to even - must be his is black] and says "black".
Third guy has heard "black" and "black" and sees an even number of black hats. He knows his hat is red [even stayed even - his hat can't be black] and says "red".
And so on, to the front of the line.
General algorithm: The first time you hear "black", say to yourself "odd". Each time your hear "black" after that, change the parity: "even", "odd", ... etc. When it's your turn, if the black hats you see match the running parity, you're Red; Black otherwise. Call out your color.
The original problem does not say that there is an even number of each color hat, just that they are either black or red. Based upon this, there is no way to know the odds of the color hat you, or the people behind you are wearing.
It's not mentioned if the number of the coloured hats are distributed evenly(50/50) or randomly,thus i think counting the number of hats doesn't seem like the solution.Since the prisoners are only not allowed to modulate their voice,i think it is safe to say that the prisoners can agree beforehand how they'll put their words to indicate the colour of the hat of the person in front of them. for example: the 100th prisoner had no choice but to guess his own hat colour.lets say he guessed that his own hat is black and the hat of the person standing in front of him is black.he can state that "my hat is black". if the hat in front of him is red he can change his structure of his sentence and says "i have a black hat". then the 99th person will know exactly what colour of hat they have on and subsequently saving the rest of the 99 prisoners.
The 100th prisoner says the color of hat of the 99th prisoner. The 99th prisoner speaks the color of his hat in Spanish if the color of the hat in front of him is red, else he speaks the color of his hat in English. There are no clues or modulations in the prisoners voice, and the prisoners in front do not need to remember odd/even rules or worry about people in front. Thus this is the simpliest algorithm.
If you read it carefully, the warden isn't asking what each person's hat color is, he is asking what color the prisoner in back is wearing.. so the last prisoner getting freed or executed determines what the next prisoner's answer will be. (If the last prisoner says red and he gets executed, that means his hat is black and everyone will answer black and be set free). This guarantees the other 99 to be freed when the 100th prisoner only has a 50% chance of being freed.
I got it right, I was just being optimistic that somehow, someone out there can think of a solution to save 99
https://www.youtube.com/watch?v=N5vJSNXPEwA
Very easy solution: The last prisoner just has to speak out the colour of the hat the prisoner in front of him (that is 99th prisoner) is wearing. By doing this it's definite that the 99th prisoner will be saved and once he is saved the rest of them can be saved by doing the same.
Sorry but that's not how it's done, I fear you have gotten the question wrong, the algorithm that the prisoners are to agree upon goes something like this:
The first guy to take a guess (the 1 0 0 t h prisoner) isn't gonna be taking a guess at all, instead he is gonna check out all the 9 9 hats infront of him and see how many are red and how many are black, and since he sees a total of 9 9 hats that means either the red hats count up to an even number, and the blacks to an odd number, or the opposit. Now the agreed upon algorithm would make the 1 0 0 t h prisoner yell '' RED '' if he sees an even number of red hats (or he could yell the colour which occurs an odd number of times, it wont matter as long as they're all on the same page), so now, all the next guy have to do is count the red hats infront of him and see: if he counts an even number of red hats then he knows he's wearing a black one, and visa versa. Now the information is updated after every prisoners, so the ones who are upfront should remember all the choices the others made in order to deduce the correct answer by counting the number of red hats (in this case) infront of them.
Log in to reply
Though the question did not specify if there were an equal number of black hats and hats.
"the question did not specify if there were an equal number of black hats and red hats. " how could you solve it without this information ??!!
Nice solution, Mr. Nader, but then in this way shouldn't the number of people who can be saved surely be all the 100?
Thanks for replying but I wasn't able to figure out why this one doesn't works:
The 100th prisoner tells the the 99th prisoner's hat color. Using this information 99th prisoner can be saved. Once, the 99th prisoner is saved, he will speak out the color of hat of the prisoner whom color is asked and that person would follow his suggestion. This way everyone can be saved except the 100th prisoner for sure.
Log in to reply
In order for a prisoner to be saved he have to guess the color of the hat he himself is wearing, if the 100th prisoner shouted the hat color of the 99th, the 99th isn't saved until his turn comes and he shoutes what the 100th told him, so you would garantee the safety of the 99th prisoner only, repeating this for the rest of them would garantee the safety of only half of them. But we devised a better algorithm in order to garantee the safety of 99 of them.
Log in to reply
@Christian Nader – I did't get it. When the 99th prisoner is saved, the 98th prisoner can be saved as 99th prisoner will tell him the true color of his hat. Next, the 98th prisoner will save the life of 97th prisoner by telling him the colour of his hat. And that's how all prisoners will be saved. Isn't it? Where am I wrong? Sorry for the inconvenience but I can't get where I am wrong.
Log in to reply
@Lokesh Sharma – I think I get it now. This statement is quite misleading:
Each prisoner can hear the guesses of all of the prisoners behind him.
It got me into thinking that when a person is being asked which hat is he wearing, everyone behind him can speak and tell him right at that time which hat is he wearing.
Thanks for your time.
if he speak out the color of the man in front of u u will be executed.... ur by that only 50 people can be saved.... one dies to save other....
while the soln is like if I can hear the guess of the man behind me I can know the color of my hat... thus only the last man may get executed but rest saved
Log in to reply
...that's what I meant to convey.
Log in to reply
the mistake you are making is
when the 100th person tells the color of the 99th person he will be executed and 99th will know his hat color
now if the 99th person tells his hat color he will be saved but 98th person would not know his hat color
and if he tells 98th person's color he may be executed... so if 99th is saved then then 98th will have to do the same as 100th person and can save 97th person but 98th will be executed
and if this continues one dies and one saved in total 50
Log in to reply
@Ahsan Galib – I think I get it now. This statement is quite misleading:
Each prisoner can hear the guesses of all of the prisoners behind him.
It got me into thinking that when a person is being asked which hat is he wearing, everyone behind him can speak and tell him right at that time which hat is he wearing.
Thanks for the clarification.
(y)
EDIT: ...once the 99th prisoner is saved the rest of prisoners in front of him can be saved as the 99th prisoner can tell the true color of hat to every prisoner as he can see them all.
Log in to reply
In the given question it is not mentioned No.of Red hats are equal to No.of black Hats.
Log in to reply
Actually, the solution does not require that the number of hats be equal. It Let me give you an example, let there be 40 red hats and 60 black hats. Let the last guy be wearing a black hat. He sees 40 red and 59 black in front of him. Let the prisoners have decided to count black hats-and call black for even and red for odd. The last guy calls out red, so the 99th guy knows there are odd number of black hats. If he sees even number of black hats ahead of him, he must be wearing black, otherwise red. After listening to his answer, the 98th person can again deduce if the number of hats is even or odd, and so it goes on
I agree!
It should have been mentioned that there are equal no. of red and black hats..
The prisoner at the very back (no.100) just says the colour of the hats which there are an even number of in front of him. This is always possible because there are 99 others in front of him, so there is always going to an even number of one colour, an odd number of another. Of course, he could just say the colour of hats which are odd numbered in front of him. Doesn't matter
Let's say he sees an even number of black hats, so he says "black".
If the prisoner in front of him (no.99) sees an odd number of black hats in front of him, he knows his is black. If he sees an even number of them, he knows his is red. He just says the colour of his hat.
A similar deductive process can occur for all the other prisoners in front.
So, only the guy at the very back is not guaranteed safety