IMO 1983 · Problem 5
Is it possible to choose 1983 distinct positive integers, all less than or equal to \(10^5\), no three of which are consecutive terms of an arithmetic progression? Justify your answer.
Official text of the problem. Official problem paper (PDF)
Answer
Yes.
Solution
Consider the set \[ S=\left\{\sum_{i=0}^{10}\varepsilon_i3^i: \varepsilon_i\in\{0,1\},\ \text{not all }\varepsilon_i=0\right\}. \] Uniqueness of base-three representation shows that these are \[ 2^{11}-1=2047 \] distinct positive integers. Every member is at most \[ 1+3+\cdots+3^{10} =\frac{3^{11}-1}{2} =88573<10^5. \]
We prove that \(S\) contains no three distinct consecutive terms of an arithmetic progression. Suppose that \(x,y,z\in S\) satisfy \[ x+z=2y. \] Write their base-three expansions as \[ x=\sum_{i=0}^{10}a_i3^i,\qquad y=\sum_{i=0}^{10}b_i3^i,\qquad z=\sum_{i=0}^{10}c_i3^i, \] where every digit belongs to \(\{0,1\}\). Then \[ \sum_{i=0}^{10}(a_i+c_i)3^i =\sum_{i=0}^{10}2b_i3^i. \] All coefficients on both sides belong to \(\{0,1,2\}\), so neither expression involves any carrying. Uniqueness of base-three representation therefore gives \[ a_i+c_i=2b_i\qquad(0\le i\le10). \] If \(b_i=0\), this forces \(a_i=c_i=0\); if \(b_i=1\), it forces \(a_i=c_i=1\). Thus \(a_i=b_i=c_i\) for every \(i\), and consequently \(x=y=z\).
Hence no three distinct members of \(S\) form an arithmetic progression. Choosing any \(1983\) of its \(2047\) members gives the required integers.
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1983 · Aufgabe 5
Ist es möglich, 1983 verschiedene positive ganze Zahlen zu wählen, die alle kleiner oder gleich \(10^5\) sind und von denen keine drei aufeinanderfolgende Glieder einer arithmetischen Folge sind? Begründe deine Antwort.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Antwort
Ja.
Lösung
Wir betrachten die Menge \[ S=\left\{\sum_{i=0}^{10}\varepsilon_i3^i: \varepsilon_i\in\{0,1\},\ \text{nicht alle }\varepsilon_i=0\right\}. \] Die Eindeutigkeit der Darstellung zur Basis drei zeigt, dass dies \[ 2^{11}-1=2047 \] verschiedene positive ganze Zahlen sind. Jedes Element ist höchstens \[ 1+3+\cdots+3^{10} =\frac{3^{11}-1}{2} =88573<10^5. \]
Wir beweisen, dass \(S\) keine drei verschiedenen aufeinanderfolgenden Glieder einer arithmetischen Folge enthält. Nehmen wir an, dass \(x,y,z\in S\) die Gleichung \[ x+z=2y \] erfüllen. Wir schreiben ihre Darstellungen zur Basis drei als \[ x=\sum_{i=0}^{10}a_i3^i,\qquad y=\sum_{i=0}^{10}b_i3^i,\qquad z=\sum_{i=0}^{10}c_i3^i, \] wobei jede Ziffer zu \(\{0,1\}\) gehört. Dann gilt \[ \sum_{i=0}^{10}(a_i+c_i)3^i =\sum_{i=0}^{10}2b_i3^i. \] Alle Koeffizienten auf beiden Seiten gehören zu \(\{0,1,2\}\), sodass in keinem der beiden Ausdrücke ein Übertrag auftritt. Aus der Eindeutigkeit der Darstellung zur Basis drei folgt daher \[ a_i+c_i=2b_i\qquad(0\le i\le10). \] Ist \(b_i=0\), so folgt zwingend \(a_i=c_i=0\); ist \(b_i=1\), so folgt zwingend \(a_i=c_i=1\). Somit gilt \(a_i=b_i=c_i\) für jedes \(i\), und folglich ist \(x=y=z\).
Also bilden keine drei verschiedenen Elemente von \(S\) eine arithmetische Folge. Wählen wir beliebige \(1983\) seiner \(2047\) Elemente, so erhalten wir die gesuchten ganzen Zahlen.
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1983 · Soru 5
Her biri \(10^5\)'ten küçük veya ona eşit olan ve hiçbir üçü bir aritmetik dizinin ardışık terimleri olmayan 1983 farklı pozitif tam sayı seçmek mümkün müdür? Cevabınızı gerekçelendiriniz.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Cevap
Evet.
Çözüm
Şu kümeyi ele alalım: \[ S=\left\{\sum_{i=0}^{10}\varepsilon_i3^i: \varepsilon_i\in\{0,1\},\ \text{tüm }\varepsilon_i=0\text{ değil}\right\}. \] Üç tabanındaki gösterimin tekliği, bunların \[ 2^{11}-1=2047 \] farklı pozitif tam sayı olduğunu gösterir. Her eleman için şu üst sınır geçerlidir: \[ 1+3+\cdots+3^{10} =\frac{3^{11}-1}{2} =88573<10^5. \]
\(S\)'nin bir aritmetik dizinin birbirinden farklı üç ardışık terimini içermediğini kanıtlayacağız. \(x,y,z\in S\) sayılarının \[ x+z=2y \] eşitliğini sağladığını varsayalım. Üç tabanındaki açılımlarını \[ x=\sum_{i=0}^{10}a_i3^i,\qquad y=\sum_{i=0}^{10}b_i3^i,\qquad z=\sum_{i=0}^{10}c_i3^i \] olarak yazalım; burada her basamak \(\{0,1\}\) kümesine aittir. O zaman \[ \sum_{i=0}^{10}(a_i+c_i)3^i =\sum_{i=0}^{10}2b_i3^i. \] Her iki taraftaki tüm katsayılar \(\{0,1,2\}\) kümesine ait olduğundan iki ifadede de elde oluşmaz. Bu nedenle üç tabanındaki gösterimin tekliğinden şu eşitlikler elde edilir: \[ a_i+c_i=2b_i\qquad(0\le i\le10). \] \(b_i=0\) ise bu eşitlik \(a_i=c_i=0\) olmasını; \(b_i=1\) ise \(a_i=c_i=1\) olmasını gerektirir. Böylece her \(i\) için \(a_i=b_i=c_i\) ve dolayısıyla \(x=y=z\) olur.
O hâlde \(S\)'nin birbirinden farklı hiçbir üç elemanı bir aritmetik dizi oluşturmaz. Kümenin \(2047\) elemanından herhangi \(1983\) tanesini seçmek, istenen tam sayıları verir.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1983 · Problema 5
¿Es posible elegir 1983 enteros positivos distintos, todos menores o iguales que \(10^5\), de modo que no haya tres de ellos que sean términos consecutivos de una progresión aritmética? Justificar la respuesta.
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Respuesta
Sí.
Solución
Consideremos el conjunto \[ S=\left\{\sum_{i=0}^{10}\varepsilon_i3^i: \varepsilon_i\in\{0,1\},\ \text{no todos los }\varepsilon_i=0\right\}. \] La unicidad de la representación en base tres muestra que estos son \[ 2^{11}-1=2047 \] enteros positivos distintos. Cada elemento es a lo sumo \[ 1+3+\cdots+3^{10} =\frac{3^{11}-1}{2} =88573<10^5. \]
Demostramos que \(S\) no contiene tres términos distintos consecutivos de una progresión aritmética. Supongamos que \(x,y,z\in S\) satisfacen \[ x+z=2y. \] Escribimos sus desarrollos en base tres como \[ x=\sum_{i=0}^{10}a_i3^i,\qquad y=\sum_{i=0}^{10}b_i3^i,\qquad z=\sum_{i=0}^{10}c_i3^i, \] donde cada cifra pertenece a \(\{0,1\}\). Entonces \[ \sum_{i=0}^{10}(a_i+c_i)3^i =\sum_{i=0}^{10}2b_i3^i. \] Todos los coeficientes de ambos miembros pertenecen a \(\{0,1,2\}\), por lo que ninguna de las dos expresiones requiere llevadas. Por tanto, la unicidad de la representación en base tres da \[ a_i+c_i=2b_i\qquad(0\le i\le10). \] Si \(b_i=0\), esto obliga a que \(a_i=c_i=0\); si \(b_i=1\), obliga a que \(a_i=c_i=1\). Así, \(a_i=b_i=c_i\) para todo \(i\), y en consecuencia \(x=y=z\).
Por tanto, no hay tres elementos distintos de \(S\) que formen una progresión aritmética. Eligiendo cualesquiera \(1983\) de sus \(2047\) elementos, se obtienen los enteros requeridos.
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1983 · 问题 5
能否选出 1983 个互不相同且均不大于 \(10^5\) 的正整数，使其中任意三个数都不是某个等差数列的连续三项？说明理由。
题目译自官方英文原文。 官方试卷 (PDF)
答案
能。
解答
考虑集合 \[ S=\left\{\sum_{i=0}^{10}\varepsilon_i3^i: \varepsilon_i\in\{0,1\},\ \text{并非所有 }\varepsilon_i=0\right\}. \] 由三进制表示的唯一性可知，这些数是 \[ 2^{11}-1=2047 \] 个互不相同的正整数。每个元素都不超过 \[ 1+3+\cdots+3^{10} =\frac{3^{11}-1}{2} =88573<10^5. \]
我们证明，\(S\) 中不存在三个互不相同的数，是某个等差数列的连续三项。假设 \(x,y,z\in S\) 满足 \[ x+z=2y. \] 将它们的三进制展开式写为 \[ x=\sum_{i=0}^{10}a_i3^i,\qquad y=\sum_{i=0}^{10}b_i3^i,\qquad z=\sum_{i=0}^{10}c_i3^i, \] 其中每个数位上的数字都属于 \(\{0,1\}\)。于是 \[ \sum_{i=0}^{10}(a_i+c_i)3^i =\sum_{i=0}^{10}2b_i3^i. \] 两边的所有系数都属于 \(\{0,1,2\}\)，所以两边的表达式均不涉及进位。因此，由三进制表示的唯一性可得 \[ a_i+c_i=2b_i\qquad(0\le i\le10). \] 若 \(b_i=0\)，则必有 \(a_i=c_i=0\)；若 \(b_i=1\)，则必有 \(a_i=c_i=1\)。因此，对每个 \(i\)，都有 \(a_i=b_i=c_i\)，从而 \(x=y=z\)。
所以 \(S\) 中任意三个互不相同的元素都不构成等差数列。从它的 \(2047\) 个元素中任取 \(1983\) 个，就得到所要求的整数。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1983 · Задача 5
Можно ли выбрать 1983 различных положительных целых числа, каждое из которых не превосходит \(10^5\), так, чтобы никакие три из них не являлись последовательными членами арифметической прогрессии? Обоснуйте ответ.
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Ответ
Да.
Решение
Рассмотрим множество \[ S=\left\{\sum_{i=0}^{10}\varepsilon_i3^i: \varepsilon_i\in\{0,1\},\ \text{не все }\varepsilon_i=0\right\}. \] Из единственности записи числа в троичной системе счисления следует, что это \[ 2^{11}-1=2047 \] различных положительных целых чисел. Каждый элемент не превосходит \[ 1+3+\cdots+3^{10} =\frac{3^{11}-1}{2} =88573<10^5. \]
Докажем, что \(S\) не содержит трёх различных последовательных членов арифметической прогрессии. Предположим, что \(x,y,z\in S\) удовлетворяют равенству \[ x+z=2y. \] Запишем их разложения в троичной системе счисления: \[ x=\sum_{i=0}^{10}a_i3^i,\qquad y=\sum_{i=0}^{10}b_i3^i,\qquad z=\sum_{i=0}^{10}c_i3^i, \] где каждая цифра принадлежит \(\{0,1\}\). Тогда \[ \sum_{i=0}^{10}(a_i+c_i)3^i =\sum_{i=0}^{10}2b_i3^i. \] Все коэффициенты в обеих частях принадлежат \(\{0,1,2\}\), поэтому ни в одном из выражений не возникает переносов в следующий разряд. Следовательно, из единственности записи числа в троичной системе счисления получаем \[ a_i+c_i=2b_i\qquad(0\le i\le10). \] Если \(b_i=0\), то отсюда следует \(a_i=c_i=0\); если \(b_i=1\), то отсюда следует \(a_i=c_i=1\). Значит, \(a_i=b_i=c_i\) для каждого \(i\), и, следовательно, \(x=y=z\).
Итак, никакие три различных элемента \(S\) не образуют арифметическую прогрессию. Выбрав любые \(1983\) из его \(2047\) элементов, получим требуемые числа.
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1983 · المسألة 5
هل يمكن اختيار 1983 عددًا صحيحًا موجبًا مختلفًا، لا يتجاوز أي منها \(10^5\)، بحيث لا تكون أي ثلاثة منها حدودًا متتالية في متتالية حسابية؟ علل إجابتك.
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الإجابة
نعم.
الحل
لننظر في المجموعة \[ S=\left\{\sum_{i=0}^{10}\varepsilon_i3^i: \varepsilon_i\in\{0,1\},\ \text{ليست كل }\varepsilon_i=0\right\}. \] تبين وحدانية التمثيل في نظام العد ذي الأساس ثلاثة أن هذه الأعداد هي \[ 2^{11}-1=2047 \] عددًا صحيحًا موجبًا مختلفًا. ولا يتجاوز أي عنصر منها \[ 1+3+\cdots+3^{10} =\frac{3^{11}-1}{2} =88573<10^5. \]
نثبت أن \(S\) لا تحتوي على ثلاثة حدود متتالية مختلفة في متتالية حسابية. لنفترض أن \(x,y,z\in S\) تحقق \[ x+z=2y. \] نكتب تمثيلاتها في نظام العد ذي الأساس ثلاثة على الصورة \[ x=\sum_{i=0}^{10}a_i3^i,\qquad y=\sum_{i=0}^{10}b_i3^i,\qquad z=\sum_{i=0}^{10}c_i3^i, \] حيث ينتمي كل رقم إلى \(\{0,1\}\). عندئذ \[ \sum_{i=0}^{10}(a_i+c_i)3^i =\sum_{i=0}^{10}2b_i3^i. \] تنتمي جميع المعاملات في الطرفين إلى \(\{0,1,2\}\)، فلا يتطلب أي من التعبيرين حملًا إلى الخانة التالية. ومن ثم تعطينا وحدانية التمثيل في نظام العد ذي الأساس ثلاثة \[ a_i+c_i=2b_i\qquad(0\le i\le10). \] إذا كان \(b_i=0\)، فإن هذا يقتضي \(a_i=c_i=0\)؛ وإذا كان \(b_i=1\)، فإنه يقتضي \(a_i=c_i=1\). إذن \(a_i=b_i=c_i\) لكل \(i\)، وبالتالي \(x=y=z\).
إذن لا تشكل أي ثلاثة عناصر مختلفة من \(S\) متتالية حسابية. وباختيار أي \(1983\) عنصرًا من عناصرها البالغ عددها \(2047\)، نحصل على الأعداد الصحيحة المطلوبة.
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).