Some discussion on Facebook led me to this puzzle:
You’re in a room with four holes, and through each hole is a button. Each time you press the button, it toggles between on and off, but you don’t know what it is to begin with and can’t tell the difference when you press the button. You have two hands, so you stick them through any two holes you choose, then either press the buttons or not. After you press the buttons, they spin around a random number of quarter turns. You can then do it again, but you don’t know whether you’re pressing the same or different buttons as last time. You’ll be free from the room when all four buttons are on or all four are off. How can you escape the room with 100% accuracy in finite time?
Here’s how I thought about it:
First, it doesn’t matter if, for example, you use the holes front and left or left and back. These are both adjacent holes, and since you don’t know how the thing’s been spun, it’s functionally the same. Thus, on each turn you only have three choices:
1) Press a single random button.
2) Press two opposite buttons.
3) Press two adjacent buttons.
Next, let’s consider the possible states of the buttons. For example, you could have three on and one off. There are four different way to do this, but since the thing spins randomly, they are all the same as each other and we can count them as one. Also, the problem is symmetric with respect to switching “on” and “off”, so we can consider three on/one off and three off/one on to be the same state. Thus, there are only four states:
B: 2/2, with opposite switches the same
C:2/2, with adjacent switches the same
Next we draw a graph showing how choices 1,2, and 3 take us between states. Blue is 1, Red is 2, Green is 3. When there are different arrows of the same color, that choice has the ability to take us different places at random.
It’s now pretty easy to make sure we escape to F. The red choice is convenient. With it, we either escape or stay put, so start with red. If you’re still stuck, you’re in either A or C. Green is now convenient because it leaves A alone while reducing C to a previously-solved case, so use green, and if not free, red. If you’re still not free, you must be on A, so do blue, red, green, red and you’ll be free.
Translating this back into the original problems, you do:
and by the time you finish all that, you’re guaranteed free.
Most of the work here was just in finding a decent way to re-visualize the problem. Once we drew the graph, finding the way out was trivial. I’ve frequently found this to be the case with tricky problems. Of course, the other main tool to solve them is “assume a clever solution exists, then work backwards.”