When all numbers are on the wall, you are done.
The premise of the problem is very clear: How do you tally the presence of 100 unique events, some of which may repeat themselves, when you may use one and only one bit to register the state of the system?
Or use names, symbols, it doesn't matter. Just wait until there are 99 different ones on the wall.
Clearly, this would be a form of communication between the prisoners.
Reminds me of this:
http://blogs.msdn.com/b/ericlippert/archive/2011/02/14/what-...
If you need help on any of the puzzles, hints and answers are on the talk page. For this specific puzzle, the talk page links to a paper by William Wu that answers this exact question with asymptotic analysis.
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBul...
[2] http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board...
[3] http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board...
100 Prisoners are told they will be given white or black hats, but they don't get to see the hat they're wearing, they will be lined up facing the same direction, and they gun-to-the-head, say "black" or "white" and if they guess the color of their hat, they get to live.
They get to speak back to front, i.e., the rearmost prisoner sees all the hats ahead.
One strategy for optimizing the number left is to speak the color of the hat directly in front of you, in which case the prisoner ahead gets to live by repeating that color. This saves 50%, but of course there's a better solution.
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?
Also, one of the prisoners is not a 100-bit accumulator. He or she would be a 7-bit accumulator (128 > 100), but this is a very tortured way to say that this one prisoner can count to 100.
