Aller au contenu

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é

Notons \(\mathbb{Z}_{\geq 0}\) l'ensemble des entiers positifs ou nuls. Soit \(f : \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0}\) une fonction non bornée telle que, si \(m\) et \(n\) sont des entiers positifs ou nuls vérifiant

\[f(m + n) = \max\{f(0), f(1), \ldots, f(m + n)\},\]

alors

\[f(m + n) = f(m) + f(n).\]

Montrer qu'il existe des entiers strictement positifs \(A\), \(B\), \(C\) et \(D\) tels que, pour tout entier \(n\) positif ou nul,

\[f(An + B) = Cn + D.\]

On dit que \(f\) est non bornée si, pour tout entier \(N\) positif ou nul, il existe un entier \(n\) positif ou nul tel que \(f(n) \geq N\).

Énoncé original (anglais)

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

\[f(m + n) = \max\{f(0), f(1), \ldots, f(m + n)\},\]

then

\[f(m + n) = f(m) + f(n).\]

Prove that there exist positive integers \(A\), \(B\), \(C\) and \(D\) such that for all nonnegative integers \(n\),

\[f(An + B) = Cn + D.\]

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,

\[f(m) = f(a^+) - f(a^+ - m) > f(a^+) - f(a) = f(a^+ - a). \quad \square\]

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

\[f(A(n+1) + B) = f(An + B) + f(A) = C(n + 1) + f(B)\]

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

\[f(a - A) = f(a) - f(A) \geq f(a) - f(a - n) = f(n). \quad \square\]

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\),

\[f(nA + B) = f((n-1)A + B) + f(A) = \cdots = n f(A) + f(B).\]

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\)

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2024 A4 ★★☆☆☆ : Quels ensembles de puissances de \(2\) peuvent être exactement l'ensemble des défauts d'additivité \(f(a + b) - f(a) - f(b)\) ?
  • 2019 N4 ★★☆☆☆ : Trouver les fonctions telles que \(a + f(b)\) divise \(a^2 + b f(a)\) dès que \(a + b > C\).
  • 2017 A3 ★★☆☆☆ : Si aucune autre fonction \(g\) ne vérifie \(f \circ g \circ f = g \circ f \circ g\), alors \(f\) est bijective sur son image.
  • 2011 A4 ★★★☆☆ : Trouver les couples de fonctions des entiers vérifiant une équation où chacune est itérée un nombre de fois donné par l'autre.