IMO 1987 · Problem 4
Prove that there is no function \(f\) from the set of non-negative integers into itself such that \(f(f(n)) = n + 1987\) for every \(n\).
Official text of the problem. Official problem paper (PDF)
Solution
Suppose such a function exists, and write \(\mathbb N_0=\{0,1,2,\ldots\}\).
First, \(f\) is injective: if \(f(a)=f(b)\), then applying \(f\) gives \[ a+1987=f(f(a))=f(f(b))=b+1987, \] so \(a=b\).
Let \(I=f(\mathbb N_0)\) be the image of \(f\), and let \(A=\mathbb N_0\setminus I\). The given identity implies \[ f(I)=\{1987,1988,1989,\ldots\}. \] Since \(f(I)\subseteq I\), the set \(A\) is contained in \(\{0,1,\ldots,1986\}\), and hence is finite.
We claim that \[ I\setminus f(I)=f(A). \] Indeed, every element of \(I\) has the form \(f(a)\), and injectivity shows that \[ f(a)\in f(I)\quad\Longleftrightarrow\quad a\in I. \] Thus \(f(a)\) belongs to \(I\setminus f(I)\) exactly when \(a\in A\), proving the claim.
Consequently, \(\mathbb N_0\setminus f(I)\) is the disjoint union of \(A\) and \(f(A)\). Since \(f\) is injective, these two finite sets have the same cardinality. Therefore \[ 1987 =\bigl|\mathbb N_0\setminus f(I)\bigr| =|A|+|f(A)| =2|A|. \] This contradicts the fact that \(1987\) is odd. Hence no such function exists. \(\square\)
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1987 · Aufgabe 4
Man beweise, dass es keine Funktion \(f\) von der Menge der nichtnegativen ganzen Zahlen in sich selbst gibt, für die \(f(f(n)) = n + 1987\) für jedes \(n\) gilt.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Angenommen, eine solche Funktion existiert, und sei \(\mathbb N_0=\{0,1,2,\ldots\}\).
Zunächst ist \(f\) injektiv: Ist \(f(a)=f(b)\), so ergibt die Anwendung von \(f\) \[ a+1987=f(f(a))=f(f(b))=b+1987, \] also \(a=b\).
Sei \(I=f(\mathbb N_0)\) die Bildmenge von \(f\), und sei \(A=\mathbb N_0\setminus I\). Aus der gegebenen Identität folgt \[ f(I)=\{1987,1988,1989,\ldots\}. \] Da \(f(I)\subseteq I\) gilt, ist die Menge \(A\) in \(\{0,1,\ldots,1986\}\) enthalten und somit endlich.
Wir behaupten, dass \[ I\setminus f(I)=f(A). \] Tatsächlich hat jedes Element von \(I\) die Form \(f(a)\), und aus der Injektivität folgt \[ f(a)\in f(I)\quad\Longleftrightarrow\quad a\in I. \] Somit gehört \(f(a)\) genau dann zu \(I\setminus f(I)\), wenn \(a\in A\) gilt, womit die Behauptung bewiesen ist.
Folglich ist \(\mathbb N_0\setminus f(I)\) die disjunkte Vereinigung von \(A\) und \(f(A)\). Da \(f\) injektiv ist, haben diese beiden endlichen Mengen dieselbe Mächtigkeit. Daher gilt \[ 1987 =\bigl|\mathbb N_0\setminus f(I)\bigr| =|A|+|f(A)| =2|A|. \] Dies widerspricht der Tatsache, dass \(1987\) ungerade ist. Also existiert keine solche Funktion. \(\square\)
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1987 · Soru 4
Negatif olmayan tam sayılar kümesinden kendisine tanımlı ve her \(n\) için \(f(f(n)) = n + 1987\) eşitliğini sağlayan bir \(f\) fonksiyonunun bulunmadığını kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
Böyle bir fonksiyonun var olduğunu varsayalım ve \(\mathbb N_0=\{0,1,2,\ldots\}\) yazalım.
Öncelikle, \(f\) bire birdir: \(f(a)=f(b)\) ise her iki tarafa \(f\) uygulayarak \[ a+1987=f(f(a))=f(f(b))=b+1987, \] dolayısıyla \(a=b\) elde ederiz.
\(f\)'nin görüntü kümesi \(I=f(\mathbb N_0)\) olsun ve \(A=\mathbb N_0\setminus I\) olarak tanımlayalım. Verilen özdeşlikten \[ f(I)=\{1987,1988,1989,\ldots\} \] elde edilir. \(f(I)\subseteq I\) olduğundan, \(A\) kümesi \(\{0,1,\ldots,1986\}\) kümesinin bir alt kümesidir ve dolayısıyla sonludur.
Şimdi \[ I\setminus f(I)=f(A) \] olduğunu iddia ediyoruz. Gerçekten de, \(I\)'nın her elemanı \(f(a)\) biçimindedir ve bire birlikten \[ f(a)\in f(I)\quad\Longleftrightarrow\quad a\in I \] olduğu görülür. Böylece \(f(a)\)'nın \(I\setminus f(I)\) kümesine ait olması için gerek ve yeter koşul \(a\in A\) olmasıdır; bu da iddiayı kanıtlar.
Sonuç olarak, \(\mathbb N_0\setminus f(I)\) kümesi, \(A\) ile \(f(A)\)'nın ayrık birleşimidir. \(f\) bire bir olduğundan, bu iki sonlu kümenin eleman sayıları eşittir. Dolayısıyla \[ 1987 =\bigl|\mathbb N_0\setminus f(I)\bigr| =|A|+|f(A)| =2|A|. \] Bu, \(1987\)'nin tek sayı olmasıyla çelişir. O hâlde böyle bir fonksiyon yoktur. \(\square\)
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1987 · Problema 4
Demostrar que no existe ninguna función \(f\) del conjunto de los enteros no negativos en sí mismo tal que \(f(f(n)) = n + 1987\) para todo \(n\).
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Supongamos que existe una función de este tipo, y escribamos \(\mathbb N_0=\{0,1,2,\ldots\}\).
En primer lugar, \(f\) es inyectiva: si \(f(a)=f(b)\), al aplicar \(f\) se obtiene \[ a+1987=f(f(a))=f(f(b))=b+1987, \] por lo que \(a=b\).
Sea \(I=f(\mathbb N_0)\) la imagen de \(f\), y sea \(A=\mathbb N_0\setminus I\). La identidad dada implica \[ f(I)=\{1987,1988,1989,\ldots\}. \] Como \(f(I)\subseteq I\), el conjunto \(A\) está contenido en \(\{0,1,\ldots,1986\}\) y, por tanto, es finito.
Afirmamos que \[ I\setminus f(I)=f(A). \] En efecto, todo elemento de \(I\) tiene la forma \(f(a)\), y la inyectividad muestra que \[ f(a)\in f(I)\quad\Longleftrightarrow\quad a\in I. \] Así, \(f(a)\) pertenece a \(I\setminus f(I)\) si y solo si \(a\in A\), lo que demuestra la afirmación.
En consecuencia, \(\mathbb N_0\setminus f(I)\) es la unión disjunta de \(A\) y \(f(A)\). Como \(f\) es inyectiva, estos dos conjuntos finitos tienen el mismo cardinal. Por tanto, \[ 1987 =\bigl|\mathbb N_0\setminus f(I)\bigr| =|A|+|f(A)| =2|A|. \] Esto contradice el hecho de que \(1987\) es impar. Por tanto, no existe ninguna función de este tipo. \(\square\)
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1987 · 问题 4
证明：不存在从非负整数集到自身的函数 \(f\)，使得对每个 \(n\) 都有 \(f(f(n)) = n + 1987\)。
题目译自官方英文原文。 官方试卷 (PDF)
解答
假设存在这样的函数，并记 \(\mathbb N_0=\{0,1,2,\ldots\}\)。
首先，\(f\) 是单射：若 \(f(a)=f(b)\)，则对两边作用 \(f\)，得到 \[ a+1987=f(f(a))=f(f(b))=b+1987, \] 所以 \(a=b\)。
设 \(I=f(\mathbb N_0)\) 为 \(f\) 的像集，并令 \(A=\mathbb N_0\setminus I\)。由已知恒等式可得 \[ f(I)=\{1987,1988,1989,\ldots\}. \] 由于 \(f(I)\subseteq I\)，集合 \(A\) 包含于 \(\{0,1,\ldots,1986\}\)，因而是有限集。
我们断言 \[ I\setminus f(I)=f(A). \] 事实上，\(I\) 中的每个元素都可写成 \(f(a)\) 的形式，而由单射性可知 \[ f(a)\in f(I)\quad\Longleftrightarrow\quad a\in I. \] 因此，\(f(a)\) 属于 \(I\setminus f(I)\) 当且仅当 \(a\in A\)，断言得证。
从而，\(\mathbb N_0\setminus f(I)\) 是 \(A\) 与 \(f(A)\) 的不交并。由于 \(f\) 是单射，这两个有限集的元素个数相等。因此 \[ 1987 =\bigl|\mathbb N_0\setminus f(I)\bigr| =|A|+|f(A)| =2|A|. \] 这与 \(1987\) 为奇数这一事实矛盾。因此，不存在这样的函数。\(\square\)
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1987 · Задача 4
Докажите, что не существует функции \(f\) из множества неотрицательных целых чисел в себя, такой, что \(f(f(n)) = n + 1987\) для любого \(n\).
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Предположим, что такая функция существует, и обозначим \(\mathbb N_0=\{0,1,2,\ldots\}\).
Прежде всего, \(f\) инъективна: если \(f(a)=f(b)\), то, применяя \(f\), получаем \[ a+1987=f(f(a))=f(f(b))=b+1987, \] откуда \(a=b\).
Пусть \(I=f(\mathbb N_0)\) — образ \(f\), и пусть \(A=\mathbb N_0\setminus I\). Из данного тождества следует, что \[ f(I)=\{1987,1988,1989,\ldots\}. \] Поскольку \(f(I)\subseteq I\), множество \(A\) содержится в \(\{0,1,\ldots,1986\}\) и потому конечно.
Утверждаем, что \[ I\setminus f(I)=f(A). \] Действительно, каждый элемент \(I\) имеет вид \(f(a)\), а из инъективности следует, что \[ f(a)\in f(I)\quad\Longleftrightarrow\quad a\in I. \] Таким образом, \(f(a)\) принадлежит \(I\setminus f(I)\) тогда и только тогда, когда \(a\in A\), что и доказывает утверждение.
Следовательно, \(\mathbb N_0\setminus f(I)\) является объединением непересекающихся множеств \(A\) и \(f(A)\). Поскольку \(f\) инъективна, эти два конечных множества имеют одинаковое число элементов. Поэтому \[ 1987 =\bigl|\mathbb N_0\setminus f(I)\bigr| =|A|+|f(A)| =2|A|. \] Это противоречит тому, что \(1987\) нечётно. Следовательно, такой функции не существует. \(\square\)
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1987 · المسألة 4
أثبت أنه لا توجد دالة \(f\) من مجموعة الأعداد الصحيحة غير السالبة إلى نفسها تحقق \(f(f(n)) = n + 1987\) لكل \(n\).
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
لنفترض وجود مثل هذه الدالة، ولنكتب \(\mathbb N_0=\{0,1,2,\ldots\}\).
أولًا، الدالة \(f\) متباينة: فإذا كان \(f(a)=f(b)\)، فإن تطبيق \(f\) يعطي \[ a+1987=f(f(a))=f(f(b))=b+1987, \] ومن ثم \(a=b\).
لتكن \(I=f(\mathbb N_0)\) صورة الدالة \(f\)، ولتكن \(A=\mathbb N_0\setminus I\). تستلزم المتطابقة المعطاة أن \[ f(I)=\{1987,1988,1989,\ldots\}. \] بما أن \(f(I)\subseteq I\)، فإن المجموعة \(A\) محتواة في \(\{0,1,\ldots,1986\}\)، ولذلك فهي منتهية.
ندّعي أن \[ I\setminus f(I)=f(A). \] فبالفعل، كل عنصر من \(I\) هو على الصورة \(f(a)\)، ومن تباين الدالة نحصل على \[ f(a)\in f(I)\quad\Longleftrightarrow\quad a\in I. \] إذن ينتمي \(f(a)\) إلى \(I\setminus f(I)\) إذا وفقط إذا كان \(a\in A\)، وهذا يثبت الادّعاء.
وبالتالي، فإن \(\mathbb N_0\setminus f(I)\) هي اتحاد المجموعتين المتباعدتين \(A\) و\(f(A)\). وبما أن \(f\) متباينة، فإن هاتين المجموعتين المنتهيتين لهما العدد نفسه من العناصر. لذلك \[ 1987 =\bigl|\mathbb N_0\setminus f(I)\bigr| =|A|+|f(A)| =2|A|. \] وهذا يناقض كون \(1987\) فرديًّا. ومن ثم لا توجد مثل هذه الدالة. \(\square\)
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).