Shortlist 2024, A7¶
Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : Japan
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Partie entière et majorations · Principe extrémal
Solution officielle : Shortlist officielle 2024 (avec solutions), section A7 (livret PDF)
Problème 6 de l'OIM 2024
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2024, où il était le problème 6 (jour 2).
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(\mathbb{Q}\) be the set of rational numbers. Let \(f : \mathbb{Q} \to \mathbb{Q}\) be a function such that the following property holds: for all \(x, y \in \mathbb{Q}\),
Determine the maximum possible number of elements of \(\{f(x) + f(-x) \mid x \in \mathbb{Q}\}\).
Indices : les idées clés
- Équations fonctionnelles : substitutions, injectivité : \(P(x, x)\) donne des points fixes, puis l'injectivité et la relation \(f(-f(-x)) = x\) montrent que \(f\) est bijective, d'inverse \(f^{-1}(x) = -f(-x)\).
- Penser en flèches : \(a \to b\) si \(f(a) = b\) ; comme \(f\) est bijective, chaque nombre a exactement une flèche entrante et une sortante, ce qui fixe les deux valeurs \(f(z)\) et \(f^{-1}(z)\).
- Partie entière : l'exemple \(f(x) = \lfloor x \rfloor - \{x\}\) atteint deux valeurs.
- Accroissements (solutions 2 et 3) : \(f(x + d) - f(x) \in \{f(d), -f(-d)\}\), et \(g(x+y) = \pm(g(x) - g(y))\) dès que \(g(x) \neq g(y)\).
- Principe extrémal (solution 3) : prendre un élément qui maximise \(g\) sur un réseau \(\{mx + ny\}\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (trois solutions et quatre remarques).
Réponse. Le nombre maximal d'éléments est \(2\).
Notations communes. Soit \(f\) une fonction vérifiant la condition. On note :
- \(a \sim b\) si \(f(a) = b\) ou \(f(b) = a\) ;
- \(a \to b\) si \(f(a) = b\) ;
- \(P(x, y)\) l'assertion « \(f(x + f(y)) = f(x) + y\) ou \(f(f(x) + y) = x + f(y)\) » ;
- \(g(x) = f(x) + f(-x)\).
La condition \(P(x, y)\) se réécrit simplement \(x + f(y) \sim f(x) + y\), et l'on cherche le nombre maximal d'éléments de \(\{g(x) \mid x \in \mathbb{Q}\}\).
Solution 1¶
Un exemple avec deux valeurs. Soit \(f(x) = \lfloor x \rfloor - \{x\}\), où \(\lfloor x \rfloor\) désigne la partie entière de \(x\) et \(\{x\} = x - \lfloor x \rfloor\) sa partie fractionnaire. Pour \(x, y \in \mathbb{Q}\),
Si \(\{x\} < \{y\}\), la partie fractionnaire de \(f(x) + y\) est \(\{y\} - \{x\}\) et sa partie entière \(\lfloor x \rfloor + \lfloor y \rfloor\), donc \(f(f(x) + y) = x + f(y)\), c'est-à-dire \(f(x) + y \to x + f(y)\). De même, si \(\{x\} > \{y\}\), alors \(x + f(y) \to f(x) + y\). Enfin, si \(\{x\} = \{y\}\), alors \(f(x) + y = x + f(y) = \lfloor x \rfloor + \lfloor y \rfloor\) est un entier, fixé par \(f\). Dans tous les cas, \(P(x, y)\) est vérifiée. Si \(x\) est entier, \(g(x) = 0\) ; sinon, \(f(-x) = -\lfloor x \rfloor - 1 - (1 - \{x\})\) et \(g(x) = -2\). On obtient bien deux valeurs.
Au plus deux valeurs. \(P(x, x)\) donne \(x + f(x) \sim x + f(x)\), c'est-à-dire, pour tout \(x\),
Lemme 1. \(f\) est bijective et vérifie
Preuve. Injectivité. Supposons \(f(x_1) = f(x_2)\). \(P(x_1, x_2)\) donne \(f(x_1) + x_2 \sim f(x_2) + x_1\) ; quitte à échanger, \(f(x_1) + x_2 \to f(x_2) + x_1\). Or \(f(f(x_1) + x_2) = f(f(x_2) + x_2) = f(x_2) + x_2\) par (1). Donc \(f(x_2) + x_1 = f(x_2) + x_2\), d'où \(x_1 = x_2\).
Ensuite, (1) avec \(x = 0\) donne \(f(f(0)) = f(0)\), donc \(f(0) = 0\) par injectivité. \(P(x, -f(x))\) donne \(0 \sim x + f(-f(x))\) : ou bien \(0 = f(0) = x + f(-f(x))\), ou bien \(f(x + f(-f(x))) = 0 = f(0)\), et alors \(x + f(-f(x)) = 0\) par injectivité. Dans les deux cas \(x = -f(-f(x))\), soit (2) en remplaçant \(x\) par \(-x\). La bijectivité découle immédiatement de (2). \(\square\)
\(f\) a donc une réciproque \(f^{-1}\), et (2) (avec \(x\) remplacé par \(-x\)) donne \(f(-x) = -f^{-1}(x)\). Ainsi
Supposons \(g(x) = u\) et \(g(y) = v\) avec \(u \neq v\) tous deux non nuls. Posons \(x' = f^{-1}(x)\) et \(y' = f^{-1}(y)\) ; par définition,
\(P(x', y)\) donne \(x + y \sim x' + y' + v\) et \(P(x, y')\) donne \(x + y \sim x' + y' + u\). Ces deux nombres sont distincts car \(u \neq v\), et \(x + y\) n'a qu'une flèche entrante et une flèche sortante (\(f\) est bijective) ; donc on a \(x' + y' + u \to x + y \to x' + y' + v\), ou la même chose avec les flèches inversées. Quitte à échanger \((x, u)\) et \((y, v)\), on peut supposer que c'est le premier sens.
Par le lemme 1, on a aussi \(-x' - u \to -x \to -x'\) (car \(f(-x' - u) = f(-f(x)) = -x\) et \(f(-x) = -f^{-1}(x) = -x'\)). \(P(x + y, -x' - u)\) donne alors \(y \sim y' + v - u\). Comme \(y \to y' + v\) et \(y' \to y\), le nombre \(y' + v - u\) vaut \(y' + v\) ou \(y'\), donc \(u = 0\) ou \(u = v\) : contradiction.
L'ensemble des valeurs de \(g\) contient donc au plus une valeur non nulle, en plus de \(g(0) = 0\) : il a au plus \(2\) éléments. \(\blacksquare\)
Solution 2¶
On commence encore par le lemme 1, avec \(f(0) = 0\). \(P(x, -f(y))\) donne \(x + f(-f(y)) \sim f(x) - f(y)\), et d'après (2) (où l'on remplace \(x\) par \(-y\)), \(f(-f(y)) = -y\) ; ainsi \(x - y \sim f(x) - f(y)\). Autrement dit, ou bien \(f(x - y) = f(x) - f(y)\), ou bien \(x - y = f(f(x) - f(y))\) ; dans ce dernier cas, (2) donne
Ainsi \(f(y) - f(x)\) vaut \(f(y - x)\) ou \(-f(x - y)\). En remplaçant \(y\) par \(x + d\) :
Affirmation. Pour tout \(n \in \mathbb{Z}_{>0}\) et tout \(d \in \mathbb{Q}\), ou bien \(g(d) = 0\), ou bien \(g(d) = \pm g(d/n)\). En particulier, si \(g(d/n) = 0\), alors \(g(d) = 0\).
Preuve. Supposons d'abord \(g(d/n) = 0\), soit \(f(d/n) = -f(-d/n)\) : alors \(f(x + d/n) - f(x) = f(d/n)\) pour tout \(x\), et en itérant, \(f(x + d) - f(x) = n f(d/n)\). Avec \(x = 0\) et \(x = -d\), puis en additionnant, \(f(d) + f(-d) = 0\), donc \(g(d) = 0\).
Prenons maintenant \(n\) et \(d\) avec \(g(d) \neq 0\) ; d'après ce qui précède, \(g(d/n) \neq 0\). Pour tout \(k \in \mathbb{Z}\), \(f(kd/n) - f((k-1)d/n) \in \{f(d/n), -f(-d/n)\}\). Soit \(A_i\) le nombre d'entiers \(k\) avec \(i - n < k \leq i\) pour lesquels cette différence vaut \(f(d/n)\). Alors, pour tout \(i \in \mathbb{Z}\),
Comme \(g(d/n) \neq 0\), c'est une fonction affine non constante de \(A_i\). Mais le membre de gauche ne prend que deux valeurs possibles (c'est un accroissement de pas \(d\)), donc \(A_i\) prend au plus deux valeurs quand \(i\) varie ; et comme \(A_{i+1} - A_i \in \{-1, 0, 1\}\), ces deux valeurs diffèrent de \(1\). Or
En soustrayant (avec \(f(0) = 0\)) : \(f(d) + f(-d) = (A_n - A_0)\, g(d/n) = \pm g(d/n)\), puisque \(A_n - A_0 \in \{-1, 0, 1\}\) et \(g(d) \neq 0\). \(\square\)
Au plus une valeur non nulle au signe près. Si \(g(d)\) et \(g(d')\) sont non nuls, il existe \(n, n' \in \mathbb{Z}_{>0}\) avec \(d/n = d'/n'\) (\(d, d'\) rationnels non nuls), et alors \(g(d) = \pm g(d/n) = \pm g(d')\).
Les deux signes ne coexistent pas. Supposons \(g(d) = c\) et \(g(d') = -c\) avec \(c \neq 0\). Alors \(f(d) + f(-d) - f(d') - f(-d') = 2c\), soit
D'après le résultat sur les accroissements, chacune des deux parenthèses vaut \(f(d - d')\) ou \(-f(d' - d)\) ; elles ne sont pas égales puisque \(c \neq 0\), donc
ce qui contredit le fait que toutes les valeurs non nulles de \(g\) valent \(\pm c\). L'ensemble des valeurs de \(g\) est donc contenu dans \(\{0, c\}\) pour un certain \(c\). \(\blacksquare\)
Solution 3¶
Comme dans la solution 1, on établit le lemme 1, on note \(f^{-1}(x) = -f(-x)\) et \(g(x) = f(x) - f^{-1}(x)\). Remarquons que \(g\) est paire.
Lemme 2. Si \(g(x) \neq g(y)\), alors \(g(x + y) = \pm\big(g(x) - g(y)\big)\).
Preuve. \(P(x, f^{-1}(y))\) donne \(x + y \sim f(x) + f^{-1}(y)\), et \(P(f^{-1}(x), y)\) donne \(x + y \sim f^{-1}(x) + f(y)\). Or
Comme \(f\) est bijective, ces deux nombres sont \(f(x + y)\) et \(f^{-1}(x + y)\) dans un certain ordre, et \(g(x + y) = f(x + y) - f^{-1}(x + y)\) est leur différence au signe près. \(\square\)
Affirmation. Si \(g(q) = 0\), alors \(g(x + nq) = g(x)\) pour tout rationnel \(x\) et tout entier \(n\).
Preuve. Si \(g(b) = 0\) et \(g(a) \neq g(a + b)\), le lemme 2 (appliqué à \(a + b\) et \(-a\), en utilisant la parité de \(g\)) donne \(g(b) = \pm\big(g(a + b) - g(a)\big) \neq 0\) : contradiction. Donc \(g(a + b) = g(a)\) dès que \(g(b) = 0\). Une récurrence immédiate donne \(g(nb) = 0\) pour tout entier \(n > 0\), puis pour \(n < 0\) par parité ; l'affirmation en découle. \(\square\)
Lemme 3. L'image de \(g\) ne peut pas contenir à la fois un élément strictement positif et un élément strictement négatif.
Preuve. Supposons \(g(x) > 0\) et \(g(y) < 0\), et soit \(S = \{mx + ny \mid m, n \in \mathbb{Z}\}\).
\(g(S)\) est infini. Sinon, par le principe extrémal, soit \(a \in S\) qui maximise \(g\) et \(b \in S\) qui maximise \(-g\) ; alors \(g(a) > 0 > g(b)\). Comme \(a + b \in S\), le lemme 2 donne \(g(a + b) = g(a) - g(b) > g(a)\) ou \(g(a + b) = g(b) - g(a) < g(b)\) : contradiction dans les deux cas.
Il existe un rationnel \(q \neq 0\) avec \(g(q) = 0\). Si \(a + f(a) = 0\) pour tout \(a\), alors \(g = 0\), ce qui est exclu. Sinon, il existe \(a\) avec \(q = a + f(a) \neq 0\), et (1) donne \(f(q) = q\) ; le lemme 1 donne alors \(f(-q) = -f^{-1}(q) = -q\), donc \(g(q) = 0\).
Le livret écrit « \(f(q) = 0\) » et « \(f(-q) = 0\) » ; il faut lire \(f(q) = q\) et \(f(-q) = -q\).
\(g(S)\) est fini. Il existe des entiers \(s, s', t, t'\) avec \(s, t \neq 0\), \(xs = qs'\) et \(yt = qt'\). D'après l'affirmation, \(g(mx + ny)\) ne dépend que de \(m\) modulo \(s\) et de \(n\) modulo \(t\), donc ne prend qu'un nombre fini de valeurs. Contradiction. \(\square\)
Conclusion. Supposons \(g(x) = u\) et \(g(y) = v\) avec \(u \neq v\) de même signe, disons \(u > v > 0\) (l'autre cas est analogue). D'après le lemme 3, \(g \geq 0\) partout. \(P(f^{-1}(x), -y)\) donne (avec \(f(-y) = -f^{-1}(y)\))
et \(P(x, -f(y))\) donne, comme dans la solution 2, \(x - y \sim f(x) - f(y)\). (Le livret écrit \(P(f^{-1}(x), f^{-1}(y))\) et \(P(x, y)\) ; les substitutions qui donnent exactement ces relations sont celles indiquées ici.) Comme \(u - v \neq 0\), \(f(x - y)\) et \(f^{-1}(x - y)\) sont ces deux nombres dans un certain ordre, et comme \(g(x - y) = f(x - y) - f^{-1}(x - y) \geq 0\),
Enfin, \(P(x - y, f^{-1}(y))\) donne \((x - y) + y \sim \big(f(x) - f(y)\big) + \big(f(y) - v\big)\), c'est-à-dire \(x \sim f(x) - v\). Or \(f(x) \neq f(x) - v\) (car \(v \neq 0\)) et \(f^{-1}(x) = f(x) - u \neq f(x) - v\) : contradiction.
L'image de \(g\) contient donc au plus une valeur non nulle, et a au plus \(2\) éléments. \(\blacksquare\)
Remarques¶
Remarque 1 (autre preuve du lemme 1). On montre d'abord que \(f\) est surjective. Sinon, soit \(t\) qui n'est pas une valeur de \(f\). \(P(x, t - f(x))\) donne \(t \sim x + f(t - f(x))\), donc nécessairement \(f(t) = x + f(t - f(x))\) pour tout \(x\). Avec \(x = f(t) - t\), on obtient \(t = f(t - f(f(t) - t))\) : contradiction. Soit alors \(t\) tel que \(f(t) = 0\) ; \(P(t, t)\) donne \(f(t) = t\), donc \(t = 0\) et \(f(0) = 0\). La suite est comme dans la solution 1.
Remarque 2. Le lemme 2 découle aussi de \(f(x + d) - f(x) \in \{f(d), -f(-d)\}\) (solution 2) : on a aussi \(f(-x) - f(-x - d) \in \{f(d), -f(-d)\}\), et en soustrayant, \(g(x + d) - g(x) \in \{g(d), -g(d), 0\}\). En remplaçant \(x + d\) et \(x\) par \(x\) et \(-y\), on obtient l'énoncé du lemme 2.
Remarque 3. À l'aide du lemme 2, on peut montrer que si l'image de \(g\) a plus de deux éléments, elle est de la forme \(\{0, c, 2c\}\) : si \(g(x) = c\) et \(g(y) = d\) avec \(0 < c < d\), alors \(g(x + y) = d - c\) (valeur positive), et \(g(y) = g((x + y) + (-x)) = |d - 2c|\) si \(d \neq 2c\). Mais on ne peut pas exclure \(\{0, c, 2c\}\) à partir du seul lemme 2 : la fonction
vérifie la conclusion du lemme 2 (bien qu'aucune fonction \(f\) ne donne ce \(g\)).
Remarque 4. La solution 1 montre que le résultat reste vrai sur \(\mathbb{R}\). Le problème a été proposé et étudié sur \(\mathbb{Q}\), ce qui permet des approches plus variées une fois le lemme 1 établi ; même cette version a été jugée assez difficile.