'(The Blog) With No Name', perhaps best described as a stream of notes and thoughts - 'remembered, recovered and (sometimes) invented'.

Monday, May 09, 2005

Of Prisoners And Switches - A Puzzle

is a nice puzzle featured on the 'Ponder This' column at IBM Research, long back. It is about a group of prisoners, isolated from one another (they can have one preliminary discussion and they will be in cells thereafter), and are randomly and repeatedly made to toggle one of two switches, alone. They have to devise a protocol to work the switches and figure out whether all of them have actually been to the room with the switches at least once.

The solution to the puzzle provided at the same place involves the prisoners electing a spokesman and this spokesman following a different protocol from the others - and only he can actually decide the answer. What follows should hopefully make some sense (and provide some extra fun) if you have gone thru the abovementioned pages.

I have been wondering whether any protocol that solves the problem has to be necessarily a spokesman-based protocol. The present guess is that a protocol where no prisoner among N prisoners is special and everyone of them can potentially answer the question CANNOT be found if there are only two switches as in the original problem.

A simple case: There are two prisoners, two switches. Neither prisoner is special. Both follow similar protocols. Can this work?
The answer apparently is 'yes'. Both prisoners and switches could be numbered 1 and 2. Each prisoner toggles 'the other' switch on the first visit. Then, on every subsequent visit, each toggles only 'his' switch - both keep note the position of both switches throughout. Then, one of them (the prisoner who actually made the FIRST visit) is bound to see 'his' switch toggled by the other prisoner from the state he saw it last. Then he can announce that both guys have been to the switch room.

Assuming this is correct, one could try more cases ( the case of 3 prisoners +3 switches, it appears can be solved by a straightforward extension of the above method; beyond that it is less clear...)and explore underlying patterns and deeper facts. One could also worry about how to improve the spokesman protocol given at IBM if there are more than 2 switches available for the N prisoners to play with.