Sign In

Communications of the ACM

Last byte

Stay in Balance


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
blocks on teeter totter

Credit: Getty Images

Two players, each with a collection of weights, sit in front of a plank that weighs three kilograms with two supports at −1 and +1. Each player wants to get rid of his or her weights, by placing them on integral markers, at most one weight per integral marker. So, for example, player A may not place a weight above A's weights or player B's weights. Further, neither player is allowed to place a weight at −1, 0, or +1.

In a turn, a player must put at least one weight somewhere on the plank, but may put several weights on the plank, if they are at consecutive integer marks. The goal of each player is to be the first to place all of his or her weights without causing the plank to tip (by having a strictly negative torque on the right support or a strictly positive torque on the left support).

Warm-Up: Let's say all weights weigh one kilogram and each player has six weights. Suppose each player always places as many weights as possible in each move (a "greedy" strategy). Which player will win?

Solution to Warm-Up: First player can put a weight at +2 and +3. So torque on left support is − (3*1 + 1*3 + 1*4) and on right support is 0. So player 2 can put weights at −2, −3, −4, −5. Now torque on right support is (1*6 + 1*5 + 1*4 + 1*3 + 3*1) – (1*1 + 1*2) = 18. The torque on the left support is now 0. Therefore the first player can add weights at +4, +5, +6, +7 and win.

So if we have just six weights of one kilogram and each is greedy, then the first player wins.

Question: If each player has seven weights of one kilogram and each is greedy, then which player wins?

Solution: Each player plays as before. After the first player adds weights at +4, +5, +6, +7, the torque on the left support is − (5 + 6 + 7 + 8) = −26 the second player can put his or her last weight at −6 and win.

uf1.jpg
Figure. Three-kilogram plank. "How can I be the first to place all my weights on the plank without causing the plank to tip?"

Question: Could the above change if the plank weighs more?

Solution: Yes, for example, if the plank weighed much more, then the first player could put all his weights on one side.

In non-greedy play, each player must put at least one weight somewhere on the plank during his or her turn. If multiple weights, they must be consecutive.

In the following upstarts, assume the same rules as before: the plank weighs three kilograms, weights can be put only on integral makers, and never on top of another weight.

Upstart 1: Is there any way the player who moves first can guarantee to win if he or she can choose the 10 integral weights that each player starts with provided each weight weighs at least one kilogram and all the weights are distinct with the further restrictions that the first player must play greedily but his or her opponent need not.

Upstart 2: One player is the chooser and given an n must choose exactly n distinct weights and they must each weigh an integral number of kilograms ≥ 1. The non-chooser decides whether to go first or second. Both must play greedily. For which values of n can the chooser guarantee to win?

Upstart 3: As in Upstart 2, the chooser, given an n, must choose exactly n distinct weights that must each weigh an integral number of kilograms ≥ 1. The chooser decides whether to go first or second, but must play greedily. The non-chooser need not play greedily. For which values of n can the chooser guarantee to win?

Back to Top

Author

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

Back to Top

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


Copyright held by author.
Request permission to (re)publish from the owner/author

The Digital Library is published by the Association for Computing Machinery. Copyright © 2021 ACM, Inc.


 

No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents:
  • Article
  • Author
  • Footnotes
  • ACM Resources