Shortlist 2011, N5¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : non indiqué
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Principe extrémal
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 68 (page 69 du PDF)
Problème 5 de l'OIM 2011
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2011, où il était le problème 5 (jour 2).
Énoncé¶
Let \(f\) be a function from the set of integers to the set of positive integers. Suppose that for any two integers \(m\) and \(n\), the difference \(f(m) - f(n)\) is divisible by \(f(m - n)\). Prove that for all integers \(m, n\) with \(f(m) \leq f(n)\) the number \(f(n)\) is divisible by \(f(m)\).
Indices : les idées clés
- Encadrement : si \(f(x) < f(y)\), alors \(f(x - y) \mid f(y) - f(x)\) donne \(f(x - y) < f(y)\), et \(d = f(x) - f(x - y)\) est un multiple de \(f(y)\) de valeur absolue \(< f(y)\), donc nul.
- Conclusion directe : \(f(x) = f(x - y)\) divise alors \(f(x) - f(y)\), donc \(f(y)\).
- Solution 2 : \(f(n) \mid f(mn)\), \(f\) est paire et ne prend qu'un nombre fini de valeurs ; récurrence sur le nombre de valeurs, avec le plus petit \(a > 0\) tel que \(f(a) > f(1)\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2011 (deux solutions et une remarque).
Solution 1¶
Soient \(x\) et \(y\) deux entiers tels que \(f(x) < f(y)\). Montrons que \(f(x) \mid f(y)\). Avec \(m = x\) et \(n = y\), on voit que
donc \(f(x - y) \leq f(y) - f(x) < f(y)\). Le nombre \(d = f(x) - f(x - y)\) vérifie donc
Avec \(m = x\) et \(n = x - y\), on voit que \(f(y) \mid d\), donc \(d = 0\), autrement dit \(f(x) = f(x - y)\). Avec \(m = x\) et \(n = y\), on voit que \(f(x) = f(x - y) \mid f(x) - f(y)\), ce qui implique \(f(x) \mid f(y)\). \(\blacksquare\)
Solution 2¶
On découpe la solution en une suite d'affirmations ; dans chacune, les lettres \(m\) et \(n\) désignent des entiers quelconques.
Affirmation 1. \(f(n) \mid f(mn)\).
Preuve. Comme trivialement \(f(n) \mid f(1 \cdot n)\) et \(f(n) \mid f((k + 1)n) - f(kn)\) pour tout entier \(k\), cela se voit facilement par récurrence sur \(m\) dans les deux sens. \(\square\)
Affirmation 2. \(f(n) \mid f(0)\) et \(f(n) = f(-n)\).
Preuve. La première partie s'obtient en prenant \(m = 0\) dans l'affirmation 1. En utilisant deux fois l'affirmation 1 avec \(m = -1\), on obtient \(f(n) \mid f(-n) \mid f(n)\), d'où la seconde partie. \(\square\)
D'après l'affirmation 1, \(f(1) \mid f(n)\) pour tout entier \(n\), donc \(f(1)\) est la plus petite valeur prise par \(f\). Ensuite, d'après l'affirmation 2, la fonction \(f\) ne prend qu'un nombre fini de valeurs, puisque toutes ces valeurs divisent \(f(0)\).
Prouvons maintenant l'énoncé par récurrence sur le nombre \(N_f\) de valeurs prises par \(f\). Dans le cas de base \(N_f \leq 2\) : ou bien \(f(0) \neq f(1)\), auquel cas ces deux nombres sont les seules valeurs prises par \(f\) et l'énoncé est clair ; ou bien \(f(0) = f(1)\), auquel cas \(f(1) \mid f(n) \mid f(0)\) pour tout entier \(n\), donc \(f\) est constante et l'énoncé est de nouveau évident.
Pour l'hérédité, supposons \(N_f \geq 3\), et soit \(a\) le plus petit entier strictement positif tel que \(f(a) > f(1)\). Un tel nombre existe grâce à la symétrie de \(f\) obtenue dans l'affirmation 2.
Affirmation 3. \(f(n) \neq f(1)\) si et seulement si \(a \mid n\).
Preuve. Comme \(f(1) = \cdots = f(a - 1) < f(a)\), l'affirmation découle du fait que
Il suffit donc de prouver ce fait.
Supposons \(f(n) = f(1)\). Alors \(f(n + a) \mid f(a) - f(-n) = f(a) - f(n) > 0\), donc \(f(n + a) \leq f(a) - f(n) < f(a)\) ; en particulier, la différence \(f(n + a) - f(n)\) est strictement inférieure à \(f(a)\). De plus, cette différence est divisible par \(f(a)\), et positive ou nulle puisque \(f(n) = f(1)\) est la plus petite valeur prise par \(f\). On a donc \(f(n + a) - f(n) = 0\), comme voulu. Pour la réciproque, il suffit de remarquer que \(f(n + a) = f(1)\) entraîne \(f(-n - a) = f(1)\), et donc \(f(n) = f(-n) = f(1)\) par l'implication directe. \(\square\)
Revenons à l'hérédité. Prenons deux entiers quelconques \(m\) et \(n\) avec \(f(m) \leq f(n)\). Si \(a \nmid m\), alors \(f(m) = f(1) \mid f(n)\). Supposons au contraire \(a \mid m\) ; alors, d'après l'affirmation 3, \(a \mid n\) aussi. Définissons la fonction \(g(x) = f(ax)\). Il est clair que \(g\) vérifie les conditions du problème, et \(N_g \leq N_f - 1\), puisque \(g\) ne prend pas la valeur \(f(1)\) (le livret écrit \(N_g < N_f - 1\) ; seule l'inégalité large est justifiée, et elle suffit.). Par hypothèse de récurrence, \(f(m) = g(m/a) \mid g(n/a) = f(n)\), comme voulu. \(\blacksquare\)
Remarque¶
Une fois établi que \(f\) ne prend qu'un nombre fini de valeurs, il y a plusieurs façons de terminer la solution. Par exemple, soient \(f(0) = b_1 > b_2 > \cdots > b_k\) toutes ces valeurs. On peut montrer (essentiellement comme dans l'affirmation 3) que l'ensemble \(S_i = \{n : f(n) \geq b_i\}\) est exactement l'ensemble des multiples d'un certain entier \(a_i \geq 0\). On a évidemment \(a_i \mid a_{i-1}\), ce qui implique \(f(a_i) \mid f(a_{i-1})\) d'après l'affirmation 1. Donc \(b_k \mid b_{k-1} \mid \cdots \mid b_1\), ce qui prouve l'énoncé.
De plus, il est alors facile de décrire toutes les fonctions vérifiant les conditions du problème. Toutes ces fonctions s'obtiennent ainsi. On considère une suite d'entiers positifs ou nuls \(a_1, a_2, \ldots, a_k\) et une suite d'entiers strictement positifs \(b_1, b_2, \ldots, b_k\) telles que \(\lvert a_k \rvert = 1\), \(a_i \neq a_j\) et \(b_i \neq b_j\) pour tous \(1 \leq i < j \leq k\), et \(a_i \mid a_{i-1}\) et \(b_i \mid b_{i-1}\) pour tout \(i = 2, \ldots, k\). On peut alors poser
Ce sont toutes les fonctions qui vérifient les conditions du problème.