IMO 2026 | General Regulations

Solution 1
First consider the claiming phase after all cuts have been made. Let the lengths of the resulting pieces, arranged in nonincreasing order, be $x_1\ge x_2\ge\cdots\ge x_m$. Liu Bang can guarantee a total length of at least $x_1+x_3+x_5+\cdots+x_{2\left\lfloor\frac{m-1}{2}\right\rfloor+1}$ by always choosing a longest remaining piece. Indeed, before his $k$-th turn, at most $2k-2$ pieces have been claimed, so some piece of length at least $x_{2k-1}$ remains. Similarly, by always choosing a longest remaining piece, Xiang Yu can guarantee for himself a total length of at least $x_2+x_4+x_6+\cdots+x_{2\left\lfloor\frac{m}{2}\right\rfloor}$, and therefore can keep Liu Bang's total length at most $x_1+x_3+x_5+\cdots+x_{2\left\lfloor\frac{m-1}{2}\right\rfloor+1}$. Hence the largest total length Liu Bang can guarantee in the claiming phase is exactly $x_1+x_3+x_5+\cdots+x_{2\left\lfloor\frac{m-1}{2}\right\rfloor+1}$.

 

Define the alternating discrepancy by $\Delta=x_1-x_2+x_3-x_4+\cdots\pm x_m$ (the last sign depends on the parity of $m$). Since $x_1+\cdots+x_m=1$, Liu Bang's share is $\frac{1+\Delta}{2}$. Thus it suffices to determine the largest discrepancy $\Delta$ that Liu Bang can guarantee. Set $d=\frac{1}{2^{n+1}-1}$. Lower bound. Liu Bang uses his $n$ marks to divide the stick into $n+1$ intervals of lengths $d,2d,4d,\ldots,2^n d$. This is possible because $d+2d+\cdots+2^n d=(2^{n+1}-1)d=1$. We prove that, after Xiang Yu makes at most $n$ further cuts, the resulting discrepancy satisfies $\Delta\ge d$.

Arrange all resulting pieces in nonincreasing order and pair consecutive pieces as $(x_1,x_2),(x_3,x_4),\ldots$. If the number of pieces is odd, append one fake piece of length $0$. Then $\Delta=\sum |u-v|$, where the sum is taken over all pairs $(u,v)$.

Construct an undirected multigraph whose vertices $0,1,\ldots,n$ correspond to Liu Bang's original intervals, with vertex $i$ having weight $2^i d$. If a fake piece of length $0$ was added, include an additional vertex $*$ of weight $0$. For each pair $(u,v)$, draw one edge between the vertices corresponding to the original intervals from which $u$ and $v$ came. If both pieces came from the same original interval, this edge is a loop.

Let $N$ be the number of actual pieces. Since Xiang Yu makes at most $n$ cuts, $N\le 2n+1$. If $N$ is even, the graph has $n+1$ vertices and $N/2\le n$ edges. If $N$ is odd, it has $n+2$ vertices and $(N+1)/2\le n+1$ edges. Thus the graph has fewer edges than vertices.

Consequently, some connected component $T$ has fewer edges than vertices. If $T$ has $v$ vertices and $e$ edges, then connectedness gives $e\ge v-1$, while $e < v$, so $e=v-1$. Hence $T$ contains no loop or cycle and is therefore a tree. Moreover, every vertex of the graph has positive degree: every original interval produces at least one piece, every piece belongs to one pair, and the fake vertex, if present, has degree $1$. Thus $T$ has at least one edge.

Choose any vertex of $T$ as a root. Let $A$ be the set of vertices at even distance from the root and $B$ the set of vertices at odd distance from the root. Since $T$ is a tree, every edge has one endpoint in $A$ and the other in $B$. Each edge $e$ remembers the pair of pieces that produced it. Let $p_e$ be the length of the piece coming from its endpoint in $A$, and let $q_e$ be the length of the piece coming from its endpoint in $B$. The contribution of $T$ to $\Delta$ is $\sum_{e\in T}|p_e-q_e|$, which by the triangle inequality is at least $\left|\sum_{e\in T}p_e-\sum_{e\in T}q_e\right|$.

Every edge incident to a vertex of $T$ belongs to $T$. Hence every piece cut from an original interval represented by a vertex of $T$ occurs exactly once among the endpoints of the edges of $T$. Therefore $\sum_{e\in T}p_e=\sum_{i\in A\setminus\{*\}}2^i d$ and $\sum_{e\in T}q_e=\sum_{j\in B\setminus\{*\}}2^j d$. Thus the contribution of $T$ to $\Delta$ is at least $\left|\sum_{i\in A\setminus\{*\}}2^i d-\sum_{j\in B\setminus\{*\}}2^j d\right|$.

Let $2^k d$ be the largest nonzero weight occurring in this signed sum. It occurs exactly once, while the sum of all smaller possible weights is at most $(1+2+\cdots+2^{k-1})d=(2^k-1)d < 2^k d$. Hence the largest term cannot be cancelled, so the signed sum is nonzero. Since it is an integer multiple of $d$, its absolute value is at least $d$. Therefore, the contribution of $T$ to $\Delta$ is at least $d$, and hence $\Delta\ge d$. It follows that Liu Bang can guarantee a total length of at least $\frac{1+d}{2}=\frac12\left(1+\frac{1}{2^{n+1}-1}\right)=\frac{2^n}{2^{n+1}-1}$. Upper bound. Suppose first that Liu Bang uses fewer than $n$ marks. Then he creates at most $n$ intervals, and Xiang Yu can bisect every one of them. Every resulting length occurs in an equal pair, so $\Delta=0$. Hence Liu Bang cannot improve his guarantee by using fewer than $n$ marks.

Now suppose that Liu Bang uses all $n$ marks, producing $r=n+1$ intervals of lengths $a_1,a_2,\ldots,a_r$, where $a_1+\cdots+a_r=1$. Consider the $2^r$ subset sums $\sum_{i\in I}a_i$ and arrange them in nondecreasing order. Since they all lie in $[0,1]$, two consecutive entries differ by at most $\frac{1}{2^r-1}=d$. Let these entries correspond to distinct subsets $I,J\subseteq\{1,\ldots,r\}$. Set $P=I\setminus J$, $Q=J\setminus I$, and $Z=\{1,\ldots,r\}\setminus(P\cup Q)$. Then $P$ and $Q$ are disjoint and $\delta=\left|\sum_{i\in P}a_i-\sum_{j\in Q}a_j\right| =\left|\sum_{i\in I}a_i-\sum_{j\in J}a_j\right|\le d$.

Since $I\ne J$, the sets $P$ and $Q$ are not both empty, so $|Z|\le r-1$. For each $i\in Z$, Xiang Yu bisects the interval of length $a_i$, producing an equal pair and using $|Z|$ cuts.

If one of $P$ and $Q$ is empty, Xiang Yu leaves the intervals indexed by the other set uncut. Removing the equal pairs obtained from the intervals indexed by $Z$ does not change the alternating discrepancy, while the remaining pieces have total length $\delta$. Hence $\Delta\le\delta\le d$, and the desired bound follows.

We may therefore suppose that both $P$ and $Q$ are nonempty. Without loss of generality, suppose that $\sum_{i\in P}a_i\ge\sum_{j\in Q}a_j$. Place the intervals indexed by $P$ consecutively in one row and those indexed by $Q$ consecutively in another row. Superimpose the division points of the two rows until the end of the shorter row. Whenever an internal division point of one row lies in the interior of an interval in the other row, Xiang Yu makes the corresponding cut. He also cuts the longer row at the endpoint of the shorter row if that point lies in the interior of one of its intervals.

The two rows have $|P|-1$ and $|Q|-1$ internal division points, respectively, and the endpoint of the shorter row requires at most one additional cut. Thus at most $|P|+|Q|-1$ cuts are used. The shorter row and an equally long initial part of the longer row are thereby divided into identical pieces, so these pieces occur in equal pairs. The remaining unpaired pieces have total length exactly $\delta$.

The total number of cuts is at most $|Z|+|P|+|Q|-1=r-1=n$. Removing two equal pieces from a decreasing list does not change its alternating discrepancy. Hence all equal pairs may be removed, leaving only pieces of total length $\delta$, and therefore $\Delta\le\delta\le d$. Xiang Yu can thus ensure that Liu Bang gets a total length of at most $\frac{1+d}{2}=\frac{2^n}{2^{n+1}-1}$. Combining the two bounds, we conclude that the answer is $\boxed{\frac{2^n}{2^{n+1}-1}}$. $\Box$

Solution 2
The answer is \[ c_n = \frac{2^n}{2^{n+1}-1}, \]which we'll show can be obtained if Liu divides the stick in ratio $1:2:4:\dots:2^n$. The following solution uses some different ideas from the various shortlisted official solutions. Setup. We first make cosmetic simplifications showing some parts of the problem are irrelevant. (These parts were likely used to make the statement compact or easier to translate.) First, we require each player to make exactly $n$ cuts but instead allow the marked points to coincide (giving length $0$ segments). Also, we remove the turn-based claiming part of the problem by noting that if $x_1 \ge x_2 \ge \dots \ge x_{2n+1} \ge 0$ are the obtained stick lengths, it's clear that Liu's score is \[ x_1 + x_3 + x_5 + \dots + x_{2n+1} \]under optimal play. (On each turn, a player should always take the largest piece available.) Rather than discussing Liu's score directly, we will often prefer to work with the gap defined as Liu's score minus Xiang's score: \[ G = x_1 - x_2 + x_3 - x_4 + \dots + x_{2n+1}. \] We show a strategy for Xiang that guarantees $G \le \frac{1}{2^{n+1}-1}$ regardless of how Liu starts the initial division. Then we prove that in the $1:2:4:\dots:2^n$ division mentioned, we always have $G \ge \frac{1}{2^{n+1}-1}$. By a segment we refer to the $n+1$ intervals (possibly of length $0$) that Liu's $n$ points divide the stick into. If $S$ is a set of segments, we let $\Sigma(S)$ denote the sum of the lengths of the segments. Strategy for Xiang. The basic strategy is the following: Claim: Let $S$ and $T$ be any two disjoint distinct subsets of the $n+1$ segments. Then Xiang can guarantee \[ G \le |\Sigma(S) - \Sigma(T)|. \]Proof. WLOG assume $\Sigma(S) \ge \Sigma(T)$. Line up $S$ and $T$ as shown in the figure below and have Xiang make mirrored cuts so that we get several pairs of equal segments plus a leftover part of length $\Sigma(S)-\Sigma(T)$. Then for all the remaining segments not in $S$ or $T$, Xiang bisects them. Xiang also bisects any segment in $S$ contained in the leftover part.

As the pairs of segments of the same length cancel off, we find $G$ is exactly equal to the length of the first segment in the overhang of $S$ over $T$ (as illustrated above). Since $G \le \Sigma(S) - \Sigma(T)$, the proof is complete. $\blacksquare$ Remark: In the original version of the problem where we allow fewer than $n$ cuts, then in fact Xiang may make one fewer cut: the rightmost cut of $T$ on $S$ is not necessary. (This is drawn with a dotted line above.) Interestingly, this means except when $T = \varnothing$, Xiang's optimal strategy requires only $n-1$ cuts, and the ability to make an $n$\textsuperscript{th} cut does not help. The problem now follows by a standard Pigeonhole argument: consider all $2^{n+1}$ possible $\Sigma(S)$, which lie in the interval $[0,1]$. By pigeonhole principle there should be $S \neq T$ already such that \[ 0 \le \Sigma(S) - \Sigma(T) \le \frac{1}{2^{n+1}-1}. \]We then prune $S$ and $T$ further by removing any common elements, which does not change $\Sigma(S) - \Sigma(T)$. Remark: By analyzing the equality case of the pigeonhole argument, it follows that the $1:2:4:\dots:2^n$ division is the unique optimal starting move for Liu. That is, if Liu picks a different division then Xiang can ensure $G < \frac{1}{2^{n+1}-1}$. Converse direction in general. Although we expect most contestants to solve this part specifically for Liu's division $1:2:4:\dots:2^n$, here we will write the ``correct'' claim that works in any division. Claim: Let $a_1$, \dots, $a_{n+1}$ denote the lengths of Liu's $n+1$ segments. Define \[ \Delta = \min_{\substack{\varepsilon_1, \dots, \varepsilon_{n+1} \in \{-1,0,1\} \\ (\varepsilon_1, \dots, \varepsilon_{n+1}) \neq (0,\dots,0)}} \left\lvert \varepsilon_1 a_1 + \varepsilon_2 a_2 + \dots + \varepsilon_{n+1} a_{n+1} \right\rvert \]Then regardless of what Xiang does, we always have $G \ge \Delta$. Proof. Let $d_1 = x_1 - x_2 \ge 0$, $d_2 = x_3 - x_4 \ge 0$, \dots, $d_n = x_{2n-1} - x_{2n} \ge 0$. Also let $d_{n+1} = x_{2n+1}$ for convenience, so that \[ G = d_1 + \dots + d_{n+1}. \]Construct a multigraph $\Gamma$ on $n+2$ vertices whose vertex set $V$ consists of one vertex for each of the $n+1$ segments, plus a dummy vertex, thought of as having length $a_0 = 0$. For each $1 \le i \le n$, we find which segments $x_{2i-1}$ and $x_{2i}$ were cut from and draw an edge joining them. Finally, we draw one extra edge from the dummy vertex to the segment containing $x_{2n+1}$. An example when $n=3$ is shown below, scaled by $15$. (In the cartoon, each vertex is labeled with the length $a_i$ of its corresponding segment for readability.)

Since $\Gamma$ has $n+2$ vertices and $n+1$ edges, some component of $\Gamma$ is a tree (in particular, no parallel edges or self-loops). That tree must be bipartite and we write its vertices as a disjoint union $S \sqcup T$. Then the main observation is that $|\Sigma(S) - \Sigma(T)|$ (which is among the expressions considered in $\Delta$'s definition) is some expression of the form $\pm d_\bullet \pm d_\bullet \pm \dots \pm d_\bullet$, across the edges present in the component, which is certainly at most $G$. More formally, if $\{d_i\}_{i \in I}$ are the edges in the component, then \[ \Delta \le \left\lvert \Sigma(S) - \Sigma(T) \right\rvert = \left\lvert \sum_{i \in I} \pm d_i \right\rvert \le \sum_{i \in I} d_i \le G \]as desired. $\blacksquare$ Remark: [Induction] This claim may also be proven by induction on $n$ in a more straightforward way than the trickier argument with the tree above. However, for this induction, stating the fully general claim and using induction on this (rather than just focusing on the $1:2:4:\dots:2^n$ division) is critical. To complete the proof, just note in the division $1:2:4:\dots:2^n$, the value of $\Delta$ indeed equals $\frac{1}{2^{n+1}-1}$ exactly. Remark: [For powers of $2$, bipartite coloring is overkill] In the special case where the $a_i$ are powers of $2$ --- which is all that is needed for the problem --- then the graph argument after locating a tree can be simplified. Rather than using a bipartite coloring in the entire tree, one considers the vertex $v$ corresponding to the largest power of $2$ in that component, say $2^N$. Summing just at that vertex $v$ is already enough to give something of the form \[ 2^N = \sum_{d_i \text{ joins } 2^N \text{ to } x_j} (\pm d_i \pm x_j). \]But the sum of the $x_j$ that appear is at most the sum of the lengths of all the other segments in the component, which in turn is at most $1+2+\dots+2^{N-1}=2^N-1$. This already shows the sum of present $d_i$ must be at least $1$. Converse direction for the specific powers-of-two division. Scaling the stick so it has total length $1+2+\dots+2^n$, we show a shorter but tricky proof in this specific case that $G \ge 1$. The idea is to prove the following claim by induction on $k$: Claim: We always have \[ x_2 + x_4 + \dots + x_{2k} \le 2^{n-1} + 2^{n-2} + \dots + 2^{n-k}. \]Proof. Assume not and consider the first $k$ for which this doesn't happen; that means Xiang, on the $k$th turn, took a piece of length strictly more than $2^{n-k}$. This means Xiang's $2k$\textsuperscript{th} piece, and thus all $2k$ pieces up until this point in time, came from one of the $k$ segments $\{2^{n-k+1}, 2^{n-k+2}, \dots, 2^n\}$. However, if all $2k$ pieces come from the $k$ largest segments then \[ x_2 + \dots + x_{2k} \le \frac{x_1 + x_2 + \dots + x_{2k}}{2} \le \frac{2^{n-k+1} + 2^{n-k+2} + \dots + 2^n}{2} \]which produces the required contradiction. $\blacksquare$

Solution 3 Solution3

Solution 4 Solution4

Solution 5 Solution5