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 3 of 5: Pigeonhole on the 2^(n+1) subset sums bounds Liu from above

Previous step Next step

2^{n+1}\ \text{subset sums }\Sigma(S)\in[0,1]\ \Longrightarrow\ \exists\,S\ne T:\ 0\le\Sigma(S)-\Sigma(T)\le\frac1{2^{n+1}-1}\ \Longrightarrow\ G\le\frac1{2^{n+1}-1}

Detailed analysis

As $S$ ranges over all $2^{n+1}$ subsets of the $n+1$ segments, the sums $\Sigma(S)$ all lie in $[0,1]$ , with $\Sigma(\varnothing)=0$ and $\Sigma(\text{all})=1$ . Dividing $[0,1]$ into $2^{n+1}-1$ subintervals of length $\tfrac1{2^{n+1}-1}$ , the pigeonhole principle gives two distinct subsets $S,T$ with $0\le\Sigma(S)-\Sigma(T)\le\tfrac1{2^{n+1}-1}$ . Deleting $S\cap T$ from both makes $S,T$ disjoint without changing $\Sigma(S)-\Sigma(T)$ , so step 2 lets Xiang guarantee $G\le\tfrac1{2^{n+1}-1}$ , i.e. Liu's total is at most $\tfrac12\bigl(1+\tfrac1{2^{n+1}-1}\bigr)=\tfrac{2^n}{2^{n+1}-1}$ .