Problem#

Let $n$ be a positive integer.

Liu Bang and Xiang Yu have a stick of side length 1 and want to divide it between themselves. Liu marks at most $n$ points on the stick, and then Xiang marks at most $n$ points on the stick. The marked points are distinct. Then, the stick is cut at all marked points, creating a number of pieces. Afterwards, they take turns claiming any unclaimed piece of the stick, with Liu going first. Each player’s goal is to maximize the total length of their own pieces.

For each $n$, determine the largest value of $c$ such that Liu may guarantee a total length of at least $c$, regardless of Xiang’s play.

Solution#

As many may agree, the lower bound $c\ge \dfrac{2^n}{2^{n+1}-1}$ is quite intuitive, so I’ll leave its complete proof as a small practice. Therefore, I will focus on proving the other direction.

First, suppose the final pieces have lengths

Liu can guarantee at least $x_1+x_3+x_5+\cdots$ by always taking a longest remaining piece.

Similarly, Xiang can guarantee at least $x_2+x_4+x_6+\cdots$ by taking a longest remaining piece on each of his turns. Since all the lengths sum to $1$, this limits Liu to at most the odd-indexed sum. So assuming optimal play, it would be:

In particular, if all the pieces can be grouped into equal-length pairs, the two players each receive $\frac12$. If there is also one unpaired piece of length $z$, Liu receives $\frac{1+z}{2}$. To see this, arrange equal lengths consecutively in the sorted list: each pair contributes equally to the odd- and even-indexed sums, while the unpaired piece contributes the difference $z$.

Suppose Liu’s marks divide the stick into $m$ intervals of lengths

where $m\le n+1$.

If $m\le n$, Xiang can simply bisect every interval. This uses at most $n$ marks and leaves only equal-length pairs, so Liu receives at most $\frac12$.

It remains to consider $m=n+1$. The nice part is that we can find two almost equal collections of intervals by looking at all $2^m$ subset sums

List these sums in nondecreasing order, keeping repetitions:

The $2^m-1$ consecutive gaps sum to $1$, so at least one gap has size

Take the two distinct subsets giving this gap, and cancel their common indices. We obtain disjoint subsets $P,Q$, not both empty, such that

Now Xiang matches the intervals in $P$ against those in $Q$. Choose one unmatched piece from each side. If their lengths are equal, pair them and set them aside. Otherwise, cut the longer one so that one part has the same length as the shorter piece, set this equal-length pair aside, and continue with the leftover part.

All these cuts can be planned before the stick is physically cut; Xiang only needs to mark the corresponding points.

When the pieces on the $Q$ side are exhausted, the unmatched pieces on the $P$ side have total length $d$. If any remain, Xiang bisects all but one of them. This leaves equal-length pairs and just one unpaired piece, whose length $z$ satisfies

If no pieces remain, put $z=0$. Xiang also bisects each of the original intervals whose index is outside $P\cup Q$.

We still need to check that this construction uses at most $n$ new marks. Write $s=|P|+|Q|$, and suppose the matching process leaves $r$ unmatched pieces. Each matching step that requires a cut reduces the number of unmatched pieces by one; a step matching two equal pieces reduces it by two without a cut.

If $d>0$, then $r\ge1$, so the matching process uses at most $s-r$ cuts. Bisecting all but one of the remaining pieces uses another $r-1$ cuts, for a total of at most $s-1$.

If $d=0$, no unmatched pieces remain. The final matching step pairs two equal pieces without a cut, so the process uses at most $s-2$ cuts, which is also at most $s-1$.

Finally, the intervals outside $P\cup Q$ require $m-s$ bisections. Therefore, the total number of new marks is at most

Xiang has arranged all the final pieces into equal-length pairs, except possibly one piece of length $z\le d$. By always choosing a longest remaining piece, he can therefore limit Liu’s total to

This proves the upper bound.