JNL

flickr

(via Bengal Tiger | by JnL | Flickr)

Here’s a fun question I got asked during a job interview. (I will not, of course, say where.)

Ten prisoners are going to be executed at dawn. The executioner gives them one chance at survival. In the morning, the prisoners will line up in single file, and the executioner will place a white or black hat (randomly selected) on each prisoner’s head. He will then ask each prisoner the color of the hat they are wearing, starting at the back of the line. The prisoners can only respond with “white” or “black.” If the prisoner is correct, they will go free; if they are wrong, they will be executed.

Each prisoner can see all the hats in front of them, but not their own hat or the hats behind them. Each prisoner can hear everything; they know the responses of the prisoners behind them and whether or not they were executed.

The prisoners can meet beforehand to decide on a strategy.

What is the maximum number of prisoners you can guarantee will be saved, and with what strategy?

Hint #1 [rot13]: Gurer vf n jnl gb thnenagrr gung avar bs gur gra cevfbaref jvyy fheivir.

Hint #2 [rot13]: Vs avar bs gur gra ner thnenagrrq gb fheivir, gurve nafjref zhfg or qrgrezvarq ol gurve bja ungf. Bayl gur svefg cevfbare pna neovgenevyl pubbfr jurgure gb fnl “juvgr” be “oynpx.” Jung fbeg bs vasbezngvba pna ur pbairl hfvat bayl bar ovg?

There is a real-world technical problem that can be solved using a similar strategy.