Communications of the ACM
Last byte
Fighting for Lava
Credit: Getty Images
The vast underground lava fields in the western U.S. feature a photogenic geyser called Old Faithful. Eruptions send approximately 15,000 liters of steaming water 50 meters into the air approximately every hour. Unfortunately, what is underground is not nearly as appealing. If the lava fields erupted in a major way, they could cause ferocious firestorms that would destroy a large portion of the western U.S. and Canada and substantially cool the planet.
Now imagine a pair of tunnel-boring energy-extraction companies are competing to cool the lava, make some money, and provide carbon-free energy besides. The idea is to tunnel from a power plant outside the lava fields to near the lava, but not too close, to avoid accidental eruptions. A pipeline could in theory then take cool water from the power plant to the end of the tunnel where the water would be heated into steam and the steam would power the turbines of the power plant. The whole system could be designed to recycle the steam back into water in a closed loop.
In this scenario, the federal government, which owns the land, steps in to lease the energy rights, identifying cross-sections underground to which tunnels can be drilled. The government identifies those underground cross-sections based on their more-or-less linear segments aboveground, so leasing a segment would confer the right to tap the lava in the vertical cross-section below that segment.
To encourage participation in the project while achieving equity for both companies, government mathematicians design a game-style protocol, whereby each company (player) takes turns to acquire non-overlapping sections of a full segment. The first player may take up to one kilometer in the first turn, the second player then takes up to two kilometers, the first player then gets up to three kilometers, the second then gets up to four kilometers, and so on.
Imagine a pair of tunnel-boring energy-extraction companies are competing to cool the lava, make some money, and provide carbon-free energy besides.
Warm-up. Suppose the line segment is five kilometers long from a stake at kilometer 0 to a stake at kilometer 5. Suppose the first player takes between 0 and 1 kilometer. Which player would get more of the line segment, assuming each plays optimally?
Answer to warm-up. Player 2. Player 1 takes kilometer 0 to 1. Player 2 then takes kilometers 2 to 4. The first player then takes one of the two remaining kilometers—1 to 2 or 4 to 5—and the second player then takes the other remaining kilometer. The second player ends up with lease rights to three of the five kilometers, thus one more kilometer than the first player.
Question 1. By playing differently, beginning with the first move, could the first player acquire the rights to more of the line segment than the second player?
Solution to question 1. Yes. If the first player takes kilometers 2 to 3, then the second player could take kilometers 0 to 2, but then the first player would take kilometers 3 to 5. The first player would thus get three of the five kilometers.
Question 2. Is there a minimal amount by which one player can win regardless of the length L of the segment?
Answer. Yes. The first player can win by at least one kilometer every time by going in the middle, meaning the halfway point of the first player's kilometer is at position L/2. After that, the first player would mirror the second player's moves. So if the second player takes x to x+2 to the left of the middle kilometer, then the first player takes (x + L/2) to (x + 2 + L/2) on the right of the middle. The net effect is the first player can always guarantee to capture at least as much territory as the second player on the two sides of that middle kilometer. The first player wins by at least the kilometer of the first move.
Upstart 1. Characterize situations in which the first player can guarantee to win by more than one kilometer or prove it cannot be done.
Upstart 2. Suppose the line segment is of length L, but there are now k players instead of two. The rules are a direct generalization of the original game; the first player may take one kilometer, the second player two, the third player three, ... the kth player k, the first player then takes k+1 ... and so on, all without overlap. Is there some length L and some number of players k whereby a player other than the first player can guarantee to capture more of the line segment than anyone else?
Upstart 3. Suppose the government leased out vertical cross-sectional squares belowground. Each player would thus take squares, with the side length of each square increasing by one kilometer with each move. The first player takes one kilometer squared. The second player then gets two kilometers squared. The first player then gets three kilometers squared, and so on, again without overlap. Does either player have a winning strategy if the area available to lease could be an arbitrary rectangular cross-section belowground? How would this generalize to more players?
Footnotes
All are invited to submit their solutions to [email protected]; 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 © 2019 ACM, Inc.
No entries found