The Brain Teaser

My favorite brain teaser of all time (and that’s saying a lot, because I love brain teasers) goes like this:

If you haven’t yet heard this problem or attempted to solve it yourself, I recommend you pause reading here. (I won’t spoil the final answer, but I will walk through several non-optimal answers below.)

From a purely statistical standpoint, if each prisoner guessed their own hat color, they would have a one-in-two chance of guessing correctly. Therefore, on average, 50% of prisoners would be saved. But, there is also a possibility that zero prisoners would guess correctly, meaning none would be freed. Recall that the question asks for the strategy that guarantees a minimum number of prisoners saved. Clearly we can do better than zero.

Here’s a strategy that ensures that at least 50 are always freed: The one at the end (let’s call them #100), says not their own color but that of the prisoner before them (#99). Then #99 knows their own color and says it. #98 says the color of #97, who now knows their color. And so on. Using this method, 50 are guaranteed to say their correct color (the odd-numbered prisoners). And the remainder have a 50% chance of being correct.

Can we do better than that? We sure can. Here’s a strategy that ensures two-thirds of all the prisoners are freed: Instead of saying the color of the prisoner in front of them, every third in line indicates whether or not the color of the two before them matches. Red means the colors are the same. Blue means the colors are different.

So if #100 says “red”, #99 now knows that their hat color is the same as #98’s (which they can see). Say #98 is wearing red. #99 says “red” and is freed.

Now #98 is up, and since they heard #100 say “red”, they will know their color matches whatever #99 says. Since #99 said “red”, #98 says “red” and is also freed. Every permutation of three prisoners can be processed using the same logic. And at the end, with this strategy, 66 are guaranteed to go free.

Notice that, in this new method, the words of the colors don’t always carry the meaning of their underlying colors. Instead, one-third of the time, they’ve been encoded to mean something entirely different (“same” or “different”). An interesting approach…

Here’s the wild thing about this brain teaser. It is possible to come up with a strategy that guarantees that 99 out of the 100 prisoners go free. Not just 50 or 66, but 99 out of the 100 with absolute certainty.

(A quick aside: If you’re enjoying this article and aren’t yet subscribed to this free weekly newsletter, click here to subscribe!)

Simple and Elegant

The first time I heard this brain teaser, I thought of nothing else for days. To devise a strategy that would ensure 99 prisoners are freed seemed mathematically impossible. When I finally did solve it, I was so excited and surprised by the answer that I recall shouting it out loud (and in so doing, spoiling the solution for a friend sitting beside me who was also thinking about the same problem).

The reason this brain teaser is my favorite is because, despite the Herculean objective we’re trying to achieve, the solution is so simple and elegant it seems to defy all logic. It is so simple, in fact, it’s actually more straightforward and easy to explain than the inferior solutions outlined above (the ones that save 50 and 66 prisoners, respectively).

Even today, decades after I first heard about the 100 prisoners and their 100 hats, I think about it often. Several reasons why:

• It proves that some of the most complicated problems have very straightforward solutions. They’re just hard to see at first.

• It proves that we humans tend to overthink, that when faced with a problem, we tend to widen the solution-space to include intricate or non-intuitive solutions.

• It proves that Occam’s Razor, the maxim that states “The simplest explanation is usually the best one” can be thought of in the inverse: The best solution is usually quite simple.

History has no shortage of ingenious resolutions to problems that plagued humanity for years. Many of these problems seemed intractable until their simple solutions were surfaced.

Consider the illness and mortality rates that preceded the simple realization that germs cause disease, and soap kills germs.

Consider Copernicus’s realization that the Earth revolves around the sun. For thousands of years before, everyone knew the universe revolved around the Earth (the “geocentric” model), but was oddly incapable of explaining why any celestial body moved through the sky as it did. A simple and elegant change in framing (“What if we aren’t the center of the universe?”) suddenly allowed all of astronomy to click into place. (I’m reminded here of the best line from the film Men in Black.)

Consider scurvy, which afflicted sailors for centuries, and its myriad ludicrous explanations suggested by the experts of the day. That is until James Lind realized in the 1700s that simply giving sailors oranges and lemons prevented the malady (later verified as a mere Vitamin C deficiency).

Some of these solutions may even seem obvious in retrospect. Yet it took generations of brilliant minds to uncover them. In the end, these non-obvious, non-intuitive answers ended up being substantially simpler and more elegant than the many years of false hypothesizing earlier postulated.

A Caveat

As much as I love simple and elegant solutions, I do love this quote from Albert Einstein (whose Theory of Relativity is yet another example of the elegance of reframing discussed above). So I’ll give him the final word.

Einstein said, “Make everything as simple as possible, but not simpler.”

I agree. It’s just, sometimes, it’s hard to know where to draw that line…