IMO 2001 · Problem 4
Let \(n\) be an odd integer greater than 1, and let \(k_1,k_2,\ldots,k_n\) be given integers. For each of the \(n!\) permutations \(a=(a_1,a_2,\ldots,a_n)\) of \(1,2,\ldots,n\), let \[ S(a)=\sum_{i=1}^{n}k_i a_i. \] Prove that there are two permutations \(b\) and \(c\), \(b\ne c\), such that \(n!\) is a divisor of \(S(b)-S(c)\).
Official text of the problem. Official problem paper (PDF)
Solution
Write \(N=n!\), and let \(\mathcal P\) be the set of all permutations of \(1,2,\ldots,n\).
Suppose, for a contradiction, that no two distinct permutations have the same value of \(S\) modulo \(N\). There are exactly \(N\) permutations and \(N\) residue classes modulo \(N\), so their values represent every residue class exactly once. Consequently, \[ \sum_{a\in\mathcal P}S(a) \equiv 0+1+\cdots+(N-1) =\frac{N(N-1)}2 \pmod N. \] Since \(n>1\), the integer \(N\) is even. Thus \[ \frac{N(N-1)}2 =N\left(\frac N2-1\right)+\frac N2 \equiv\frac N2\not\equiv0\pmod N. \]
On the other hand, for each fixed position \(i\), every number \(j\in\{1,\ldots,n\}\) occurs as \(a_i\) in exactly \((n-1)!\) permutations, because the remaining entries can be arranged arbitrarily. Hence \[ \begin{aligned} \sum_{a\in\mathcal P}S(a) &=\sum_{i=1}^{n}k_i\sum_{a\in\mathcal P}a_i\\ &=\sum_{i=1}^{n}k_i\,(n-1)!\,\frac{n(n+1)}2\\ &=N\,\frac{n+1}{2}\sum_{i=1}^{n}k_i. \end{aligned} \] Because \(n\) is odd, \((n+1)/2\) is an integer, so this sum is divisible by \(N\), a contradiction.
Therefore two distinct permutations \(b,c\) satisfy \(S(b)\equiv S(c)\pmod{n!}\), as required. \(\square\)
The solution was checked against Evan Chen's published IMO solution notes.
IMO 2001 · Aufgabe 4
Sei \(n\) eine ungerade ganze Zahl größer als 1, und seien \(k_1,k_2,\ldots,k_n\) gegebene ganze Zahlen. Für jede der \(n!\) Permutationen \(a=(a_1,a_2,\ldots,a_n)\) von \(1,2,\ldots,n\) sei \[ S(a)=\sum_{i=1}^{n}k_i a_i. \] Man beweise, dass es zwei Permutationen \(b\) und \(c\), \(b\ne c\), gibt, sodass \(n!\) ein Teiler von \(S(b)-S(c)\) ist.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Wir schreiben \(N=n!\) und bezeichnen mit \(\mathcal P\) die Menge aller Permutationen von \(1,2,\ldots,n\).
Wir nehmen zum Widerspruch an, dass keine zwei verschiedenen Permutationen denselben Wert von \(S\) modulo \(N\) haben. Es gibt genau \(N\) Permutationen und \(N\) Restklassen modulo \(N\), also repräsentieren ihre Werte jede Restklasse genau einmal. Folglich gilt \[ \sum_{a\in\mathcal P}S(a) \equiv 0+1+\cdots+(N-1) =\frac{N(N-1)}2 \pmod N. \] Wegen \(n>1\) ist die ganze Zahl \(N\) gerade. Somit gilt \[ \frac{N(N-1)}2 =N\left(\frac N2-1\right)+\frac N2 \equiv\frac N2\not\equiv0\pmod N. \]
Andererseits tritt an jeder festen Position \(i\) jede Zahl \(j\in\{1,\ldots,n\}\) in genau \((n-1)!\) Permutationen als \(a_i\) auf, da die übrigen Einträge beliebig angeordnet werden können. Daher gilt \[ \begin{aligned} \sum_{a\in\mathcal P}S(a) &=\sum_{i=1}^{n}k_i\sum_{a\in\mathcal P}a_i\\ &=\sum_{i=1}^{n}k_i\,(n-1)!\,\frac{n(n+1)}2\\ &=N\,\frac{n+1}{2}\sum_{i=1}^{n}k_i. \end{aligned} \] Da \(n\) ungerade ist, ist \((n+1)/2\) eine ganze Zahl, sodass diese Summe durch \(N\) teilbar ist, ein Widerspruch.
Also erfüllen zwei verschiedene Permutationen \(b,c\) die Kongruenz \(S(b)\equiv S(c)\pmod{n!}\), wie behauptet. \(\square\)
Die Lösung wurde mit den veröffentlichten IMO-Lösungsnotizen von Evan Chen abgeglichen.
IMO 2001 · Soru 4
\(n\), 1'den büyük bir tek tam sayı ve \(k_1,k_2,\ldots,k_n\) verilmiş tam sayılar olsun. \(1,2,\ldots,n\) sayılarının \(n!\) tane \(a=(a_1,a_2,\ldots,a_n)\) permütasyonunun her biri için \[ S(a)=\sum_{i=1}^{n}k_i a_i \] olsun. \(n!\)'in \(S(b)-S(c)\)'yi böldüğü, \(b\ne c\) koşulunu sağlayan iki \(b\) ve \(c\) permütasyonu bulunduğunu kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
\(N=n!\) yazalım ve \(1,2,\ldots,n\) sayılarının tüm permütasyonlarının kümesini \(\mathcal P\) ile gösterelim.
Çelişki elde etmek amacıyla, herhangi iki farklı permütasyonun \(S\) değerlerinin mod \(N\)'ye göre aynı olmadığını varsayalım. Tam olarak \(N\) permütasyon ve mod \(N\)'ye göre \(N\) kalan sınıfı olduğundan, bu değerler her kalan sınıfını tam bir kez temsil eder. Dolayısıyla \[ \sum_{a\in\mathcal P}S(a) \equiv 0+1+\cdots+(N-1) =\frac{N(N-1)}2 \pmod N. \] \(n>1\) olduğundan \(N\) tam sayısı çifttir. Böylece \[ \frac{N(N-1)}2 =N\left(\frac N2-1\right)+\frac N2 \equiv\frac N2\not\equiv0\pmod N. \]
Öte yandan, sabit bir \(i\) konumu için her \(j\in\{1,\ldots,n\}\) sayısı, tam olarak \((n-1)!\) permütasyonda \(a_i\) olarak yer alır; çünkü kalan elemanlar istenen sırada dizilebilir. Buradan \[ \begin{aligned} \sum_{a\in\mathcal P}S(a) &=\sum_{i=1}^{n}k_i\sum_{a\in\mathcal P}a_i\\ &=\sum_{i=1}^{n}k_i\,(n-1)!\,\frac{n(n+1)}2\\ &=N\,\frac{n+1}{2}\sum_{i=1}^{n}k_i \end{aligned} \] elde edilir. \(n\) tek olduğundan \((n+1)/2\) bir tam sayıdır; dolayısıyla bu toplam \(N\)'ye bölünür ve bir çelişki elde edilir.
O hâlde iki farklı \(b,c\) permütasyonu, istendiği gibi \(S(b)\equiv S(c)\pmod{n!}\) koşulunu sağlar. \(\square\)
Çözüm, Evan Chen'in yayımlanmış IMO çözüm notlarıyla karşılaştırılarak kontrol edildi.
IMO 2001 · Problema 4
Sea \(n\) un entero impar mayor que 1, y sean \(k_1,k_2,\ldots,k_n\) enteros dados. Para cada una de las \(n!\) permutaciones \(a=(a_1,a_2,\ldots,a_n)\) de \(1,2,\ldots,n\), sea \[ S(a)=\sum_{i=1}^{n}k_i a_i. \] Demostrar que existen dos permutaciones \(b\) y \(c\), \(b\ne c\), tales que \(n!\) es un divisor de \(S(b)-S(c)\).
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Escribamos \(N=n!\), y sea \(\mathcal P\) el conjunto de todas las permutaciones de \(1,2,\ldots,n\).
Supongamos, por reducción al absurdo, que no hay dos permutaciones distintas con el mismo valor de \(S\) módulo \(N\). Hay exactamente \(N\) permutaciones y \(N\) clases de residuos módulo \(N\), por lo que sus valores representan cada clase de residuos exactamente una vez. En consecuencia, \[ \sum_{a\in\mathcal P}S(a) \equiv 0+1+\cdots+(N-1) =\frac{N(N-1)}2 \pmod N. \] Como \(n>1\), el entero \(N\) es par. Por tanto, \[ \frac{N(N-1)}2 =N\left(\frac N2-1\right)+\frac N2 \equiv\frac N2\not\equiv0\pmod N. \]
Por otra parte, para cada posición fija \(i\), cada número \(j\in\{1,\ldots,n\}\) aparece como \(a_i\) en exactamente \((n-1)!\) permutaciones, porque los elementos restantes pueden ordenarse arbitrariamente. Así pues, \[ \begin{aligned} \sum_{a\in\mathcal P}S(a) &=\sum_{i=1}^{n}k_i\sum_{a\in\mathcal P}a_i\\ &=\sum_{i=1}^{n}k_i\,(n-1)!\,\frac{n(n+1)}2\\ &=N\,\frac{n+1}{2}\sum_{i=1}^{n}k_i. \end{aligned} \] Como \(n\) es impar, \((n+1)/2\) es un entero, de modo que esta suma es divisible por \(N\), una contradicción.
Por tanto, dos permutaciones distintas \(b,c\) satisfacen \(S(b)\equiv S(c)\pmod{n!}\), como se quería demostrar. \(\square\)
La solución se comprobó con las notas de soluciones de la IMO publicadas por Evan Chen.
IMO 2001 · 问题 4
设 \(n\) 为大于 1 的奇数，\(k_1,k_2,\ldots,k_n\) 为给定的整数。对于 \(1,2,\ldots,n\) 的 \(n!\) 个排列 \(a=(a_1,a_2,\ldots,a_n)\) 中的每一个，令 \[ S(a)=\sum_{i=1}^{n}k_i a_i. \] 证明：存在两个排列 \(b\) 和 \(c\)，\(b\ne c\)，使得 \(n!\) 整除 \(S(b)-S(c)\)。
题目译自官方英文原文。 官方试卷 (PDF)
解答
记 \(N=n!\)，并设 \(\mathcal P\) 为 \(1,2,\ldots,n\) 的所有排列组成的集合。
用反证法，假设任意两个不同排列的 \(S\) 值模 \(N\) 均不同余。排列恰有 \(N\) 个，而模 \(N\) 的剩余类也有 \(N\) 个，因此这些值在每个剩余类中恰好出现一次。所以， \[ \sum_{a\in\mathcal P}S(a) \equiv 0+1+\cdots+(N-1) =\frac{N(N-1)}2 \pmod N. \] 由于 \(n>1\)，整数 \(N\) 为偶数。于是 \[ \frac{N(N-1)}2 =N\left(\frac N2-1\right)+\frac N2 \equiv\frac N2\not\equiv0\pmod N. \]
另一方面，对每个固定的位置 \(i\)，每个数 \(j\in\{1,\ldots,n\}\) 都恰好在 \((n-1)!\) 个排列中作为 \(a_i\) 出现，因为其余各项可以任意排列。因此 \[ \begin{aligned} \sum_{a\in\mathcal P}S(a) &=\sum_{i=1}^{n}k_i\sum_{a\in\mathcal P}a_i\\ &=\sum_{i=1}^{n}k_i\,(n-1)!\,\frac{n(n+1)}2\\ &=N\,\frac{n+1}{2}\sum_{i=1}^{n}k_i. \end{aligned} \] 由于 \(n\) 为奇数，\((n+1)/2\) 为整数，所以这个和能被 \(N\) 整除，矛盾。
因此，存在两个不同的排列 \(b,c\)，满足 \(S(b)\equiv S(c)\pmod{n!}\)，命题得证。\(\square\)
解答已与 Evan Chen 发布的 IMO 解答笔记核对。
IMO 2001 · Задача 4
Пусть \(n\) — нечётное целое число, большее 1, а \(k_1,k_2,\ldots,k_n\) — заданные целые числа. Для каждой из \(n!\) перестановок \(a=(a_1,a_2,\ldots,a_n)\) чисел \(1,2,\ldots,n\) положим \[ S(a)=\sum_{i=1}^{n}k_i a_i. \] Докажите, что существуют две перестановки \(b\) и \(c\), \(b\ne c\), для которых \(n!\) является делителем \(S(b)-S(c)\).
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Обозначим \(N=n!\), а через \(\mathcal P\) — множество всех перестановок чисел \(1,2,\ldots,n\).
Предположим противное: никакие две различные перестановки не имеют одинаковых значений \(S\) по модулю \(N\). Всего имеется ровно \(N\) перестановок и \(N\) классов вычетов по модулю \(N\), поэтому их значения представляют каждый класс вычетов ровно один раз. Следовательно, \[ \sum_{a\in\mathcal P}S(a) \equiv 0+1+\cdots+(N-1) =\frac{N(N-1)}2 \pmod N. \] Поскольку \(n>1\), целое число \(N\) чётно. Поэтому \[ \frac{N(N-1)}2 =N\left(\frac N2-1\right)+\frac N2 \equiv\frac N2\not\equiv0\pmod N. \]
С другой стороны, на каждой фиксированной позиции \(i\) каждое число \(j\in\{1,\ldots,n\}\) встречается в качестве \(a_i\) ровно в \((n-1)!\) перестановках, поскольку остальные элементы можно расположить произвольным образом. Следовательно, \[ \begin{aligned} \sum_{a\in\mathcal P}S(a) &=\sum_{i=1}^{n}k_i\sum_{a\in\mathcal P}a_i\\ &=\sum_{i=1}^{n}k_i\,(n-1)!\,\frac{n(n+1)}2\\ &=N\,\frac{n+1}{2}\sum_{i=1}^{n}k_i. \end{aligned} \] Поскольку \(n\) нечётно, \((n+1)/2\) — целое число, поэтому эта сумма делится на \(N\), что даёт противоречие.
Следовательно, существуют две различные перестановки \(b,c\), для которых \(S(b)\equiv S(c)\pmod{n!}\), что и требовалось доказать. \(\square\)
Решение проверено по опубликованным заметкам Эвана Чена с решениями IMO.
IMO 2001 · المسألة 4
ليكن \(n\) عددًا صحيحًا فرديًا أكبر من 1، ولتكن \(k_1,k_2,\ldots,k_n\) أعدادًا صحيحة معطاة. لكل تبديل \(a=(a_1,a_2,\ldots,a_n)\) من تبديلات \(1,2,\ldots,n\) البالغ عددها \(n!\)، نضع \[ S(a)=\sum_{i=1}^{n}k_i a_i. \] أثبت وجود تبديلين \(b\) و\(c\)، حيث \(b\ne c\)، بحيث يكون \(n!\) قاسمًا لـ \(S(b)-S(c)\).
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
لنكتب \(N=n!\)، ولتكن \(\mathcal P\) مجموعة جميع تبديلات \(1,2,\ldots,n\).
لنفترض، طلبًا للتناقض، أنه لا يوجد تبديلان مختلفان لهما القيمة نفسها لـ \(S\) بترديد \(N\). يوجد بالضبط \(N\) تبديلًا و\(N\) فئة بواقٍ بترديد \(N\)، لذا تمثل قيمها كل فئة بواقٍ مرة واحدة بالضبط. وعليه، \[ \sum_{a\in\mathcal P}S(a) \equiv 0+1+\cdots+(N-1) =\frac{N(N-1)}2 \pmod N. \] وبما أن \(n>1\)، فإن العدد الصحيح \(N\) زوجي. ومن ثم \[ \frac{N(N-1)}2 =N\left(\frac N2-1\right)+\frac N2 \equiv\frac N2\not\equiv0\pmod N. \]
ومن جهة أخرى، لكل موضع ثابت \(i\)، يظهر كل عدد \(j\in\{1,\ldots,n\}\) بوصفه \(a_i\) في \((n-1)!\) تبديلًا بالضبط، لأن العناصر المتبقية يمكن ترتيبها كيفما نشاء. ومن ثم \[ \begin{aligned} \sum_{a\in\mathcal P}S(a) &=\sum_{i=1}^{n}k_i\sum_{a\in\mathcal P}a_i\\ &=\sum_{i=1}^{n}k_i\,(n-1)!\,\frac{n(n+1)}2\\ &=N\,\frac{n+1}{2}\sum_{i=1}^{n}k_i. \end{aligned} \] وبما أن \(n\) فردي، فإن \((n+1)/2\) عدد صحيح، لذا فإن هذا المجموع يقبل القسمة على \(N\)، وهو تناقض.
إذن يوجد تبديلان مختلفان \(b,c\) يحققان \(S(b)\equiv S(c)\pmod{n!}\)، وهو المطلوب. \(\square\)
تمت مراجعة الحل بمقارنته بملاحظات حلول IMO المنشورة لإيفان تشين.