MathLabs

Problem 3

Let nn be a positive integer. Liu Bang and Xiang Yu have a stick of length 11 and want to divide it between themselves. Liu marks at most nn points on the stick, and then Xiang marks at most nn 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 nn, determine the largest value cc such that Liu may guarantee a total length of at least cc, regardless of Xiang's play.
Step 1 of 5: Reduce the claiming phase to the alternating gap G
Previous stepNext step
x1≥x2≥⋯≥x2n+1≥0,G:=x1−x2+x3−x4+⋯+x2n+1,Liu’s total=1+G2x_1\ge x_2\ge\cdots\ge x_{2n+1}\ge0,\qquad G:=x_1-x_2+x_3-x_4+\cdots+x_{2n+1},\qquad \text{Liu's total}=\frac{1+G}{2}
Detailed analysis

Allow coinciding cuts (giving length-00 pieces) so that each player makes exactly nn cuts and there are 2n+12n+1 pieces of lengths x1≥x2≥⋯≥x2n+1≥0x_1\ge x_2\ge\cdots\ge x_{2n+1}\ge0 with ∑i=12n+1xi=1\sum_{i=1}^{2n+1}x_i=1. During the claiming phase, each player optimally takes the largest remaining piece on their turn, so Liu collects x1+x3+⋯+x2n+1x_1+x_3+\cdots+x_{2n+1} and Xiang collects x2+x4+⋯+x2nx_2+x_4+\cdots+x_{2n}. In terms of the gap G:=x1−x2+x3−x4+⋯+x2n+1G:=x_1-x_2+x_3-x_4+\cdots+x_{2n+1}, Liu's total is 1+G2\tfrac{1+G}{2} and Xiang's is 1−G2\tfrac{1-G}{2}, so maximizing Liu's total is equivalent to maximizing GG.