Posts Tagged ‘puzzles’

A calculator is broken so that the only

April 27, 2013

A calculator is broken so that the only keys that still work are the sin, cos, tan, arcsin, arccos, and arctan buttons. The display initially shows 0. Given any positive rational number q, show that pressing some finite sequence of buttons will yield q. Assume that the calculator does real number calculations with infinite precision. All functions are in terms of radians.

I’ve started reading Zeitz’s The Art and Craft of Problem Solving. This one took me about 90 minutes, though as usual, once I had a solution it seemed obvious. Originally from USAMO 1995. Who comes up with these problems? How? You sit down and say, “Okay, it’s time to invent a problem that can be solved with elementary math, but only if you see some diabolical trick”, and then you do what?

Advertisements

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