IMO 1993 · Problem 5
Does there exist a function \(f : \mathbb{N} \to \mathbb{N}\) such that \(f(1) = 2\), \(f(f(n)) = f(n) + n\) for all \(n \in \mathbb{N}\), and \(f(n) < f(n + 1)\) for all \(n \in \mathbb{N}\)?
Official text of the problem. Official problem paper (PDF)
Answer
Yes. One such function is \[ \boxed{f(n)=\left\lfloor \frac{1+\sqrt5}{2}\,n+\frac12\right\rfloor.} \]
Solution
Put \(\alpha=(1+\sqrt5)/2\). Then \[ \alpha^2=\alpha+1,\qquad \frac32<\alpha<2. \] Define \[ f(n)=\left\lfloor \alpha n+\frac12\right\rfloor. \] Since \(\alpha>1\), we have \(f(n)\ge n\), so this maps \(\mathbb N\) into itself. Also, \[ f(1)=\left\lfloor\alpha+\frac12\right\rfloor=2. \] Moreover, \[ f(n+1) =\left\lfloor\alpha n+\frac12+\alpha\right\rfloor \ge \left\lfloor\alpha n+\frac12+1\right\rfloor =f(n)+1, \] which proves strict increase.
It remains to verify the functional equation. Fix \(n\), and write \[ e=f(n)-\alpha n. \] The definition of the floor function gives \[ -\frac12<e\le\frac12. \] Using \(\alpha(\alpha-1)=1\), we obtain \[ \alpha f(n)-(f(n)+n) =(\alpha-1)(\alpha n+e)-n =(\alpha-1)e. \] Because \(0<\alpha-1<1\), it follows that \[ \left|\alpha f(n)-(f(n)+n)\right|<\frac12. \] Consequently, \[ f(n)+n<\alpha f(n)+\frac12<f(n)+n+1. \] Taking floors yields \[ f(f(n)) =\left\lfloor\alpha f(n)+\frac12\right\rfloor =f(n)+n. \] Thus all the required conditions hold.
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1993 · Aufgabe 5
Gibt es eine Funktion \(f : \mathbb{N} \to \mathbb{N}\), sodass \(f(1) = 2\), \(f(f(n)) = f(n) + n\) für alle \(n \in \mathbb{N}\) und \(f(n) < f(n + 1)\) für alle \(n \in \mathbb{N}\) gelten?
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Antwort
Ja. Eine solche Funktion ist \[ \boxed{f(n)=\left\lfloor \frac{1+\sqrt5}{2}\,n+\frac12\right\rfloor.} \]
Lösung
Setze \(\alpha=(1+\sqrt5)/2\). Dann gilt \[ \alpha^2=\alpha+1,\qquad \frac32<\alpha<2. \] Definiere \[ f(n)=\left\lfloor \alpha n+\frac12\right\rfloor. \] Da \(\alpha>1\) ist, gilt \(f(n)\ge n\), sodass dies \(\mathbb N\) in sich selbst abbildet. Außerdem gilt \[ f(1)=\left\lfloor\alpha+\frac12\right\rfloor=2. \] Ferner gilt \[ f(n+1) =\left\lfloor\alpha n+\frac12+\alpha\right\rfloor \ge \left\lfloor\alpha n+\frac12+1\right\rfloor =f(n)+1, \] womit die strenge Monotonie bewiesen ist.
Es bleibt, die Funktionalgleichung zu überprüfen. Sei \(n\) fest gewählt, und setze \[ e=f(n)-\alpha n. \] Aus der Definition der Abrundungsfunktion folgt \[ -\frac12<e\le\frac12. \] Mit \(\alpha(\alpha-1)=1\) erhalten wir \[ \alpha f(n)-(f(n)+n) =(\alpha-1)(\alpha n+e)-n =(\alpha-1)e. \] Wegen \(0<\alpha-1<1\) folgt daraus \[ \left|\alpha f(n)-(f(n)+n)\right|<\frac12. \] Folglich gilt \[ f(n)+n<\alpha f(n)+\frac12<f(n)+n+1. \] Durch Abrunden erhalten wir \[ f(f(n)) =\left\lfloor\alpha f(n)+\frac12\right\rfloor =f(n)+n. \] Somit sind alle geforderten Bedingungen erfüllt.
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1993 · Soru 5
\(f(1) = 2\), her \(n \in \mathbb{N}\) için \(f(f(n)) = f(n) + n\) ve her \(n \in \mathbb{N}\) için \(f(n) < f(n + 1)\) koşullarını sağlayan bir \(f : \mathbb{N} \to \mathbb{N}\) fonksiyonu var mıdır?
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Cevap
Evet. Böyle bir fonksiyon \[ \boxed{f(n)=\left\lfloor \frac{1+\sqrt5}{2}\,n+\frac12\right\rfloor} \] ile verilir.
Çözüm
\(\alpha=(1+\sqrt5)/2\) olsun. O hâlde \[ \alpha^2=\alpha+1,\qquad \frac32<\alpha<2. \] \[ f(n)=\left\lfloor \alpha n+\frac12\right\rfloor \] olarak tanımlayalım. \(\alpha>1\) olduğundan \(f(n)\ge n\)'dir; dolayısıyla bu fonksiyon \(\mathbb N\)'yi kendisine götürür. Ayrıca, \[ f(1)=\left\lfloor\alpha+\frac12\right\rfloor=2. \] Bunun yanında, \[ f(n+1) =\left\lfloor\alpha n+\frac12+\alpha\right\rfloor \ge \left\lfloor\alpha n+\frac12+1\right\rfloor =f(n)+1, \] olur; bu da kesin artanlığı kanıtlar.
Geriye fonksiyonel denklemi doğrulamak kalır. \(n\)'yi sabitleyelim ve \[ e=f(n)-\alpha n \] yazalım. Tam değer fonksiyonunun tanımından \[ -\frac12<e\le\frac12 \] elde edilir. \(\alpha(\alpha-1)=1\) eşitliğini kullanarak \[ \alpha f(n)-(f(n)+n) =(\alpha-1)(\alpha n+e)-n =(\alpha-1)e \] elde ederiz. \(0<\alpha-1<1\) olduğundan, \[ \left|\alpha f(n)-(f(n)+n)\right|<\frac12 \] olur. Sonuç olarak, \[ f(n)+n<\alpha f(n)+\frac12<f(n)+n+1. \] Tam değerler alınırsa \[ f(f(n)) =\left\lfloor\alpha f(n)+\frac12\right\rfloor =f(n)+n \] elde edilir. Böylece istenen tüm koşullar sağlanır.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1993 · Problema 5
¿Existe una función \(f : \mathbb{N} \to \mathbb{N}\) tal que \(f(1) = 2\), \(f(f(n)) = f(n) + n\) para todo \(n \in \mathbb{N}\), y \(f(n) < f(n + 1)\) para todo \(n \in \mathbb{N}\)?
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Respuesta
Sí. Una función que cumple estas condiciones es \[ \boxed{f(n)=\left\lfloor \frac{1+\sqrt5}{2}\,n+\frac12\right\rfloor.} \]
Solución
Sea \(\alpha=(1+\sqrt5)/2\). Entonces \[ \alpha^2=\alpha+1,\qquad \frac32<\alpha<2. \] Definamos \[ f(n)=\left\lfloor \alpha n+\frac12\right\rfloor. \] Como \(\alpha>1\), tenemos \(f(n)\ge n\), de modo que esta función lleva \(\mathbb N\) en sí mismo. Además, \[ f(1)=\left\lfloor\alpha+\frac12\right\rfloor=2. \] Por otra parte, \[ f(n+1) =\left\lfloor\alpha n+\frac12+\alpha\right\rfloor \ge \left\lfloor\alpha n+\frac12+1\right\rfloor =f(n)+1, \] lo que demuestra que es estrictamente creciente.
Queda por verificar la ecuación funcional. Fijemos \(n\) y escribamos \[ e=f(n)-\alpha n. \] La definición de la función parte entera da \[ -\frac12<e\le\frac12. \] Usando \(\alpha(\alpha-1)=1\), obtenemos \[ \alpha f(n)-(f(n)+n) =(\alpha-1)(\alpha n+e)-n =(\alpha-1)e. \] Como \(0<\alpha-1<1\), se sigue que \[ \left|\alpha f(n)-(f(n)+n)\right|<\frac12. \] En consecuencia, \[ f(n)+n<\alpha f(n)+\frac12<f(n)+n+1. \] Tomando partes enteras, resulta \[ f(f(n)) =\left\lfloor\alpha f(n)+\frac12\right\rfloor =f(n)+n. \] Así pues, se cumplen todas las condiciones requeridas.
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1993 · 问题 5
是否存在函数 \(f : \mathbb{N} \to \mathbb{N}\)，使得 \(f(1) = 2\)，对所有 \(n \in \mathbb{N}\) 都有 \(f(f(n)) = f(n) + n\)，且对所有 \(n \in \mathbb{N}\) 都有 \(f(n) < f(n + 1)\)？
题目译自官方英文原文。 官方试卷 (PDF)
答案
存在。一个这样的函数是 \[ \boxed{f(n)=\left\lfloor \frac{1+\sqrt5}{2}\,n+\frac12\right\rfloor.} \]
解答
令 \(\alpha=(1+\sqrt5)/2\)。则 \[ \alpha^2=\alpha+1,\qquad \frac32<\alpha<2. \] 定义 \[ f(n)=\left\lfloor \alpha n+\frac12\right\rfloor. \] 由于 \(\alpha>1\)，有 \(f(n)\ge n\)，因此该函数将 \(\mathbb N\) 映入自身。此外， \[ f(1)=\left\lfloor\alpha+\frac12\right\rfloor=2. \] 又有 \[ f(n+1) =\left\lfloor\alpha n+\frac12+\alpha\right\rfloor \ge \left\lfloor\alpha n+\frac12+1\right\rfloor =f(n)+1, \] 这就证明了该函数严格递增。
只需再验证函数方程。固定 \(n\)，并记 \[ e=f(n)-\alpha n. \] 由下取整函数的定义得 \[ -\frac12<e\le\frac12. \] 利用 \(\alpha(\alpha-1)=1\)，得到 \[ \alpha f(n)-(f(n)+n) =(\alpha-1)(\alpha n+e)-n =(\alpha-1)e. \] 由于 \(0<\alpha-1<1\)，可得 \[ \left|\alpha f(n)-(f(n)+n)\right|<\frac12. \] 因此， \[ f(n)+n<\alpha f(n)+\frac12<f(n)+n+1. \] 两边取下整，得到 \[ f(f(n)) =\left\lfloor\alpha f(n)+\frac12\right\rfloor =f(n)+n. \] 因此，所有要求的条件均成立。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1993 · Задача 5
Существует ли функция \(f : \mathbb{N} \to \mathbb{N}\), такая, что \(f(1) = 2\), \(f(f(n)) = f(n) + n\) для всех \(n \in \mathbb{N}\) и \(f(n) < f(n + 1)\) для всех \(n \in \mathbb{N}\)?
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Ответ
Да. Одна из таких функций — \[ \boxed{f(n)=\left\lfloor \frac{1+\sqrt5}{2}\,n+\frac12\right\rfloor.} \]
Решение
Положим \(\alpha=(1+\sqrt5)/2\). Тогда \[ \alpha^2=\alpha+1,\qquad \frac32<\alpha<2. \] Определим \[ f(n)=\left\lfloor \alpha n+\frac12\right\rfloor. \] Поскольку \(\alpha>1\), имеем \(f(n)\ge n\), так что эта функция отображает \(\mathbb N\) в себя. Кроме того, \[ f(1)=\left\lfloor\alpha+\frac12\right\rfloor=2. \] Далее, \[ f(n+1) =\left\lfloor\alpha n+\frac12+\alpha\right\rfloor \ge \left\lfloor\alpha n+\frac12+1\right\rfloor =f(n)+1, \] что доказывает строгое возрастание.
Остаётся проверить функциональное уравнение. Зафиксируем \(n\) и положим \[ e=f(n)-\alpha n. \] Из определения целой части следует \[ -\frac12<e\le\frac12. \] Используя \(\alpha(\alpha-1)=1\), получаем \[ \alpha f(n)-(f(n)+n) =(\alpha-1)(\alpha n+e)-n =(\alpha-1)e. \] Так как \(0<\alpha-1<1\), отсюда следует \[ \left|\alpha f(n)-(f(n)+n)\right|<\frac12. \] Следовательно, \[ f(n)+n<\alpha f(n)+\frac12<f(n)+n+1. \] Переходя к целым частям, получаем \[ f(f(n)) =\left\lfloor\alpha f(n)+\frac12\right\rfloor =f(n)+n. \] Таким образом, все требуемые условия выполнены.
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1993 · المسألة 5
هل توجد دالة \(f : \mathbb{N} \to \mathbb{N}\) بحيث \(f(1) = 2\)، و\(f(f(n)) = f(n) + n\) لكل \(n \in \mathbb{N}\)، و\(f(n) < f(n + 1)\) لكل \(n \in \mathbb{N}\)؟
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الإجابة
نعم. إحدى هذه الدوال هي \[ \boxed{f(n)=\left\lfloor \frac{1+\sqrt5}{2}\,n+\frac12\right\rfloor.} \]
الحل
لنضع \(\alpha=(1+\sqrt5)/2\). عندئذ \[ \alpha^2=\alpha+1,\qquad \frac32<\alpha<2. \] نعرّف \[ f(n)=\left\lfloor \alpha n+\frac12\right\rfloor. \] بما أن \(\alpha>1\)، فإن \(f(n)\ge n\)، لذا فهذه الدالة تأخذ \(\mathbb N\) إلى نفسها. وكذلك، \[ f(1)=\left\lfloor\alpha+\frac12\right\rfloor=2. \] وعلاوة على ذلك، \[ f(n+1) =\left\lfloor\alpha n+\frac12+\alpha\right\rfloor \ge \left\lfloor\alpha n+\frac12+1\right\rfloor =f(n)+1, \] مما يثبت أنها متزايدة تمامًا.
يبقى التحقق من المعادلة الدالية. نثبت \(n\)، ونكتب \[ e=f(n)-\alpha n. \] يعطي تعريف دالة الجزء الصحيح \[ -\frac12<e\le\frac12. \] وباستخدام \(\alpha(\alpha-1)=1\)، نحصل على \[ \alpha f(n)-(f(n)+n) =(\alpha-1)(\alpha n+e)-n =(\alpha-1)e. \] ولأن \(0<\alpha-1<1\)، ينتج أن \[ \left|\alpha f(n)-(f(n)+n)\right|<\frac12. \] وبالتالي، \[ f(n)+n<\alpha f(n)+\frac12<f(n)+n+1. \] وبأخذ الأجزاء الصحيحة نحصل على \[ f(f(n)) =\left\lfloor\alpha f(n)+\frac12\right\rfloor =f(n)+n. \] وهكذا تتحقق جميع الشروط المطلوبة.
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).