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.
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?
All are invited to submit their solutions to email@example.com; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2021 ACM, Inc.
No entries found