IMO 2009 · Problem 1
Let \(n\) be a positive integer and let \(a_1,\ldots,a_k\) (\(k\ge 2\)) be distinct integers in the set \(\{1,\ldots,n\}\) such that \(n\) divides \(a_i(a_{i+1}-1)\) for \(i=1,\ldots,k-1\). Prove that \(n\) does not divide \(a_k(a_1-1)\).
Official text of the problem. Official problem paper (PDF)
Solution
Suppose, for a contradiction, that \(n\) also divides \(a_k(a_1-1)\). Extend the indices cyclically, so that \(a_{i+k}=a_i\). Then \[ a_i a_{i+1}\equiv a_i\pmod n \] for every \(i\).
Let \(P=a_1a_2\cdots a_k\). For each \(i\), we have \[ a_i \equiv a_i a_{i+1} \equiv a_i a_{i+1}a_{i+2} \equiv \cdots \equiv a_i a_{i+1}\cdots a_{i+k-1} =P \pmod n. \] Indeed, each step replaces the last factor \(a_j\) by \(a_j a_{j+1}\), which is congruent to it modulo \(n\). The final product contains each of \(a_1,\ldots,a_k\) exactly once.
Consequently, \(a_1\equiv a_2\pmod n\). But \(1\le a_1,a_2\le n\), so \(|a_1-a_2|<n\). Thus \(a_1=a_2\), contradicting their distinctness.
Therefore \(n\) does not divide \(a_k(a_1-1)\). \(\square\)
The solution was checked against the official IMO shortlist solutions.
IMO 2009 · Aufgabe 1
Es seien \(n\) und \(k\) positive ganze Zahlen mit \(k\ge 2\). Ferner seien \(a_1,\ldots,a_k\) paarweise verschiedene ganze Zahlen aus der Menge \(\{1,\ldots,n\}\) derart, dass \(n\) die Zahl \(a_i(a_{i+1}-1)\) für jedes \(i=1,\ldots,k-1\) teilt. Man zeige, dass dann \(n\) die Zahl \(a_k(a_1-1)\) nicht teilt.
Offizieller deutscher Aufgabentext. Offizielles Aufgabenblatt (PDF)
Lösung
Nehmen wir zum Widerspruch an, dass \(n\) auch \(a_k(a_1-1)\) teilt. Wir setzen die Indizes zyklisch fort, sodass \(a_{i+k}=a_i\) gilt. Dann gilt \[ a_i a_{i+1}\equiv a_i\pmod n \] für jedes \(i\).
Sei \(P=a_1a_2\cdots a_k\). Für jedes \(i\) gilt \[ a_i \equiv a_i a_{i+1} \equiv a_i a_{i+1}a_{i+2} \equiv \cdots \equiv a_i a_{i+1}\cdots a_{i+k-1} =P \pmod n. \] Tatsächlich wird in jedem Schritt der letzte Faktor \(a_j\) durch \(a_j a_{j+1}\) ersetzt, das zu ihm modulo \(n\) kongruent ist. Das letzte Produkt enthält jede der Zahlen \(a_1,\ldots,a_k\) genau einmal.
Folglich gilt \(a_1\equiv a_2\pmod n\). Wegen \(1\le a_1,a_2\le n\) ist jedoch \(|a_1-a_2|<n\). Also gilt \(a_1=a_2\), im Widerspruch dazu, dass die Zahlen verschieden sind.
Somit teilt \(n\) die Zahl \(a_k(a_1-1)\) nicht. \(\square\)
Die Lösung wurde mit den offiziellen Lösungen der IMO-Shortlist abgeglichen.
IMO 2009 · Soru 1
\(n\) pozitif bir tam sayı; \(a_1,\ldots,a_k\) (\(k\ge 2\)) de, \(\{1,\ldots,n\}\) kümesine ait olan ve, her \(i=1,\ldots,k-1\) için, \(n\) sayısının \(a_i(a_{i+1}-1)\) sayısını bölmesini sağlayan birbirinden farklı tam sayılar olsun. \(n\) sayısının \(a_k(a_1-1)\) sayısını bölmediğini kanıtlayınız.
Sorunun resmi Türkçe metni. Resmi soru kâğıdı (PDF)
Çözüm
Bir çelişki elde etmek üzere, \(n\) sayısının \(a_k(a_1-1)\) sayısını da böldüğünü varsayalım. İndisleri \(a_{i+k}=a_i\) olacak biçimde döngüsel olarak genişletelim. O hâlde her \(i\) için \[ a_i a_{i+1}\equiv a_i\pmod n \] olur.
\(P=a_1a_2\cdots a_k\) olsun. Her \(i\) için \[ a_i \equiv a_i a_{i+1} \equiv a_i a_{i+1}a_{i+2} \equiv \cdots \equiv a_i a_{i+1}\cdots a_{i+k-1} =P \pmod n. \] Gerçekten de her adımda son çarpan \(a_j\), modül \(n\)'de kendisine denk olan \(a_j a_{j+1}\) ile değiştirilir. Son çarpım, \(a_1,\ldots,a_k\) sayılarının her birini tam bir kez içerir.
Dolayısıyla \(a_1\equiv a_2\pmod n\) olur. Ancak \(1\le a_1,a_2\le n\) olduğundan \(|a_1-a_2|<n\) olur. Böylece \(a_1=a_2\) elde edilir; bu da bu sayıların farklı olmasıyla çelişir.
O hâlde \(n\) sayısı \(a_k(a_1-1)\) sayısını bölmez. \(\square\)
Çözüm, resmi IMO shortlist çözümleriyle karşılaştırılarak kontrol edildi.
IMO 2009 · Problema 1
Sea \(n\) un entero positivo y sean \(a_1,\ldots,a_k\) (\(k\ge 2\)) enteros distintos del conjunto \(\{1,\ldots,n\}\), tales que \(n\) divide a \(a_i(a_{i+1}-1)\), para \(i=1,\ldots,k-1\). Demostrar que \(n\) no divide a \(a_k(a_1-1)\).
Texto oficial en español del problema. Enunciado oficial (PDF)
Solución
Supongamos, por reducción al absurdo, que \(n\) también divide a \(a_k(a_1-1)\). Extendamos los índices cíclicamente, de modo que \(a_{i+k}=a_i\). Entonces \[ a_i a_{i+1}\equiv a_i\pmod n \] para todo \(i\).
Sea \(P=a_1a_2\cdots a_k\). Para cada \(i\), tenemos \[ a_i \equiv a_i a_{i+1} \equiv a_i a_{i+1}a_{i+2} \equiv \cdots \equiv a_i a_{i+1}\cdots a_{i+k-1} =P \pmod n. \] En efecto, en cada paso se sustituye el último factor \(a_j\) por \(a_j a_{j+1}\), que es congruente con él módulo \(n\). El producto final contiene cada uno de los números \(a_1,\ldots,a_k\) exactamente una vez.
Por consiguiente, \(a_1\equiv a_2\pmod n\). Pero \(1\le a_1,a_2\le n\), de modo que \(|a_1-a_2|<n\). Así pues, \(a_1=a_2\), lo que contradice que sean distintos.
Por lo tanto, \(n\) no divide a \(a_k(a_1-1)\). \(\square\)
La solución se comprobó con las soluciones oficiales de la shortlist de la IMO.
IMO 2009 · 问题 1
设 \(n\) 是一个正整数，\(a_1,a_2,\cdots,a_k\,(k\ge 2)\) 是集合 \(\{1,\cdots,n\}\) 中的互不相同的整数，使得对于 \(i=1,\cdots,k-1\)，都有 \(n\) 整除 \(a_i(a_{i+1}-1)\)．证明：\(n\) 不整除 \(a_k(a_1-1)\)．
题目为官方中文译本。 官方试卷 (PDF)
解答
用反证法，假设 \(n\) 也整除 \(a_k(a_1-1)\)。将下标按循环方式延拓，使得 \(a_{i+k}=a_i\)。于是，对每个 \(i\)，都有 \[ a_i a_{i+1}\equiv a_i\pmod n \] 成立。
令 \(P=a_1a_2\cdots a_k\)。对每个 \(i\)，有 \[ a_i \equiv a_i a_{i+1} \equiv a_i a_{i+1}a_{i+2} \equiv \cdots \equiv a_i a_{i+1}\cdots a_{i+k-1} =P \pmod n. \] 事实上，每一步都将最后一个因子 \(a_j\) 替换为与它模 \(n\) 同余的 \(a_j a_{j+1}\)。最后的乘积恰好包含 \(a_1,\ldots,a_k\) 中的每一个数各一次。
因此，\(a_1\equiv a_2\pmod n\)。但 \(1\le a_1,a_2\le n\)，所以 \(|a_1-a_2|<n\)。于是 \(a_1=a_2\)，这与它们互不相同矛盾。
所以 \(n\) 不整除 \(a_k(a_1-1)\)。\(\square\)
解答已与 IMO 官方预选题（shortlist）解答核对。
IMO 2009 · Задача 1
Даны целое положительное число \(n\) и попарно различные целые числа \(a_1,\ldots,a_k\) (\(k\ge 2\)) из множества \(\{1,\ldots,n\}\) такие, что для каждого \(i=1,\ldots,k-1\) число \(a_i(a_{i+1}-1)\) делится на \(n\). Докажите, что число \(a_k(a_1-1)\) не делится на \(n\).
Официальный русский текст задачи. Официальный текст задач (PDF)
Решение
Предположим противное: \(n\) делит также \(a_k(a_1-1)\). Продолжим индексы циклически, положив \(a_{i+k}=a_i\). Тогда \[ a_i a_{i+1}\equiv a_i\pmod n \] для каждого \(i\).
Пусть \(P=a_1a_2\cdots a_k\). Для каждого \(i\) имеем \[ a_i \equiv a_i a_{i+1} \equiv a_i a_{i+1}a_{i+2} \equiv \cdots \equiv a_i a_{i+1}\cdots a_{i+k-1} =P \pmod n. \] Действительно, на каждом шаге последний множитель \(a_j\) заменяется на \(a_j a_{j+1}\), сравнимый с ним по модулю \(n\). Последнее произведение содержит каждое из чисел \(a_1,\ldots,a_k\) ровно один раз.
Следовательно, \(a_1\equiv a_2\pmod n\). Но \(1\le a_1,a_2\le n\), поэтому \(|a_1-a_2|<n\). Значит, \(a_1=a_2\), что противоречит их различности.
Таким образом, \(n\) не делит \(a_k(a_1-1)\). \(\square\)
Решение проверено по официальным решениям шортлиста IMO.
IMO 2009 · المسألة 1
ليكن \(n\) عدداً صحيحاً موجباً و لتكن \(a_1,a_2,\ldots,a_k\) \((k\ge 2)\) أعداداً صحيحة مختلفة من المجموعة \(\{1,\ldots,n\}\) حيث أن \(n\) يقسم \(a_i(a_{i+1}-1)\) لكل \(i\) من \(\{1,\ldots,k-1\}\). برهن أن \(n\) لا يقسم \(a_k(a_1-1)\).
نص المسألة هو الترجمة العربية الرسمية. ورقة المسائل الرسمية (PDF)
الحل
لنفترض، وصولاً إلى تناقض، أن \(n\) يقسم أيضاً \(a_k(a_1-1)\). نمدّد الفهارس دورياً، بحيث \(a_{i+k}=a_i\). عندئذ \[ a_i a_{i+1}\equiv a_i\pmod n \] لكل \(i\).
لتكن \(P=a_1a_2\cdots a_k\). لكل \(i\)، لدينا \[ a_i \equiv a_i a_{i+1} \equiv a_i a_{i+1}a_{i+2} \equiv \cdots \equiv a_i a_{i+1}\cdots a_{i+k-1} =P \pmod n. \] ففي كل خطوة نستبدل العامل الأخير \(a_j\) بـ \(a_j a_{j+1}\)، وهو موافق له بترديد \(n\). ويحتوي الجداء الأخير على كل من \(a_1,\ldots,a_k\) مرة واحدة بالضبط.
وبالتالي، \(a_1\equiv a_2\pmod n\). لكن \(1\le a_1,a_2\le n\)، ومن ثم \(|a_1-a_2|<n\). إذن \(a_1=a_2\)، وهذا يناقض كونهما مختلفين.
وعليه، فإن \(n\) لا يقسم \(a_k(a_1-1)\). \(\square\)
تمت مراجعة الحل بمقارنته بالحلول الرسمية لقائمة IMO المختصرة.