Switches brainteaser
I’m a huge brainteaser fan… thus, I was looking at Joel Spolsky’s blog and I came across a nice one: the 23 Prisoners and the 2 switches riddle.
I figure that this is one of those brainteasers whose answer depends both on the current state of the switches and the prisoners’ memories of the switches; thus, the position of the switches does not comprise the entirety of the state of the problem. That said, I think some base cases would help:
- The answer for one prisoner is trivial. On the first day, after visiting the switch room, the prisoner knows that all the prisoners have visited the switch room. The prisoner is therefore free.
- The answer for two prisoners goes like this: the two prisoners confer, and decide that Prisoner A is given Switch A, while Prisoner B is given Switch B. The first important information point comes when the warden takes the other prisoner to the switch room: if for the last n times Prisoner A has been going, the first time that Prisoner B goes to the switch room, we have a good starting point. Prisoner B notices the position of the switches, and flips the designated switch (switch B). On any further visits, Prisoner B flips switch A. When Prisoner A gets a turn, Prisoner A will notice that Switch B has been flipped, and therefore Prisoner B has visited the switch room. Thus, Prisoner A knows for sure that both prisoners have visited the switch room. The reverse situation works as well…