The 23 prisoner problem

I’ve been thinking about the 23 prisoners puzzle on David Weinberger’s blog, and I’ve come up with an answer. It’s different than the one Mike Booth found. Mike’s solution has a very nice elegance to it; mine is a brute force probability solution, which relies all numbers coming up equally often–eventually.

I don’t remember enough of my statistics to calculate the expected time for my solution to free all the prisoners, but I have a strong suspicion that it’s not nearly as long as you would think. I don’t think it’s a coincidence that there are 23 prisoners in the puzzle. This is exactly the number of people you need in a room for the probability of two of them sharing a birthday to be 50% (the “Birthday Paradox”).

Anyway, here’s the (a) solution. Look away now if you want to try the puzzle on your own.

Part 1: Properties of the two-switch system

With two binary switches, you can encode four digits: 0, 1, 2, and 3. However, because you have to change the state of one and only one of the switches, there are some states the switches cannot be in when you leave the room. For example, if the switches are set to zero (off, off), you can set them to 1 (off, on) or 2 (on, off), but you can’t set them to 3, nor can you leave them at 0.

What you can always do, however, is ensure that the switches encode an odd or an even number. No matter what state the switches were in when you entered the room, it is your choice whether they end up odd or even when you leave the room. (See diagram below.) Thus, you can leave a 1-bit message to the person who enters the room the next day.

Part 2: Instructions for the prisoners

In your strategy session on the first day, every prisoner is given a number from 1 to 23. You also agree to keep a new kind of calendar, where every month has 23 days, also numbered from 1 to 23. (The names of the months are not important, just that after day 23, you roll back around to day 1 again.)

On all subsequent days, whenever you go into the switch room, you set the switches to “odd” if your prisoner number matches the number of the calendar day. If your number doesn’t match the calendar day, you sets the switches to “even”.

What you also have to do is “read” the 1-bit message the previous prisoner sent to you. As soon as you enter the switch room, you know two pieces of information:

1. The number of the previous day (e.g., day 16)
2. Whether that day’s prisoner (number 16) was in the room yesterday (if the switches were set to “odd”)

Now, all you have to do is wait, and keep track of all the days when a the correctly numbered prisoner was in the switch room the day before you. Eventually (after many months) you will have visted the switch room on all 23 days. And eventually you will reach a point where you will have marked off all the prisoner numbers on your checklist. Then you can go tell the warden to let you all go.

Will this really work?

I think so, eventually. The calculation isn’t quite the same as the Birthday Paradox, though. With birthdays, the probability of catching two on the same day increases as you get more people into the room. With the prisoner problem, even though each additional prisoner increases the chances of one of them getting an incredibly lucky streak, each additional prisoner also increases the number of “coincidence events” that are necessary for everyone to go free.

The real-world answer, of course, is that they’re all ‘gator food no matter what. Either

• A) they wouldn’t agree on a strategy on that first day, or
• B) someone would forget what strategy they’d agreed on, or
• C) the solitary confinement would drive someone mad enough to fancy their chances with the alligators instead of spending another day in the box, or
• D) the warden was just messing with their heads, and never had any intention of setting them free in the first place. He was twisted enough to come up with this scheme. Do you really think he’s going to let his evil plans be thwarted by a bunch of pesky kids?

Update: Several people have pointed out the flaw in my reasoning. I’ve written a little more about it here.