20051015, 12:53  #1 
Aug 2005
Brazil
2×181 Posts 
Classic: Hats puzzle
Many people already know this puzzle, but others might find it interesting, at least.
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. Most people know this puzzle by the "prisioner" version: 10 straightjacketed prisoners are on death row. Tomorrow they will be arranged in single file, all facing one direction. The guy in the front of the line (he can't see anything in front of him) will be called the 1st guy, and the guy in the back of the line (he can see the heads of the other nine people) will be called the 10th guy. An executioner will then put a hat on everyone's head; the hat will either be black or white, totally random. Prisoners cannot see the color of their own hat. The executioner then goes to the 10th guy and asks him what color hat he is wearing; the prisoner can respond with either "black" or "white". If what he says matches the color of the hat he's wearing, he will live. Else, he dies. The executioner then proceeds to the 9th guy, and asks the same question, then asks the 8th guy ... this continues until all of the prisoners have been queried. This is the night before the execution. The prisoners are allowed to get together to discuss a plan for maximizing the number of lives saved tomorrow. What is the optimal plan? P.S: After you try to solve it by the "black and white" case, assume the 7 rainbow colors are used. After that, generalize it to N people and K colors of hats. Good luck 
20051015, 15:48  #2 
Jan 2003
far from M40
5^{3} Posts 
Obviously, the 10th person has a 50% chance to survive, as noone
except the monster can see his/her hat's colour. Nonetheless, the person is able to see all the other 9 hats. As 9 is odd, there must be an odd number of either white or black hats remaining. So, by "guessing" the color which appears an odd number of times, the 10th person survives with 50% chance and gives away all information needed to save the remaining 9. The (2n+1)th person survives by confirming his/her neighbour's choice, if that colour appears an even number of times among the remaining 2n hats, and altering it otherwise. The 2nth person survives by confirming his/her neighbour's choice, if that colour appears an odd number of times among the remaining (2n1) hats, and altering it otherwise. If there were an odd number of inhabitants, the one who's asked first would have to "guess" a preagreedupon colour, if his/her neighbour's hat has the colour that appears an odd number of times among the remaining ones, excluding his/her neighbour. 
20051016, 02:08  #3  
Jun 2003
1,579 Posts 
Quote:
Anyway for the probability of being eaten is here, based on position #10=50% #9=33% .... Since the person standing first in the line has the lowest probability of being eaten, standing there is the best thing. They will avoid the monster the longest. But again it is based on luck and anything can happen. Citrix Last fiddled with by Citrix on 20051016 at 02:10 

20051016, 05:03  #4 
Jun 2003
3·1,619 Posts 
General Strategy  N people. K colors
Assign the colors numbers from 0 thru K1.
Person(N) sums up the colors of all the people in front of him modulo K, and announces the corresponding color. He will survive with probability 1/K. Person(N1) also sums up the colors in front of him modulo K and then subtracts the color announced by person(N) (again modulo K). He survives!! Repeat! Last fiddled with by axn on 20051016 at 05:04 
20051016, 05:21  #5 
Jun 2003
62B_{16} Posts 
I have a variant of this question:
If the monster wanted to eat a person. Say the name of one of the persons their was XYZ and the monster wanted to eat him for some personal reasons. Then how should the monster place the hats such that it is most likely that he will be having XYZ for dinner tonight. What algorithm should the monster use? Citrix 
20051016, 11:23  #6  
Jun 2003
The Texas Hill Country
441_{16} Posts 
Quote:
Quote:
This collaboration is implied by the statement of the task. However, you are looking at the individuals rather than the collective group. I believe that you should be seeking a solution that maximizes the expected number of survivors. Perhaps you should consider the idea of sacrificing one individual to save the majority of the group. 

20051016, 11:33  #7  
Jun 2003
The Texas Hill Country
3^{2}×11^{2} Posts 
Quote:
CHEAT (change the rules)  Assuming that the group is capable of determining and executing the optimum strategy, the odds of survival are independent of the actual color placements. 

20051016, 11:45  #8  
Aug 2005
Brazil
2·181 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Classic problem: Four 4's  Ken_g6  Puzzles  105  20161020 20:36 
Suggestions for the "Classic Summary" page  davieddy  PrimeNet  26  20110613 09:38 
"Classic" (colourful) Status report  davieddy  PrimeNet  6  20091004 08:33 
Dot puzzle  nibble4bits  Puzzles  37  20060227 09:35 
Classic puzzle  JuanTutors  Puzzles  24  20050828 23:46 