IMO 1975 · Problem 1
Let \(x_i,y_i\) \((i=1,2,\ldots,n)\) be real numbers such that \[ x_1\ge x_2\ge\cdots\ge x_n \quad\text{and}\quad y_1\ge y_2\ge\cdots\ge y_n. \] Prove that, if \(z_1,z_2,\ldots,z_n\) is any permutation of \(y_1,y_2,\ldots,y_n\), then \[ \sum_{i=1}^{n}(x_i-y_i)^2 \le \sum_{i=1}^{n}(x_i-z_i)^2. \]
Official text of the problem. Official problem paper (PDF)
Solution
We prove the assertion by induction on \(n\). For \(n=1\), we have \(z_1=y_1\), so equality holds.
Suppose \(n\ge2\) and the assertion holds for \(n-1\). Choose an index \(j\) such that \(z_j=y_1\), and obtain \(w_1,\ldots,w_n\) by exchanging \(z_1\) and \(z_j\). Thus \(w_1=y_1\).
This exchange cannot increase the sum of squared differences. Indeed, if \(j=1\), nothing changes. Otherwise, \[ \begin{aligned} &\sum_{i=1}^{n}(x_i-z_i)^2 -\sum_{i=1}^{n}(x_i-w_i)^2\\ &\quad=(x_1-z_1)^2+(x_j-y_1)^2 -(x_1-y_1)^2-(x_j-z_1)^2\\ &\quad=2(x_1-x_j)(y_1-z_1)\ge0, \end{aligned} \] because \(x_1\ge x_j\) and \(y_1\) is the largest of the values being permuted.
After removing the first entry \(w_1=y_1\), the remaining entries \(w_2,\ldots,w_n\) form a permutation of \(y_2,\ldots,y_n\), including their multiplicities. The induction hypothesis therefore gives \[ \sum_{i=2}^{n}(x_i-w_i)^2 \ge \sum_{i=2}^{n}(x_i-y_i)^2. \] Consequently, \[ \begin{aligned} \sum_{i=1}^{n}(x_i-z_i)^2 &\ge \sum_{i=1}^{n}(x_i-w_i)^2\\ &=(x_1-y_1)^2+\sum_{i=2}^{n}(x_i-w_i)^2\\ &\ge \sum_{i=1}^{n}(x_i-y_i)^2. \end{aligned} \] This completes the induction. \(\square\)
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1975 · Aufgabe 1
Es seien \(x_i,y_i\) \((i=1,2,\ldots,n)\) reelle Zahlen mit \[ x_1\ge x_2\ge\cdots\ge x_n \quad\text{und}\quad y_1\ge y_2\ge\cdots\ge y_n. \] Man beweise, dass für jede Permutation \(z_1,z_2,\ldots,z_n\) von \(y_1,y_2,\ldots,y_n\) gilt: \[ \sum_{i=1}^{n}(x_i-y_i)^2 \le \sum_{i=1}^{n}(x_i-z_i)^2. \]
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Wir beweisen die Behauptung durch vollständige Induktion über \(n\). Für \(n=1\) gilt \(z_1=y_1\), also gilt Gleichheit.
Es sei nun \(n\ge2\), und die Behauptung gelte für \(n-1\). Wir wählen einen Index \(j\) mit \(z_j=y_1\) und erhalten \(w_1,\ldots,w_n\), indem wir \(z_1\) und \(z_j\) vertauschen. Somit ist \(w_1=y_1\).
Durch diese Vertauschung kann die Summe der quadrierten Differenzen nicht größer werden. Ist nämlich \(j=1\), so ändert sich nichts. Andernfalls gilt \[ \begin{aligned} &\sum_{i=1}^{n}(x_i-z_i)^2 -\sum_{i=1}^{n}(x_i-w_i)^2\\ &\quad=(x_1-z_1)^2+(x_j-y_1)^2 -(x_1-y_1)^2-(x_j-z_1)^2\\ &\quad=2(x_1-x_j)(y_1-z_1)\ge0, \end{aligned} \] denn \(x_1\ge x_j\), und \(y_1\) ist der größte der permutierten Werte.
Nach dem Entfernen des ersten Gliedes \(w_1=y_1\) bilden die verbleibenden Glieder \(w_2,\ldots,w_n\) eine Permutation von \(y_2,\ldots,y_n\), wobei auch die Vielfachheiten berücksichtigt werden. Nach der Induktionsvoraussetzung gilt daher \[ \sum_{i=2}^{n}(x_i-w_i)^2 \ge \sum_{i=2}^{n}(x_i-y_i)^2. \] Folglich ist \[ \begin{aligned} \sum_{i=1}^{n}(x_i-z_i)^2 &\ge \sum_{i=1}^{n}(x_i-w_i)^2\\ &=(x_1-y_1)^2+\sum_{i=2}^{n}(x_i-w_i)^2\\ &\ge \sum_{i=1}^{n}(x_i-y_i)^2. \end{aligned} \] Damit ist die Induktion abgeschlossen. \(\square\)
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1975 · Soru 1
\(x_i,y_i\) \((i=1,2,\ldots,n)\), \[ x_1\ge x_2\ge\cdots\ge x_n \quad\text{ve}\quad y_1\ge y_2\ge\cdots\ge y_n \] koşullarını sağlayan gerçel sayılar olsun. \(z_1,z_2,\ldots,z_n\), \(y_1,y_2,\ldots,y_n\) sayılarının herhangi bir permütasyonu ise \[ \sum_{i=1}^{n}(x_i-y_i)^2 \le \sum_{i=1}^{n}(x_i-z_i)^2 \] olduğunu kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
İddiayı \(n\) üzerinden tümevarımla kanıtlayacağız. \(n=1\) için \(z_1=y_1\) olduğundan eşitlik sağlanır.
\(n\ge2\) olduğunu ve iddianın \(n-1\) için doğru olduğunu varsayalım. \(z_j=y_1\) olacak şekilde bir \(j\) indisi seçelim ve \(z_1\) ile \(z_j\)'nin yerlerini değiştirerek \(w_1,\ldots,w_n\) sayıları elde edelim. Böylece \(w_1=y_1\) olur.
Bu yer değiştirme, farkların kareleri toplamını artıramaz. Gerçekten de \(j=1\) ise hiçbir şey değişmez. Aksi hâlde, \[ \begin{aligned} &\sum_{i=1}^{n}(x_i-z_i)^2 -\sum_{i=1}^{n}(x_i-w_i)^2\\ &\quad=(x_1-z_1)^2+(x_j-y_1)^2 -(x_1-y_1)^2-(x_j-z_1)^2\\ &\quad=2(x_1-x_j)(y_1-z_1)\ge0 \end{aligned} \] çünkü \(x_1\ge x_j\) ve \(y_1\), permütasyonu alınan değerlerin en büyüğüdür.
İlk terim olan \(w_1=y_1\) çıkarıldığında, geriye kalan \(w_2,\ldots,w_n\) terimleri, tekrar sayıları da korunmak üzere \(y_2,\ldots,y_n\) sayılarının bir permütasyonunu oluşturur. Dolayısıyla tümevarım varsayımından \[ \sum_{i=2}^{n}(x_i-w_i)^2 \ge \sum_{i=2}^{n}(x_i-y_i)^2 \] elde edilir. Sonuç olarak, \[ \begin{aligned} \sum_{i=1}^{n}(x_i-z_i)^2 &\ge \sum_{i=1}^{n}(x_i-w_i)^2\\ &=(x_1-y_1)^2+\sum_{i=2}^{n}(x_i-w_i)^2\\ &\ge \sum_{i=1}^{n}(x_i-y_i)^2. \end{aligned} \] Böylece tümevarım tamamlanır. \(\square\)
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1975 · Problema 1
Sean \(x_i,y_i\) \((i=1,2,\ldots,n)\) números reales tales que \[ x_1\ge x_2\ge\cdots\ge x_n \quad\text{y}\quad y_1\ge y_2\ge\cdots\ge y_n. \] Demostrar que, si \(z_1,z_2,\ldots,z_n\) es cualquier permutación de \(y_1,y_2,\ldots,y_n\), entonces \[ \sum_{i=1}^{n}(x_i-y_i)^2 \le \sum_{i=1}^{n}(x_i-z_i)^2. \]
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Demostramos la afirmación por inducción sobre \(n\). Para \(n=1\), tenemos \(z_1=y_1\), por lo que se cumple la igualdad.
Supongamos que \(n\ge2\) y que la afirmación se cumple para \(n-1\). Elegimos un índice \(j\) tal que \(z_j=y_1\), y obtenemos \(w_1,\ldots,w_n\) intercambiando \(z_1\) y \(z_j\). Así, \(w_1=y_1\).
Este intercambio no puede aumentar la suma de los cuadrados de las diferencias. En efecto, si \(j=1\), nada cambia. En caso contrario, \[ \begin{aligned} &\sum_{i=1}^{n}(x_i-z_i)^2 -\sum_{i=1}^{n}(x_i-w_i)^2\\ &\quad=(x_1-z_1)^2+(x_j-y_1)^2 -(x_1-y_1)^2-(x_j-z_1)^2\\ &\quad=2(x_1-x_j)(y_1-z_1)\ge0, \end{aligned} \] porque \(x_1\ge x_j\) y \(y_1\) es el mayor de los valores que se permutan.
Al eliminar el primer término \(w_1=y_1\), los términos restantes \(w_2,\ldots,w_n\) forman una permutación de \(y_2,\ldots,y_n\), contando sus multiplicidades. Por tanto, la hipótesis de inducción da \[ \sum_{i=2}^{n}(x_i-w_i)^2 \ge \sum_{i=2}^{n}(x_i-y_i)^2. \] En consecuencia, \[ \begin{aligned} \sum_{i=1}^{n}(x_i-z_i)^2 &\ge \sum_{i=1}^{n}(x_i-w_i)^2\\ &=(x_1-y_1)^2+\sum_{i=2}^{n}(x_i-w_i)^2\\ &\ge \sum_{i=1}^{n}(x_i-y_i)^2. \end{aligned} \] Esto completa la inducción. \(\square\)
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1975 · 问题 1
设实数 \(x_i,y_i\) \((i=1,2,\ldots,n)\) 满足 \[ x_1\ge x_2\ge\cdots\ge x_n \quad\text{且}\quad y_1\ge y_2\ge\cdots\ge y_n. \] 证明：若 \(z_1,z_2,\ldots,z_n\) 是 \(y_1,y_2,\ldots,y_n\) 的任意一个排列，则 \[ \sum_{i=1}^{n}(x_i-y_i)^2 \le \sum_{i=1}^{n}(x_i-z_i)^2. \]
题目译自官方英文原文。 官方试卷 (PDF)
解答
我们对 \(n\) 用数学归纳法证明此命题。当 \(n=1\) 时，有 \(z_1=y_1\)，因此等号成立。
设 \(n\ge2\)，并假设命题对 \(n-1\) 成立。选取一个下标 \(j\)，使得 \(z_j=y_1\)，交换 \(z_1\) 与 \(z_j\)，得到 \(w_1,\ldots,w_n\)。于是 \(w_1=y_1\)。
这次交换不会使差的平方和增大。事实上，若 \(j=1\)，则没有任何变化。否则， \[ \begin{aligned} &\sum_{i=1}^{n}(x_i-z_i)^2 -\sum_{i=1}^{n}(x_i-w_i)^2\\ &\quad=(x_1-z_1)^2+(x_j-y_1)^2 -(x_1-y_1)^2-(x_j-z_1)^2\\ &\quad=2(x_1-x_j)(y_1-z_1)\ge0, \end{aligned} \] 因为 \(x_1\ge x_j\)，且 \(y_1\) 是参与排列的各数中的最大值。
去掉第一项 \(w_1=y_1\) 后，其余各项 \(w_2,\ldots,w_n\) 构成 \(y_2,\ldots,y_n\) 的一个排列，其中各数出现的次数也保持不变。因此，由归纳假设可得 \[ \sum_{i=2}^{n}(x_i-w_i)^2 \ge \sum_{i=2}^{n}(x_i-y_i)^2. \] 从而， \[ \begin{aligned} \sum_{i=1}^{n}(x_i-z_i)^2 &\ge \sum_{i=1}^{n}(x_i-w_i)^2\\ &=(x_1-y_1)^2+\sum_{i=2}^{n}(x_i-w_i)^2\\ &\ge \sum_{i=1}^{n}(x_i-y_i)^2. \end{aligned} \] 归纳证明完成。\(\square\)
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1975 · Задача 1
Пусть \(x_i,y_i\) \((i=1,2,\ldots,n)\) — действительные числа, такие что \[ x_1\ge x_2\ge\cdots\ge x_n \quad\text{и}\quad y_1\ge y_2\ge\cdots\ge y_n. \] Докажите, что если \(z_1,z_2,\ldots,z_n\) — произвольная перестановка чисел \(y_1,y_2,\ldots,y_n\), то \[ \sum_{i=1}^{n}(x_i-y_i)^2 \le \sum_{i=1}^{n}(x_i-z_i)^2. \]
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Докажем утверждение индукцией по \(n\). При \(n=1\) имеем \(z_1=y_1\), поэтому достигается равенство.
Пусть \(n\ge2\) и утверждение верно для \(n-1\). Выберем индекс \(j\), для которого \(z_j=y_1\), и получим \(w_1,\ldots,w_n\), поменяв местами \(z_1\) и \(z_j\). Таким образом, \(w_1=y_1\).
Такая перестановка не может увеличить сумму квадратов разностей. Действительно, если \(j=1\), ничего не меняется. В противном случае \[ \begin{aligned} &\sum_{i=1}^{n}(x_i-z_i)^2 -\sum_{i=1}^{n}(x_i-w_i)^2\\ &\quad=(x_1-z_1)^2+(x_j-y_1)^2 -(x_1-y_1)^2-(x_j-z_1)^2\\ &\quad=2(x_1-x_j)(y_1-z_1)\ge0, \end{aligned} \] поскольку \(x_1\ge x_j\), а \(y_1\) — наибольшее из переставляемых чисел.
После удаления первого члена \(w_1=y_1\) оставшиеся члены \(w_2,\ldots,w_n\) образуют перестановку чисел \(y_2,\ldots,y_n\) с учётом их кратностей. Поэтому по предположению индукции \[ \sum_{i=2}^{n}(x_i-w_i)^2 \ge \sum_{i=2}^{n}(x_i-y_i)^2. \] Следовательно, \[ \begin{aligned} \sum_{i=1}^{n}(x_i-z_i)^2 &\ge \sum_{i=1}^{n}(x_i-w_i)^2\\ &=(x_1-y_1)^2+\sum_{i=2}^{n}(x_i-w_i)^2\\ &\ge \sum_{i=1}^{n}(x_i-y_i)^2. \end{aligned} \] Индукционный переход завершён. \(\square\)
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1975 · المسألة 1
لتكن \(x_i,y_i\) \((i=1,2,\ldots,n)\) أعدادًا حقيقية بحيث \[ x_1\ge x_2\ge\cdots\ge x_n \quad\text{و}\quad y_1\ge y_2\ge\cdots\ge y_n. \] أثبت أنه إذا كانت \(z_1,z_2,\ldots,z_n\) تبديلًا كيفما كان للأعداد \(y_1,y_2,\ldots,y_n\)، فإن \[ \sum_{i=1}^{n}(x_i-y_i)^2 \le \sum_{i=1}^{n}(x_i-z_i)^2. \]
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
نثبت المطلوب بالاستقراء على \(n\). عندما \(n=1\)، يكون لدينا \(z_1=y_1\)، فتتحقق المساواة.
لنفترض أن \(n\ge2\) وأن المطلوب صحيح من أجل \(n-1\). نختار دليلًا \(j\) بحيث \(z_j=y_1\)، ونحصل على \(w_1,\ldots,w_n\) بتبادل \(z_1\) و\(z_j\). وعليه فإن \(w_1=y_1\).
لا يمكن لهذا التبادل أن يزيد مجموع مربعات الفروق. بالفعل، إذا كان \(j=1\)، فلا يتغير شيء. وإلا فإن \[ \begin{aligned} &\sum_{i=1}^{n}(x_i-z_i)^2 -\sum_{i=1}^{n}(x_i-w_i)^2\\ &\quad=(x_1-z_1)^2+(x_j-y_1)^2 -(x_1-y_1)^2-(x_j-z_1)^2\\ &\quad=2(x_1-x_j)(y_1-z_1)\ge0, \end{aligned} \] لأن \(x_1\ge x_j\) ولأن \(y_1\) أكبر القيم التي يجري تبديلها.
بعد حذف الحد الأول \(w_1=y_1\)، تشكل الحدود المتبقية \(w_2,\ldots,w_n\) تبديلًا للأعداد \(y_2,\ldots,y_n\)، مع مراعاة عدد مرات تكرار كل منها. ومن ثم تعطينا فرضية الاستقراء \[ \sum_{i=2}^{n}(x_i-w_i)^2 \ge \sum_{i=2}^{n}(x_i-y_i)^2. \] وبالتالي، \[ \begin{aligned} \sum_{i=1}^{n}(x_i-z_i)^2 &\ge \sum_{i=1}^{n}(x_i-w_i)^2\\ &=(x_1-y_1)^2+\sum_{i=2}^{n}(x_i-w_i)^2\\ &\ge \sum_{i=1}^{n}(x_i-y_i)^2. \end{aligned} \] وبذلك يكتمل الاستقراء. \(\square\)
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).