Solution: The Prisoners' Hats Probem

The N=3 solution is: Guy #3 says "black" if the hats in front of him are a different color, "white" if they are the same. He may live or die. Guy #2 understands this message, and says the same color as Guy #1 if he hears "white." Guy #1 understands these messages, and says the same color as Guy #2 if Guy #3 said "white."

The generalization of Guy #3's "same/different" message is Guy #N's "even/odd parity" message. Guy #N says "black" if he sees odd parity (i.e. if there are an odd number of black hats), "white" otherwise. Guy #i says "white" if the number of black hats on guys #i-1 through #1 plus the number of black announcements of guys #N-1 through #i+1 equals the even/odd parity that Guy #N said.

The generalization of even/odd parity (to K hat colors) is modular arithmatic. If the hat colors are numbered zero through K-1, Guy number #N says the color number of the sum of the hat colors he sees mod K. Guy number #i uses the hat colors seen and heard by Guys #N-1 through #i+1 with the original modular sum announced by Guy #N to deduce his own hat color.

Back