Library / /740 of 740

, 2024

Combinatorics Difficulty 6.1 National Olympiad Prove it United States

Problem:

Jasper and Rose are playing a game. Twenty-six $32$ -ounce jugs are in a line, labeled Quart $A$ through Quart $Z$ from left to right. All twenty-six jugs are initially full. Jasper and Rose take turns making one of the following two moves:
- Remove a positive integer number of ounces from the leftmost nonempty jug, possibly emptying it
- Remove an equal positive integer number of ounces from the two leftmost nonempty jugs, possibly emptying one or both of them. (Attempting to remove more ounces from a jug than it currently contains is not allowed.)
Jasper plays first. A player's score is the number of ounces they take from Quart $Z$ . If both players play to maximize their score, compute the maximum score that Jasper can guarantee.

Solution

Solution:

Notice that after any sequence of moves, the leftmost nonempty jug has at most as many ounces as the second leftmost nonempty jug.

Jasper's strategy for $31$ is as follows: as long as at least two jugs are nonempty, remove all but one ounce from the first jug. This will ensure Rose only ever gets to take one ounce from one or two jugs at a time, so on Jasper's turn the first jug will always have more than one ounce. Eventually, Rose will be forced to take one ounce from jug $Y$ and at most one from jug $Z$ , leaving at least $31$ for Jasper.

It remains to show $32$ is not attainable. If all but jugs $Y$ and $Z$ are empty on Rose's turn, then Rose can guarantee at least one ounce. Thus, the only way Jasper could guarantee all $32$ ounces in Quart $Z$ is by making Rose empty jug $X$ without touching jugs $Y$ or $Z$ , so that Jasper can then take all $32$ from $Z$ in one move. This can only happen if Rose is forced to empty jugs $W$ and $X$ simultaneously; otherwise, Rose would have the option to empty part of $Y$ as well. But then Rose could just empty $W$ only, contradiction.

Thus $31$ is maximal.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.