Blur Circle

Steve Yost's weblog
February 15, 2003
Car Talk Puzzler: Switches and Prisoners

Here's my answer to the Car Talk puzzler that I noticed on David's site yesterday. I sent him an answer last night, then woke early this morning realizing a flaw. Writing it again, I think I could state more concisely, but here's what I sent to David and Car Talk:

One prisoner is designated the record-keeper. The right-hand switch is used to indicate new visitors to the switch. When a person visits for the first time, he flicks the right-hand switch up if it's not already up -- otherwise he has to wait until he finds it down to switch it up.

If a prisoner finds the right-hand switch already up, he must flick the left-hand switch. Only the designated record-keeper can flick the right-hand switch down, to reset it for the next 'round'.

The first time the record-keeper visits the switch, he flicks it down if it's up, but he can't count that instance: he may be the first one to visit, and nobody knows the original state of the switches. On subsequent visits he keeps track of how many times he finds the right-hand switch up, and when it's 22, it's sure that 23 (including himself) have visited.

[Update 5:37am: I just read the IBM solution
(July 2002) and I see the error in mine. Each prisoner really must flick the right-hand switch up at the first *two* instances they find it down, and the record keeper must count to 44. That's because none of the non-record-keepers knows whether they're the first prisoner to visit (in which case their first visit won't be recorded by the record-keeper).

My answer would never result in an alligator meal, but it only has a 1/23 chance of freeing the prisoners (assuming random selection of prisoners): the count would only reach 22 if the record-keeper were chosen first.]

February 15, 2003 05:04 AM