Brain Teasers
Survival of the People
The Situation:
There is an island with 10 inhabitants. One day a monster comes and says that he intends to eat every one of them but will give them a chance to survive in the following way:
In the morning, the monster will line up all the people - single file so that the last person sees the remaining 9, the next person sees the remaining 8, and so on until the first person that obviously sees no one in front of himself. The monster will then place black or white hats on their heads randomly (they can be all white, all black or any combination thereof).
The monster will offer each person starting with the last one (who sees everyone else's hats) to guess the color of his/her own hat. The answer can only be one word: "white" or "black". The monster will eat him on the spot if he guessed wrong, and will leave him alive if he guessed right. All the remaining people will hear both the guess and the outcome of the guess. The monster will then go on to the next to last person (who only sees 8 people), and so on until the end.
The monster gives them the whole night to think.
The Task:
Devise the optimal strategy that these poor natives could use to maximize their survival rate.
Assumptions:
1) All the 10 people can easily understand your strategy, and will execute it with perfect precision.
2) If the monster suspects that any of the people are giving away information to any of the remaining team members by intonation of words when answering, or any other signs, or by touch, he will eat everyone.
3) The only allowed response is a short, unemotional "white" or "black".
4) Having said that, I will add that you can put any value you like into each of these words. For example, "white" can mean "my mother did my laundry" and "black" can mean the guy in front of me is wearing a black hat.
There is an island with 10 inhabitants. One day a monster comes and says that he intends to eat every one of them but will give them a chance to survive in the following way:
In the morning, the monster will line up all the people - single file so that the last person sees the remaining 9, the next person sees the remaining 8, and so on until the first person that obviously sees no one in front of himself. The monster will then place black or white hats on their heads randomly (they can be all white, all black or any combination thereof).
The monster will offer each person starting with the last one (who sees everyone else's hats) to guess the color of his/her own hat. The answer can only be one word: "white" or "black". The monster will eat him on the spot if he guessed wrong, and will leave him alive if he guessed right. All the remaining people will hear both the guess and the outcome of the guess. The monster will then go on to the next to last person (who only sees 8 people), and so on until the end.
The monster gives them the whole night to think.
The Task:
Devise the optimal strategy that these poor natives could use to maximize their survival rate.
Assumptions:
1) All the 10 people can easily understand your strategy, and will execute it with perfect precision.
2) If the monster suspects that any of the people are giving away information to any of the remaining team members by intonation of words when answering, or any other signs, or by touch, he will eat everyone.
3) The only allowed response is a short, unemotional "white" or "black".
4) Having said that, I will add that you can put any value you like into each of these words. For example, "white" can mean "my mother did my laundry" and "black" can mean the guy in front of me is wearing a black hat.
Hint
1) First hint is an example. Here is a simple strategy that will guarantee safety to 50%. Guy #10 (when he guesses) says the color of the hat on guy #9. Thus #10 may die or may luck out, but #9 will save himself since he will know his hat color. Thus #8 helps #7, #6 helps number #5, and so on. You thus save numbers 9, 7, 5, 3, and 1, or half the people. But you can do a lot better than that.2) The best strategy will save a minimum of 90% of the people.
Answer
Here it is: The first guy to guess (guy #10) will be the only one to assume the following value for the words "white" and "black": The answer "black" will mean that there are an odd number of black hats that he sees. The answer "white" will mean that there are an odd number of white hats that he sees. This way one by one all the other 9 people will know the color of their hats.Let us say that guy #10 (first to speak, and sees the hats of the remaining 9) says "white". That should mean to everybody else that he sees an odd number of white hats. At this time guy #9 will either be wearing a white or a black hat. If he is wearing a white hat he will only see an even number of white hats, and since guy #10 said that there is and odd number of white hats, guy #9 will know that he is wearing white and will say it. But if guy #9 is wearing a black hat, he will see an odd number of white hats (just like #10 did), and thus will know that he is wearing a black hat and will say it. No matter what #9 answers, guy #8 (who heard guy #10 and guy #9) can now easily incorporate the color of hat on guy #9 into the original answer of guy #10. This will allow #8 to know if he should see an odd or even number of white hats in front of him to determine his own hat color. The same thing repeats with #7-1. And they all get it right except of course #10, though he may get lucky.
Hide Hint Show Hint Hide Answer Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments
Nice teaser!
Wow, this one makes a lot of sense logically. Great teaser.
it makes sense but i would never have came to that answer
What's wrong with simply saying the color of the hat of the person infront of you? Same survival percentage.
In reply to "Asbestos'" comment. You would only save 50% that way. If you say the color of the person in front of you (lets say black), he/she still has to say black not to get eaten (regardless of what the color in front of them is). So therefore the 3rd person in line will not know their own color since the person before them saved themselves and didn't necessarily speak the color of the next person.
Nice teaser...but situation might mess up after the number 9 guess says his answer. And plus the monster might have put them on not white black white black...etc.
Golfer, there's nothing wrong with the logic in this teaser. It will work no matter what arrangement of hats the monster uses. Also, assumption #1 states that person number 9 WILL NOT mess up. I must say that this is a terrific logic teaser in my opinion.
This was a great riddle with great logic. The best i could do was save a minimum of five depending on the arrangement of hats.
I think it was a bit long personally but it does all make sence so great teaser
The logic works well. Actually, even if person 9 makes the wrong answer, the monster will eat that person, which would be a pretty strong indicator that they made the wrong decision. This could also be accounted for. The only person who need be correct is 10, the rest can be saved by their own logic.
Wow, that was an exellent teaser!
Another way to win is if the 10th guy tells everyone that "white" means your hat is the same color as the guy in front of you and "black" means your hat is a different color from the guy in front of you. Therefore, the only two who have to rely on luck are the 1st and the 10th
This will not work Pookie21. You need to say the colour of your hat in order not to get eaten.
Adamko
Adamko
Awesome logic teaser, one of the best I have seen. I could only think of the 50% solution, so I was going to stand and fight to the death. Maybe dig a large spike filled covered hole behind the 10th person as a trap for the monster. But that is not really solving the teaser, it is a Captain Kirk type of solution. 8^)
This is by far the best teaser I've read here. course, i just got here and am going thru the 'most popular list'.
BTW, I came up with the even guys sacrifice by saying the color of the guy in front of thems color, like many of you. Which would result in AT LEAST 50% survival (odds-wise more like 70 or 80%). Think about it. .. however tyhe solution is brilliant! 90% guaranteed, with 100% possible.
Really cool puzzler!
BTW, I came up with the even guys sacrifice by saying the color of the guy in front of thems color, like many of you. Which would result in AT LEAST 50% survival (odds-wise more like 70 or 80%). Think about it. .. however tyhe solution is brilliant! 90% guaranteed, with 100% possible.
Really cool puzzler!
That's going STRAIGHT to my favourites list ... TOTALLY a GREAT teaser. It was really fun n.n; and really hard as well Oo; ... I came up with some weird thing that was just a guess ... nice brain BTW.
-tangerine-
-tangerine-
Boy, would I not wanna be the last person in line...
Wouldn't mind being the last guy. Being the first guy is a problem. Brilliant teaser!
My solution was that the last person would say Black or White depending on how many times the colour changed in front of him. Black for even no. of times and white for odd no. of times. From this each person could find out his own colour by seeing the no. of colour changes and deciding whether he is the same colour as the one in front. The given soln. is much simpler, though.
Ya, I got this one. If you know anything about computers, this is the same concept as parity. The way I did it is that White means there are an even number of white hats, while black means odd. Take 0 to mean even. Great riddle
Great Logic! I loved the teaser.
Jan 05, 2004
A 3.0/3.0 teaser. One of the best
thats a hard 1
great teaser!
If the first guy yells out the color of the hat of the guy in front, he's got a 50/50 shot at guessing right for his own. From then on, everyone knows the color of their own hat.
OOPS - that won't work.
it's too long!
That was a hard one for me.
Good one
Good one
nice teaser!
I think I've done a similar one a long time ago, but it involved 3 people, pink&purple hats, and a wall separating 2 people from the other person...
I think I've done a similar one a long time ago, but it involved 3 people, pink&purple hats, and a wall separating 2 people from the other person...
The whole thing about and odd number of black and white hats deosn't make sense. if there are ten hats, and an odd number (let's say 7) of white hats, then there are an odd number of black hats too (3 in this case). What does the last guy yell if there are an even number of each? (let's say 4 white and 6 black). If there are an odd number, then it shouldn't matter what color he yells.
This is in response to ragsdaleam:
If you read the solution carefully, it doesn't suggest that you should communicate the color that has an odd number of hats, it suggests that you should communicate weather one specific color (agreed upon in advance) will be present in an odd amount or an even amount. In other words if we agreed that "white" means that there is an odd number of blacks, and "black" means that there is an even number of blacks, we will always be able to relate weather there is an even or odd number of black hats (independent of how many white hats there are).
If you read the solution carefully, it doesn't suggest that you should communicate the color that has an odd number of hats, it suggests that you should communicate weather one specific color (agreed upon in advance) will be present in an odd amount or an even amount. In other words if we agreed that "white" means that there is an odd number of blacks, and "black" means that there is an even number of blacks, we will always be able to relate weather there is an even or odd number of black hats (independent of how many white hats there are).
Or you can have it done as it states in the solution, where all you are looking for is an indication of weather or not one of the colors is odd or even (independent of how many hats of the other color there are). To figure out what you have you just gotta count. So in your example of 7 black and 3 white. If I know that there is an odd number of whites and I am the 9th guy. I can count what is ahead of me. I will either see 3 whites or 2 in front of me and if I see 2 then I have the third one. Same logic for all consecutive players.
Directly form your explanation of the answer:
"The answer "black" will mean that there are an odd number of black hats that he sees. The answer "white" will mean that there are an odd number of white hats that he sees."
So what would he say if there are an even number of both?
"The answer "black" will mean that there are an odd number of black hats that he sees. The answer "white" will mean that there are an odd number of white hats that he sees."
So what would he say if there are an even number of both?
You know, funny enough, you are right. I am surpirsed no-one noticed. The solution still works just needs to be rephrased:
The answer "black" will mean that there are an ODD number of black hats that he sees. The answer "white" will mean that there are an EVEN number of black hats that he sees (zero black hats should be treated as an even number).
The answer "black" will mean that there are an ODD number of black hats that he sees. The answer "white" will mean that there are an EVEN number of black hats that he sees (zero black hats should be treated as an even number).
Ragsdaleam, your logic is a little off. The tenth person can only see 9 hats, so theres no way that he can see both an odd number of black and an odd number of white hats.
Yes, ever since Ragsdaleam's comment on the fact that if there are 8 black, then there are 2 whites, everybody has been wrong. Number 10's hat color has NOTHING to do with the puzzle, because he can only see 9 hats. If he sees 3 black hats, then he will see 6 white hats, so he will say black, and therefore save his fellow native's, and maybe even his own life (Whether his hat happens to be black or not, he has a 50/50 chance).
First of all I want to say that this was an excellent riddle. The answer given makes sense and is one solution to the problem, but I believe me and my colleagues have found an alternate solution which results in the same survival rate. Check this scenario out: Overnight we agree that when the monster asks the color of the hat of native #10, he will call out the color of the person in front of him. From native #9 onward we will use a code system, if you answer "quickly", that will mean that the color of the person in front of you is white, if you give a "delayed" answer, that will mean that the color of the person in front of you is black. In this way you can save a minimum of 90% of the natives with a possible 100% if the #10 guy gets lucky. I think this is a less complex answer and it is simpler to understand.
for Paragon83. Your answer would be great actually if not for the "Assumption" section of the teaser. Points (2) and (3) have been clarified for that exact purpose. If the monstr suspects any such foul play the risk is that everyone will get eaten.
hehehe...i don't think that the poor natives will understand because they not even know what is odd and what is even.As you said earlier the solution must be simple so that the natives can understand easily.if some of them make a mistake.......the monster will be happy.
Mar 10, 2010
Does the ansewer work if the monster uses 5 black and 5 white hats. It doesnt say that in the question
Mar 10, 2010
Doesnt* the ansewer only work if he uses 5 of each?
Jan 29, 2011
Again you can only assume that the monster doesn't pick that combination of hats
I have a solution that is slightly more optimal than the given one. It involves an arbitrarily high level of precision for the villagers, but given assumption 1 such strategies are valid. The strategy is as follows:
Black hats represent 0. White hats represent 1. The last villager sees 9 hats, and thus 9 digits that represent a unique number in binary form. The 10th villager then waits exactly this many (arbitrarily small) time units from the time he is prompted to guess his color before giving an answer. All other villagers then have perfect information about every villager's hat from 1 to 9.
When it is each villager's turn to 'guess,' they each wait the exact amount of time before giving their answer as did the first villager, so there is no distinction between answers and the monster has no reason to suspect foul play.
The reason this solution is slightly more optimal is because it results in a higher probability of the 10th villager surviving. In the given solution, the 10th villager's answer is completely determined by the monster's configuration of hats, and cannot be changed. In my solution, the 10th villager can give the guess that is statistically favored (or just a random guess), thus ensuring a 95% survival rate in all cases.
Black hats represent 0. White hats represent 1. The last villager sees 9 hats, and thus 9 digits that represent a unique number in binary form. The 10th villager then waits exactly this many (arbitrarily small) time units from the time he is prompted to guess his color before giving an answer. All other villagers then have perfect information about every villager's hat from 1 to 9.
When it is each villager's turn to 'guess,' they each wait the exact amount of time before giving their answer as did the first villager, so there is no distinction between answers and the monster has no reason to suspect foul play.
The reason this solution is slightly more optimal is because it results in a higher probability of the 10th villager surviving. In the given solution, the 10th villager's answer is completely determined by the monster's configuration of hats, and cannot be changed. In my solution, the 10th villager can give the guess that is statistically favored (or just a random guess), thus ensuring a 95% survival rate in all cases.
This is definitely one of my all time favorites! I worked on this for DAYS and ultimately came up with this overly complicated equation, that as it turns out simply meant that if there were an odd number of white hats #10 would say white, and if there were an even number of white hats, he'd say black. I didn't even realize that that was the answer I ended up with until I looked at the solution and read back over my answer. I'm either dumb for a smart guy or smart for a dumb guy. Or possibly just lucky for a dumb guy.
As for Vecht's answer, what a creative solution! I tried to think of a way to make binary code work for me, but I just couldn't make it fit. Although I think the given answer is a whole lot simpler. And #10's chances are 50/50 no matter what. No amount of statistical analysis will help, because the teaser states that the monster places the hats at random. No matter which color #10 says, whether he says it because it imparts meaning to the others, or because he was guessing, he will still have a 1 out of 2 chance of getting it right as long as the hat placement was random.
But anyway, kudos to sakirski for a killer logic puzzle!
As for Vecht's answer, what a creative solution! I tried to think of a way to make binary code work for me, but I just couldn't make it fit. Although I think the given answer is a whole lot simpler. And #10's chances are 50/50 no matter what. No amount of statistical analysis will help, because the teaser states that the monster places the hats at random. No matter which color #10 says, whether he says it because it imparts meaning to the others, or because he was guessing, he will still have a 1 out of 2 chance of getting it right as long as the hat placement was random.
But anyway, kudos to sakirski for a killer logic puzzle!
Sakiriski, you are now one of my fave teaser-posters. I got the same solution as the answer (yay!) but I think both krishnan and Vacht's solutions are possible too. Loved this.
Wait. The answer's wrong. white- EVEN number of BLACK hats. Black- ODD number of BLACK hats. That's the solution that I got and it works all the time. I'm not sure the solution posted always works.
Princess, your answer and the teaser's answer are equivalent. Even number of white hats = odd number of black hats when the total number of hats is odd.
@spikethru *total number of hats that can be seen by the end person (i.e. total - 1)
The answer only works for an even number of natives. The updated answer of sakirski (Jun 06, 2005) works always, which is the same as the one given by princess2007 (Feb 22, 2013).
However there is another solution. This is a real solution. Not something with time intervals to add some extra form of communication. Here it is:
The natives first have to determine a colour they should say as follows: #2 should just say the colour of #1. The others should should WHITE when the person in front of them has the same hat as the colour they should say to save all natvies in front of them and BLACK otherwise.
Then #10 starts by saying the colour he determined (he might get lucky). Then going forward everybody has to keep track if the colour the person is saying is the actual colour or the opposite and update his own colour accordingly.
For example: #10 says WHITE. So #9 can just say the colour he determined. He says BLACK. Then #8 has to switch colours. He says BLACK. So #7 knows #8 switched colours and realizes #8 should have said WHITE, which means he can just say the colour he determined for himself. etc. etc.
Believe me... The natives will be spared (except maybe #10).
However there is another solution. This is a real solution. Not something with time intervals to add some extra form of communication. Here it is:
The natives first have to determine a colour they should say as follows: #2 should just say the colour of #1. The others should should WHITE when the person in front of them has the same hat as the colour they should say to save all natvies in front of them and BLACK otherwise.
Then #10 starts by saying the colour he determined (he might get lucky). Then going forward everybody has to keep track if the colour the person is saying is the actual colour or the opposite and update his own colour accordingly.
For example: #10 says WHITE. So #9 can just say the colour he determined. He says BLACK. Then #8 has to switch colours. He says BLACK. So #7 knows #8 switched colours and realizes #8 should have said WHITE, which means he can just say the colour he determined for himself. etc. etc.
Believe me... The natives will be spared (except maybe #10).
Great Teaser. The fact that all the remaining people will hear the outcome of the guess is unnecessary.
What a fantastic teaser! Good point from jad that the natives don't need to hear who gets eaten. I had no idea what Boardy was suggesting.
This was very difficult to solve, but also very fun. This goes on my faves list.
This was very difficult to solve, but also very fun. This goes on my faves list.
To post a comment, please create an account and sign in.
Follow Braingle!