Problem 3

Problem

Let $n$ be a positive integer. Liu Bang and Xiang Yu have a stick of length $1$ and want to divide it between themselves. Liu first marks at most $n$ points on the stick, and then Xiang marks at most $n$ points on the stick. All marked points are distinct. The stick is cut at all marked points. Liu and Xiang then take turns claiming any unclaimed piece, with Liu moving first, and each aims to maximize the total length obtained.

Determine the largest real number $c$ such that Liu can guarantee pieces of total length at least $c$, regardless of Xiang's play.

Solution

The largest guaranteed length is

Set

Then

If the final piece lengths, sorted in nonincreasing order, are $x_1\ge x_2\ge\cdots$, optimal play gives Liu the odd-indexed pieces. His total is therefore

because the sum of all pieces is $1$.

This is the value of the draft. Liu can obtain at least the odd-indexed sum by always taking a largest remaining piece. Before his $j$th turn, at most $2j-2$ pieces have been claimed, so at least one of $x_1,\ldots,x_{2j-1}$ remains; Liu's choice is therefore worth at least $x_{2j-1}$.

For the reverse inequality, use induction on the number of pieces. If Liu first takes $x_i$, then Xiang is the first player on the sorted list with $x_i$ removed. By the induction hypothesis, Xiang can secure the odd-indexed sum of that shorter list. This sum is at least

Indeed, before the removed term, pair each $x_{2j-1}$ with $x_{2j}$ and use $x_{2j-1}\ge x_{2j}$; after the removed term, the terms contributing to the shorter list's odd-indexed sum line up exactly with the remaining even-indexed terms of the original list. Thus Liu receives at most $1-E=x_1+x_3+x_5+\cdots$. Together with the greedy lower bound, this proves the claimed draft value.

Liu's lower bound

Liu divides the stick initially into the $n+1$ geometrically increasing pieces

Their sum is $(2^{n+1}-1)\delta=1$, so this uses exactly $n$ marks.

After Xiang adds at most $n$ marks, there are at most $2n+1$ final pieces. Tag each final piece by the initial geometric piece from which it came, and sort the tagged pieces by length. Pair consecutive sorted pieces:

There are fewer such pairs than the $n+1$ possible tags. Form a graph whose vertices are the tags and whose edges join the two tags in each consecutive pair, allowing loops or repeated edges. Since the graph has fewer edges than vertices, at least one connected component has no odd cycle: a component containing an odd cycle has at least as many edges as vertices, so not every component can have that property. Such a component is bipartite. Two-color it by $1$ and $-1$, and color every other vertex $0$. This gives coefficients in $\{-1,0,1\}$, not all zero, with opposite coefficients at the ends of every edge.

For a fixed tag, the lengths of all pieces carrying that tag add to one of $\delta,2\delta,\ldots,2^n\delta$. Hence the coefficient-weighted sum of all tagged pieces is

The signed binary integer in parentheses is nonzero: at its least-index nonzero coefficient, reduction modulo $2$ prevents the remaining higher powers of $2$ from cancelling it. Its absolute value is therefore at least $1$, so the absolute value of the weighted sum is at least $\delta$. On every consecutive pair, the two coefficients are opposite, so that pair contributes either $0$ or plus or minus its length difference. If there is one unpaired final piece, its contribution has absolute value at most its length. Therefore $x_{2j-1}\ge x_{2j}\ge0$ bounds the absolute value of the whole weighted sum above by

Thus $A\ge\delta$, and Liu receives at least

Xiang's upper bound

Now let Liu make an arbitrary initial partition into $r\le n+1$ positive pieces.

If $r\le n$, Xiang bisects every initial piece. The final pieces occur in equal pairs, so their sorted alternating sum is $0$. Liu then receives exactly $1/2\le c_n$.

It remains to consider $r=n+1$. There are $2^r$ subset sums of the $r$ initial piece lengths, all in $[0,1]$. After sorting them, the $2^r-1$ consecutive gaps have total at most $1$, so one gap is at most $1/(2^r-1)$. The corresponding subsets are distinct. Removing their common intersection leaves two disjoint, not-both-empty collections with the same difference of sums, hence with total lengths differing by at most

Xiang refines the pieces in these two collections greedily into equal pairs: compare the first remaining lengths, match the smaller one, split the larger one if necessary, and continue. If the two collections contain $s$ original pieces in total, each matching step consumes at least one currently remaining source piece, so they create at most $2s-1$ refined pieces. Every unused initial piece is bisected. Combining the two counts gives at most $2r-1=2n+1$ final pieces, so Xiang uses at most $n$ new marks. Up to permutation, the final list consists of duplicated equal pieces and a remainder whose total length is exactly the difference between the two selected subset sums, and is therefore at most $\delta$.

When two equal entries are inserted into a sorted list, the equal values may be placed next to each other; their two opposite contributions cancel without changing the alternating sum of the remaining entries. Removing all duplicated pairs therefore leaves only the sorted remainder. Pairing adjacent terms shows that the alternating sum of a sorted nonnegative list lies between $0$ and its ordinary sum, so

Therefore Xiang can ensure that Liu receives at most

The lower and upper bounds coincide, proving the claimed value.