Problem 3

Call the $n+1$ intervals made by Liu's cuts the original segments, and write $\Sigma(S)$ for the sum of the lengths in a subset $S$. Take disjoint subsets $S,T$, not both empty, and orient them so that $\Sigma(S)\ge\Sigma(T)$. Lay the segments of $S$ and $T$ out in their left-to-right orders on two rows, starting both rows at a common origin. Sweep from that origin: whenever the running endpoint in one row reaches an endpoint of a segment in the other row, Xiang cuts the corresponding physical segment at exactly that distance. Thus the portions traversed before the shorter row ends occur in equal-length pairs, while the longer row has one overhang of length $\Sigma(S)-\Sigma(T)$. Xiang bisects every original segment outside $S\cup T$; inside the overhang he also bisects each complete original $S$-segment, so no unpaired piece there can be used to create an extra alternating contribution. For the count, let q be the number of complete S-segments lying in the overhang. Before the T-row ends, the S-row has at most the number of S-segments minus q minus one internal boundaries, and the T-row has one fewer internal boundaries than its number of segments; each such boundary causes at most one mirrored cut. Thus the mirrored stage uses at most the number of S-segments plus the number of T-segments minus q minus two cuts. Bisecting the q overhang segments and every segment outside S and T adds q plus the remaining segments, so the total is at most n-1, hence certainly at most n. If T is empty, simply bisect all but one of the n+1 segments, using n cuts. Every paired piece has an equal mate. In the sorted list, equal mates contribute opposite signs to $G$; after all such cancellations, only the single piece at the end of the overhang can remain, and its length is at most $\Sigma(S)-\Sigma(T)$. Therefore Xiang can force $G\le\lvert\Sigma(S)-\Sigma(T)\rvert$.