Single-file hat execution

Riddle courtesy of William Wu’s riddle archive.

10 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. Assume each prisoner can hear each previous answer.

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? How many lives can you save?

The original riddle calls for you to also generalize the plan to N prisoners and K different color hats. I haven’t done that yet.

This entry was posted in Uncategorized. Bookmark the permalink.

8 Responses to Single-file hat execution

  1. amy says:

    the only answer i could come up with for this one is dependant on how they say the word.. something like loud for black and soft for white…

  2. Patrick says:

    I’d like a little clarification. Does the prisoner know if the previous prisoner got it right or not? If the executioner doesn’t tell them “right” or “wrong” then knowing what the previous man answered doesn’t help much.

    I suppose you could always just get everyone to choose 1 color. That at least theoretically saves 1 life, unless there is a chance that you have 10 black hats and 0 white, or vice versa. Since this doesn’t tell you how many of each type of hat there are, assuming that the prisoner knows if the previous prisoner got the answer right or not, my gut instinct is to tell each prisoner to choose the same color hat as the one before them if they get it wrong and are killed, but switch colors if the previous one got it right. It’s as good a plan as any.

  3. Robert says:

    dependant on how they say the word

    It’s possible to solve this without relying on inflections, loudness, pauses, or anything else except the color guessed by each prisoner.

    Does the prisoner know if the previous prisoner got it right or not?

    There’s at least one solution doesn’t require that knowledge. I suppose if it helps, you can assume they execute or release each prisoner immediately when he guesses, and that the other prisoners are aware of this.

    tell each prisoner to choose the same color hat as the one before them if they get it wrong and are killed, but switch colors if the previous one got it right. It’s as good a plan as any.

    If the hats alternate colors (BWBWBWBWBW) and the first guy guesses “B”, he’ll live. The second guy will guess “B” and die. The third guy will then switch and guess “W” and die, etc. So all but 1 person dies.

    Another solution can guarantee a 50% survival rate. Every other prisoner (1,3,5,7,9) says the color of the hat in front of him. He may live or die, but it guarantees the survival of prisoners 2,4,6,8,10.

    It is possible to guarantee that, for N prisoners, N-1 lives are saved.

    I solved this by solving for 2, then 3, then 4 prisoners.

  4. amy says:

    apparently, you can save all but one guy. (got some help on this one). they get together and decide that they will use a code for the first guy. the code will tell them if there is an odd number of white hats or even number. black for odd, white for even. if you’ve got BWWBWWBBW, the first guy would say black. the next guy would know there is an even number of white hats, but he only sees four, so he knows he’s got a white had too. the next guy now knows that the guy before him had a white hat, so now there should be an even number, but he only sees three white, so he can guy white as well, and be safe. the next guy knows the two guys before had white hats, so there should now be an odd number, which there is, so he knows he’s got a black hat… and so on and so forth.

  5. Ohad & Doron & Kedem says:

    The following solution is for the N-person and K-color problem. It is based upon the creation of three groups of series that represent the reminders of hats that every person sees according to a base of the number of colors.
    The distance between each series in a group should be the number of colors K, whereas the range of the numbers in the group is from 0 to K-1.
    For example in the case of K=3 and N=100, we defined the following three color groups – x,y and z.
    x (0 0 0; 1 1 1; 2 2 2) – represents that each color appears with an equal reminder.
    y (0 1 2; 1 2 0; 2 0 1) – represents that each color appears in a cyclic form.
    z (0 2 1; 1 0 2; 2 1 0) – similar to y, but in an ti-cyclic form.
    The first person declares either x, y or z according the reminders of the colors that he/she counted. From here onwards, the next in line counts the number of reminders and completes his/her color according to the declartion of the previous declaration.
    bon chance

  6. I didn’t understand anything you said!

    Why not do the parity thing? You can save (N-K) prisoners, with each of the first K prisoners being assigned a particular color and announcing the parity bit excluding the first K prisoners. Each subsequent prisoner would have to have a pretty good memory, but would simply determine which color was not “in parity” so to speak and know that he had that hat on.

  7. Riddle says:

    the way to save everyone but the last guy in line is have a code whisper black loud white. The last guy in line says, doesn’t matter in what voice, the color of the hat of the guy before him. The guy in front of him (9th in this case) repeats the color, but in low/high voice depending if the hat of the guy in front of him is black/white. The guy in front then says his color, but in a relevant tone of voice… etc….

  8. Spidy says:

    UMMM…. If the only color hat you cant see is your own then why doesnt the the `10th guy who is in the back of the line and who will be executed first call out the color of the guys hat in front of him hoping that it is also the same color as his own. Apon hearing this the 9th guy will know the color of his hat. Now he cant call out the color of the persons hat in front of him if it doesnt match his own or he’ll be killed, so they say the color of thier hat in a loud voice if the persons hat matches there’s own or soft if it doesnt . This way 9 are saved for sure and possibly the 10tht if his hat matches the guys in front of him :)

Comments are closed.