Posts Tagged ‘logic puzzle’

Spinning Room (puzzle)

January 21, 2013

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:

F: freedom

A: 3/1

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.

spinning_room

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:

Opposite buttons

Adjacent buttons

Opposite buttons

One button

Opposite buttons

Adjacent buttons

Opposite buttons

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.”

New Problem: Lights In A Room

November 11, 2010

You have probably seen puzzles involving lights in a room before, but here’s one I heard recently that was new to me.

There’s a room with 64 labeled light bulbs, each of the which can be either on or off, and each of which has its own switch. You walk into the room and find the light bulbs in some arbitrary pattern of on and off. You get to flip one light bulb of your choosing (and you are forced to flip exactly one switch).

Next, you leave the room and I enter. By looking at the pattern now on the lights, I might be able to get some information – you might be able to send me a message.

How much information can we communicate this way? If we convene before hand to create a strategy and write a list of messages we want to be able to send, how long should the list be?