Shortlist 2013, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Israel
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Partie entière et majorations · Principe extrémal
Solution officielle : Shortlist officielle 2013 (avec solutions), p. 61 (page 61 du PDF)
Énoncé¶
Determine all functions \(f : \mathbb{Q} \to \mathbb{Z}\) satisfying
for all \(x \in \mathbb{Q}\), \(a \in \mathbb{Z}\), and \(b \in \mathbb{Z}_{>0}\). (Here, \(\mathbb{Z}_{>0}\) denotes the set of positive integers.)
Indices : les idées clés
- Les solutions : les fonctions constantes, la partie entière \(\lfloor x \rfloor\) et la partie entière supérieure \(\lceil x \rceil\).
- Substitutions : si \(f(m) \neq m\) pour un entier \(m\), alors \(f\) est constante ; sinon \(f(x + a) = f(x) + a\), et l'on pose \(\omega = f\left(\frac{1}{2}\right) \in \{0, 1\}\).
- Plus petit dénominateur (solution 1) : par l'absurde, avec un \(\frac{a}{b} \in (0, 1)\) de dénominateur minimal tel que \(f\left(\frac{a}{b}\right) \neq \omega\), Bézout fournit une fraction de plus petit dénominateur qui contredit la minimalité.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2013 (deux solutions et deux remarques).
Réponse : il y a trois types de solutions : toutes les fonctions constantes, la fonction partie entière et la fonction partie entière supérieure.
Solution 1¶
I. Vérifions d'abord que ces fonctions conviennent. C'est clair pour les fonctions constantes. Considérons un triplet \((x, a, b) \in \mathbb{Q} \times \mathbb{Z} \times \mathbb{Z}_{>0}\) et posons
Cela signifie que \(q\) est un entier et que \(bq \leq x + a < b(q + 1)\). Il s'ensuit que \(bq \leq \lfloor x \rfloor + a < b(q + 1)\), donc
la fonction partie entière vérifie bien (1). On vérifie de même que la fonction partie entière supérieure a la même propriété.
II. Supposons réciproquement que \(f : \mathbb{Q} \to \mathbb{Z}\) vérifie (1) pour tout \((x, a, b) \in \mathbb{Q} \times \mathbb{Z} \times \mathbb{Z}_{>0}\). On distingue deux cas selon le comportement de \(f\) sur les entiers.
Cas 1 : il existe \(m \in \mathbb{Z}\) tel que \(f(m) \neq m\). Posons \(f(m) = C\), et notons \(\eta \in \{-1, +1\}\) et \(b\) le signe et la valeur absolue de \(f(m) - m\). Pour tout entier \(r\), en substituant le triplet \((m, rb - C, b)\) dans (1), on obtient \(f(r) = f(r - \eta)\). En partant de \(m\) et par récurrence dans les deux sens, on en déduit que \(f(r) = C\) pour tout entier \(r\). Tout rationnel \(y\) s'écrit \(y = \frac{p}{q}\) avec \((p, q) \in \mathbb{Z} \times \mathbb{Z}_{>0}\), et en substituant \((C - p, p - C, q)\) dans (1), on obtient \(f(y) = f(0) = C\). Donc \(f\) est la fonction constante égale à \(C\).
Cas 2 : \(f(m) = m\) pour tout entier \(m\). Le cas particulier \(b = 1\) de (1) prend alors une forme particulièrement simple :
Posons \(f\left(\frac{1}{2}\right) = \omega\) et procédons en trois étapes.
Étape A : \(\omega \in \{0, 1\}\). Si \(\omega \leq 0\), on peut substituer \(\left(\frac{1}{2}, -\omega, 1 - 2\omega\right)\) dans (1), ce qui donne \(0 = f(0) = f\left(\frac{1}{2}\right) = \omega\). Dans le cas contraire \(\omega \geq 1\), on raisonne de même avec le triplet \(\left(\frac{1}{2}, \omega - 1, 2\omega - 1\right)\).
Étape B : \(f(x) = \omega\) pour tout rationnel \(x\) avec \(0 < x < 1\). Supposons le contraire, et prenons un rationnel \(\frac{a}{b} \in (0, 1)\) avec \(b\) minimal tel que \(f\left(\frac{a}{b}\right) \neq \omega\). Évidemment \(\operatorname{pgcd}(a, b) = 1\) et \(b \geq 2\). Si \(b\) est pair, alors \(a\) est impair, et l'on peut substituer \(\left(\frac{1}{2}, \frac{a-1}{2}, \frac{b}{2}\right)\) dans (1), ce qui donne
Or \(0 \leq \frac{a-1}{2} < \frac{b}{2}\). Dans les deux cas \(\omega = 0\) et \(\omega = 1\), le membre de gauche de (3) vaut donc \(\omega\), soit par minimalité de \(b\), soit parce que \(f(\omega) = \omega\). Contradiction.
Donc \(b\) est impair, \(b = 2k + 1\) avec \(k \geq 1\). En appliquant (1) à \(\left(\frac{1}{2}, k, b\right)\), on obtient
Comme \(a\) et \(b\) sont premiers entre eux, il existe des entiers \(r \in \{1, 2, \ldots, b\}\) et \(m\) tels que \(ra - mb = k + \omega\) (Bézout). On a en fait \(1 \leq r < b\), puisque le membre de droite n'est pas multiple de \(b\). Si \(m\) était négatif, on aurait \(ra - mb > b \geq k + \omega\), ce qui est absurde. De même, \(m \geq r\) donnerait \(ra - mb < br - br = 0\), ce qui est également impossible ; donc \(0 \leq m \leq r - 1\).
Substituons enfin \(\left(\frac{k + \omega}{b}, m, r\right)\) dans (1) et utilisons (4) :
Mais, comme ci-dessus, le membre de gauche vaut \(\omega\) par minimalité de \(b\). Cette contradiction conclut l'étape B.
Étape C. Si \(\omega = 0\), alors \(f(x) = \lfloor x \rfloor\) pour tout rationnel \(x\) avec \(0 \leq x < 1\), donc, par (2), pour tout rationnel \(x\). De même, si \(\omega = 1\), alors \(f(x) = \lceil x \rceil\) pour tout \(x \in \mathbb{Q}\). Le problème est résolu. \(\blacksquare\)
Remarque 1. Voici un autre traitement des étapes B et C du second cas, dû à l'auteur du problème. Notons \([\cdot]\) la partie entière si \(\omega = 0\) et la partie entière supérieure si \(\omega = 1\). On veut montrer que \(f(x) = [x]\) pour tout \(x \in \mathbb{Q}\) ; grâce à l'étape A et à (2), on le sait déjà quand \(2x \in \mathbb{Z}\). En appliquant (1) à \((2x, 0, 2)\), on obtient
ce qui, par l'observation précédente, donne
Une récurrence facile montre alors
Supposons d'abord que \(x\) n'est pas entier mais s'écrit \(\frac{p}{q}\) avec \(p \in \mathbb{Z}\) et \(q \in \mathbb{Z}_{>0}\) tous deux impairs. Soit \(d\) l'ordre multiplicatif de \(2\) modulo \(q\) et \(m\) un grand entier. En prenant \(n = dm\) dans (6) et en utilisant (2), on obtient
Comme \(x\) n'est pas entier, la fonction \([\cdot]\) est continue en \(x\) ; en faisant tendre \(m\) vers l'infini, on obtient \(f(x) = [x]\). Pour conclure, il suffit de remarquer que si un \(y \in \mathbb{Q}\) vérifie \(f(y) = [y]\), alors (5) donne \(f\left(\frac{y}{2}\right) = f\left(\frac{[y]}{2}\right) = \left[\frac{[y]}{2}\right] = \left[\frac{y}{2}\right]\).
Solution 2¶
On donne ici un autre argument pour le second cas de la solution précédente. On utilise encore l'équation (2). Il s'ensuit que l'ensemble \(S\) des zéros de \(f\) contient, pour tout \(x \in \mathbb{Q}\), exactement un terme de la suite infinie \(\ldots, x - 2, x - 1, x, x + 1, x + 2, \ldots\)
Montrons ensuite que
Il suffit de substituer \(\left(\frac{p}{q}, p, q + 1\right)\) dans (1), ce qui donne \(f\left(\frac{p}{q + 1}\right) = f\left(\frac{p}{q}\right) = 0\).
On en déduit que
En effet, si \(x = \frac{p}{q}\) et \(y = \frac{r}{s}\) avec \(p, q, r, s \in \mathbb{Z}_{>0}\), alors \(ps > qr\), et (7) donne
Essentiellement le même argument montre que
Par (8) et (9), \(0 \in S \subseteq (-1, +1)\), donc le réel \(\alpha = \sup(S)\) existe et vérifie \(0 \leq \alpha \leq 1\).
Supposons qu'on ait en fait \(0 < \alpha < 1\). On a \(f(x) = 0\) pour \(x \in (0, \alpha) \cap \mathbb{Q}\) par (8), et \(f(x) = 1\) pour \(x \in (\alpha, 1) \cap \mathbb{Q}\) par (9) et (2). Soit \(K\) l'unique entier strictement positif tel que \(K\alpha < 1 \leq (K + 1)\alpha\). La première inégalité entraîne \(\alpha < \frac{1 + \alpha}{K + 1}\), donc il existe un rationnel \(x \in \left(\alpha, \frac{1 + \alpha}{K + 1}\right)\). En posant \(y = (K + 1)x - 1\) et en substituant \((y, 1, K + 1)\) dans (1), on obtient
Comme \(\alpha < x < 1\) et \(0 < y < \alpha\), cela se simplifie en
Mais comme \(0 < \frac{1}{K + 1} \leq \alpha\), ce n'est possible que si \(\alpha = \frac{1}{K + 1}\) et \(f(\alpha) = 1\). On obtient alors la contradiction
L'hypothèse \(0 < \alpha < 1\) est donc fausse, et \(\alpha \in \{0, 1\}\). Si \(\alpha = 0\), alors \(S \subseteq (-1, 0]\), d'où \(S = (-1, 0] \cap \mathbb{Q}\), ce qui donne \(f(x) = \lceil x \rceil\) pour tout \(x \in \mathbb{Q}\) par (2). De même, \(\alpha = 1\) entraîne \(S = [0, 1) \cap \mathbb{Q}\) et \(f(x) = \lfloor x \rfloor\) pour tout \(x \in \mathbb{Q}\). La solution est complète. \(\blacksquare\)
Remarque¶
Remarque 2. Il semble que toutes les solutions de ce problème séparent par une distinction de cas les solutions constantes des solutions non bornées, même si les « descriptions » des cas peuvent varier selon le travail fait au début. Par exemple, les deux cas peuvent aussi être « \(f\) est périodique sur les entiers » et « \(f\) n'est pas périodique sur les entiers ». Le cas qui mène aux solutions non bornées semble être le plus difficile.
Dans la plupart des approches, les cas menant aux fonctions \(x \mapsto \lfloor x \rfloor\) et \(x \mapsto \lceil x \rceil\) se traitent en parallèle, mais il peut être utile de savoir qu'une symétrie du problème échange ces deux fonctions : si \(f : \mathbb{Q} \to \mathbb{Z}\) vérifie (1), alors la fonction \(g : \mathbb{Q} \to \mathbb{Z}\) définie par \(g(x) = -f(-x)\) vérifie aussi (1). On aurait donc pu se limiter au cas \(\omega = 0\) dans la première solution et, une fois \(\alpha \in \{0, 1\}\) obtenu, au cas \(\alpha = 0\) dans la seconde.