And now Martin Sutherland has found a solution to the vexing problem of the 23 prisoners. His solution is different from the one I found.
Martin has independently discovered that you can only relay one bit of information. I chose to describe the process as “switch B carries the information, and switch A allows you to waste time and avoid changing switch B”. Martin prefers to talk about “odd” and “even” settings. It’s exactly the same thing; we just use different words.
Unfortunately, Martin’s answer has a bug: he implicitly assumes that only one prisoner visits the switch room each day. The statement of the problem was:
from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room
and that means that there can be more than one prisoner selected each day. That’s a problem. Imagine that you enter the switch room at noon on Day 11 and see that the switches are set to “odd”, in Martin’s terminology. Martin would then have you conclude that Prisoner Number 10 was in the room yesterday (on Day 10). But that isn’t necessarily so. What if Prisoner 11 was in the room half an hour ago, and the “odd” setting was made by him?
Martin also implicitly assumes that at least one prisoner visits the switch room each day. That’s a problem, too. What if Prisoner 9 sets the switches to “odd” on Day 9, and then the warden takes Day 10 off and doesn’t bring anyone to the switch room on Day 10? On Day 11 a prisoner comes in and sees the switches set to “odd”. Does he conclude that Prisoner 10 was in yesterday? He’d better not!
So Martin’s solution, though ingenious, doesn’t solve the right problem. I haven’t been able to figure out how to fix it. And that’s too bad, because here’s another sign that Martin might be on the right track: The number 23 just happens to be nearly equal to the number of hours in a day. Instead of using a 23-day calendar, we could just assign each prisoner a different hour of the day, and speed up Martin’s system by a factor of 23!
Comment from Martin Sutherland (martin ~at~ sunpig .dot. com) at 02/14/2003 04:23:38 PM:
You’re right. My wife pointed out the same flaw earlier this evening. The number “23” is still bothering me, though. Why 23? Why not 38, or 15? If there is a reason beyond random chance, I think it must have something to do with the probable length of time it takes for the prisoners to be released.
Comment from Mike Booth (mike ~at~ castleblack .dot. net) at 02/14/2003 05:13:51 PM:
Martin,
I’m not sure that 23 isn’t a completely random number. It’s a decoy, designed to make you think that there’s something about the number (like the fact that it’s a prime, or the fact that it’s almost equal to the number of hours in a day) that makes it special.
It’s sort of like the way in which the problem uses two switches instead of just one. They could have set up the problem with a single switch, and removed the requirement that the prisoner flip the switch, and it would have been the same problem (as both you and I have argued). Why not set up the problem that way? Because it makes it easier to see the solution! Having an extra switch creates the optical illusion of four useful states, while in fact there are only two.
Comment from Cam Solo (camsolo ~at~ hotmail .dot. com) at 07/06/2003 07:47:07 AM:
There is a solution here: http://socpol.anu.edu.au/~cbrown/stuff.php3
Comment from Chris Shih (christopher_shih ~at~ hotmail .dot. com) at 12/09/2003 07:36:22 PM:
What if the warden only has each of the prisoners in 30 times each? The “Counter” will never have reached 43 and will never know when to declare that they have all visited. The prisoners will all assume that other prisoners are going and not them and therefore will be stuck in the prison forever.