Problem 3

For the converse, scale the stick by $2^{n+1}-1$; Liu can place his cuts so that the $n+1$ original segments have lengths $1,2,4,\ldots,2^n$. After Xiang's cuts, sort all pieces as in step 1. We prove by induction on $k=1,\ldots,n$ that $x_2+x_4+\cdots+x_{2k}\le2^{n-1}+2^{n-2}+\cdots+2^{n-k}$. For $k=1$ this says $x_2\le2^{n-1}$, since a piece longer than $2^{n-1}$ can only lie in the unique segment of length $2^n$, and two such disjoint pieces cannot fit there. Now suppose the assertion holds through $k-1$ and fails first at $k$. Subtracting the bound at $k-1$ from the failed bound gives $x_{2k}>2^{n-k}$. Since the pieces are sorted, every one of $x_1,\ldots,x_{2k}$ is strictly longer than $2^{n-k}$. A piece cut out of an original segment of length at most $2^{n-k}$ cannot be that long, so all these $2k$ pieces must lie wholly in the $k$ largest original segments, of lengths $2^{n-k+1},\ldots,2^n$. Consequently $x_1+\cdots+x_{2k}$ is at most their total $2^{n-k+1}+\cdots+2^n$. Pairwise sorting gives $x_{2i-1}\ge x_{2i}$, hence the sum of the even-indexed pieces is at most half of this total, namely $2^{n-k}+\cdots+2^{n-1}$, contradicting failure at $k$. This proves the induction; the strict inequality also handles zero or coincident cuts without a limiting argument.