IMO 1996 · Problem 3
Let \(S\) denote the set of nonnegative integers. Find all functions \(f\) from \(S\) to itself such that \[ f(m+f(n))=f(f(m))+f(n)\qquad \forall m,n\in S. \]
Official text of the problem. Official problem paper (PDF)
Answer
The solutions are \(f(n)=0\) for every \(n\in S\), and all functions of the following form:
Choose a positive integer \(d\) and arbitrary nonnegative integers \(c_0,c_1,\ldots,c_{d-1}\) with \(c_0=0\). Set \[ \boxed{f(qd+r)=d(q+c_r)\qquad(q\ge0,\ 0\le r<d).} \]
Solution
Putting \(m=n=0\) in the given equation yields \[ f(f(0))=f(f(0))+f(0), \] so \(f(0)=0\). Taking \(m=0\) now gives \[ f(f(n))=f(n)\qquad(n\in S). \] Consequently, the original equation becomes \[ f(m+f(n))=f(m)+f(n)\qquad(m,n\in S). \tag{1} \]
The identically zero function is a solution. Suppose henceforth that \(f\) is not identically zero. Let \(d\) be its smallest positive value, and choose \(t\in S\) with \(f(t)=d\). Equation (1), with \(n=t\), gives \[ f(m+d)=f(m)+d\qquad(m\in S). \] Iterating this identity, we obtain \[ f(qd+r)=qd+f(r)\qquad(q\ge0,\ 0\le r<d). \tag{2} \]
We next prove that each \(f(r)\), for \(0\le r<d\), is divisible by \(d\). By the division algorithm, write \[ f(r)=kd+s,\qquad k\ge0,\quad 0\le s<d. \] Using idempotence and (2), we have \[ kd+s=f(r)=f(f(r))=f(kd+s)=kd+f(s). \] Thus \(f(s)=s\). If \(s>0\), this would make \(s\) a positive value of \(f\) smaller than \(d\), contradicting the choice of \(d\). Therefore \(s=0\).
It follows that \(f(r)=dc_r\) for some nonnegative integer \(c_r\). Since \(f(0)=0\), we have \(c_0=0\), and (2) becomes precisely \[ f(qd+r)=d(q+c_r). \] This proves that every solution has one of the stated forms.
Conversely, choose any parameters as in the answer and define \(f\) by that formula. It maps \(S\) into \(S\). Since \(c_0=0\), \[ f(kd)=kd\qquad(k\ge0). \] Every value of \(f\) is a multiple of \(d\), so \(f(f(m))=f(m)\).
For arbitrary \(m,n\in S\), write \(m=qd+r\), where \(0\le r<d\), and write \(f(n)=kd\). Then \[ \begin{aligned} f(m+f(n)) &=f((q+k)d+r)\\ &=d(q+k+c_r)\\ &=f(m)+f(n)\\ &=f(f(m))+f(n). \end{aligned} \] Thus every listed function satisfies the required equation, completing the classification.
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1996 · Aufgabe 3
Sei \(S\) die Menge der nichtnegativen ganzen Zahlen. Bestimme alle Funktionen \(f\) von \(S\) in sich selbst, für die \[ f(m+f(n))=f(f(m))+f(n)\qquad \forall m,n\in S \] gilt.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Antwort
Die Lösungen sind \(f(n)=0\) für jedes \(n\in S\) sowie alle Funktionen der folgenden Form:
Wähle eine positive ganze Zahl \(d\) und beliebige nichtnegative ganze Zahlen \(c_0,c_1,\ldots,c_{d-1}\) mit \(c_0=0\). Setze \[ \boxed{f(qd+r)=d(q+c_r)\qquad(q\ge0,\ 0\le r<d).} \]
Lösung
Setzt man \(m=n=0\) in die gegebene Gleichung ein, so erhält man \[ f(f(0))=f(f(0))+f(0), \] also \(f(0)=0\). Mit \(m=0\) ergibt sich nun \[ f(f(n))=f(n)\qquad(n\in S). \] Damit wird die ursprüngliche Gleichung zu \[ f(m+f(n))=f(m)+f(n)\qquad(m,n\in S). \tag{1} \]
Die identisch verschwindende Funktion ist eine Lösung. Wir nehmen im Folgenden an, dass \(f\) nicht identisch verschwindet. Sei \(d\) ihr kleinster positiver Wert, und wähle \(t\in S\) mit \(f(t)=d\). Gleichung (1) liefert mit \(n=t\) \[ f(m+d)=f(m)+d\qquad(m\in S). \] Durch wiederholte Anwendung dieser Identität erhalten wir \[ f(qd+r)=qd+f(r)\qquad(q\ge0,\ 0\le r<d). \tag{2} \]
Als Nächstes beweisen wir, dass jeder Wert \(f(r)\) mit \(0\le r<d\) durch \(d\) teilbar ist. Mittels Division mit Rest schreiben wir \[ f(r)=kd+s,\qquad k\ge0,\quad 0\le s<d. \] Aus der Idempotenz und (2) folgt \[ kd+s=f(r)=f(f(r))=f(kd+s)=kd+f(s). \] Somit ist \(f(s)=s\). Wäre \(s>0\), so wäre \(s\) ein positiver Wert von \(f\), der kleiner als \(d\) ist, im Widerspruch zur Wahl von \(d\). Daher gilt \(s=0\).
Es folgt \(f(r)=dc_r\) für eine nichtnegative ganze Zahl \(c_r\). Wegen \(f(0)=0\) gilt \(c_0=0\), und (2) wird genau zu \[ f(qd+r)=d(q+c_r). \] Damit ist bewiesen, dass jede Lösung eine der angegebenen Formen hat.
Umgekehrt wählen wir beliebige Parameter wie in der Antwort und definieren \(f\) durch die dort angegebene Formel. Sie bildet \(S\) in \(S\) ab. Wegen \(c_0=0\) gilt \[ f(kd)=kd\qquad(k\ge0). \] Jeder Wert von \(f\) ist ein Vielfaches von \(d\), also gilt \(f(f(m))=f(m)\).
Für beliebige \(m,n\in S\) schreiben wir \(m=qd+r\) mit \(0\le r<d\) sowie \(f(n)=kd\). Dann gilt \[ \begin{aligned} f(m+f(n)) &=f((q+k)d+r)\\ &=d(q+k+c_r)\\ &=f(m)+f(n)\\ &=f(f(m))+f(n). \end{aligned} \] Somit erfüllt jede angegebene Funktion die geforderte Gleichung, womit die Klassifikation abgeschlossen ist.
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1996 · Soru 3
\(S\), negatif olmayan tam sayılar kümesini göstersin. \(S\) kümesinden kendisine tanımlı ve \[ f(m+f(n))=f(f(m))+f(n)\qquad \forall m,n\in S \] eşitliğini sağlayan tüm \(f\) fonksiyonlarını bulunuz.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Cevap
Çözümler, her \(n\in S\) için \(f(n)=0\) olan fonksiyon ile aşağıdaki biçimdeki tüm fonksiyonlardır:
Bir pozitif tam sayı \(d\) ve \(c_0=0\) koşulunu sağlayan keyfî negatif olmayan \(c_0,c_1,\ldots,c_{d-1}\) tam sayılarını seçelim. Fonksiyonu \[ \boxed{f(qd+r)=d(q+c_r)\qquad(q\ge0,\ 0\le r<d)} \] olarak tanımlayalım.
Çözüm
Verilen denklemde \(m=n=0\) koyarsak \[ f(f(0))=f(f(0))+f(0), \] elde ederiz; dolayısıyla \(f(0)=0\) olur. Şimdi \(m=0\) alırsak \[ f(f(n))=f(n)\qquad(n\in S) \] buluruz. Böylece başlangıçtaki denklem \[ f(m+f(n))=f(m)+f(n)\qquad(m,n\in S) \tag{1} \] biçimini alır.
Özdeş olarak sıfır olan fonksiyon bir çözümdür. Bundan sonra \(f\) fonksiyonunun özdeş olarak sıfır olmadığını varsayalım. Aldığı en küçük pozitif değer \(d\) olsun ve \(f(t)=d\) olacak şekilde bir \(t\in S\) seçelim. (1) denkleminde \(n=t\) alırsak \[ f(m+d)=f(m)+d\qquad(m\in S) \] elde ederiz. Bu özdeşliği art arda uygulayarak \[ f(qd+r)=qd+f(r)\qquad(q\ge0,\ 0\le r<d) \tag{2} \] buluruz.
Şimdi \(0\le r<d\) için her \(f(r)\) değerinin \(d\) ile bölündüğünü kanıtlayacağız. Bölme algoritmasına göre \[ f(r)=kd+s,\qquad k\ge0,\quad 0\le s<d \] yazalım. İdempotentlik özelliğini ve (2) eşitliğini kullanarak \[ kd+s=f(r)=f(f(r))=f(kd+s)=kd+f(s) \] elde ederiz. Dolayısıyla \(f(s)=s\) olur. \(s>0\) olsaydı, \(s\), \(f\) fonksiyonunun \(d\) değerinden küçük bir pozitif değeri olurdu; bu ise \(d\) seçimiyle çelişir. Öyleyse \(s=0\) olur.
Buna göre negatif olmayan bir \(c_r\) tam sayısı için \(f(r)=dc_r\) olur. \(f(0)=0\) olduğundan \(c_0=0\) olur ve (2) eşitliği tam olarak \[ f(qd+r)=d(q+c_r) \] biçimini alır. Bu, her çözümün belirtilen biçimlerden birinde olduğunu kanıtlar.
Tersine, cevaptaki koşulları sağlayan herhangi bir parametre seçimi yapalım ve \(f\) fonksiyonunu bu formülle tanımlayalım. Bu fonksiyon \(S\) kümesini \(S\) kümesine götürür. \(c_0=0\) olduğundan \[ f(kd)=kd\qquad(k\ge0) \] olur. \(f\) fonksiyonunun her değeri \(d\) sayısının bir katı olduğundan \(f(f(m))=f(m)\) olur.
Keyfî \(m,n\in S\) için \(0\le r<d\) olmak üzere \(m=qd+r\) yazalım ve \(f(n)=kd\) olsun. O hâlde \[ \begin{aligned} f(m+f(n)) &=f((q+k)d+r)\\ &=d(q+k+c_r)\\ &=f(m)+f(n)\\ &=f(f(m))+f(n). \end{aligned} \] Böylece listelenen her fonksiyon istenen denklemi sağlar ve sınıflandırma tamamlanır.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1996 · Problema 3
Sea \(S\) el conjunto de los enteros no negativos. Hallar todas las funciones \(f\) de \(S\) en sí mismo tales que \[ f(m+f(n))=f(f(m))+f(n)\qquad \forall m,n\in S. \]
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Respuesta
Las soluciones son \(f(n)=0\) para todo \(n\in S\), y todas las funciones de la siguiente forma:
Elegimos un entero positivo \(d\) y enteros no negativos arbitrarios \(c_0,c_1,\ldots,c_{d-1}\) con \(c_0=0\). Definimos \[ \boxed{f(qd+r)=d(q+c_r)\qquad(q\ge0,\ 0\le r<d).} \]
Solución
Al tomar \(m=n=0\) en la ecuación dada, obtenemos \[ f(f(0))=f(f(0))+f(0), \] por lo que \(f(0)=0\). Tomando ahora \(m=0\), resulta \[ f(f(n))=f(n)\qquad(n\in S). \] Por consiguiente, la ecuación original se convierte en \[ f(m+f(n))=f(m)+f(n)\qquad(m,n\in S). \tag{1} \]
La función idénticamente nula es una solución. Supongamos en adelante que \(f\) no es idénticamente nula. Sea \(d\) su menor valor positivo, y elijamos \(t\in S\) tal que \(f(t)=d\). La ecuación (1), con \(n=t\), da \[ f(m+d)=f(m)+d\qquad(m\in S). \] Iterando esta identidad, obtenemos \[ f(qd+r)=qd+f(r)\qquad(q\ge0,\ 0\le r<d). \tag{2} \]
A continuación demostraremos que cada \(f(r)\), para \(0\le r<d\), es divisible por \(d\). Por el algoritmo de la división, escribimos \[ f(r)=kd+s,\qquad k\ge0,\quad 0\le s<d. \] Usando la idempotencia y (2), tenemos \[ kd+s=f(r)=f(f(r))=f(kd+s)=kd+f(s). \] Por tanto, \(f(s)=s\). Si \(s>0\), esto haría de \(s\) un valor positivo de \(f\) menor que \(d\), contradiciendo la elección de \(d\). Por tanto, \(s=0\).
Se sigue que \(f(r)=dc_r\) para algún entero no negativo \(c_r\). Como \(f(0)=0\), tenemos \(c_0=0\), y (2) se convierte precisamente en \[ f(qd+r)=d(q+c_r). \] Esto demuestra que toda solución tiene una de las formas indicadas.
Recíprocamente, elegimos cualesquiera parámetros como en la respuesta y definimos \(f\) mediante esa fórmula. Esta función aplica \(S\) en \(S\). Como \(c_0=0\), \[ f(kd)=kd\qquad(k\ge0). \] Todo valor de \(f\) es múltiplo de \(d\), por lo que \(f(f(m))=f(m)\).
Para \(m,n\in S\) arbitrarios, escribimos \(m=qd+r\), donde \(0\le r<d\), y \(f(n)=kd\). Entonces \[ \begin{aligned} f(m+f(n)) &=f((q+k)d+r)\\ &=d(q+k+c_r)\\ &=f(m)+f(n)\\ &=f(f(m))+f(n). \end{aligned} \] Así pues, todas las funciones indicadas satisfacen la ecuación requerida, lo que completa la clasificación.
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1996 · 问题 3
用 \(S\) 表示非负整数集。求所有从 \(S\) 到自身的函数 \(f\)，使得 \[ f(m+f(n))=f(f(m))+f(n)\qquad \forall m,n\in S. \]
题目译自官方英文原文。 官方试卷 (PDF)
答案
所有解为：对每个 \(n\in S\) 都有 \(f(n)=0\) 的函数，以及以下形式的所有函数：
选取一个正整数 \(d\) 和任意满足 \(c_0=0\) 的非负整数 \(c_0,c_1,\ldots,c_{d-1}\)。令 \[ \boxed{f(qd+r)=d(q+c_r)\qquad(q\ge0,\ 0\le r<d).} \]
解答
在所给方程中令 \(m=n=0\)，得到 \[ f(f(0))=f(f(0))+f(0), \] 故 \(f(0)=0\)。现在取 \(m=0\)，得到 \[ f(f(n))=f(n)\qquad(n\in S). \] 因此，原方程化为 \[ f(m+f(n))=f(m)+f(n)\qquad(m,n\in S). \tag{1} \]
恒为零的函数是一个解。以下假设 \(f\) 不恒为零。设 \(d\) 是它的最小正值，并选取 \(t\in S\) 使 \(f(t)=d\)。在方程 (1) 中取 \(n=t\)，得到 \[ f(m+d)=f(m)+d\qquad(m\in S). \] 反复应用这个恒等式，得到 \[ f(qd+r)=qd+f(r)\qquad(q\ge0,\ 0\le r<d). \tag{2} \]
接下来证明，对于 \(0\le r<d\)，每个 \(f(r)\) 都能被 \(d\) 整除。由带余除法，写成 \[ f(r)=kd+s,\qquad k\ge0,\quad 0\le s<d. \] 利用幂等性和 (2)，有 \[ kd+s=f(r)=f(f(r))=f(kd+s)=kd+f(s). \] 因此 \(f(s)=s\)。若 \(s>0\)，则 \(s\) 就是 \(f\) 的一个小于 \(d\) 的正值，与 \(d\) 的选取矛盾。因此 \(s=0\)。
由此可知，\(f(r)=dc_r\)，其中 \(c_r\) 是某个非负整数。由于 \(f(0)=0\)，有 \(c_0=0\)，且 (2) 恰好化为 \[ f(qd+r)=d(q+c_r). \] 这就证明了每个解都具有所述形式之一。
反过来，任取满足答案中条件的参数，并用该公式定义 \(f\)。它将 \(S\) 映射到 \(S\)。由于 \(c_0=0\)， \[ f(kd)=kd\qquad(k\ge0). \] \(f\) 的每个值都是 \(d\) 的倍数，因此 \(f(f(m))=f(m)\)。
对任意 \(m,n\in S\)，写成 \(m=qd+r\)，其中 \(0\le r<d\)，并写成 \(f(n)=kd\)。于是 \[ \begin{aligned} f(m+f(n)) &=f((q+k)d+r)\\ &=d(q+k+c_r)\\ &=f(m)+f(n)\\ &=f(f(m))+f(n). \end{aligned} \] 因此，所列的每个函数都满足所要求的方程，分类完成。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1996 · Задача 3
Пусть \(S\) — множество неотрицательных целых чисел. Найдите все функции \(f\) из \(S\) в себя, для которых \[ f(m+f(n))=f(f(m))+f(n)\qquad \forall m,n\in S. \]
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Ответ
Решениями являются функция \(f(n)=0\) для всех \(n\in S\) и все функции следующего вида:
Выберем положительное целое число \(d\) и произвольные неотрицательные целые числа \(c_0,c_1,\ldots,c_{d-1}\), где \(c_0=0\). Положим \[ \boxed{f(qd+r)=d(q+c_r)\qquad(q\ge0,\ 0\le r<d).} \]
Решение
Подставляя \(m=n=0\) в данное уравнение, получаем \[ f(f(0))=f(f(0))+f(0), \] поэтому \(f(0)=0\). Теперь, полагая \(m=0\), находим \[ f(f(n))=f(n)\qquad(n\in S). \] Следовательно, исходное уравнение принимает вид \[ f(m+f(n))=f(m)+f(n)\qquad(m,n\in S). \tag{1} \]
Тождественно нулевая функция является решением. Далее предположим, что \(f\) не тождественно равна нулю. Пусть \(d\) — её наименьшее положительное значение; выберем \(t\in S\) так, чтобы \(f(t)=d\). Из уравнения (1) при \(n=t\) получаем \[ f(m+d)=f(m)+d\qquad(m\in S). \] Многократно применяя это тождество, получаем \[ f(qd+r)=qd+f(r)\qquad(q\ge0,\ 0\le r<d). \tag{2} \]
Теперь докажем, что каждое \(f(r)\) при \(0\le r<d\) делится на \(d\). По теореме о делении с остатком запишем \[ f(r)=kd+s,\qquad k\ge0,\quad 0\le s<d. \] Используя идемпотентность и (2), имеем \[ kd+s=f(r)=f(f(r))=f(kd+s)=kd+f(s). \] Таким образом, \(f(s)=s\). Если бы \(s>0\), то \(s\) было бы положительным значением \(f\), меньшим \(d\), что противоречит выбору \(d\). Поэтому \(s=0\).
Отсюда следует, что \(f(r)=dc_r\) для некоторого неотрицательного целого числа \(c_r\). Поскольку \(f(0)=0\), имеем \(c_0=0\), и (2) принимает в точности вид \[ f(qd+r)=d(q+c_r). \] Тем самым доказано, что каждое решение имеет один из указанных видов.
Обратно, выберем любые параметры, как в ответе, и определим \(f\) этой формулой. Эта функция отображает \(S\) в \(S\). Поскольку \(c_0=0\), \[ f(kd)=kd\qquad(k\ge0). \] Каждое значение \(f\) кратно \(d\), поэтому \(f(f(m))=f(m)\).
Для произвольных \(m,n\in S\) запишем \(m=qd+r\), где \(0\le r<d\), и \(f(n)=kd\). Тогда \[ \begin{aligned} f(m+f(n)) &=f((q+k)d+r)\\ &=d(q+k+c_r)\\ &=f(m)+f(n)\\ &=f(f(m))+f(n). \end{aligned} \] Таким образом, каждая из перечисленных функций удовлетворяет требуемому уравнению, что завершает классификацию.
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1996 · المسألة 3
لتكن \(S\) مجموعة الأعداد الصحيحة غير السالبة. أوجد جميع الدوال \(f\) من \(S\) إلى نفسها التي تحقق \[ f(m+f(n))=f(f(m))+f(n)\qquad \forall m,n\in S. \]
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الإجابة
الحلول هي \(f(n)=0\) لكل \(n\in S\)، وجميع الدوال ذات الصورة الآتية:
نختار عددًا صحيحًا موجبًا \(d\) وأعدادًا صحيحة غير سالبة اختيارية \(c_0,c_1,\ldots,c_{d-1}\) تحقق \(c_0=0\). ونضع \[ \boxed{f(qd+r)=d(q+c_r)\qquad(q\ge0,\ 0\le r<d).} \]
الحل
بوضع \(m=n=0\) في المعادلة المعطاة نحصل على \[ f(f(0))=f(f(0))+f(0), \] ومن ثم \(f(0)=0\). وبأخذ \(m=0\) الآن نحصل على \[ f(f(n))=f(n)\qquad(n\in S). \] وبالتالي تصبح المعادلة الأصلية \[ f(m+f(n))=f(m)+f(n)\qquad(m,n\in S). \tag{1} \]
الدالة المنعدمة تطابقيًا حل. ولنفترض فيما يأتي أن \(f\) ليست منعدمة تطابقيًا. ليكن \(d\) أصغر قيمة موجبة لها، ولنختر \(t\in S\) بحيث \(f(t)=d\). تعطينا المعادلة (1)، مع \(n=t\)، \[ f(m+d)=f(m)+d\qquad(m\in S). \] وبتكرار تطبيق هذه المتطابقة، نحصل على \[ f(qd+r)=qd+f(r)\qquad(q\ge0,\ 0\le r<d). \tag{2} \]
نثبت الآن أن كل \(f(r)\)، حيث \(0\le r<d\)، يقبل القسمة على \(d\). بحسب خوارزمية القسمة، نكتب \[ f(r)=kd+s,\qquad k\ge0,\quad 0\le s<d. \] باستخدام خاصية ثبات الدالة عند تكرار تطبيقها و(2)، لدينا \[ kd+s=f(r)=f(f(r))=f(kd+s)=kd+f(s). \] إذًا \(f(s)=s\). وإذا كان \(s>0\)، لكان \(s\) قيمة موجبة للدالة \(f\) أصغر من \(d\)، مما يناقض اختيار \(d\). لذلك \(s=0\).
يترتب على ذلك أن \(f(r)=dc_r\) لعدد صحيح غير سالب ما \(c_r\). وبما أن \(f(0)=0\)، فإن \(c_0=0\)، وتصبح (2) بالضبط \[ f(qd+r)=d(q+c_r). \] وهذا يثبت أن كل حل له إحدى الصور المذكورة.
وعكسًا، نختار أي معاملات كما في الإجابة ونعرّف \(f\) بتلك الصيغة. وهي ترسل \(S\) إلى \(S\). وبما أن \(c_0=0\)، فإن \[ f(kd)=kd\qquad(k\ge0). \] كل قيمة للدالة \(f\) من مضاعفات \(d\)، لذا \(f(f(m))=f(m)\).
لأي \(m,n\in S\)، نكتب \(m=qd+r\)، حيث \(0\le r<d\)، ونكتب \(f(n)=kd\). عندئذ \[ \begin{aligned} f(m+f(n)) &=f((q+k)d+r)\\ &=d(q+k+c_r)\\ &=f(m)+f(n)\\ &=f(f(m))+f(n). \end{aligned} \] إذًا تحقق كل دالة مذكورة المعادلة المطلوبة، وبذلك يكتمل التصنيف.
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).