Problem 3

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 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 maximise the total length of their own pieces. For each

n

, determine the largest value

c

such that Liu may guarantee a total length of at least

c

, regardless of Xiang's play.

Step 5 of 5: Conclusion

Previous step Next step

c=\frac{2^n}{2^{n+1}-1}

Detailed analysis

Taking $k=n$ in step 4 (and dividing back by the scale factor $2^{n+1}-1$ ) shows Xiang's total $x_2+x_4+\cdots+x_{2n}$ is at most $\tfrac{2^n-1}{2^{n+1}-1}$ , so Liu guarantees at least $1-\tfrac{2^n-1}{2^{n+1}-1}=\tfrac{2^n}{2^{n+1}-1}$ . Combined with Xiang's upper bound from step 3, the largest guaranteed total length for Liu is $c=\tfrac{2^n}{2^{n+1}-1}$ .