Shortlist 2025, A4¶
Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : Mongolia
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe extrémal · Principe des tiroirs
Solution officielle : Shortlist officielle 2025 (avec solutions), section A4 (livret PDF)
Énoncé¶
Let \(\mathbb{Z}_{\geq 0}\) be the set of all nonnegative integers. Let \(f : \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0}\) be an unbounded function such that, if \(m\) and \(n\) are nonnegative integers satisfying
then
Prove that there exist positive integers \(A\), \(B\), \(C\) and \(D\) such that for all nonnegative integers \(n\),
We say that \(f\) is unbounded if for each nonnegative integer \(N\), there exists some nonnegative integer \(n\) such that \(f(n) \geq N\).
Indices : les idées clés
- Entiers « grands » et « énormes » : si \(a\) est grand (\(f(b) \leq f(a)\) pour tout \(b \leq a\)), l'hypothèse donne \(f(a) = f(b) + f(a - b)\) pour tout \(b \leq a\).
- Équations fonctionnelles : substitutions : \(m = n = 0\) donne \(f(0) = 0\) ; en écrivant un entier énorme \(a\) comme \(b + (a - b)\), on obtient \(f(n) \geq 1\) pour \(n \geq 1\), puis que les entiers grands sont énormes (solution 1).
- Principe extrémal : on prend pour \(C\) la plus petite valeur strictement positive de \(f\), atteinte en \(A\) ; elle fixe l'écart entre deux entiers énormes consécutifs (solution 1).
- Principe des tiroirs (solution 2) : une classe modulo \(A\) contient une infinité d'entiers grands, et on redescend de \(A\) en \(A\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (deux solutions).
Solution 1¶
Soit \(f\) une fonction non bornée vérifiant l'hypothèse. Un entier \(a \geq 0\) est dit grand si \(f(b) \leq f(a)\) pour tout \(b \leq a\). Si \(a\) est grand, alors \(f(a) = f(b) + f(a - b)\) pour tout \(b \leq a\), d'après l'hypothèse (avec \(m = b\), \(n = a - b\)). En particulier, \(0\) est grand, donc \(f(0) = f(0) + f(0)\), et \(f(0) = 0\). On dit aussi que \(a \geq 0\) est énorme si \(f(b) < f(a)\) pour tout \(b < a\). En particulier, \(0\) est énorme, et tout entier énorme est grand.
Affirmation 1.1. Il y a une infinité d'entiers énormes.
Preuve. S'il n'y en avait qu'un nombre fini, la valeur de \(f\) au plus grand d'entre eux majorerait \(f\). \(\square\)
Affirmation 1.2. \(f(n) \geq 1\) pour tout \(n \geq 1\).
Preuve. D'après l'affirmation 1.1, pour tout \(n \geq 1\) il existe un entier énorme \(a > n\). Alors \(f(n) = f(a) - f(a - n) > 0\). \(\square\)
Affirmation 1.3. Tout entier grand est énorme.
Preuve. Rappelons que \(0\) est grand et énorme. Si \(a \geq 1\) était grand sans être énorme, il existerait \(0 \leq b < a\) avec \(f(b) = f(a)\). Comme \(a\) est grand, \(f(a) = f(b) + f(a - b)\), donc \(f(a - b) = 0\), ce qui contredit l'affirmation 1.2 puisque \(a - b \geq 1\). \(\square\)
Si \(a\) est énorme, on note \(a^+\) le plus petit entier énorme strictement supérieur à \(a\).
Affirmation 1.4. Si \(a\) est énorme et si \(n \geq 0\) vérifie \(n < a^+\) et \(n \neq a\), alors \(f(n) < f(a)\).
Preuve. Si \(n < a\), c'est immédiat car \(a\) est énorme. Sinon, soit \(m\) le plus petit entier \(m > a\) tel que \(f(m) \geq f(a)\) (il existe car \(f\) n'est pas bornée). Par minimalité, \(m\) est grand, donc énorme (affirmation 1.3). Donc \(m = a^+\), et l'affirmation suit. \(\square\)
Affirmation 1.5. Si \(a\) est énorme et si \(m \geq 1\) vérifie \(m \leq a^+\) et \(m \neq a^+ - a\), alors \(f(m) > f(a^+ - a)\).
Preuve. On applique l'affirmation 1.4 avec \(n = a^+ - m < a^+\) (et \(n \neq a\)) : \(f(a) > f(a^+ - m)\). Comme \(a^+\) est grand,
Conclusion. Soit \(C\) la plus petite valeur strictement positive prise par \(f\) (principe extrémal), et \(A\) le plus petit entier positif tel que \(f(A) = C\). Soit \(B\) un entier énorme avec \(B \geq A\). En appliquant l'affirmation 1.5 avec \(a = B\) et \(m = A\) : on a \(1 \leq A \leq B^+\), mais \(f(A) > f(B^+ - B)\) est faux par minimalité de \(f(A)\) ; donc \(A = B^+ - B\). Ainsi \(B^+ = A + B\) est énorme, et \(f(A + B) = f(A) + f(B) = C + f(B)\).
Montrons par récurrence que, pour tout entier \(n \geq 0\), \(An + B\) est énorme et \(f(An + B) = Cn + f(B)\). Les cas \(n = 0\) et \(n = 1\) sont acquis. En appliquant l'affirmation 1.5 avec \(m = A\) et \(a = An + B\) : \(1 \leq A \leq (An + B)^+\), mais \(f(A) > f\big((An + B)^+ - (An + B)\big)\) est faux, donc \((An + B)^+ = A(n + 1) + B\). Ainsi \(A(n+1) + B\) est énorme et
par hypothèse de récurrence. On conclut avec \(D = f(B)\), qui est strictement positif d'après l'affirmation 1.2 (car \(B \geq A \geq 1\)). \(\blacksquare\)
Solution 2¶
On procède comme dans la solution 1 jusqu'à l'affirmation 1.1 incluse (en particulier \(f(0) = 0\)), avec la même terminologie. Soit \(A \geq 1\) un entier quelconque tel que \(f(A)\) soit la plus petite valeur strictement positive de \(f\).
Affirmation 2.1. Si \(a\) est grand et \(a \geq A\), alors \(a - A\) est grand.
Preuve. Pour tout \(n \leq a - A\), comme \(a\) est grand et que \(f(A) \leq f(a - n)\) (car \(a - n \geq A \geq 1\) et \(f(a - n) > 0\) par l'affirmation 1.2), on a
Affirmation 2.2. Il existe un entier \(B\) avec \(1 \leq B \leq A\) tel que \(nA + B\) soit grand pour tout \(n \geq 1\).
Preuve. D'après l'affirmation 1.1, il y a une infinité d'entiers grands. Par le principe des tiroirs (version infinie), une classe de congruence modulo \(A\) en contient une infinité : il existe \(1 \leq B \leq A\) tel qu'il y ait une infinité d'entiers grands de la forme \(nA + B\). L'affirmation 2.1 montre que si \(nA + B\) est grand et \(n \geq 1\), alors \((n-1)A + B\) est grand. Donc tous les entiers \(nA + B\), \(n \geq 1\), sont grands. \(\square\)
D'après l'affirmation 2.2, pour tout \(n \geq 1\),
En posant \(C = f(A)\) et \(D = f(B)\), on obtient la conclusion (l'égalité est triviale pour \(n = 0\)). Précision ajoutée : \(D = f(B) \geq 1\) par l'affirmation 1.2, puisque \(B \geq 1\) ; et l'affirmation 1.2, qui ne dépend que de l'affirmation 1.1, est utilisée dans la preuve de l'affirmation 2.1. \(\blacksquare\)