News for hackers. Stuff that matters.
Re:100 Prisoners and a Lamp by mikeash on Sunday November 24, 2013 @08:23PM (#6792003)
Spoiler ahead! Potential answer!

My solution is that the first prisoner states the color of the hat in front of him, the second prisoner states the color he just heard, and so forth with odd and even numbers until you get to the end. This saves 75% (even numbers are guaranteed to live, odd numbers live with 50% odds).

Is this optimal?

Re:100 Prisoners and a Lamp by ssfermoy on Sunday November 24, 2013 @08:28PM (#6792022)
If they decide the guy at the back indicates an odd number of black hats by saying white or an even number of black hats by saying black. Now the remaining prisoners all live and the back guy has a 50/50 shot.
Re:100 Prisoners and a Lamp by Ellipsis753 on Sunday November 24, 2013 @08:46PM (#6792077)
That's awesome. To me it seems like a parity bit for RAID or an error-correcting code.
Re:100 Prisoners and a Lamp by mikeash on Sunday November 24, 2013 @08:54PM (#6792098)
Very nice. It took me a while to see why that works, so I wonder how long it would have taken me to come up with it.

Now that I get it, it seems almost obvious. It's basically the same as my solution, except I'm essentially using this technique on 50 separate lines of 2 people each.

Re:100 Prisoners and a Lamp by ssfermoy on Sunday November 24, 2013 @09:15PM (#6792161)
Glad you like it. Heard this as an interview question at a trading company. Gave something similar to your solution and was asked for a better one, eventually work my way to the solution above but was given no indication if it was what they wanted. It wasn't a pleasant experience.