IMO 1987 · Problem 3
Let \(x_1,x_2,\ldots,x_n\) be real numbers satisfying \(x_1^2+x_2^2+\cdots+x_n^2=1\). Prove that for every integer \(k\geq2\) there are integers \(a_1,a_2,\ldots,a_n\), not all \(0\), such that \(|a_i|\leq k-1\) for all \(i\) and \[ |a_1x_1+a_1x_2+\cdots+a_nx_n| \leq \frac{(k-1)\sqrt n}{k^n-1}. \]
Official text of the problem. Official problem paper (PDF)
Solution
The supplied paper prints \(a_1x_2\) in the second term; we read this typographical error as \(a_2x_2\). Thus the linear form to be bounded is \(\sum_{i=1}^n a_ix_i\).
Fix an integer \(k\geq2\). Consider all \(N=k^n\) distinct integer tuples \[ (b_1,\ldots,b_n)\in\{0,1,\ldots,k-1\}^n, \] and associate to each tuple the real number \(\sum_{i=1}^n b_ix_i\). Order the tuples as \[ \mathbf b^{(1)},\mathbf b^{(2)},\ldots,\mathbf b^{(N)} \] so that their associated numbers satisfy \[ s_1\leq s_2\leq\cdots\leq s_N, \qquad s_j=\sum_{i=1}^n b_i^{(j)}x_i. \] Equal values are allowed; their tuples are still distinct.
Since every coordinate lies between \(0\) and \(k-1\), the triangle inequality and Cauchy–Schwarz give \[ \begin{aligned} s_N-s_1 &=\left|\sum_{i=1}^n \bigl(b_i^{(N)}-b_i^{(1)}\bigr)x_i\right|\\ &\leq (k-1)\sum_{i=1}^n |x_i|\\ &\leq (k-1)\sqrt{n\sum_{i=1}^n x_i^2}\\ &=(k-1)\sqrt n. \end{aligned} \] The \(N-1\) nonnegative consecutive gaps satisfy \[ \sum_{j=1}^{N-1}(s_{j+1}-s_j)=s_N-s_1. \] Consequently, at least one index \(j\) satisfies \[ s_{j+1}-s_j \leq \frac{s_N-s_1}{N-1} \leq \frac{(k-1)\sqrt n}{k^n-1}. \]
For this index, set \[ a_i=b_i^{(j+1)}-b_i^{(j)} \qquad(1\leq i\leq n). \] These are integers with \(|a_i|\leq k-1\). They are not all zero because the two tuples are distinct. Finally, \[ \left|\sum_{i=1}^n a_ix_i\right| =|s_{j+1}-s_j| =s_{j+1}-s_j \leq\frac{(k-1)\sqrt n}{k^n-1}. \] This proves the assertion, including the cases of coincident sums and \(n=1\). \(\square\)
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1987 · Aufgabe 3
Seien \(x_1,x_2,\ldots,x_n\) reelle Zahlen mit \(x_1^2+x_2^2+\cdots+x_n^2=1\). Man beweise, dass es für jede ganze Zahl \(k\geq2\) ganze Zahlen \(a_1,a_2,\ldots,a_n\) gibt, die nicht alle \(0\) sind, sodass \(|a_i|\leq k-1\) für alle \(i\) gilt und \[ |a_1x_1+a_1x_2+\cdots+a_nx_n| \leq \frac{(k-1)\sqrt n}{k^n-1}. \]
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Auf dem vorliegenden Aufgabenblatt steht im zweiten Term \(a_1x_2\); wir berichtigen diesen Druckfehler zu \(a_2x_2\). Die abzuschätzende Linearform lautet also \(\sum_{i=1}^n a_ix_i\).
Sei eine ganze Zahl \(k\geq2\) fest gewählt. Wir betrachten alle \(N=k^n\) verschiedenen ganzzahligen Tupel \[ (b_1,\ldots,b_n)\in\{0,1,\ldots,k-1\}^n, \] und ordnen jedem Tupel die reelle Zahl \(\sum_{i=1}^n b_ix_i\) zu. Wir ordnen die Tupel in der Reihenfolge \[ \mathbf b^{(1)},\mathbf b^{(2)},\ldots,\mathbf b^{(N)} \] so an, dass für die zugehörigen Zahlen gilt: \[ s_1\leq s_2\leq\cdots\leq s_N, \qquad s_j=\sum_{i=1}^n b_i^{(j)}x_i. \] Gleiche Werte sind zulässig; die zugehörigen Tupel sind dennoch verschieden.
Da jede Koordinate zwischen \(0\) und \(k-1\) liegt, liefern die Dreiecksungleichung und die Cauchy-Schwarz-Ungleichung \[ \begin{aligned} s_N-s_1 &=\left|\sum_{i=1}^n \bigl(b_i^{(N)}-b_i^{(1)}\bigr)x_i\right|\\ &\leq (k-1)\sum_{i=1}^n |x_i|\\ &\leq (k-1)\sqrt{n\sum_{i=1}^n x_i^2}\\ &=(k-1)\sqrt n. \end{aligned} \] Für die \(N-1\) nichtnegativen Differenzen aufeinanderfolgender Werte gilt \[ \sum_{j=1}^{N-1}(s_{j+1}-s_j)=s_N-s_1. \] Folglich gibt es mindestens einen Index \(j\), für den \[ s_{j+1}-s_j \leq \frac{s_N-s_1}{N-1} \leq \frac{(k-1)\sqrt n}{k^n-1} \] gilt.
Für diesen Index setzen wir \[ a_i=b_i^{(j+1)}-b_i^{(j)} \qquad(1\leq i\leq n). \] Dies sind ganze Zahlen mit \(|a_i|\leq k-1\). Sie sind nicht alle null, da die beiden Tupel verschieden sind. Schließlich gilt \[ \left|\sum_{i=1}^n a_ix_i\right| =|s_{j+1}-s_j| =s_{j+1}-s_j \leq\frac{(k-1)\sqrt n}{k^n-1}. \] Damit ist die Behauptung bewiesen, einschließlich der Fälle übereinstimmender Summen und \(n=1\). \(\square\)
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1987 · Soru 3
\(x_1,x_2,\ldots,x_n\), \(x_1^2+x_2^2+\cdots+x_n^2=1\) eşitliğini sağlayan gerçel sayılar olsun. Her \(k\geq2\) tam sayısı için, hepsi birden \(0\) olmayan, her \(i\) için \(|a_i|\leq k-1\) koşulunu ve \[ |a_1x_1+a_1x_2+\cdots+a_nx_n| \leq \frac{(k-1)\sqrt n}{k^n-1} \] eşitsizliğini sağlayan \(a_1,a_2,\ldots,a_n\) tam sayılarının var olduğunu kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
Verilen sınav kâğıdında ikinci terim \(a_1x_2\) olarak basılmıştır; bu yazım hatasını \(a_2x_2\) olarak düzelterek okuyacağız. Dolayısıyla sınırlandırılacak doğrusal ifade \(\sum_{i=1}^n a_ix_i\)'dir.
Bir \(k\geq2\) tam sayısını sabitleyelim. Birbirinden farklı \(N=k^n\) tane \[ (b_1,\ldots,b_n)\in\{0,1,\ldots,k-1\}^n, \] tam sayı n'lisinin tümünü ele alalım ve her birine \(\sum_{i=1}^n b_ix_i\) gerçel sayısını karşılık getirelim. Bu n'lileri \[ \mathbf b^{(1)},\mathbf b^{(2)},\ldots,\mathbf b^{(N)} \] şeklinde, karşılık gelen sayılar \[ s_1\leq s_2\leq\cdots\leq s_N, \qquad s_j=\sum_{i=1}^n b_i^{(j)}x_i \] koşulunu sağlayacak biçimde sıralayalım. Değerler eşit olabilir; bunlara karşılık gelen n'liler yine de birbirinden farklıdır.
Her koordinat \(0\) ile \(k-1\) arasında olduğundan, üçgen eşitsizliği ve Cauchy–Schwarz eşitsizliği ile \[ \begin{aligned} s_N-s_1 &=\left|\sum_{i=1}^n \bigl(b_i^{(N)}-b_i^{(1)}\bigr)x_i\right|\\ &\leq (k-1)\sum_{i=1}^n |x_i|\\ &\leq (k-1)\sqrt{n\sum_{i=1}^n x_i^2}\\ &=(k-1)\sqrt n \end{aligned} \] elde edilir. Ardışık terimler arasındaki negatif olmayan \(N-1\) fark, \[ \sum_{j=1}^{N-1}(s_{j+1}-s_j)=s_N-s_1 \] eşitliğini sağlar. Bunun sonucunda, en az bir \(j\) indisi için \[ s_{j+1}-s_j \leq \frac{s_N-s_1}{N-1} \leq \frac{(k-1)\sqrt n}{k^n-1} \] olur.
Bu indis için, \[ a_i=b_i^{(j+1)}-b_i^{(j)} \qquad(1\leq i\leq n) \] olarak tanımlayalım. Bunlar \(|a_i|\leq k-1\) koşulunu sağlayan tam sayılardır. İki n'li birbirinden farklı olduğu için hepsi birden sıfır değildir. Son olarak, \[ \left|\sum_{i=1}^n a_ix_i\right| =|s_{j+1}-s_j| =s_{j+1}-s_j \leq\frac{(k-1)\sqrt n}{k^n-1}. \] Bu, toplamların eşit olduğu durumlar ve \(n=1\) durumu da dâhil olmak üzere iddiayı kanıtlar. \(\square\)
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1987 · Problema 3
Sean \(x_1,x_2,\ldots,x_n\) números reales que satisfacen \(x_1^2+x_2^2+\cdots+x_n^2=1\). Demostrar que para todo entero \(k\geq2\) existen enteros \(a_1,a_2,\ldots,a_n\), no todos iguales a \(0\), tales que \(|a_i|\leq k-1\) para todo \(i\) y \[ |a_1x_1+a_1x_2+\cdots+a_nx_n| \leq \frac{(k-1)\sqrt n}{k^n-1}. \]
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
En el documento proporcionado aparece \(a_1x_2\) en el segundo término; interpretamos esta errata como \(a_2x_2\). Por tanto, la forma lineal que hay que acotar es \(\sum_{i=1}^n a_ix_i\).
Fijemos un entero \(k\geq2\). Consideremos las \(N=k^n\) tuplas distintas de enteros \[ (b_1,\ldots,b_n)\in\{0,1,\ldots,k-1\}^n, \] y asociemos a cada tupla el número real \(\sum_{i=1}^n b_ix_i\). Ordenemos las tuplas como \[ \mathbf b^{(1)},\mathbf b^{(2)},\ldots,\mathbf b^{(N)} \] de modo que sus números asociados satisfagan \[ s_1\leq s_2\leq\cdots\leq s_N, \qquad s_j=\sum_{i=1}^n b_i^{(j)}x_i. \] Se permiten valores iguales; las tuplas correspondientes siguen siendo distintas.
Como cada coordenada está entre \(0\) y \(k-1\), la desigualdad triangular y la de Cauchy–Schwarz dan \[ \begin{aligned} s_N-s_1 &=\left|\sum_{i=1}^n \bigl(b_i^{(N)}-b_i^{(1)}\bigr)x_i\right|\\ &\leq (k-1)\sum_{i=1}^n |x_i|\\ &\leq (k-1)\sqrt{n\sum_{i=1}^n x_i^2}\\ &=(k-1)\sqrt n. \end{aligned} \] Las \(N-1\) diferencias no negativas entre términos consecutivos satisfacen \[ \sum_{j=1}^{N-1}(s_{j+1}-s_j)=s_N-s_1. \] En consecuencia, al menos un índice \(j\) satisface \[ s_{j+1}-s_j \leq \frac{s_N-s_1}{N-1} \leq \frac{(k-1)\sqrt n}{k^n-1}. \]
Para este índice, definamos \[ a_i=b_i^{(j+1)}-b_i^{(j)} \qquad(1\leq i\leq n). \] Estos son enteros con \(|a_i|\leq k-1\). No son todos cero porque las dos tuplas son distintas. Finalmente, \[ \left|\sum_{i=1}^n a_ix_i\right| =|s_{j+1}-s_j| =s_{j+1}-s_j \leq\frac{(k-1)\sqrt n}{k^n-1}. \] Esto demuestra la afirmación, incluidos los casos de sumas coincidentes y \(n=1\). \(\square\)
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1987 · 问题 3
设实数 \(x_1,x_2,\ldots,x_n\) 满足 \(x_1^2+x_2^2+\cdots+x_n^2=1\)。证明：对每个整数 \(k\geq2\)，都存在不全为 \(0\) 的整数 \(a_1,a_2,\ldots,a_n\)，使得对所有 \(i\) 都有 \(|a_i|\leq k-1\)，且 \[ |a_1x_1+a_1x_2+\cdots+a_nx_n| \leq \frac{(k-1)\sqrt n}{k^n-1}. \]
题目译自官方英文原文。 官方试卷 (PDF)
解答
所提供的试卷将第二项印成了 \(a_1x_2\)；我们将这一排印错误更正为 \(a_2x_2\)。因此，要估计的线性式为 \(\sum_{i=1}^n a_ix_i\)。
固定一个整数 \(k\geq2\)。考虑所有 \(N=k^n\) 个互不相同的整数元组 \[ (b_1,\ldots,b_n)\in\{0,1,\ldots,k-1\}^n, \] 并将每个元组与实数 \(\sum_{i=1}^n b_ix_i\) 对应。将这些元组排列为 \[ \mathbf b^{(1)},\mathbf b^{(2)},\ldots,\mathbf b^{(N)} \] 使其对应的数满足 \[ s_1\leq s_2\leq\cdots\leq s_N, \qquad s_j=\sum_{i=1}^n b_i^{(j)}x_i. \] 允许出现相等的值；它们对应的元组仍然互不相同。
由于每个坐标都介于 \(0\) 与 \(k-1\) 之间，由三角不等式和柯西–施瓦茨不等式得 \[ \begin{aligned} s_N-s_1 &=\left|\sum_{i=1}^n \bigl(b_i^{(N)}-b_i^{(1)}\bigr)x_i\right|\\ &\leq (k-1)\sum_{i=1}^n |x_i|\\ &\leq (k-1)\sqrt{n\sum_{i=1}^n x_i^2}\\ &=(k-1)\sqrt n. \end{aligned} \] 这 \(N-1\) 个非负的相邻差满足 \[ \sum_{j=1}^{N-1}(s_{j+1}-s_j)=s_N-s_1. \] 因此，至少有一个下标 \(j\) 满足 \[ s_{j+1}-s_j \leq \frac{s_N-s_1}{N-1} \leq \frac{(k-1)\sqrt n}{k^n-1}. \]
对这个下标，令 \[ a_i=b_i^{(j+1)}-b_i^{(j)} \qquad(1\leq i\leq n). \] 这些数都是整数，且满足 \(|a_i|\leq k-1\)。由于这两个元组不同，这些数不全为零。最后， \[ \left|\sum_{i=1}^n a_ix_i\right| =|s_{j+1}-s_j| =s_{j+1}-s_j \leq\frac{(k-1)\sqrt n}{k^n-1}. \] 这就证明了所述结论，其中也包括有些和相等以及 \(n=1\) 的情形。\(\square\)
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1987 · Задача 3
Пусть \(x_1,x_2,\ldots,x_n\) — действительные числа, удовлетворяющие условию \(x_1^2+x_2^2+\cdots+x_n^2=1\). Докажите, что для любого целого \(k\geq2\) существуют целые числа \(a_1,a_2,\ldots,a_n\), не все равные \(0\), такие, что \(|a_i|\leq k-1\) для всех \(i\) и \[ |a_1x_1+a_1x_2+\cdots+a_nx_n| \leq \frac{(k-1)\sqrt n}{k^n-1}. \]
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
В предоставленном тексте условий во втором слагаемом напечатано \(a_1x_2\); мы исправляем эту опечатку на \(a_2x_2\). Таким образом, линейная форма, которую нужно оценить, имеет вид \(\sum_{i=1}^n a_ix_i\).
Зафиксируем целое число \(k\geq2\). Рассмотрим все \(N=k^n\) различных наборов целых чисел \[ (b_1,\ldots,b_n)\in\{0,1,\ldots,k-1\}^n, \] и сопоставим каждому набору действительное число \(\sum_{i=1}^n b_ix_i\). Упорядочим наборы \[ \mathbf b^{(1)},\mathbf b^{(2)},\ldots,\mathbf b^{(N)} \] так, чтобы соответствующие им числа удовлетворяли условиям \[ s_1\leq s_2\leq\cdots\leq s_N, \qquad s_j=\sum_{i=1}^n b_i^{(j)}x_i. \] Значения могут совпадать; соответствующие им наборы при этом остаются различными.
Поскольку каждая координата лежит между \(0\) и \(k-1\), из неравенства треугольника и неравенства Коши — Буняковского получаем \[ \begin{aligned} s_N-s_1 &=\left|\sum_{i=1}^n \bigl(b_i^{(N)}-b_i^{(1)}\bigr)x_i\right|\\ &\leq (k-1)\sum_{i=1}^n |x_i|\\ &\leq (k-1)\sqrt{n\sum_{i=1}^n x_i^2}\\ &=(k-1)\sqrt n. \end{aligned} \] Для \(N-1\) неотрицательных разностей соседних членов выполняется равенство \[ \sum_{j=1}^{N-1}(s_{j+1}-s_j)=s_N-s_1. \] Следовательно, существует хотя бы один индекс \(j\), для которого \[ s_{j+1}-s_j \leq \frac{s_N-s_1}{N-1} \leq \frac{(k-1)\sqrt n}{k^n-1}. \]
Для этого индекса положим \[ a_i=b_i^{(j+1)}-b_i^{(j)} \qquad(1\leq i\leq n). \] Это целые числа, удовлетворяющие \(|a_i|\leq k-1\). Они не все равны нулю, поскольку два набора различны. Наконец, \[ \left|\sum_{i=1}^n a_ix_i\right| =|s_{j+1}-s_j| =s_{j+1}-s_j \leq\frac{(k-1)\sqrt n}{k^n-1}. \] Утверждение доказано, в том числе в случаях совпадающих сумм и \(n=1\). \(\square\)
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1987 · المسألة 3
لتكن \(x_1,x_2,\ldots,x_n\) أعدادًا حقيقية تحقق \(x_1^2+x_2^2+\cdots+x_n^2=1\). أثبت أنه لكل عدد صحيح \(k\geq2\) توجد أعداد صحيحة \(a_1,a_2,\ldots,a_n\)، ليست كلها \(0\)، بحيث \(|a_i|\leq k-1\) لكل \(i\)، و \[ |a_1x_1+a_1x_2+\cdots+a_nx_n| \leq \frac{(k-1)\sqrt n}{k^n-1}. \]
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
ورد في الورقة المقدمة \(a_1x_2\) في الحد الثاني؛ ونقرأ هذا الخطأ المطبعي على أنه \(a_2x_2\). ومن ثم فإن الصيغة الخطية المراد إيجاد حد لها هي \(\sum_{i=1}^n a_ix_i\).
لنثبت عددًا صحيحًا \(k\geq2\). ننظر في جميع الصفوف المرتبة المختلفة ذات المركبات الصحيحة، وعددها \(N=k^n\)، \[ (b_1,\ldots,b_n)\in\{0,1,\ldots,k-1\}^n, \] ونقرن بكل صف مرتب العدد الحقيقي \(\sum_{i=1}^n b_ix_i\). نرتب الصفوف على النحو \[ \mathbf b^{(1)},\mathbf b^{(2)},\ldots,\mathbf b^{(N)} \] بحيث تحقق الأعداد المقترنة بها \[ s_1\leq s_2\leq\cdots\leq s_N, \qquad s_j=\sum_{i=1}^n b_i^{(j)}x_i. \] يجوز أن تتساوى بعض القيم؛ وتظل الصفوف المقترنة بها مختلفة.
بما أن كل مركبة تقع بين \(0\) و\(k-1\)، فإن متباينة المثلث ومتباينة كوشي–شفارتز تعطيان \[ \begin{aligned} s_N-s_1 &=\left|\sum_{i=1}^n \bigl(b_i^{(N)}-b_i^{(1)}\bigr)x_i\right|\\ &\leq (k-1)\sum_{i=1}^n |x_i|\\ &\leq (k-1)\sqrt{n\sum_{i=1}^n x_i^2}\\ &=(k-1)\sqrt n. \end{aligned} \] الفروق المتتالية غير السالبة، وعددها \(N-1\)، تحقق \[ \sum_{j=1}^{N-1}(s_{j+1}-s_j)=s_N-s_1. \] وبالتالي، يوجد دليل واحد على الأقل \(j\) يحقق \[ s_{j+1}-s_j \leq \frac{s_N-s_1}{N-1} \leq \frac{(k-1)\sqrt n}{k^n-1}. \]
لهذا الدليل، نضع \[ a_i=b_i^{(j+1)}-b_i^{(j)} \qquad(1\leq i\leq n). \] هذه أعداد صحيحة تحقق \(|a_i|\leq k-1\). وليست كلها صفرًا لأن الصفين مختلفان. وأخيرًا، \[ \left|\sum_{i=1}^n a_ix_i\right| =|s_{j+1}-s_j| =s_{j+1}-s_j \leq\frac{(k-1)\sqrt n}{k^n-1}. \] وهذا يثبت المطلوب، بما في ذلك حالات تساوي المجاميع وحالة \(n=1\). \(\square\)
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).