IMO 1997 · Problem 3
Let \(x_1,x_2,\ldots,x_n\) be real numbers satisfying the conditions \[ |x_1+x_2+\cdots+x_n|=1 \] and \[ |x_i|\leq \frac{n+1}{2}\qquad i=1,2,\ldots,n. \] Show that there exists a permutation \(y_1,y_2,\ldots,y_n\) of \(x_1,x_2,\ldots,x_n\) such that \[ |y_1+2y_2+\cdots+ny_n|\leq \frac{n+1}{2}. \]
Official text of the problem. Official problem paper (PDF)
Solution
Put \(c=(n+1)/2\). Negating all the numbers preserves the hypotheses and the desired conclusion, so we may assume \[ x_1+\cdots+x_n=1. \]
For an ordering \(a=(a_1,\ldots,a_n)\) of the given numbers, write \[ F(a)=\sum_{i=1}^{n}i a_i. \] Its reverse \(a^{\mathrm{rev}}=(a_n,\ldots,a_1)\) satisfies \[ F(a)+F(a^{\mathrm{rev}}) =\sum_{i=1}^{n}\bigl(i+(n+1-i)\bigr)a_i =(n+1)\sum_{i=1}^{n}a_i =2c. \] Consequently, either \(F(a)=c\), which proves the result immediately, or one of these two orderings has weighted sum greater than \(c\) and the other has weighted sum less than \(c\).
Start with the ordering whose weighted sum is greater than \(c\), and transform it into the other ordering through finitely many swaps of adjacent entries. Such a transformation is always possible: move the entry required in the first position there by adjacent swaps, then do the same for the second position, and continue.
If adjacent entries \(u,v\), in positions \(i,i+1\), are interchanged, the change in the weighted sum is \[ \bigl(iv+(i+1)u\bigr)-\bigl(iu+(i+1)v\bigr)=u-v. \] Thus every swap changes the weighted sum by at most \[ |u-v|\leq |u|+|v|\leq 2c. \]
Since the initial weighted sum is greater than \(c\) and the final one is less than \(c\), there is a first swap after which the weighted sum is at most \(c\). Denote the sums immediately before and after this swap by \(U\) and \(V\). Then \[ U>c,\qquad V\leq c,\qquad |V-U|\leq 2c, \] so \[ V\geq U-2c>-c. \] Therefore \(-c<V\leq c\). The ordering at this stage is the required permutation, since \[ |y_1+2y_2+\cdots+ny_n|\leq c=\frac{n+1}{2}. \] \(\square\)
The solution was checked against Evan Chen's published IMO solution notes.
IMO 1997 · Aufgabe 3
Seien \(x_1,x_2,\ldots,x_n\) reelle Zahlen mit den Eigenschaften \[ |x_1+x_2+\cdots+x_n|=1 \] und \[ |x_i|\leq \frac{n+1}{2}\qquad i=1,2,\ldots,n. \] Zeige, dass es eine Permutation \(y_1,y_2,\ldots,y_n\) von \(x_1,x_2,\ldots,x_n\) gibt, sodass \[ |y_1+2y_2+\cdots+ny_n|\leq \frac{n+1}{2}. \]
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Setze \(c=(n+1)/2\). Ein Vorzeichenwechsel aller Zahlen erhält sowohl die Voraussetzungen als auch die gewünschte Schlussfolgerung, sodass wir Folgendes annehmen dürfen: \[ x_1+\cdots+x_n=1. \]
Für eine Anordnung \(a=(a_1,\ldots,a_n)\) der gegebenen Zahlen schreiben wir \[ F(a)=\sum_{i=1}^{n}i a_i. \] Für ihre umgekehrte Anordnung \(a^{\mathrm{rev}}=(a_n,\ldots,a_1)\) gilt \[ F(a)+F(a^{\mathrm{rev}}) =\sum_{i=1}^{n}\bigl(i+(n+1-i)\bigr)a_i =(n+1)\sum_{i=1}^{n}a_i =2c. \] Folglich gilt entweder \(F(a)=c\), womit die Behauptung unmittelbar bewiesen ist, oder eine dieser beiden Anordnungen hat eine gewichtete Summe größer als \(c\) und die andere eine gewichtete Summe kleiner als \(c\).
Wir beginnen mit der Anordnung, deren gewichtete Summe größer als \(c\) ist, und überführen sie durch endlich viele Vertauschungen benachbarter Einträge in die andere Anordnung. Eine solche Umformung ist stets möglich: Man bringt den für die erste Position vorgesehenen Eintrag durch benachbarte Vertauschungen dorthin, verfährt dann ebenso mit der zweiten Position und setzt dies fort.
Werden benachbarte Einträge \(u,v\) an den Positionen \(i,i+1\) vertauscht, so ändert sich die gewichtete Summe um \[ \bigl(iv+(i+1)u\bigr)-\bigl(iu+(i+1)v\bigr)=u-v. \] Somit ändert jede Vertauschung die gewichtete Summe dem Betrag nach um höchstens \[ |u-v|\leq |u|+|v|\leq 2c. \]
Da die gewichtete Summe zu Beginn größer als \(c\) und am Ende kleiner als \(c\) ist, gibt es eine erste Vertauschung, nach der die gewichtete Summe höchstens \(c\) beträgt. Wir bezeichnen die Summen unmittelbar vor und nach dieser Vertauschung mit \(U\) und \(V\). Dann gilt \[ U>c,\qquad V\leq c,\qquad |V-U|\leq 2c, \] also \[ V\geq U-2c>-c. \] Daher gilt \(-c<V\leq c\). Die zu diesem Zeitpunkt vorliegende Anordnung ist die gesuchte Permutation, denn \[ |y_1+2y_2+\cdots+ny_n|\leq c=\frac{n+1}{2}. \] \(\square\)
Die Lösung wurde mit den veröffentlichten IMO-Lösungsnotizen von Evan Chen abgeglichen.
IMO 1997 · Soru 3
\(x_1,x_2,\ldots,x_n\), \[ |x_1+x_2+\cdots+x_n|=1 \] ve \[ |x_i|\leq \frac{n+1}{2}\qquad i=1,2,\ldots,n \] koşullarını sağlayan gerçel sayılar olsun. \(x_1,x_2,\ldots,x_n\) sayılarının, \[ |y_1+2y_2+\cdots+ny_n|\leq \frac{n+1}{2} \] eşitsizliğini sağlayan bir \(y_1,y_2,\ldots,y_n\) permütasyonunun bulunduğunu gösteriniz.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
\(c=(n+1)/2\) olsun. Tüm sayıların işaretlerini değiştirmek, varsayımları ve istenen sonucu korur; dolayısıyla \[ x_1+\cdots+x_n=1 \] olduğunu varsayabiliriz.
Verilen sayıların bir \(a=(a_1,\ldots,a_n)\) sıralaması için \[ F(a)=\sum_{i=1}^{n}i a_i \] yazalım. Ters sıralaması \(a^{\mathrm{rev}}=(a_n,\ldots,a_1)\), \[ F(a)+F(a^{\mathrm{rev}}) =\sum_{i=1}^{n}\bigl(i+(n+1-i)\bigr)a_i =(n+1)\sum_{i=1}^{n}a_i =2c \] eşitliğini sağlar. Dolayısıyla ya \(F(a)=c\) olur ve bu, sonucu hemen kanıtlar ya da bu iki sıralamadan birinin ağırlıklı toplamı \(c\)'den büyük, diğerininki ise \(c\)'den küçüktür.
Ağırlıklı toplamı \(c\)'den büyük olan sıralamadan başlayıp, komşu terimlerin yerlerini sonlu sayıda değiştirerek onu diğer sıralamaya dönüştürelim. Böyle bir dönüşüm her zaman mümkündür: ilk konumda bulunması gereken terimi komşu terimlerle yer değiştirerek oraya taşıyalım, sonra ikinci konum için aynı işlemi yapalım ve bu şekilde devam edelim.
\(i,i+1\) konumlarındaki komşu \(u,v\) terimleri yer değiştirirse, ağırlıklı toplamdaki değişim \[ \bigl(iv+(i+1)u\bigr)-\bigl(iu+(i+1)v\bigr)=u-v \] olur. Böylece her yer değiştirmede ağırlıklı toplamdaki değişimin mutlak değeri en fazla \[ |u-v|\leq |u|+|v|\leq 2c \] olur.
Başlangıçtaki ağırlıklı toplam \(c\)'den büyük, sondaki ise \(c\)'den küçük olduğundan, ağırlıklı toplamın ilk kez \(c\)'yi aşmadığı bir yer değiştirme vardır. Bu yer değiştirmeden hemen önceki ve hemen sonraki toplamları \(U\) ve \(V\) ile gösterelim. O zaman \[ U>c,\qquad V\leq c,\qquad |V-U|\leq 2c, \] dolayısıyla \[ V\geq U-2c>-c. \] Böylece \(-c<V\leq c\) olur. Bu aşamadaki sıralama istenen permütasyondur, çünkü \[ |y_1+2y_2+\cdots+ny_n|\leq c=\frac{n+1}{2}. \] \(\square\)
Çözüm, Evan Chen'in yayımlanmış IMO çözüm notlarıyla karşılaştırılarak kontrol edildi.
IMO 1997 · Problema 3
Sean \(x_1,x_2,\ldots,x_n\) números reales que satisfacen las condiciones \[ |x_1+x_2+\cdots+x_n|=1 \] y \[ |x_i|\leq \frac{n+1}{2}\qquad i=1,2,\ldots,n. \] Demostrar que existe una permutación \(y_1,y_2,\ldots,y_n\) de \(x_1,x_2,\ldots,x_n\) tal que \[ |y_1+2y_2+\cdots+ny_n|\leq \frac{n+1}{2}. \]
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Sea \(c=(n+1)/2\). Cambiar el signo de todos los números conserva las hipótesis y la conclusión que se quiere demostrar, por lo que podemos suponer que \[ x_1+\cdots+x_n=1. \]
Para una ordenación \(a=(a_1,\ldots,a_n)\) de los números dados, escribamos \[ F(a)=\sum_{i=1}^{n}i a_i. \] Su ordenación inversa \(a^{\mathrm{rev}}=(a_n,\ldots,a_1)\) satisface \[ F(a)+F(a^{\mathrm{rev}}) =\sum_{i=1}^{n}\bigl(i+(n+1-i)\bigr)a_i =(n+1)\sum_{i=1}^{n}a_i =2c. \] En consecuencia, o bien \(F(a)=c\), lo que demuestra el resultado inmediatamente, o bien una de estas dos ordenaciones tiene suma ponderada mayor que \(c\) y la otra tiene suma ponderada menor que \(c\).
Partamos de la ordenación cuya suma ponderada es mayor que \(c\) y transformémosla en la otra ordenación mediante un número finito de intercambios de términos adyacentes. Esta transformación siempre es posible: llevamos el término que debe ocupar la primera posición hasta ella mediante intercambios adyacentes, hacemos después lo mismo con la segunda posición y continuamos.
Si se intercambian dos términos adyacentes \(u,v\), situados en las posiciones \(i,i+1\), el cambio en la suma ponderada es \[ \bigl(iv+(i+1)u\bigr)-\bigl(iu+(i+1)v\bigr)=u-v. \] Así, cada intercambio cambia la suma ponderada a lo sumo en \[ |u-v|\leq |u|+|v|\leq 2c. \]
Como la suma ponderada inicial es mayor que \(c\) y la final es menor que \(c\), existe un primer intercambio tras el cual la suma ponderada es a lo sumo \(c\). Denotemos por \(U\) y \(V\) las sumas inmediatamente anterior y posterior a este intercambio. Entonces \[ U>c,\qquad V\leq c,\qquad |V-U|\leq 2c, \] de modo que \[ V\geq U-2c>-c. \] Por tanto, \(-c<V\leq c\). La ordenación en esta etapa es la permutación buscada, pues \[ |y_1+2y_2+\cdots+ny_n|\leq c=\frac{n+1}{2}. \] \(\square\)
La solución se comprobó con las notas de soluciones de la IMO publicadas por Evan Chen.
IMO 1997 · 问题 3
设实数 \(x_1,x_2,\ldots,x_n\) 满足条件 \[ |x_1+x_2+\cdots+x_n|=1 \] 以及 \[ |x_i|\leq \frac{n+1}{2}\qquad i=1,2,\ldots,n. \] 证明：存在 \(x_1,x_2,\ldots,x_n\) 的一个排列 \(y_1,y_2,\ldots,y_n\)，使得 \[ |y_1+2y_2+\cdots+ny_n|\leq \frac{n+1}{2}. \]
题目译自官方英文原文。 官方试卷 (PDF)
解答
令 \(c=(n+1)/2\)。将所有数同时取相反数，不会改变题设条件和待证结论，因此可以假设 \[ x_1+\cdots+x_n=1. \]
对于所给各数的一个排列 \(a=(a_1,\ldots,a_n)\)，记 \[ F(a)=\sum_{i=1}^{n}i a_i. \] 其逆序排列 \(a^{\mathrm{rev}}=(a_n,\ldots,a_1)\) 满足 \[ F(a)+F(a^{\mathrm{rev}}) =\sum_{i=1}^{n}\bigl(i+(n+1-i)\bigr)a_i =(n+1)\sum_{i=1}^{n}a_i =2c. \] 因此，要么 \(F(a)=c\)，此时结论立即成立；要么这两个排列中的一个加权和大于 \(c\)，另一个加权和小于 \(c\)。
从加权和大于 \(c\) 的排列出发，通过有限次交换相邻两项，将其变成另一个排列。这样的变换总是可以做到的：通过相邻交换，将第一位置所需的项移到该位置，再对第二位置作同样的操作，如此继续。
如果交换位于第 \(i,i+1\) 个位置的相邻两项 \(u,v\)，加权和的变化量为 \[ \bigl(iv+(i+1)u\bigr)-\bigl(iu+(i+1)v\bigr)=u-v. \] 因此，每次交换使加权和改变的绝对值至多为 \[ |u-v|\leq |u|+|v|\leq 2c. \]
由于初始加权和大于 \(c\)，最终加权和小于 \(c\)，必有第一次交换，使交换后的加权和不大于 \(c\)。将这次交换前后的加权和分别记为 \(U\) 和 \(V\)。于是 \[ U>c,\qquad V\leq c,\qquad |V-U|\leq 2c, \] 所以 \[ V\geq U-2c>-c. \] 因此 \(-c<V\leq c\)。此时的排列就是所求排列，因为 \[ |y_1+2y_2+\cdots+ny_n|\leq c=\frac{n+1}{2}. \] \(\square\)
解答已与 Evan Chen 发布的 IMO 解答笔记核对。
IMO 1997 · Задача 3
Пусть \(x_1,x_2,\ldots,x_n\) — действительные числа, удовлетворяющие условиям \[ |x_1+x_2+\cdots+x_n|=1 \] и \[ |x_i|\leq \frac{n+1}{2}\qquad i=1,2,\ldots,n. \] Покажите, что существует перестановка \(y_1,y_2,\ldots,y_n\) чисел \(x_1,x_2,\ldots,x_n\), такая что \[ |y_1+2y_2+\cdots+ny_n|\leq \frac{n+1}{2}. \]
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Положим \(c=(n+1)/2\). Замена всех чисел на противоположные сохраняет условия и требуемое заключение, поэтому можно считать, что \[ x_1+\cdots+x_n=1. \]
Для упорядочения \(a=(a_1,\ldots,a_n)\) данных чисел обозначим \[ F(a)=\sum_{i=1}^{n}i a_i. \] Для обратного упорядочения \(a^{\mathrm{rev}}=(a_n,\ldots,a_1)\) выполняется \[ F(a)+F(a^{\mathrm{rev}}) =\sum_{i=1}^{n}\bigl(i+(n+1-i)\bigr)a_i =(n+1)\sum_{i=1}^{n}a_i =2c. \] Следовательно, либо \(F(a)=c\), что сразу доказывает утверждение, либо у одного из этих двух упорядочений взвешенная сумма больше \(c\), а у другого — меньше \(c\).
Начнём с упорядочения, у которого взвешенная сумма больше \(c\), и преобразуем его в другое упорядочение с помощью конечного числа перестановок соседних элементов. Такое преобразование всегда возможно: переместим на первое место нужный элемент перестановками соседних элементов, затем сделаем то же самое для второго места и продолжим.
Если соседние элементы \(u,v\), стоящие на местах \(i,i+1\), меняются местами, то изменение взвешенной суммы равно \[ \bigl(iv+(i+1)u\bigr)-\bigl(iu+(i+1)v\bigr)=u-v. \] Таким образом, при каждой перестановке взвешенная сумма изменяется по модулю не более чем на \[ |u-v|\leq |u|+|v|\leq 2c. \]
Поскольку начальная взвешенная сумма больше \(c\), а конечная меньше \(c\), существует первая перестановка, после которой взвешенная сумма не превосходит \(c\). Обозначим суммы непосредственно до и после этой перестановки через \(U\) и \(V\). Тогда \[ U>c,\qquad V\leq c,\qquad |V-U|\leq 2c, \] откуда \[ V\geq U-2c>-c. \] Следовательно, \(-c<V\leq c\). Упорядочение на этом шаге и является искомой перестановкой, поскольку \[ |y_1+2y_2+\cdots+ny_n|\leq c=\frac{n+1}{2}. \] \(\square\)
Решение проверено по опубликованным заметкам Эвана Чена с решениями IMO.
IMO 1997 · المسألة 3
لتكن \(x_1,x_2,\ldots,x_n\) أعدادًا حقيقية تحقق الشرطين \[ |x_1+x_2+\cdots+x_n|=1 \] و \[ |x_i|\leq \frac{n+1}{2}\qquad i=1,2,\ldots,n. \] بيّن أنه يوجد تبديل \(y_1,y_2,\ldots,y_n\) للأعداد \(x_1,x_2,\ldots,x_n\) بحيث \[ |y_1+2y_2+\cdots+ny_n|\leq \frac{n+1}{2}. \]
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
نضع \(c=(n+1)/2\). إن تغيير إشارات الأعداد كلها يحافظ على الفرضيات وعلى النتيجة المطلوبة، لذا يمكننا أن نفترض \[ x_1+\cdots+x_n=1. \]
لكل ترتيب \(a=(a_1,\ldots,a_n)\) للأعداد المعطاة، نكتب \[ F(a)=\sum_{i=1}^{n}i a_i. \] ويحقق ترتيبه المعكوس \(a^{\mathrm{rev}}=(a_n,\ldots,a_1)\) \[ F(a)+F(a^{\mathrm{rev}}) =\sum_{i=1}^{n}\bigl(i+(n+1-i)\bigr)a_i =(n+1)\sum_{i=1}^{n}a_i =2c. \] وبالتالي، إما أن يكون \(F(a)=c\)، وهو ما يثبت النتيجة مباشرة، وإما أن يكون المجموع الموزون لأحد هذين الترتيبين أكبر من \(c\)، وللآخر أصغر من \(c\).
نبدأ بالترتيب الذي مجموعه الموزون أكبر من \(c\)، ونحوّله إلى الترتيب الآخر بعدد منتهٍ من عمليات مبادلة عنصرين متجاورين. وهذا التحويل ممكن دائمًا: ننقل العنصر المطلوب في الموضع الأول إلى ذلك الموضع بمبادلات بين عناصر متجاورة، ثم نفعل الشيء نفسه للموضع الثاني، وهكذا.
إذا بُودل عنصران متجاوران \(u,v\)، في الموضعين \(i,i+1\)، فإن التغير في المجموع الموزون يساوي \[ \bigl(iv+(i+1)u\bigr)-\bigl(iu+(i+1)v\bigr)=u-v. \] ومن ثم فإن كل مبادلة تغيّر المجموع الموزون بمقدار لا يتجاوز \[ |u-v|\leq |u|+|v|\leq 2c. \]
بما أن المجموع الموزون الابتدائي أكبر من \(c\) والمجموع النهائي أصغر من \(c\)، فلا بد من وجود أول مبادلة يصبح بعدها المجموع الموزون أصغر من أو يساوي \(c\). ولنرمز إلى المجموعين قبل هذه المبادلة مباشرة وبعدها مباشرة بـ\(U\) و\(V\). عندئذ \[ U>c,\qquad V\leq c,\qquad |V-U|\leq 2c, \] ومن ثم \[ V\geq U-2c>-c. \] إذن \(-c<V\leq c\). والترتيب في هذه المرحلة هو التبديل المطلوب، إذ \[ |y_1+2y_2+\cdots+ny_n|\leq c=\frac{n+1}{2}. \] \(\square\)
تمت مراجعة الحل بمقارنته بملاحظات حلول IMO المنشورة لإيفان تشين.