Spinning Room (puzzle)

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.

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

Tricky Calculus Problem

Here’s a cute problem I heard from Moor Xu:

Let . has exactly three critical points. Find the parabola that passes through these critical points.

I’ve been doing a daily problem of the day for my physics camp students. Questions and answers are posted here the day after we give them to the students. I haven’t been copying them over to this blog because many are repeats, and none are original. They might still be entertaining if you’re in to that sort of thing.

Leakier, Slower, and No Rain

A while ago, I asked a standard freshman physics problem about a cart that has rain fall into it, then opens a hole and rain leaks out. Then I gave an answer saying that as rain falls vertically into an open cart running on a frictionless track, the cart slows down, but as rain leaks out it shows no change in speed.

That was mostly correct, given the picture I drew of the hole:

Water leaks out a hole in the bottom of the cart as it slides to the right.

The key is that the hole is in the center. Yesterday, Martin Gales posed a question on Physics.StackExchange pointing out that this makes a difference, because if we imagine a stationary cart with a hole all the way to the left, then as it drains, the water moves left, and so the cart will have to move right a little to conserve momentum. But then once the cart starts moving the water leaking out of the cart is moving…

I spent three hours last night trying to solve this seemingly-trivial problem. (My answer is at the original question.) It’s simple enough to pose to first-term freshmen, and yet I went through dozens of slightly-wrong ideas and calculations before hitting on the surprising answer. Further, once I knew what happens, it didn’t seem very complicated any more, leaving me to wonder what the hell is wrong with my overclocked simian brain. The feeling you get when thinking about such a problem is an asymmetric oscillation of healthy frustration and premature joy unparalleled in other pursuits. I want to be mind-fucked like this every night.

Answer: Lights in a Room

The problem asked

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 must flip one).

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.

If we convene before hand to create a strategy and write a list of pre-recorded messages we want to be able to send by picking one off the list, how long should the list be?

The answer is that the list should be 64 messages long.

By the pigeonhole principle, 64 messages is an upper bound, because when you enter the room you have have to choose between 64 light bulbs.

We’ll prove 64 is attainable constructively.

Since we’re flipping a switch, it’s natural to think about the parity of the bulbs. We’re not interested in the parity of the entire sequence, though; that is forced to change because you flip exactly one switch.

If we wanted to settle for a two-item list, we could simply consider the parities first and second halves of the bulbs independently. We can easily control the parity of the first half by flipping a bulb in the first half if we want to change its parity, or flipping a bulb in the second half if we don’t. This lets us encode a one-bit message, but it’s a wasteful strategy. All the bulbs in the first half are treated the same. It would be better to cut the sequence in half more ways, and do them simultaneously. Let’s call these different halves “slices”.

Another natural slice is to take evens and odds. But in between first half/second half and even/odd slices there is a sequence of slices.

• (1-32), (33-64)
• (1-16, 33-48), (17-32, 49-64)
• (1-8, 17-24, 33-40, 49-56), (9-16, 25-32, 41-48, 57-64)
• etc.

Or, to put it another way, start the light bulbs’ numbering at zero and make the slices

1. (0-31 mod 64),(32-63 mod 64)
2. (0-15 mod 32),(16-31 mod 32)
3. (0-7 mod 16),(8-15 mod 16)
4. (0-3 mod 8),(4-7 mod 8)
5. (0,1 mod 4),(2,3 mod 4)
6. (0 mod 2),(1 mod 2)

The important thing about this breakdown is that it allows you to zero in on a single light bulb by saying that that it’s in the left half slices 1, 4, 5, and 6 and the right half of slices 2 and 3, for example. That uniquely picks out bulb 24. It also goes the other way. Any bulb has a unique combination of left halves/right halves.

This is perfect! Now we can send six one-bit messages at the same time. To send our first one-bit message, as before we control the parity of the first half of the bulbs. To send the second bit, we control the parity of the bulbs in the left half of slice two. To send the third bit, we control the parity of the bulbs in the left half of slice three, etc. There will always be exactly one bulb that correctly changes / fails to change all six parities in the way we want.

So we can send six bits, or 2^6=64 messages.

New Problem: Lights In A Room

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?

Solution: Halving the Triangle

The problem asked

Suppose you have an equilateral triangle and you want to cut it in half using a pizza cutter (which can cut curves, not just straight lines). What is the shortest cut you can make?

Two commenters got the correct answer. The cut is one sixth of a circle whose center is at a vertex of the triangle.

It’s not immediately obvious to me why this is true. However, the following picture from Mahajan’s book makes it pretty clear.

Assuming the cut goes from one side of the triangle to another, we could tile six triangles around to make a hexagon, and find a minimum-length cut to divide all the triangles in half. As long as you believe a circle has the minimum perimeter for a fixed area, this should be pretty convincing.

New Problem: Halving the Triangle

Here is a wonderful problem I read about in Sanjoy Mahajan’s Street-Fighting Mathematics (link to full book pdf).

Suppose you have an equilateral triangle and you want to cut it in half using a pizza cutter (which can cut curves, not just straight lines). What is the shortest cut you can make?

“Cut in half” means you wind up with two pieces of equal area, not necessarily two identical pieces.

Hint: You might be able to solve this with some fancy calculus, but you can get away with a picture if it’s clever enough.

Answer: Lemmings (part 2)

Here is another answer to the Lemming problem, complementing yesterday’s answer.

In case you’re behind, the problem was:

On a remote Norwegian mountain top, there is a huge checkerboard, 1000 squares wide and 1000 squares long, surrounded by steep cliffs to the north, south, east, and west. Each square is marked with an arrow pointing in one of the eight compass directions, so (with the possible exception of some squares on the edges), each square has an arrow pointing to one of its eight nearest neighbors. The arrows on squares sharing an edge differ by at most 45 degrees. A lemming is placed randomly on one of the squares, and it jumps from square to square following the arrows.

Prove that the poor creature will eventually plunge from a cliff to its death.

For this proof, we’ll again focus on closed loops, this time proving they cannot not have a “rotation”, and so the lemming must fall.

As before, we argue that because the number of squares is finite, the lemming will run around a closed loop if and only if it never falls off. Also, the loop must be simple, specifically it cannot cross itself (see previous solution for detail).

Next we introduce the new concept of a path. A path is like a closed loop – a sequence of squares next to or diagonal from each other that you can trace your way around. The difference is that a loop is something the lemming would actually follow because the arrows point from one square on the loop to the next, whereas in creating a path we ignore the arrows. So a loop is a special case of a path. Because we know that any viable loop doesn’t cross itself, we will only consider paths that also do not cross themselves.

An example path. It ignores the arrows underneath it, which in this example are in a legal configuration.

Although we don’t look at the arrows when creating a path, we can still notice the arrows once the path is created. That is what we’ll do, using the arrows to define a “rotation” for each path.

Consider an arbitrary path. Trace your way around the path, noting each jump involved. For each jump, the arrow underneath where you are will, in general, rotate. It can rotate up to 45 degrees when moving between squares that share an edge and up to 90 degrees when moving diagonally.

If the arrow rotates 45 degrees clockwise as you jump, call that +45. If it rotates 45 degrees counterclockwise, call the -45. Similarly for 90 degrees. If the arrow remains the same, call that zero. Sum the rotations from all the jumps going around the path and call that the path’s rotation.

A path that closes on itself must have rotation that is a multiple of 360, because it starts and ends with the same arrow.

Consider a 2×2 path. There are four transitions, each with a rotation of at most 45 degrees. Since this cannot let you build up to 360 degrees, any 2×2 path must have rotation zero.

A 2x2 path must have rotation zero. Red are the arrows. Green is the path. Blue are the jumps.

Similarly for a triangular path like this:

A small triangular path like this must also have rotation zero.

How about a 3×2 path? Such a path is built up from two 2×2 paths. When placing the two 2×2 paths on top each other, the overlapping parts cancel because they are traversed in opposite directions. Hence, the rotation for a 3×2 path is the sum of the rotations for the two 2×2 paths. All 3×2 paths have rotation zero.

If you traverse the green path, then the purple path, the transition you do twice cancels, and all the other transitions sum to the same thing as the gold path.

We can build up an arbitrary non-crossing path from lots of 2×2 squares and triangles. An arbitrary path’s rotation is the sum of its constituent little paths. Since the little paths’ rotations are zero, all big paths have rotation zero, too.

Our original example path made up of lots of little squares and triangles. Some squares are used twice.

On the other hand, a loop like the lemming would follow is also a path, and it must have rotation +/- 360 since loops cannot cross themselves. A loop cannot have rotation zero and rotation 360. These loops cannot exist, and the lemming dies.

Answer: Lemming

The problem asked:

On a remote Norwegian mountain top, there is a huge checkerboard, 1000 squares wide and 1000 squares long, surrounded by steep cliffs to the north, south, east, and west. Each square is marked with an arrow pointing in one of the eight compass directions, so (with the possible exception of some squares on the edges), each square has an arrow pointing to one of its eight nearest neighbors. The arrows on squares sharing an edge differ by at most 45 degrees. A lemming is placed randomly on one of the squares, and it jumps from square to square following the arrows.

Prove that the poor creature will eventually plunge from a cliff to its death.

Here is a proof using reductio ad absurdum:

First, prove that if the lemming never falls off there must be a closed loop the lemming goes around endlessly.

There are 1,000,000 squares, so by the lemming’s 1,000,001^st jump, it must have revisited at least one square. Take the first instance in which the lemming revisited a square. From there it will repeat exactly what it did the first time it hit that square, going on and on in a closed loop.

An example of a closed loop for the lemming to roam on. The remaining arrows aren't filled in. This turns out not to be a valid path.

So, if the lemming is not going to fall off, there must be loops on the checkerboard, and if there are loops on the checkerboard, then obviously it is possible for the lemming to avoid falling off.

Now we only need to prove that loops do not exist. To begin, we’ll assert that if loops do exist, they must be fairly simple. Specifically, they cannot cross themselves.

Take a look at the green box pasted onto the original example below. It highlights the region where a loop crosses itself. This is not a legal configuration of arrows because the 45 degree rule is violated, but any time a loop crosses itself it must do it this way. Hence loops don’t cross themselves.

The same loop as before, but here we see that when a loop crosses itself it must break the rule about rotating only 45 degrees between squares that share an edge.

Now we know that we’re considering simple, non-crossing loops, and we want to prove they don’t exist. We assume they do and find a contradiction.

Simple, closed loops have an inside and an outside. We can categorize loops by how large they are – how many squares are on the inside. If we consider all the possible loops, there must be one (or a set of ones) that are the smallest. This sets a minimum size for loops.

A candidate simple loop with the inside of the loop shown in green.

We will show the existence of an arbitrary loop implies the existence of a smaller loop, contradicting the existence of a minimal loop size.

Suppose we have checkerboard A with a simple loop. We create a new checkerboard B which is just like A except that every single square has its arrow rotated 45 degrees in the same direction. The direction is chosen so that arrows on the loop are rotated towards the inside of the loop. This new checkerboard is legal if the first one was, because none of the arrows rotate relative to each other.

The loop on board A is old news. On board B, we rotate every arrow from board A 45 degrees (not all arrows shown, of course).

Imagine the lemming starting on board B on a green square. If it ever hits a square where the arrow is drawn, it will be pushed back into the green area on its next move. It can never escape to outside the old loop. The lemming instead runs around indefinitely on a combination of the old loop and the green. This means it finds a new loop, and because that new loop includes at least some green squares, it has a smaller inside.

Whenever there is a legal board with a loop, there must be another legal board with a smaller loop. This contradicts the fact that there must be a smallest loop. Thus there is no legal board with a loop and the lemming dies.

New Problem: Lemming

solution 1
solution 2

I’m at summer camp now, and my dorm is split between math and physics. I hear a lot of cute math problems. Here’s a recent one that I like. It’s significantly more “mathy” than some of the other cute problems I’ve heard.

This is from Ravi Vakil’s A Mathematical Mosaic: Patterns and Problem Solving

On a remote Norwegian mountain top, there is a huge checkerboard, 1000 squares wide and 1000 squares long, surrounded by steep cliffs to the north, south, east, and west. Each square is marked with an arrow pointing in one of the eight compass directions, so (with the possible exception of some squares on the edges), each square has an arrow pointing to one of its eight nearest neighbors. The arrows on squares sharing an edge differ by at most 45 degrees. A lemming is placed randomly on one of the squares, and it jumps from square to square following the arrows.

Prove that the poor creature will eventually plunge from a cliff to its death.