# Communications of the ACM

Last Byte

## Seesaw Gold

Consider a seesaw of length six meters. The fulcrum is at the three-meter mark. There is a gold weight of one kilogram on meter two and one kilogram at meter four. This is represented as: _1_f1__ where the "_" represents no weight, the "1" represents a weight of one, and the "f" represents the fulcrum, which is just a point (see the accompanying image).

Warm-Up: Once we let the seesaw tilt, what will happen?

Solution to Warm-Up: Because the torque on the left side is greater than the torque on the right side, the seesaw tilts toward the left. The configuration will evolve as follows:

_1_f1__ initial configuration

1_1f___ all weights move one to the left (skipping over the fulcrum point)

_1_f___ the leftmost weight falls off the edge

1__f___

___f___ the second weight falls off and seesaw regains balance

Figure. If torque is more on the left side than on the right, all weights will move one space to the left. If a weight is at the leftmost position and the seesaw tilts left, the weight falls off the seesaw. At that point, of course, that weight no longer exercises torque. All this works symmetrically on the right side. How does the situation in this image evolve?

Question: Can you create a seesaw with twice the weight on the right side than on the left but where all the gold weights fall to the left?

Solution: Here is one of many possibilities:

1__f2__ initial configuration more torque on the left

__2f___ left weight falls off but right weight goes to left side

Question: Can you find a starting configuration of length six meters that will start by tilting one way and then tilt the other before losing all the weights?

Solution: Here is one solution.

1__f_1_

which evolves as follows

1__f_1_ initial

___f1__ tilts to the left but loses that first weight

___f_1_ tilts to the right

___f__ 1 keeps tilting

___f___ the second weight falls off and seesaw regains balance

Question: On a seesaw of length 14, create a configuration such the seesaw tilts to the left, then to the right, then to the left again.

Solution:

1___1__f____1_ initial

___1___f____1__ left weight falls off

____1__f____1_ moves toward the right

___1_f___1 moves toward the right

___1f____ right weight falls off, so now seesaw will tilt to left

Now let's consider a game. One player is called Right and one is called Left. Each player wants as much weight in gold as possible to fall to his or her side. The seesaw is fixed at some length. Left places weights and then Right places weights. This is called the Left-first version of the game. Because Right has an advantage in the Left-first game, Left has one advantage: Left receives any weights on the seesaw if the seesaw ever reaches balance (as much torque on the left as on the right).

Question: Suppose Left has weights 1, 2, 3, as does Right. Suppose the board is only of length 6 (three to the left and three to the right of the fulcrum), then can Left guarantee to win?

Solution: Surprisingly, Left will win with 321fxyz where x, y, and z represent any values that Right puts on its part of the board. Here's why. First, if Right sets things up as 321f123, then the two sides have the same torque, so the seesaw will be in balance in which case Left gets all the weights. This implies that Right should allow the left side to have more torque at the beginning but then make it so the right side has more torque thereafter. The best possible such configuration is 321f132. Let's see what happens in that case. After one time unit, the configuration becomes 211f32_, because the leftmost 1 on the right side moves to the left. But then the torque on the left becomes 6 + 2 + 1 = 9 and on the right 3 + 4 = 7, so the board will stay tilted to the left thereafter. Because all weights fall to the left, let's call this a shutout.

Question: Now consider a board of length 8. Suppose Left has weights 3, 2, 1 in this configuration 321_fxyzw Where can Right put weights 1, 2, 3 in order to make as much weight as possible to fall to the right and avoid a balanced seesaw?

Solution:

321_f_132 initial

21__f132_ move to the left, 3 falls to the left, torque is 11 on left (8+3) and 13 on right

_21_f_132 move to the right

__21f__13 move to the right

___2f1__1 move to the right

____f21__ move to the right

The weights that fall to the right are all the initial rightside weights and the 2 and 1 from the left side.

End of solution

Question: Can Right always win when the weights are 1, 2, 3, and the board is of length 8?

Solution: No. Left can win with this: 231_fxyzw. Right cannot choose 231_f_123 because then Right would win once and then lose thereafter. Right cannot choose 231_f_132, because that would be in balance. Right could, however, choose: 231_f_231

Once we let the seesaw tilt, what will happen?

Left torque: 8 + 9+2 = 19; Right torque: 4 + 9 + 4 = 17.

Go left to 31__f231_ Left torque: 13

Right Torque: 11

Go left to 1__2f31__. Left torque: 6.

Right torque: 6. This would continue and be a shutout for Left. If Right did not use all three of the rightmost meters, the same configuration would again lead to a shutout.

Upstart 1: In the Left-first game, given a board length, weights for Left, and weights for Right, try to find an algorithm that determines a winning configuration for Left (meaning Right never gets more weight in total than Left) if there is one regardless of what Right does. If there is none, show how Right can win no matter how Left places its pieces. Do the same for shutouts.

We call the variation of the game in which Left places the first weight, then Right places a weight and so on until both sides run out Alternating.

Upstart 2: Answer the previous Upstart for the Alternating configuration.

### Author

Dennis Shasha (dennisshasha@yahoo.com) is a professor of computer science in the Department of Computer Science at the Courant Institute at New York University, New York, NY, USA, as well as the chronicler of his good friend the omniheurist Dr. Ecco.

### Footnotes

All are invited to submit their solutions to upstartpuzzles@cacm.acm.org; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html