Shortlist 2008, A6

Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : non indiqué

Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide

Solution officielle : Shortlist officielle 2008 (avec solutions), p. 15 (page 16 du PDF)

Énoncé

Let \(f : \mathbb{R} \to \mathbb{N}\) be a function which satisfies

\[f\left(x + \frac{1}{f(y)}\right) = f\left(y + \frac{1}{f(x)}\right) \qquad \text{for all } x, y \in \mathbb{R}. \tag{1}\]

Prove that there is a positive integer which is not a value of \(f\).

Indices : les idées clés

• Normalisation : on suppose \(f(\mathbb{R}) = \mathbb{N}\) et, par translation, \(f(0) = 1\) ; alors \(\{f(c + \frac{1}{n}) : n \in \mathbb{N}\} = \mathbb{N}\) pour tout \(c\).
• Translations rationnelles : \(f(u) = f(v)\) implique \(f(u + q) = f(v + q)\) pour tout rationnel \(q \geq 0\) ; d'où \(f\) est \(1\)-périodique sur les rationnels positifs et \(f(1/n) = n\).
• Bézout : avec \(f(\frac{1}{3} + \frac{1}{n}) = 1\) et \(\frac{1}{3} + \frac{1}{n} = \frac{s}{t}\), on trouve \(ks - lt = 1\) et \(f(1/t) = 1\), contredisant \(f(1/t) = t > 1\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution).

Solution

Supposons l'énoncé faux, c'est-à-dire \(f(\mathbb{R}) = \mathbb{N}\). Prouvons plusieurs propriétés de la fonction \(f\) pour aboutir à une contradiction.

Remarquons d'abord qu'on peut supposer \(f(0) = 1\). En effet, soit \(a \in \mathbb{R}\) tel que \(f(a) = 1\), et considérons la fonction \(g(x) = f(x + a)\). En substituant \(x + a\) et \(y + a\) à \(x\) et \(y\) dans (1), on obtient

\[g\left(x + \frac{1}{g(y)}\right) = f\left(x + a + \frac{1}{f(y + a)}\right) = f\left(y + a + \frac{1}{f(x + a)}\right) = g\left(y + \frac{1}{g(x)}\right).\]

Donc \(g\) vérifie l'équation fonctionnelle (1), avec en plus \(g(0) = 1\). De plus, \(g\) et \(f\) ont le même ensemble de valeurs : \(g(\mathbb{R}) = f(\mathbb{R}) = \mathbb{N}\). Désormais, on suppose \(f(0) = 1\).

Affirmation 1. Pour tout \(c \in \mathbb{R}\) fixé, on a \(\left\{f\left(c + \frac{1}{n}\right) : n \in \mathbb{N}\right\} = \mathbb{N}\).

Preuve. L'équation (1) et \(f(\mathbb{R}) = \mathbb{N}\) donnent

\[f(\mathbb{R}) = \left\{f\left(x + \frac{1}{f(c)}\right) : x \in \mathbb{R}\right\} = \left\{f\left(c + \frac{1}{f(x)}\right) : x \in \mathbb{R}\right\} \subset \left\{f\left(c + \frac{1}{n}\right) : n \in \mathbb{N}\right\} \subset f(\mathbb{R}).\]

L'affirmation en découle. \(\square\)

On utilisera l'affirmation 1 dans les cas particuliers \(c = 0\) et \(c = 1/3\) :

\[\left\{f\left(\frac{1}{n}\right) : n \in \mathbb{N}\right\} = \left\{f\left(\frac{1}{3} + \frac{1}{n}\right) : n \in \mathbb{N}\right\} = \mathbb{N}. \tag{2}\]

Affirmation 2. Si \(f(u) = f(v)\) pour certains \(u, v \in \mathbb{R}\), alors \(f(u + q) = f(v + q)\) pour tout rationnel \(q \geq 0\). De plus, si \(f(q) = 1\) pour un certain rationnel \(q \geq 0\), alors \(f(kq) = 1\) pour tout \(k \in \mathbb{N}\).

Preuve. Pour tout \(x \in \mathbb{R}\), on a d'après (1)

\[f\left(u + \frac{1}{f(x)}\right) = f\left(x + \frac{1}{f(u)}\right) = f\left(x + \frac{1}{f(v)}\right) = f\left(v + \frac{1}{f(x)}\right).\]

Comme \(f(x)\) prend toutes les valeurs entières strictement positives, cela donne \(f(u + 1/n) = f(v + 1/n)\) pour tout \(n \in \mathbb{N}\). Soit \(q = k/n\) un rationnel strictement positif. Alors \(k\) répétitions de la dernière étape donnent

\[f(u + q) = f\left(u + \frac{k}{n}\right) = f\left(v + \frac{k}{n}\right) = f(v + q).\]

Soit maintenant \(f(q) = 1\) pour un certain rationnel \(q \geq 0\), et soit \(k \in \mathbb{N}\). Comme \(f(0) = 1\), la conclusion précédente donne successivement \(f(q) = f(2q)\), \(f(2q) = f(3q)\), …, \(f((k - 1)q) = f(kq)\), comme voulu. \(\square\)

Affirmation 3. L'égalité \(f(q) = f(q + 1)\) est vraie pour tout rationnel \(q \geq 0\).

Preuve. Soit \(m\) un entier strictement positif tel que \(f(1/m) = 1\). Un tel \(m\) existe d'après (2). La seconde partie de l'affirmation 2 avec \(q = 1/m\) et \(k = m\) donne \(f(1) = 1\).

Comme \(f(0) = f(1) = 1\), la première partie de l'affirmation 2 implique \(f(q) = f(q + 1)\) pour tout rationnel \(q \geq 0\). \(\square\)

Affirmation 4. L'égalité \(f\left(\frac{1}{n}\right) = n\) est vraie pour tout \(n \in \mathbb{N}\).

Preuve. Pour un rationnel \(q \geq 0\), on pose \(x = q\), \(y = 0\) dans (1) et l'on utilise l'affirmation 3 pour obtenir

\[f\left(\frac{1}{f(q)}\right) = f\left(q + \frac{1}{f(0)}\right) = f(q + 1) = f(q).\]

D'après (2), pour tout \(n \in \mathbb{N}\), il existe un \(k \in \mathbb{N}\) tel que \(f(1/k) = n\). En appliquant la dernière égalité avec \(q = 1/k\), on a

\[n = f\left(\frac{1}{k}\right) = f\left(\frac{1}{f(1/k)}\right) = f\left(\frac{1}{n}\right). \qquad \square\]

Nous sommes prêts à obtenir une contradiction. Soit \(n \in \mathbb{N}\) tel que \(f(1/3 + 1/n) = 1\). Un tel \(n\) existe d'après (2). Écrivons \(1/3 + 1/n = s/t\), où \(s, t \in \mathbb{N}\) sont premiers entre eux. Remarquons que \(t > 1\), puisque \(1/3 + 1/n\) n'est pas entier. Choisissons \(k, l \in \mathbb{N}\) tels que \(ks - lt = 1\).

Comme \(f(0) = f(s/t) = 1\), l'affirmation 2 implique \(f(ks/t) = 1\). Or \(f(ks/t) = f(1/t + l)\) ; d'autre part, \(f(1/t + l) = f(1/t)\) par \(l\) applications successives de l'affirmation 3. Enfin, \(f(1/t) = t\) d'après l'affirmation 4, ce qui mène à l'égalité impossible \(t = 1\). La solution est complète. \(\blacksquare\)