IMO 2026 · 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.
Official text of the problem. Official problem paper (PDF)
Answer
\(\displaystyle c=\frac{2^n}{2^{n+1}-1}\).
Solution
First, suppose that after all cuts the piece lengths, in decreasing order, are \[ x_1\ge x_2\ge\cdots\ge x_p>0. \] The value Liu can guarantee in the claiming stage is \[ x_1+x_3+x_5+\cdots=\frac{1+D}{2}, \qquad D=x_1-x_2+x_3-x_4+\cdots+(-1)^{p+1}x_p. \] Indeed, if Liu always takes a longest remaining piece, his \(j\)-th piece has length at least \(x_{2j-1}\), since only \(2j-2\) pieces have previously been claimed. Similarly, if Xiang always takes a longest remaining piece, his \(j\)-th piece has length at least \(x_{2j}\). These two strategies prove the asserted value.
We will also use the following observation: deleting two equal lengths from the sorted list does not change \(D\). Equal entries can be placed consecutively, so their contributions cancel, and deleting them preserves the signs of all later entries.
Set \[ u=\frac{1}{2^{n+1}-1}. \]
We first show that Liu can guarantee \((1+u)/2\). He places his \(n\) marks so that the resulting \(n+1\) intervals have lengths \[ a_i=2^iu,\qquad i=0,1,\ldots,n. \] These lengths sum to \(1\).
After Xiang places his marks, there are at most \(2n+1\) pieces. Sort their lengths as above and pair them as \[ (x_1,x_2),\ (x_3,x_4),\ \ldots, \] leaving \(x_p\) unpaired if \(p\) is odd.
Construct a graph whose vertices are the original intervals \(0,1,\ldots,n\). Each pair of pieces gives an edge joining the original intervals containing those two pieces. Loops and multiple edges are allowed. This graph has \(n+1\) vertices and \[ \left\lfloor\frac p2\right\rfloor\le n \] edges.
Consequently, some connected component is a tree, possibly a single isolated vertex. To see this, every connected component on \(v\) vertices contains a spanning tree with \(v-1\) edges. If no component were itself a tree, each would have at least \(v\) edges, giving at least \(n+1\) edges altogether.
Choose such a tree component and divide its vertices into two classes \(A,B\) so that every edge joins the two classes. This is possible by assigning classes according to the parity of the distance from any chosen root.
Consider \[ S=\sum_{i\in A}a_i-\sum_{i\in B}a_i. \] Expand each \(a_i\) as the sum of the lengths of its final pieces. Every paired edge in this component contributes the difference between its two piece lengths, with one of the two possible signs. The sole possible unpaired piece contributes either its length or its negative if it belongs to the component. Therefore, by the triangle inequality, \[ |S| \le \sum_{j=1}^{\lfloor p/2\rfloor}(x_{2j-1}-x_{2j}) +\begin{cases} x_p,&p\text{ odd},\\ 0,&p\text{ even} \end{cases} =D. \]
On the other hand, let \(r\) be the largest index in this component. Its contribution to \(S\) has absolute value \(2^ru\), whereas all smaller indices together have total length at most \((2^r-1)u\). Hence \[ |S|\ge 2^ru-\sum_{i=0}^{r-1}2^iu=u. \] Thus \(D\ge u\), regardless of Xiang’s marks. Liu can consequently guarantee \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1}. \]
We now prove the matching upper bound. Suppose Liu’s marks create \(m\le n+1\) intervals. Marks at the endpoints, if any, can be ignored.
If \(m\le n\), Xiang bisects every interval, using at most \(n\) marks. All resulting pieces occur in equal pairs, so \(D=0\). Thus Liu can obtain at most \(1/2\) against optimal play.
It remains to consider \(m=n+1\). Write the interval lengths as \(b_1,\ldots,b_m\). Their \(2^m\) subset sums all lie in \([0,1]\), with smallest sum \(0\) and largest sum \(1\). List these sums in nondecreasing order, retaining repetitions. Since their \(2^m-1\) consecutive gaps sum to \(1\), two distinct subsets have sums differing by some \[ 0\le\delta\le\frac1{2^m-1}=u. \] Remove their common indices. This gives disjoint sets \(A,B\), not both empty, whose total lengths satisfy \[ \alpha=\sum_{i\in A}b_i,\qquad \beta=\sum_{i\in B}b_i,\qquad \alpha\ge\beta,\qquad \alpha-\beta=\delta. \]
We claim that Xiang can use at most \(m-1\) marks so that all pieces, except for pieces of total length \(\delta\), occur in equal pairs.
If \(B\) is empty, simply bisect every interval outside \(A\). This uses \[ m-|A|\le m-1 \] marks, and the remaining intervals have total length \(\alpha=\delta\).
Otherwise both sets are nonempty. Conceptually arrange the intervals of \(A\) end to end in one row of length \(\alpha\), and those of \(B\) in another row of length \(\beta\), with their left endpoints aligned. On the common portion \([0,\beta]\), copy every interval boundary in either row to the other row, making a cut there whenever necessary. Also cut the first row at \(\beta\) if this lies inside one of its intervals.
The two rows now have identical subdivisions on \([0,\beta]\), giving equal pairs. The remaining portion of the first row has total length \(\delta\). There are at most \[ (|A|-1)+(|B|-1)+1=|A|+|B|-1 \] new cuts: each internal boundary of a row requires at most one cut in the other, and the endpoint \(\beta\) requires at most one further cut. This also covers \(\alpha=\beta\), when that further cut is unnecessary.
Finally, bisect every original interval outside \(A\cup B\). The total number of marks is at most \[ |A|+|B|-1+(m-|A|-|B|)=m-1=n, \] proving the claim. The row arrangement is only a way to specify cuts within the original intervals; no physical rearrangement is needed.
Delete all the equal pairs from the sorted list of final piece lengths. This leaves \(D\) unchanged. The remaining pieces have total length \(\delta\), so their alternating sum is at most \(\delta\). Consequently, \[ D\le\delta\le u. \] By playing optimally in the claiming stage, Xiang therefore ensures that Liu receives at most \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1}. \] Together with Liu’s strategy, this proves the answer.
The solution was checked against Evan Chen's published IMO solution notes.
IMO 2026 · Aufgabe 3
Sei \(n\) eine positive ganze Zahl. Liu Bang und Xiang Yu möchten einen Stab der Länge 1 untereinander aufteilen. Liu markiert höchstens \(n\) Punkte auf dem Stab. Danach markiert Xiang höchstens \(n\) Punkte auf dem Stab. Dabei müssen die markierten Punkte paarweise verschieden sein. Nun wird der Stab an den markierten Punkten zerschnitten, wodurch er in Stücke zerteilt wird. Anschließend nehmen die beiden abwechselnd jeweils ein Stück, wobei Liu beginnt. Dabei möchte jeder Spieler die Gesamtlänge seiner Stücke maximieren. Für jedes \(n\) bestimme man das größte \(c\), sodass Liu garantiert eine Gesamtlänge von mindestens \(c\) erreichen kann, unabhängig davon, wie Xiang spielt.
Offizieller deutscher Aufgabentext. Offizielles Aufgabenblatt (PDF)
Antwort
\(\displaystyle c=\frac{2^n}{2^{n+1}-1}\).
Lösung
Zunächst seien nach allen Schnitten die Stücklängen in absteigender Reihenfolge \[ x_1\ge x_2\ge\cdots\ge x_p>0. \] Der Wert, den Liu beim anschließenden Nehmen der Stücke garantieren kann, ist \[ x_1+x_3+x_5+\cdots=\frac{1+D}{2}, \qquad D=x_1-x_2+x_3-x_4+\cdots+(-1)^{p+1}x_p. \] Wenn Liu stets ein längstes verbleibendes Stück nimmt, hat sein \(j\)-tes Stück nämlich mindestens die Länge \(x_{2j-1}\), da zuvor erst \(2j-2\) Stücke genommen wurden. Wenn Xiang stets ein längstes verbleibendes Stück nimmt, hat entsprechend sein \(j\)-tes Stück mindestens die Länge \(x_{2j}\). Diese beiden Strategien beweisen den behaupteten Wert.
Wir werden außerdem die folgende Beobachtung verwenden: Entfernt man zwei gleiche Längen aus der sortierten Liste, so ändert sich \(D\) nicht. Gleiche Einträge können unmittelbar hintereinander angeordnet werden, sodass sich ihre Beiträge aufheben, und beim Entfernen bleiben die Vorzeichen aller späteren Einträge erhalten.
Wir setzen \[ u=\frac{1}{2^{n+1}-1}. \]
Zuerst zeigen wir, dass Liu \((1+u)/2\) garantieren kann. Er setzt seine \(n\) Markierungen so, dass die entstehenden \(n+1\) Intervalle die Längen \[ a_i=2^iu,\qquad i=0,1,\ldots,n \] haben. Diese Längen ergeben in der Summe \(1\).
Nachdem Xiang seine Markierungen gesetzt hat, gibt es höchstens \(2n+1\) Stücke. Wir sortieren ihre Längen wie oben und bilden die Paare \[ (x_1,x_2),\ (x_3,x_4),\ \ldots, \] wobei \(x_p\) ungepaart bleibt, falls \(p\) ungerade ist.
Wir konstruieren einen Graphen, dessen Knoten die ursprünglichen Intervalle \(0,1,\ldots,n\) sind. Jedes Paar von Stücken ergibt eine Kante zwischen den ursprünglichen Intervallen, die diese beiden Stücke enthalten. Schleifen und Mehrfachkanten sind erlaubt. Dieser Graph hat \(n+1\) Knoten und \[ \left\lfloor\frac p2\right\rfloor\le n \] Kanten.
Folglich ist eine seiner Zusammenhangskomponenten ein Baum, möglicherweise ein einzelner isolierter Knoten. Um dies einzusehen, beachten wir, dass jede Zusammenhangskomponente mit \(v\) Knoten einen Spannbaum mit \(v-1\) Kanten enthält. Wäre keine Komponente selbst ein Baum, so hätte jede mindestens \(v\) Kanten, was insgesamt mindestens \(n+1\) Kanten ergäbe.
Wir wählen eine solche Baumkomponente und teilen ihre Knoten in zwei Klassen \(A,B\) ein, sodass jede Kante die beiden Klassen verbindet. Dies ist möglich, indem wir die Klassen nach der Parität des Abstands von einer beliebig gewählten Wurzel zuweisen.
Wir betrachten \[ S=\sum_{i\in A}a_i-\sum_{i\in B}a_i. \] Wir schreiben jedes \(a_i\) als Summe der Längen seiner endgültigen Stücke. Jede durch ein Paar gebildete Kante dieser Komponente trägt die Differenz ihrer beiden Stücklängen mit einem der beiden möglichen Vorzeichen bei. Das einzige möglicherweise ungepaarte Stück trägt entweder seine Länge oder deren Negatives bei, falls es zu dieser Komponente gehört. Daher gilt nach der Dreiecksungleichung \[ |S| \le \sum_{j=1}^{\lfloor p/2\rfloor}(x_{2j-1}-x_{2j}) +\begin{cases} x_p,&p\text{ ungerade},\\ 0,&p\text{ gerade} \end{cases} =D. \]
Andererseits sei \(r\) der größte Index in dieser Komponente. Sein Beitrag zu \(S\) hat den Betrag \(2^ru\), während alle kleineren Indizes zusammen eine Gesamtlänge von höchstens \((2^r-1)u\) haben. Somit gilt \[ |S|\ge 2^ru-\sum_{i=0}^{r-1}2^iu=u. \] Also gilt \(D\ge u\), unabhängig von Xiangs Markierungen. Liu kann folglich \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1} \] garantieren.
Wir beweisen nun die dazu passende obere Schranke. Angenommen, Lius Markierungen erzeugen \(m\le n+1\) Intervalle. Etwaige Markierungen an den Endpunkten können ignoriert werden.
Ist \(m\le n\), so halbiert Xiang jedes Intervall und verwendet dabei höchstens \(n\) Markierungen. Alle entstehenden Stücke treten in gleich langen Paaren auf, also gilt \(D=0\). Somit kann Liu gegen optimales Spiel höchstens \(1/2\) erhalten.
Es bleibt der Fall \(m=n+1\). Wir bezeichnen die Intervalllängen mit \(b_1,\ldots,b_m\). Ihre \(2^m\) Teilsummen liegen alle in \([0,1]\), wobei die kleinste Summe \(0\) und die größte Summe \(1\) ist. Wir listen diese Summen in nicht absteigender Reihenfolge auf und behalten Wiederholungen bei. Da ihre \(2^m-1\) aufeinanderfolgenden Abstände in der Summe \(1\) ergeben, gibt es zwei verschiedene Teilmengen, deren Summen sich um ein \[ 0\le\delta\le\frac1{2^m-1}=u \] unterscheiden. Wir entfernen ihre gemeinsamen Indizes. Dadurch erhalten wir disjunkte Mengen \(A,B\), die nicht beide leer sind und deren Gesamtlängen \[ \alpha=\sum_{i\in A}b_i,\qquad \beta=\sum_{i\in B}b_i,\qquad \alpha\ge\beta,\qquad \alpha-\beta=\delta \] erfüllen.
Wir behaupten, dass Xiang mit höchstens \(m-1\) Markierungen erreichen kann, dass alle Stücke bis auf Stücke der Gesamtlänge \(\delta\) in gleich langen Paaren auftreten.
Ist \(B\) leer, so halbiert er einfach jedes Intervall außerhalb von \(A\). Dafür benötigt er \[ m-|A|\le m-1 \] Markierungen, und die verbleibenden Intervalle haben die Gesamtlänge \(\alpha=\delta\).
Andernfalls sind beide Mengen nicht leer. Wir ordnen gedanklich die Intervalle von \(A\) hintereinander in einer Reihe der Länge \(\alpha\) und diejenigen von \(B\) in einer weiteren Reihe der Länge \(\beta\) an, wobei die linken Endpunkte beider Reihen übereinstimmen. Auf dem gemeinsamen Abschnitt \([0,\beta]\) übertragen wir jede Intervallgrenze einer Reihe auf die andere und setzen dort bei Bedarf einen Schnitt. Außerdem schneiden wir die erste Reihe bei \(\beta\), falls dieser Punkt im Inneren eines ihrer Intervalle liegt.
Die beiden Reihen haben nun auf \([0,\beta]\) identische Unterteilungen, wodurch gleich lange Paare entstehen. Der verbleibende Abschnitt der ersten Reihe hat die Gesamtlänge \(\delta\). Es gibt höchstens \[ (|A|-1)+(|B|-1)+1=|A|+|B|-1 \] neue Schnitte: Jede innere Grenze einer Reihe erfordert höchstens einen Schnitt in der anderen, und der Endpunkt \(\beta\) erfordert höchstens einen weiteren Schnitt. Dies schließt auch \(\alpha=\beta\) ein, wenn dieser weitere Schnitt unnötig ist.
Schließlich halbieren wir jedes ursprüngliche Intervall außerhalb von \(A\cup B\). Die Gesamtzahl der Markierungen beträgt höchstens \[ |A|+|B|-1+(m-|A|-|B|)=m-1=n, \] womit die Behauptung bewiesen ist. Die Anordnung in Reihen dient lediglich dazu, Schnitte innerhalb der ursprünglichen Intervalle festzulegen; ein tatsächliches Umordnen ist nicht nötig.
Wir entfernen alle gleich langen Paare aus der sortierten Liste der endgültigen Stücklängen. Dadurch bleibt \(D\) unverändert. Die verbleibenden Stücke haben die Gesamtlänge \(\delta\), also ist ihre alternierende Summe höchstens \(\delta\). Folglich gilt \[ D\le\delta\le u. \] Durch optimales Spiel beim Nehmen der Stücke stellt Xiang daher sicher, dass Liu höchstens \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1} \] erhält. Zusammen mit Lius Strategie beweist dies die Antwort.
Die Lösung wurde mit den veröffentlichten IMO-Lösungsnotizen von Evan Chen abgeglichen.
IMO 2026 · Soru 3
\(n\) verilmiş bir pozitif tam sayı olsun. Liu Bang ve Xiang Yu 1 uzunluğunda bir çubuğu kendi aralarında bölüşmek istiyor. Başlangıçta, Liu çubuk üzerinde en fazla \(n\) tane nokta işaretliyor ve bundan sonra Xiang çubuk üzerinde en fazla \(n\) tane nokta işaretliyor. İşaretlenmiş noktalar birbirlerinden farklı olmalıdır. Daha sonra bu çubuk tüm işaretli noktalardan kesilerek parçalara ayrılıyor. Sonrasında, oyuncular sırayla hamle yapıyorlar ve her hamlede sırası gelen oyuncu daha önce alınmamış parçalardan birini alıyor. İlk hamleyi Liu yapıyor. Her oyuncunun amacı, aldığı parçaların uzunluklarının toplamının mümkün olduğunca fazla olmasıdır.
\(n\) sayısı verildiğinde, Xiang nasıl oynarsa oynasın Liu aldığı parçaların uzunluklarının toplamının en az \(c\) olmasını garantileyebiliyorsa, \(c\) sayısının alabileceği en büyük değeri bulunuz.
Sorunun resmi Türkçe metni. Resmi soru kâğıdı (PDF)
Cevap
\(\displaystyle c=\frac{2^n}{2^{n+1}-1}\).
Çözüm
Önce, tüm kesimler yapıldıktan sonra parça uzunluklarının azalan sırayla \[ x_1\ge x_2\ge\cdots\ge x_p>0 \] olduğunu varsayalım. Parçaları alma aşamasında Liu’nun garanti edebileceği değer \[ x_1+x_3+x_5+\cdots=\frac{1+D}{2}, \qquad D=x_1-x_2+x_3-x_4+\cdots+(-1)^{p+1}x_p \] olur. Gerçekten de Liu her seferinde kalan en uzun parçalardan birini alırsa, daha önce yalnızca \(2j-2\) parça alınmış olduğundan, aldığı \(j\). parçanın uzunluğu en az \(x_{2j-1}\) olur. Benzer şekilde, Xiang her seferinde kalan en uzun parçalardan birini alırsa, aldığı \(j\). parçanın uzunluğu en az \(x_{2j}\) olur. Bu iki strateji, belirtilen değeri kanıtlar.
Şu gözlemi de kullanacağız: sıralı listeden birbirine eşit iki uzunluğu silmek \(D\)’yi değiştirmez. Eşit terimler art arda yerleştirilebildiğinden katkıları birbirini götürür ve bunları silmek daha sonraki tüm terimlerin işaretlerini korur.
\[ u=\frac{1}{2^{n+1}-1} \] olarak tanımlayalım.
Önce Liu’nun \((1+u)/2\)’yi garanti edebileceğini göstereceğiz. Liu, \(n\) işaretini oluşan \(n+1\) aralığın uzunlukları \[ a_i=2^iu,\qquad i=0,1,\ldots,n \] olacak şekilde yerleştirir. Bu uzunlukların toplamı \(1\)’dir.
Xiang işaretlerini yerleştirdikten sonra en fazla \(2n+1\) parça vardır. Uzunluklarını yukarıdaki gibi sıralayıp \[ (x_1,x_2),\ (x_3,x_4),\ \ldots \] biçiminde eşleyelim; \(p\) tek ise \(x_p\)’yi eşlenmemiş bırakalım.
Köşeleri başlangıçtaki \(0,1,\ldots,n\) aralıkları olan bir çizge oluşturalım. Her parça çifti, bu iki parçayı içeren başlangıç aralıklarını birleştiren bir kenar versin. Döngülere ve çoklu kenarlara izin veriyoruz. Bu çizgenin \(n+1\) köşesi ve \[ \left\lfloor\frac p2\right\rfloor\le n \] kenarı vardır.
Dolayısıyla bağlantılı bileşenlerden biri, tek bir yalıtılmış köşe de olabilecek bir ağaçtır. Bunu görmek için, \(v\) köşeli her bağlantılı bileşenin \(v-1\) kenarlı bir kapsayan ağaç içerdiğine dikkat edelim. Hiçbir bileşenin kendisi ağaç olmasaydı, her birinin en az \(v\) kenarı olurdu ve toplamda en az \(n+1\) kenar bulunurdu.
Böyle bir ağaç bileşen seçelim ve köşelerini, her kenar iki sınıfı birleştirecek şekilde \(A,B\) sınıflarına ayıralım. Herhangi bir kök seçip köşeleri köke uzaklıklarının tekliğine veya çiftliğine göre sınıflara atayarak bunu yapabiliriz.
\[ S=\sum_{i\in A}a_i-\sum_{i\in B}a_i \] ifadesini ele alalım. Her \(a_i\)’yi, son durumda içerdiği parçaların uzunluklarının toplamı olarak açalım. Bu bileşendeki her eşlemeye karşılık gelen kenar, iki parçasının uzunlukları arasındaki farkı, olası iki işaretten biriyle katkı olarak verir. Varsa tek eşlenmemiş parça bu bileşene aitse, katkısı uzunluğu veya uzunluğunun negatifidir. Dolayısıyla üçgen eşitsizliğinden, \[ |S| \le \sum_{j=1}^{\lfloor p/2\rfloor}(x_{2j-1}-x_{2j}) +\begin{cases} x_p,&p\text{ tek},\\ 0,&p\text{ çift} \end{cases} =D. \]
Öte yandan, \(r\) bu bileşendeki en büyük indis olsun. Bunun \(S\)’ye katkısının mutlak değeri \(2^ru\) iken, daha küçük tüm indislerin toplam uzunluğu en fazla \((2^r-1)u\)’dur. Bu nedenle \[ |S|\ge 2^ru-\sum_{i=0}^{r-1}2^iu=u. \] Böylece Xiang’ın işaretlerinden bağımsız olarak \(D\ge u\) olur. Sonuç olarak Liu \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1} \] değerini garanti edebilir.
Şimdi buna eşit olan üst sınırı kanıtlayacağız. Liu’nun işaretlerinin \(m\le n+1\) aralık oluşturduğunu varsayalım. Varsa uç noktalardaki işaretler göz ardı edilebilir.
\(m\le n\) ise Xiang, en fazla \(n\) işaret kullanarak her aralığı iki eşit parçaya böler. Oluşan tüm parçalar eşit çiftler hâlinde bulunduğundan \(D=0\) olur. Dolayısıyla Liu, en iyi şekilde oynayan bir rakibe karşı en fazla \(1/2\) elde edebilir.
Geriye \(m=n+1\) durumu kalır. Aralık uzunluklarını \(b_1,\ldots,b_m\) ile gösterelim. Bunların \(2^m\) alt küme toplamının tümü \([0,1]\) aralığında bulunur; en küçük toplam \(0\), en büyük toplam \(1\)’dir. Tekrarları koruyarak bu toplamları azalmayan sırada listeleyelim. Ardışık toplamlar arasındaki \(2^m-1\) farkın toplamı \(1\) olduğundan, birbirinden farklı iki alt kümenin toplamları arasındaki fark, bir \[ 0\le\delta\le\frac1{2^m-1}=u \] değeridir. Ortak indislerini çıkaralım. Böylece ikisi birden boş olmayan, toplam uzunlukları \[ \alpha=\sum_{i\in A}b_i,\qquad \beta=\sum_{i\in B}b_i,\qquad \alpha\ge\beta,\qquad \alpha-\beta=\delta \] koşullarını sağlayan ayrık \(A,B\) kümeleri elde edilir.
Xiang’ın en fazla \(m-1\) işaret kullanarak, toplam uzunluğu \(\delta\) olan parçalar dışındaki tüm parçaların eşit çiftler hâlinde bulunmasını sağlayabileceğini iddia ediyoruz.
\(B\) boş ise yalnızca \(A\) dışındaki her aralığı iki eşit parçaya bölsün. Bunun için \[ m-|A|\le m-1 \] işaret kullanılır ve kalan aralıkların toplam uzunluğu \(\alpha=\delta\) olur.
Aksi hâlde iki küme de boş değildir. Zihnimizde \(A\)’nın aralıklarını uç uca ekleyerek \(\alpha\) uzunluğunda bir sıra, \(B\)’nin aralıklarını uç uca ekleyerek \(\beta\) uzunluğunda başka bir sıra oluşturalım ve sol uçlarını hizalayalım. Ortak \([0,\beta]\) kısmında, her iki sıradaki her aralık sınırını diğer sıraya aktaralım ve gereken yerlerde kesim yapalım. Ayrıca \(\beta\), ilk sıradaki aralıklardan birinin içinde kalıyorsa ilk sırayı \(\beta\)’da da keselim.
İki sıra artık \([0,\beta]\) üzerinde aynı bölünmelere sahiptir; böylece eşit çiftler elde edilir. İlk sıranın kalan kısmının toplam uzunluğu \(\delta\)’dır. En fazla \[ (|A|-1)+(|B|-1)+1=|A|+|B|-1 \] yeni kesim vardır: bir sıranın her iç sınırı diğer sırada en fazla bir kesim gerektirir ve \(\beta\) uç noktası en fazla bir ek kesim gerektirir. Bu, söz konusu ek kesimin gereksiz olduğu \(\alpha=\beta\) durumunu da kapsar.
Son olarak, \(A\cup B\) dışındaki her başlangıç aralığını iki eşit parçaya bölelim. Toplam işaret sayısı en fazla \[ |A|+|B|-1+(m-|A|-|B|)=m-1=n \] olur; böylece iddia kanıtlanır. Sıralar hâlinde düzenleme, yalnızca başlangıç aralıklarının içindeki kesimleri belirtmenin bir yoludur; fiziksel olarak yeniden düzenleme gerekmez.
Son parça uzunluklarının sıralı listesinden tüm eşit çiftleri silelim. Bu, \(D\)’yi değiştirmez. Kalan parçaların toplam uzunluğu \(\delta\) olduğundan, bunların dönüşümlü işaretli toplamı en fazla \(\delta\)’dır. Dolayısıyla, \[ D\le\delta\le u. \] Böylece Xiang, parçaları alma aşamasında en iyi şekilde oynayarak Liu’nun en fazla \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1} \] almasını sağlar. Bu, Liu’nun stratejisiyle birlikte cevabı kanıtlar.
Çözüm, Evan Chen'in yayımlanmış IMO çözüm notlarıyla karşılaştırılarak kontrol edildi.
IMO 2026 · Problema 3
Sea \(n\) un entero positivo. Liu Bang y Xiang Yu tienen una varilla de longitud 1 y quieren cortarla y repartírsela entre ellos. Liu marca como mucho \(n\) puntos en la varilla y después Xiang marca como mucho \(n\) puntos en la varilla. Los puntos marcados son distintos. Entonces la varilla se corta por todos los puntos marcados obteniéndose así una cierta cantidad de piezas. Después, por turnos, cada uno recoge una de las piezas que no se haya repartido aún, empezando por Liu. El objetivo de cada uno es maximizar la suma de las longitudes de sus piezas.
Para cada \(n\), determinar el mayor valor \(c\) tal que Liu puede asegurarse una longitud total mayor o igual a \(c\), independientemente de las elecciones de Xiang.
Texto oficial en español del problema. Enunciado oficial (PDF)
Respuesta
\(\displaystyle c=\frac{2^n}{2^{n+1}-1}\).
Solución
Supongamos primero que, después de todos los cortes, las longitudes de las piezas, en orden decreciente, son \[ x_1\ge x_2\ge\cdots\ge x_p>0. \] El valor que Liu puede garantizar en la fase de reparto es \[ x_1+x_3+x_5+\cdots=\frac{1+D}{2}, \qquad D=x_1-x_2+x_3-x_4+\cdots+(-1)^{p+1}x_p. \] En efecto, si Liu toma siempre una de las piezas más largas que quedan, su \(j\)-ésima pieza tiene longitud al menos \(x_{2j-1}\), pues antes solo se han recogido \(2j-2\) piezas. Análogamente, si Xiang toma siempre una de las piezas más largas que quedan, su \(j\)-ésima pieza tiene longitud al menos \(x_{2j}\). Estas dos estrategias demuestran el valor afirmado.
También usaremos la siguiente observación: eliminar dos longitudes iguales de la lista ordenada no cambia \(D\). Los términos iguales pueden colocarse consecutivamente, de modo que sus contribuciones se cancelan, y eliminarlos conserva los signos de todos los términos posteriores.
Pongamos \[ u=\frac{1}{2^{n+1}-1}. \]
Mostremos primero que Liu puede garantizar \((1+u)/2\). Coloca sus \(n\) marcas de modo que los \(n+1\) intervalos resultantes tengan longitudes \[ a_i=2^iu,\qquad i=0,1,\ldots,n. \] Estas longitudes suman \(1\).
Después de que Xiang coloque sus marcas, hay a lo sumo \(2n+1\) piezas. Ordenemos sus longitudes como antes y emparejémoslas así: \[ (x_1,x_2),\ (x_3,x_4),\ \ldots, \] dejando \(x_p\) sin pareja si \(p\) es impar.
Construyamos un grafo cuyos vértices sean los intervalos originales \(0,1,\ldots,n\). Cada pareja de piezas da una arista que une los intervalos originales que contienen esas dos piezas. Se permiten lazos y aristas múltiples. Este grafo tiene \(n+1\) vértices y \[ \left\lfloor\frac p2\right\rfloor\le n \] aristas.
En consecuencia, alguna componente conexa es un árbol, posiblemente un único vértice aislado. Para verlo, toda componente conexa con \(v\) vértices contiene un árbol generador con \(v-1\) aristas. Si ninguna componente fuera un árbol, cada una tendría al menos \(v\) aristas, lo que daría al menos \(n+1\) aristas en total.
Elijamos una de esas componentes que sea un árbol y dividamos sus vértices en dos clases \(A,B\) de modo que toda arista una las dos clases. Esto es posible asignando las clases según la paridad de la distancia a una raíz elegida cualquiera.
Consideremos \[ S=\sum_{i\in A}a_i-\sum_{i\in B}a_i. \] Desarrollemos cada \(a_i\) como la suma de las longitudes de sus piezas finales. Cada arista de esta componente, correspondiente a una pareja, aporta la diferencia entre las longitudes de sus dos piezas, con uno de los dos signos posibles. La única pieza que puede quedar sin pareja aporta su longitud o su opuesto si pertenece a la componente. Por tanto, por la desigualdad triangular, \[ |S| \le \sum_{j=1}^{\lfloor p/2\rfloor}(x_{2j-1}-x_{2j}) +\begin{cases} x_p,&p\text{ impar},\\ 0,&p\text{ par} \end{cases} =D. \]
Por otra parte, sea \(r\) el mayor índice de esta componente. Su contribución a \(S\) tiene valor absoluto \(2^ru\), mientras que todos los índices menores juntos tienen longitud total a lo sumo \((2^r-1)u\). Por tanto, \[ |S|\ge 2^ru-\sum_{i=0}^{r-1}2^iu=u. \] Así, \(D\ge u\), independientemente de las marcas de Xiang. En consecuencia, Liu puede garantizar \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1}. \]
Demostremos ahora la cota superior coincidente. Supongamos que las marcas de Liu crean \(m\le n+1\) intervalos. Las marcas en los extremos, si las hay, pueden ignorarse.
Si \(m\le n\), Xiang divide cada intervalo por la mitad, usando a lo sumo \(n\) marcas. Todas las piezas resultantes aparecen en parejas de igual longitud, de modo que \(D=0\). Por tanto, Liu puede obtener a lo sumo \(1/2\) si su adversario juega óptimamente.
Queda por considerar \(m=n+1\). Escribamos las longitudes de los intervalos como \(b_1,\ldots,b_m\). Sus \(2^m\) sumas de subconjuntos están todas en \([0,1]\), con suma mínima \(0\) y suma máxima \(1\). Enumeremos estas sumas en orden no decreciente, conservando las repeticiones. Como sus \(2^m-1\) diferencias consecutivas suman \(1\), hay dos subconjuntos distintos cuyas sumas difieren en algún \[ 0\le\delta\le\frac1{2^m-1}=u. \] Eliminemos sus índices comunes. Esto da conjuntos disjuntos \(A,B\), no ambos vacíos, cuyas longitudes totales satisfacen \[ \alpha=\sum_{i\in A}b_i,\qquad \beta=\sum_{i\in B}b_i,\qquad \alpha\ge\beta,\qquad \alpha-\beta=\delta. \]
Afirmamos que Xiang puede usar a lo sumo \(m-1\) marcas de modo que todas las piezas, salvo algunas de longitud total \(\delta\), aparezcan en parejas de igual longitud.
Si \(B\) es vacío, basta dividir por la mitad cada intervalo que no esté en \(A\). Esto usa \[ m-|A|\le m-1 \] marcas, y los intervalos restantes tienen longitud total \(\alpha=\delta\).
En caso contrario, ambos conjuntos son no vacíos. Dispongamos mentalmente los intervalos de \(A\) uno a continuación de otro en una fila de longitud \(\alpha\), y los de \(B\) en otra fila de longitud \(\beta\), con sus extremos izquierdos alineados. En la parte común \([0,\beta]\), copiemos cada límite de intervalo de cualquiera de las filas a la otra, haciendo un corte allí siempre que sea necesario. Cortemos también la primera fila en \(\beta\) si este punto está en el interior de uno de sus intervalos.
Las dos filas tienen ahora subdivisiones idénticas en \([0,\beta]\), lo que da parejas de igual longitud. La parte restante de la primera fila tiene longitud total \(\delta\). Hay a lo sumo \[ (|A|-1)+(|B|-1)+1=|A|+|B|-1 \] cortes nuevos: cada límite interno de una fila requiere a lo sumo un corte en la otra, y el extremo \(\beta\) requiere a lo sumo un corte adicional. Esto también abarca \(\alpha=\beta\), caso en el que ese corte adicional es innecesario.
Finalmente, dividamos por la mitad cada intervalo original que no esté en \(A\cup B\). El número total de marcas es a lo sumo \[ |A|+|B|-1+(m-|A|-|B|)=m-1=n, \] lo que demuestra la afirmación. La disposición en filas es solo una manera de especificar cortes dentro de los intervalos originales; no se necesita ninguna reordenación física.
Eliminemos todas las parejas de igual longitud de la lista ordenada de longitudes de las piezas finales. Esto deja \(D\) inalterado. Las piezas restantes tienen longitud total \(\delta\), de modo que su suma alternada es a lo sumo \(\delta\). En consecuencia, \[ D\le\delta\le u. \] Jugando óptimamente en la fase de reparto, Xiang se asegura, por tanto, de que Liu reciba a lo sumo \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1}. \] Junto con la estrategia de Liu, esto demuestra la respuesta.
La solución se comprobó con las notas de soluciones de la IMO publicadas por Evan Chen.
IMO 2026 · 问题 3
设 \(n\) 是正整数。刘邦和项羽有一根长度为 \(1\) 的细棍，他们按下述方式进行分配。刘邦先在细棍上标记不超过 \(n\) 个点，接着项羽再标记不超过 \(n\) 个点。标记的点是互不相同的。随后在所有标记点处将细棍切开，这样细棍被分成了若干个小段。在此之后，他们轮流选取一个未被选取的小段，由刘邦优先，直至全部选完。每个人的目标均是使得自己选取的小段的总长度尽可能大。
对每个 \(n\)，求最大的 \(c\)，使得无论项羽如何操作，刘邦总能确保自己选取的小段的总长度不小于 \(c\)。
题目为官方中文译本。 官方试卷 (PDF)
答案
\(\displaystyle c=\frac{2^n}{2^{n+1}-1}\)。
解答
首先，设切开后所有小段的长度按从大到小的顺序排列为 \[ x_1\ge x_2\ge\cdots\ge x_p>0. \] 在选取阶段，刘邦能够保证得到的总长度为 \[ x_1+x_3+x_5+\cdots=\frac{1+D}{2}, \qquad D=x_1-x_2+x_3-x_4+\cdots+(-1)^{p+1}x_p. \] 事实上，若刘邦每次都选取剩余小段中最长的一段，则他第 \(j\) 次选取的小段的长度至少为 \(x_{2j-1}\)，因为此前只选走了 \(2j-2\) 段。类似地，若项羽每次都选取剩余小段中最长的一段，则他第 \(j\) 次选取的小段的长度至少为 \(x_{2j}\)。这两个策略证明了上述值。
我们还将用到以下观察：从排好序的长度序列中删去两个相等的长度，不会改变 \(D\)。相等的项可以相邻放置，所以它们的贡献相互抵消，而删去它们后，所有后续项的符号都保持不变。
令 \[ u=\frac{1}{2^{n+1}-1}. \]
我们先证明刘邦能够保证得到 \((1+u)/2\)。他标记 \(n\) 个点，使所得的 \(n+1\) 个区间的长度为 \[ a_i=2^iu,\qquad i=0,1,\ldots,n. \] 这些长度之和为 \(1\)。
项羽标记之后，至多有 \(2n+1\) 个小段。将它们的长度按上述方式排序，并配成如下各对： \[ (x_1,x_2),\ (x_3,x_4),\ \ldots, \] 若 \(p\) 为奇数，则留下 \(x_p\) 不配对。
构造一个图，其顶点为原来的区间 \(0,1,\ldots,n\)。每对小段对应一条边，连接包含这两个小段的原区间。允许有自环和重边。该图有 \(n+1\) 个顶点以及 \[ \left\lfloor\frac p2\right\rfloor\le n \] 条边。
因此，必有一个连通分支是树，也可能是一个孤立顶点。为说明这一点，注意每个有 \(v\) 个顶点的连通分支都包含一棵有 \(v-1\) 条边的生成树。若没有一个连通分支本身是树，则每个分支至少有 \(v\) 条边，总共便至少有 \(n+1\) 条边。
选取这样的一个树分支，并将其顶点分为 \(A,B\) 两类，使每条边都连接不同类的顶点。这可以通过任选一个根，再按各顶点到根的距离的奇偶性分类来实现。
考虑 \[ S=\sum_{i\in A}a_i-\sum_{i\in B}a_i. \] 将每个 \(a_i\) 展开为其中最终各小段的长度之和。该分支中每条由配对产生的边的贡献，都是所对应两个小段的长度之差，符号可能为正，也可能为负。唯一可能未配对的小段若属于该分支，则贡献其长度或其相反数。因此，由三角不等式， \[ |S| \le \sum_{j=1}^{\lfloor p/2\rfloor}(x_{2j-1}-x_{2j}) +\begin{cases} x_p,&p\text{ 为奇数},\\ 0,&p\text{ 为偶数} \end{cases} =D. \]
另一方面，设 \(r\) 为该分支中最大的下标。它对 \(S\) 的贡献的绝对值为 \(2^ru\)，而所有较小下标对应的区间的总长度至多为 \((2^r-1)u\)。因此， \[ |S|\ge 2^ru-\sum_{i=0}^{r-1}2^iu=u. \] 所以，无论项羽如何标记，都有 \(D\ge u\)。因此刘邦能够保证得到 \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1}. \]
现在证明与之相符的上界。设刘邦的标记产生了 \(m\le n+1\) 个区间。若端点处有标记，可以忽略。
若 \(m\le n\)，项羽将每个区间二等分，所用标记不超过 \(n\) 个。所得的所有小段都成对等长，所以 \(D=0\)。因此，面对最优应对，刘邦至多能得到 \(1/2\)。
只需考虑 \(m=n+1\) 的情形。记各区间长度为 \(b_1,\ldots,b_m\)。它们的 \(2^m\) 个子集和都在 \([0,1]\) 内，其中最小的和为 \(0\)，最大的和为 \(1\)。将这些和按非降顺序排列，并保留重复值。由于相邻两项的 \(2^m-1\) 个差之和为 \(1\)，必有两个不同子集的和相差某个 \[ 0\le\delta\le\frac1{2^m-1}=u. \] 去掉它们的公共下标，便得到两个不交且不同时为空的集合 \(A,B\)，其总长度满足 \[ \alpha=\sum_{i\in A}b_i,\qquad \beta=\sum_{i\in B}b_i,\qquad \alpha\ge\beta,\qquad \alpha-\beta=\delta. \]
我们断言，项羽可以使用至多 \(m-1\) 个标记，使除总长度为 \(\delta\) 的一些小段之外，所有小段都成对等长。
若 \(B\) 为空，只需将 \(A\) 之外的每个区间二等分。这需要 \[ m-|A|\le m-1 \] 个标记，而其余区间的总长度为 \(\alpha=\delta\)。
否则，两个集合均非空。在思考中，将 \(A\) 中的区间首尾相接排成长度为 \(\alpha\) 的一行，将 \(B\) 中的区间排成长度为 \(\beta\) 的另一行，并对齐两行的左端点。在公共部分 \([0,\beta]\) 上，将任一行中的每个区间分界点复制到另一行，必要时在那里切开。此外，若 \(\beta\) 位于第一行某个区间的内部，就在该处切开第一行。
现在，两行在 \([0,\beta]\) 上具有相同的分段，从而给出等长的配对。第一行剩余部分的总长度为 \(\delta\)。新增的切口至多有 \[ (|A|-1)+(|B|-1)+1=|A|+|B|-1 \] 个：一行的每个内部分界点至多需要在另一行中增加一个切口，而端点 \(\beta\) 至多需要再增加一个切口。这也包括 \(\alpha=\beta\) 的情形，此时不需要那个额外的切口。
最后，将 \(A\cup B\) 之外的每个原区间二等分。标记总数至多为 \[ |A|+|B|-1+(m-|A|-|B|)=m-1=n, \] 断言得证。排成两行只是指定原区间内部切口的一种方式，无需实际重新排列。
从排好序的最终小段长度序列中删去所有等长的配对。这不会改变 \(D\)。剩余小段的总长度为 \(\delta\)，所以它们的交错和至多为 \(\delta\)。因此， \[ D\le\delta\le u. \] 所以，项羽在选取阶段采用最优策略，就能确保刘邦所得的总长度至多为 \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1}. \] 结合刘邦的策略，即得所求答案。
解答已与 Evan Chen 发布的 IMO 解答笔记核对。
IMO 2026 · Задача 3
Дано целое положительное число \(n\). У Карлсона и Малыша есть палка длины 1, которую они делят между собой. Сначала Карлсон отмечает на палке не более чем \(n\) точек. Затем Малыш отмечает на палке не более чем \(n\) точек. Все отмеченные точки должны быть различны. Затем палка разрезается по отмеченным точкам, при этом образуются куски-палочки. После этого Карлсон и Малыш поочерёдно берут себе по одной палочке, начинает Карлсон. Так продолжается, пока они не разберут все палочки. Цель каждого — максимизировать суммарную длину своих палочек. При каждом \(n\) определите наибольшее значение \(c\), для которого Карлсон может обеспечить себе суммарную длину палочек, не меньшую \(c\), независимо от действий Малыша.
Официальный русский текст задачи. Официальный текст задач (PDF)
Ответ
\(\displaystyle c=\frac{2^n}{2^{n+1}-1}\).
Решение
Сначала предположим, что после всех разрезов длины палочек, расположенные в порядке убывания, равны \[ x_1\ge x_2\ge\cdots\ge x_p>0. \] Суммарная длина, которую Карлсон может гарантировать себе на этапе выбора палочек, равна \[ x_1+x_3+x_5+\cdots=\frac{1+D}{2}, \qquad D=x_1-x_2+x_3-x_4+\cdots+(-1)^{p+1}x_p. \] Действительно, если Карлсон всегда берёт самую длинную из оставшихся палочек, то его \(j\)-я палочка имеет длину не меньше \(x_{2j-1}\), поскольку до этого было взято лишь \(2j-2\) палочек. Аналогично, если Малыш всегда берёт самую длинную из оставшихся палочек, то его \(j\)-я палочка имеет длину не меньше \(x_{2j}\). Эти две стратегии доказывают указанное значение.
Нам также понадобится следующее наблюдение: удаление двух равных длин из упорядоченного списка не меняет \(D\). Равные элементы можно расположить рядом, так что их вклады взаимно уничтожаются, а их удаление сохраняет знаки всех последующих элементов.
Положим \[ u=\frac{1}{2^{n+1}-1}. \]
Сначала покажем, что Карлсон может гарантировать себе \((1+u)/2\). Он ставит свои \(n\) отметок так, чтобы получившиеся \(n+1\) отрезков имели длины \[ a_i=2^iu,\qquad i=0,1,\ldots,n. \] Сумма этих длин равна \(1\).
После того как Малыш поставит свои отметки, получится не более \(2n+1\) палочек. Упорядочим их длины, как выше, и разобьём их на пары \[ (x_1,x_2),\ (x_3,x_4),\ \ldots, \] оставив \(x_p\) без пары, если \(p\) нечётно.
Построим граф, вершины которого — исходные отрезки \(0,1,\ldots,n\). Каждая пара палочек задаёт ребро, соединяющее исходные отрезки, содержащие эти две палочки. Допускаются петли и кратные рёбра. Этот граф имеет \(n+1\) вершин и \[ \left\lfloor\frac p2\right\rfloor\le n \] рёбер.
Следовательно, некоторая компонента связности является деревом, возможно, состоящим из одной изолированной вершины. Чтобы это увидеть, заметим, что каждая компонента связности с \(v\) вершинами содержит остовное дерево с \(v-1\) рёбрами. Если бы ни одна компонента сама не была деревом, то в каждой было бы не менее \(v\) рёбер, что в сумме дало бы не менее \(n+1\) рёбер.
Выберем такую компоненту-дерево и разобьём её вершины на два класса \(A,B\) так, чтобы каждое ребро соединяло вершины разных классов. Это можно сделать, распределяя вершины по классам в зависимости от чётности расстояния до произвольно выбранного корня.
Рассмотрим \[ S=\sum_{i\in A}a_i-\sum_{i\in B}a_i. \] Представим каждое \(a_i\) как сумму длин палочек, на которые в итоге разрезан соответствующий отрезок. Каждое ребро этой компоненты, соответствующее паре палочек, даёт вклад, равный разности их длин с одним из двух возможных знаков. Единственная возможная палочка без пары даёт вклад, равный её длине или противоположному числу, если она принадлежит компоненте. Поэтому по неравенству треугольника \[ |S| \le \sum_{j=1}^{\lfloor p/2\rfloor}(x_{2j-1}-x_{2j}) +\begin{cases} x_p,&p\text{ нечётно},\\ 0,&p\text{ чётно} \end{cases} =D. \]
С другой стороны, пусть \(r\) — наибольший индекс в этой компоненте. Его вклад в \(S\) по абсолютной величине равен \(2^ru\), тогда как суммарная длина отрезков со всеми меньшими индексами не превосходит \((2^r-1)u\). Следовательно, \[ |S|\ge 2^ru-\sum_{i=0}^{r-1}2^iu=u. \] Таким образом, \(D\ge u\) независимо от отметок Малыша. Следовательно, Карлсон может гарантировать себе \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1}. \]
Теперь докажем совпадающую с этой оценкой верхнюю границу. Пусть отметки Карлсона образуют \(m\le n+1\) отрезков. Отметки на концах палки, если они есть, можно не учитывать.
Если \(m\le n\), Малыш делит каждый отрезок пополам, используя не более \(n\) отметок. Все полученные палочки разбиваются на пары равной длины, поэтому \(D=0\). Значит, при оптимальной игре Малыша Карлсон может получить не более \(1/2\).
Остаётся рассмотреть случай \(m=n+1\). Обозначим длины отрезков через \(b_1,\ldots,b_m\). Все \(2^m\) сумм по их подмножествам лежат в \([0,1]\), причём наименьшая сумма равна \(0\), а наибольшая — \(1\). Выпишем эти суммы в порядке неубывания, сохраняя повторения. Поскольку сумма \(2^m-1\) разностей между соседними суммами равна \(1\), найдутся два различных подмножества, суммы которых отличаются на некоторое число \[ 0\le\delta\le\frac1{2^m-1}=u. \] Удалим их общие индексы. Получим непересекающиеся множества \(A,B\), не оба пустые, для суммарных длин которых выполняется \[ \alpha=\sum_{i\in A}b_i,\qquad \beta=\sum_{i\in B}b_i,\qquad \alpha\ge\beta,\qquad \alpha-\beta=\delta. \]
Утверждаем, что Малыш может поставить не более \(m-1\) отметок так, чтобы все палочки, за исключением палочек суммарной длины \(\delta\), разбивались на пары равной длины.
Если \(B\) пусто, достаточно разделить пополам каждый отрезок вне \(A\). Для этого потребуется \[ m-|A|\le m-1 \] отметок, а суммарная длина оставшихся отрезков равна \(\alpha=\delta\).
В противном случае оба множества непусты. Мысленно расположим отрезки из \(A\) друг за другом в ряд длины \(\alpha\), а отрезки из \(B\) — в другой ряд длины \(\beta\), совместив левые концы рядов. На общей части \([0,\beta]\) перенесём каждую границу отрезков любого ряда в другой ряд, делая там разрез, если это необходимо. Также разрежем первый ряд в точке \(\beta\), если она лежит внутри одного из его отрезков.
Теперь оба ряда имеют одинаковые разбиения на \([0,\beta]\), что даёт пары равной длины. Оставшаяся часть первого ряда имеет суммарную длину \(\delta\). Число новых разрезов не превосходит \[ (|A|-1)+(|B|-1)+1=|A|+|B|-1 \] : каждая внутренняя граница одного ряда требует не более одного разреза в другом, а конец \(\beta\) — не более одного дополнительного разреза. Это рассуждение охватывает и случай \(\alpha=\beta\), когда дополнительный разрез не нужен.
Наконец, разделим пополам каждый исходный отрезок вне \(A\cup B\). Общее число отметок не превосходит \[ |A|+|B|-1+(m-|A|-|B|)=m-1=n, \] что доказывает утверждение. Расположение в два ряда — лишь способ указать разрезы внутри исходных отрезков; физически переставлять их не требуется.
Удалим все пары равной длины из упорядоченного списка длин полученных палочек. При этом \(D\) не изменится. Оставшиеся палочки имеют суммарную длину \(\delta\), поэтому их знакопеременная сумма не превосходит \(\delta\). Следовательно, \[ D\le\delta\le u. \] Таким образом, играя оптимально на этапе выбора палочек, Малыш обеспечивает, что Карлсон получит не более \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1}. \] Вместе со стратегией Карлсона это доказывает ответ.
Решение проверено по опубликованным заметкам Эвана Чена с решениями IMO.
IMO 2026 · المسألة 3
ليكن \(n\) عدداً صحيحاً موجباً. لدى ليو بانغ وشيانغ يو عصا طولها 1، ويريدان تقسيمها فيما بينهما. يقوم ليو بتحديد \(n\) نقطة على العصا على الأكثر. بعد ذلك، يقوم شيانغ بتحديد \(n\) نقطة على العصا على الأكثر بحيث تكون النقاط المحددة مختلفة. نقوم بقص العصا عند جميع النقاط المحددة للحصول على عدد من القطع. بعد ذلك، يتناوب ليو وشيانغ الأدوار في اختيار القطع التي لم يتم اختيارها ابتداءً من ليو أولاً. هدف كل لاعب من اللاعبين هو تعظيم مجموع أطوال قطعه التي اختارها.
لكل \(n\)، حدد أكبر قيمة \(c\) بحيث يضمن ليو مجموع أطوال قطع \(c\) على الأقل، بغض النظر عن طريقة لعب شيانغ.
نص المسألة هو الترجمة العربية الرسمية. ورقة المسائل الرسمية (PDF)
الإجابة
\(\displaystyle c=\frac{2^n}{2^{n+1}-1}\).
الحل
أولًا، افترض أن أطوال القطع بعد إجراء جميع القصّات، مرتبة ترتيبًا تنازليًا، هي \[ x_1\ge x_2\ge\cdots\ge x_p>0. \] القيمة التي يمكن لليو ضمانها في مرحلة اختيار القطع هي \[ x_1+x_3+x_5+\cdots=\frac{1+D}{2}, \qquad D=x_1-x_2+x_3-x_4+\cdots+(-1)^{p+1}x_p. \] بالفعل، إذا اختار ليو دائمًا قطعة من أطول القطع المتبقية، فإن قطعته ذات الترتيب \(j\) لا يقل طولها عن \(x_{2j-1}\)، إذ لم تُختَر قبلها سوى \(2j-2\) قطعة. وبالمثل، إذا اختار شيانغ دائمًا قطعة من أطول القطع المتبقية، فإن قطعته ذات الترتيب \(j\) لا يقل طولها عن \(x_{2j}\). وتثبت هاتان الاستراتيجيتان القيمة المدّعاة.
سنستخدم أيضًا الملاحظة التالية: حذف طولين متساويين من القائمة المرتبة لا يغيّر \(D\). إذ يمكن وضع العناصر المتساوية متتالية، فتُلغي مساهماتها بعضها بعضًا، ويحافظ حذفها على إشارات جميع العناصر اللاحقة.
ضع \[ u=\frac{1}{2^{n+1}-1}. \]
نثبت أولًا أن ليو يستطيع ضمان \((1+u)/2\). يضع علاماته الـ\(n\) بحيث تكون أطوال الفترات الـ\(n+1\) الناتجة هي \[ a_i=2^iu,\qquad i=0,1,\ldots,n. \] مجموع هذه الأطوال هو \(1\).
بعد أن يضع شيانغ علاماته، يكون عدد القطع على الأكثر \(2n+1\). نرتّب أطوالها كما سبق، ونقرنها على النحو التالي: \[ (x_1,x_2),\ (x_3,x_4),\ \ldots, \] مع إبقاء \(x_p\) دون قرين إذا كان \(p\) فرديًا.
ننشئ رسمًا بيانيًا رؤوسه الفترات الأصلية \(0,1,\ldots,n\). ويعطي كل زوج من القطع حافة تصل بين الفترتين الأصليتين اللتين تحتويان هاتين القطعتين. ويُسمح بالحلقات والحواف المتعددة. لهذا الرسم البياني \(n+1\) رأسًا و \[ \left\lfloor\frac p2\right\rfloor\le n \] حافة.
بالتالي، توجد مركّبة متصلة تكون شجرة، وربما كانت رأسًا منفردًا معزولًا. ولرؤية ذلك، فإن كل مركّبة متصلة ذات \(v\) رأسًا تحتوي على شجرة ممتدة ذات \(v-1\) حافة. ولو لم تكن أي مركّبة شجرةً، لكان لكل منها \(v\) حافة على الأقل، مما يعطي ما لا يقل عن \(n+1\) حافة إجمالًا.
نختار مركّبة شجرية كهذه، ونقسّم رؤوسها إلى فئتين \(A,B\) بحيث تصل كل حافة بين الفئتين. وهذا ممكن بإسناد الفئات وفق زوجية المسافة من أي جذر نختاره.
اعتبر \[ S=\sum_{i\in A}a_i-\sum_{i\in B}a_i. \] نكتب كل \(a_i\) على صورة مجموع أطوال قطعه النهائية. تساهم كل حافة تمثّل زوجًا في هذه المركّبة بالفرق بين طولي قطعتيها، بإحدى الإشارتين الممكنتين. وتساهم القطعة الوحيدة المحتمل بقاؤها دون قرين بطولها أو بسالبه إذا كانت تنتمي إلى المركّبة. لذلك، بمتباينة المثلث، \[ |S| \le \sum_{j=1}^{\lfloor p/2\rfloor}(x_{2j-1}-x_{2j}) +\begin{cases} x_p,&p\text{ فردي},\\ 0,&p\text{ زوجي} \end{cases} =D. \]
من ناحية أخرى، ليكن \(r\) أكبر دليل في هذه المركّبة. القيمة المطلقة لمساهمته في \(S\) هي \(2^ru\)، بينما لا يزيد مجموع أطوال جميع الأدلة الأصغر على \((2^r-1)u\). ومن ثم \[ |S|\ge 2^ru-\sum_{i=0}^{r-1}2^iu=u. \] إذن \(D\ge u\)، بغض النظر عن علامات شيانغ. وبالتالي يستطيع ليو ضمان \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1}. \]
نثبت الآن الحد العلوي المطابق. افترض أن علامات ليو تنشئ \(m\le n+1\) فترة. ويمكن تجاهل العلامات الواقعة عند الطرفين، إن وُجدت.
إذا كان \(m\le n\)، ينصّف شيانغ كل فترة، مستخدمًا على الأكثر \(n\) علامة. وتأتي جميع القطع الناتجة في أزواج متساوية، لذا \(D=0\). ومن ثم لا يستطيع ليو الحصول على أكثر من \(1/2\) في مواجهة اللعب الأمثل.
يبقى النظر في الحالة \(m=n+1\). لنكتب أطوال الفترات على الصورة \(b_1,\ldots,b_m\). تقع مجاميع مجموعاتها الجزئية الـ\(2^m\) كلها في \([0,1]\)، وأصغرها \(0\) وأكبرها \(1\). نسرد هذه المجاميع بترتيب غير تناقصي، مع الإبقاء على التكرارات. وبما أن مجموع الفروق المتتالية الـ\(2^m-1\) هو \(1\)، فإن مجموعَي مجموعتين جزئيتين مختلفتين يختلفان بمقدار \[ 0\le\delta\le\frac1{2^m-1}=u. \] نحذف الأدلة المشتركة بينهما. فنحصل على مجموعتين متباعدتين \(A,B\)، ليستا كلتاهما فارغتين، يحقق مجموعا أطوالهما \[ \alpha=\sum_{i\in A}b_i,\qquad \beta=\sum_{i\in B}b_i,\qquad \alpha\ge\beta,\qquad \alpha-\beta=\delta. \]
ندّعي أن شيانغ يستطيع استخدام ما لا يزيد على \(m-1\) علامة بحيث تأتي جميع القطع في أزواج متساوية، باستثناء قطع مجموع أطوالها \(\delta\).
إذا كانت \(B\) فارغة، يكفي تنصيف كل فترة خارج \(A\). ويستخدم ذلك \[ m-|A|\le m-1 \] علامة، ويكون مجموع أطوال الفترات المتبقية \(\alpha=\delta\).
وإلا فكلتا المجموعتين غير فارغة. نتصوّر ترتيب فترات \(A\) متلاصقة طرفًا بطرف في صف طوله \(\alpha\)، وفترات \(B\) في صف آخر طوله \(\beta\)، مع محاذاة طرفيهما الأيسرين. وعلى الجزء المشترك \([0,\beta]\)، ننقل كل حدّ بين الفترات في أي من الصفين إلى الصف الآخر، ونُجري قصّة هناك متى لزم ذلك. ونقصّ الصف الأول أيضًا عند \(\beta\) إذا وقعت داخل إحدى فتراته.
أصبح للصفين الآن تقسيمان متطابقان على \([0,\beta]\)، مما يعطي أزواجًا متساوية. ويبلغ مجموع أطوال الجزء المتبقي من الصف الأول \(\delta\). ولا يزيد عدد القصّات الجديدة على \[ (|A|-1)+(|B|-1)+1=|A|+|B|-1 \] قصّة: فكل حدّ داخلي في صف يتطلب قصّة واحدة على الأكثر في الصف الآخر، والطرف \(\beta\) يتطلب قصّة إضافية واحدة على الأكثر. ويشمل ذلك أيضًا \(\alpha=\beta\)، حيث لا تلزم تلك القصّة الإضافية.
أخيرًا، ننصّف كل فترة أصلية خارج \(A\cup B\). ولا يزيد العدد الكلي للعلامات على \[ |A|+|B|-1+(m-|A|-|B|)=m-1=n, \] وهذا يثبت الادّعاء. وترتيب الصفين ليس سوى وسيلة لتحديد مواضع القصّ داخل الفترات الأصلية؛ فلا حاجة إلى إعادة ترتيب فعلية.
نحذف جميع الأزواج المتساوية من القائمة المرتبة لأطوال القطع النهائية. وهذا يُبقي \(D\) دون تغيير. مجموع أطوال القطع المتبقية هو \(\delta\)، لذا لا يزيد مجموعها المتناوب على \(\delta\). وبالتالي، \[ D\le\delta\le u. \] إذن، باللعب الأمثل في مرحلة اختيار القطع، يضمن شيانغ ألا يحصل ليو على أكثر من \[ \frac{1+u}{2}=\frac{2^n}{2^{n+1}-1}. \] وبضم ذلك إلى استراتيجية ليو، تثبت الإجابة.
تمت مراجعة الحل بمقارنته بملاحظات حلول IMO المنشورة لإيفان تشين.