One-hundred prisoners all in a line. How many live and how many die? The answer depends entirely – well, almost entirely – on you.

This week's puzzle is one of my favorite twists on a popular style of brain teaser involving prisoners and hats. The goal of these riddles is nearly always the same: A prisoner must win her freedom – and, occasionally, the freedom of her fellow prisoners – by correctly identifying the color of her hat, which she cannot see. How does a prisoner deduce the color of her own hat, based on the visible hats and/or actions of her fellow prisoners?

Advertisement

Two well-known variations on this genus of puzzle involve three captives in a line, or four prisoners arranged single file, with the third and fourth prisoners separated by a wall; many of you have suggested these brain teasers to me via e-mail in recent weeks, but today's puzzle involves significantly more prisoners – and a different approach – than either of these better-known versions. I've borrowed this version from the Tierney Lab post where I first encountered it. A few sentences have been modified for the sake of clarity.

Sunday Puzzle #9: The Puzzle Of 100 Hats

One hundred prisoners are lined up single file, facing in the same direction. Each prisoner will be randomly assigned either a red hat or a blue hat. No one can see the color of his or her own hat. However, each person is able to see the color of the hat worn by every person in front of him or her. To wit, the person at the head of the line cannot see the color of anyone's hat, the second prisoner can see only the first prisoner's hat, the third can see the first two prisoners' hats, and so on. The last person in line – the 100th prisoner – can see the colors of the hats on all 99 people in front of him or her.

Advertisement

Beginning with the last person in line, and then moving to the 99th person, the 98th, etc., each will be asked to name the color of his or her own hat. If the color is correctly named, the person lives; if incorrectly named, the person is shot dead on the spot. Everyone in line is able to hear every response as well as hear the gunshot; also, everyone in line is able to remember all that needs to be remembered and is able to compute all that needs to be computed.

Before being lined up, the 100 prisoners are allowed to discuss strategy, with an eye toward developing a plan that will allow as many of them as possible to name the correct color of his or her own hat (and thus survive). They know all of the preceding information in this problem. Once lined up, each person is allowed only to say "Red" or "Blue" when his or her turn arrives, beginning with the last person in line.

Develop a plan that allows as many people as possible to live. How many prisoners can you definitely save?


Looking for a hint? Here, in order of spoiler-potential, are some hints: 1 | 2 | 3

We'll be back next week with the solution – and a new puzzle! Got a great brainteaser, original or otherwise, that you'd like to see featured? E-mail me with your recommendations. (Be sure to include "Sunday Puzzle" in the subject line.)

Art by Jim Cooke

Solution to Sunday Puzzle #8: A Monkey And His Uncle

Last week, I asked you all to take a crack at a devilishly phrased word problem. The math, I told you, wasn't terribly complex (it requires basic algebra to solve), but I also warned that the puzzle would almost certainly require an organized approach to solve. After all, there's a lot of information to keep track of in this puzzle – the weight of the monkey, the weight of the uncle, the weight of the rope, and the monkeys' ages, for instance. And then, of course, there's that "evil" fifth sentence:

The uncle is twice as old as the monkey was when the uncle was half as old as the monkey will be when the monkey is three times as old as the uncle was when the uncle was three times as old as the monkey.

Last week, I stated over and over again that a clear plan of attack is the key to solving many good logic puzzles. Something I didn't mention, that was nonetheless masterfully demonstrated by several of you who submitted correct responses, is that a solution arrived at via a well-organized approach is almost always easier to verify and explain than one happened upon by way of ad-hoc inquest. One of the most elegantly presented solutions to last week's puzzle came from Kevindrewster, whose response begins with a lucid explanation of how he tackled this sentence, which many of you saw as the crux of the puzzle:

I found it easiest to work this "evil" sentence in reverse. To begin, we know that at some point in the past, the uncle was 3 times the age of the monkey. This doesn't give their ages, but it allows for a unit of measure to be established. Whatever age the monkey is at this time, let's call that 1 unit (1u). So, how old was the uncle when he was 3 times as old as the monkey? The uncle was 3u.

The previous part of the sentence states that the monkey will someday be 3 times this past age that we just established. So how old will the monkey be? He will be 9u.

Next, the uncle used to be half as old as this future version of our monkey. So, the uncle used to be 4.5u.

This first (and sort-of final) part of the sentence is the trickiest. The uncle is currently twice as old as the MONKEY was when the UNCLE was 4.5u. Well, we know that they both age at the same rate, so we can extrapolate. If the monkey was 1u when the uncle was 3u, then a year and a half later when the uncle was 4.5u, the monkey must have been 2.5u. Thus, we know that the uncle is currently twice the age of 2.5u, making him 5u.

Now, we can figure out the monkey's current age using the same technique we just used. (when the monkey was 1u, the uncle was 3u, so now that the uncle is 5u, the monkey must be 3u)

We also know that adding their ages will equal 4. So:

3u+5u=4

8u=4

u=4/8

u=.5

This makes our monkey 1.5 years old, and his uncle 2.5

Now, to finish off this puzzle! The monkey's weight is the same as the uncle's age, so the monkey weighs 2.5lbs. And since they're suspended at equal distances, we know that they must weigh the same. This will help us weigh the rope

The final sentence of the puzzle is actually pretty simple. The weight of the rope (R) plus the weight of the uncle (U) is one-half again (more simply put, 1 1/2 times) the difference between the weight of the monkey (M) and that of the uncle plus the monkey (U+M).

R+U=1.5((U+M)-M)

R+U=1.5U Then, subtract U from both sides, and you get

R=.5U

So the rope is half the weight of the uncle, making it 1.25lbs, or 20 ounces. Knowing that each foot of rope is 4 ounces, we can establish the length of the rope at 5 feet.

I hope this was easy enough to understand. If nothing else, I learned how hard it is to parse out complex algebraic word problems in a concise, easy to comprehend way.

Impressive job! Those looking for a purely mathematical answer to last week's riddle would do well to check out this response from TristanW, which includes of a photograph of some nice, clean, organized equations.

Previous Weeks' Puzzles