As both Mike Booth and my wife pointed out, my solution to the 23 Prisoners Problem is flawed. It works if the warden takes one prisoner into the switch room every day, but the puzzle explicitly says that this isn’t the case:
“After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room.”
Damn. I’d felt so pleased with myself for figuring it out. I even sent David Weinberger a link to my solution. He posted a link to it on his blog, which means that I can’t go back and destroy all evidence of trying…. Curse the permanence of the web!
My solution tried to solve the problem by allowing the prisoners to add some extra bits of information to the problem. But the problem is phrased very carefully to ensure that no extra information beyond the state of those two switches can be inserted. The random selection of prisoners, and the random interval between them being picked, effectively destroys any attempt to pass state information in any other way.
Mike’s solution is wonderfully elegant, but I can’t help feeling that there is another way it can be done. The fact that problem emphasises the evenness of the random distribution (“But, given enough time, everyone will eventually visit the switch room as many times as everyone else.”) makes me think that there is a probabilitistic answer somewhere. Also, with there being exactly 23 prisoners, I can’t help but wonder about a connection with the Birthday Paradox.
Or maybe the number 23 is just a coincidence stemming from the Law of Small Numbers (i.e., there aren’t enough small numbers for each of them to have a unique purpose).
More pondering is required.