Presented by Cold Stone Creamery(R)

The Department of Mathematics Challenge of the Week

A solution and a new problem is posted every Monday during fall and spring semesters at www.cs.colostate.edu/~rmm

Email your solutions to solution@math.colostate.edu

One winner each week is eligible for a free ice cream and topping, courtesy of Cold Stone Creamery.


Challenge 2, Fall '04

A prison faces budget cuts, and the warden has to reduce the number of inmates by ten. He rounds up ten of the prisoners and announces his plan for accomplishing this. In the morning, he will line them up, put them all in straightjackets, blindfold them, and put a cap on each of them. The blindfolds will then be removed, and each prisoner will be able to see only the colors of the caps of people in front of him in the line.

Each cap can be red or green, and the colors will be assigned randomly; even ten caps of one color are possible.

Starting from the back of the line, each prisoner must announce his guess about what color his own cap is. Afterward, the ones who guessed correctly will be set free, and the ones who guessed incorrectly will be executed.

The prisoners have a chance to get together the evening before to come up with a collective strategy for maximizing the number of survivors. What is the best strategy?

Solution: The main insight is that if you're one of the prisoners and you happen to know the parity of the number of red caps the prisoner behind you sees in front of him, you can figure out your own cap color: you have a red cap if and only if the number of red caps you see in front of you has the opposite parity.

Prisoner 10 says red if he sees an even number of red caps in front of him, and green otherwise. This allows Prisoner 9 to announce the correct color of his cap. Together with knowledge of the parity of red caps Prisoner 10 sees, the prisoners in front of 9 now know the parity of the red hats that 9 sees. Knowing this allows Prisoner 8 to figure out and correctly announce the color of his own cap. Together with knowledge of the parity of red caps that 9 sees, this allows prisoners in front of 8 to figure out the parity of red caps that 8 sees, etc.

Working by induction from 9 down through 1, we see that all Prisoners 1-9 will answer correctly. (Prisoner 10 will also survive if he's lucky.)

People who got this solution: Ben Joeris (student at Fort Collins High), Tim Ellis (undergrad), Tim O'Connor, Li Hua (grad), Ben Manvel (faculty), Julien Gagneur (Cellzome Corporation, Heidelberg). Many others submitted interesting schemes for saving between six and eight prisoners.

For questions, comments or suggestions for future challenge problems: please e-mail Ross McConnell, rmm@cs.colostate.edu.