Shortlist 2006, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : United States of America
Concepts : Équations diophantiennes : factorisation et encadrement · Convexité, inégalité de Jensen, lissage · Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2006 (avec solutions), p. 60 (page 61 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(a > b > 1\) be relatively prime positive integers. Define the weight of an integer \(c\), denoted by \(w(c)\), to be the minimal possible value of \(\lvert x \rvert + \lvert y \rvert\) taken over all pairs of integers \(x\) and \(y\) such that
An integer \(c\) is called a local champion if \(w(c) \geq w(c \pm a)\) and \(w(c) \geq w(c \pm b)\).
Find all local champions and determine their number.
Indices : les idées clés
- Signes opposés : dans une représentation optimale d'un champion local, \(x\) et \(y\) sont de signes opposés ; on écrit \(c = ax - by\) avec \(x, y > 0\) (équation de Bézout).
- Caractérisation : \(c\) est un champion si et seulement si \(\lvert x \rvert < b\) et \(\lvert x \rvert + \lvert y \rvert = \left\lfloor \frac{a + b}{2} \right\rfloor\) ; la convexité de \(t \mapsto \lvert x + 1 - bt \rvert + \lvert y - at \rvert\) permet de prendre \(k = 1\).
- Comptage : deux progressions arithmétiques de \(b - 1\) termes et de raison \(a + b\), confondues si \(a\), \(b\) sont impairs et disjointes modulo \(a + b\) sinon.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2006 (une solution et une remarque).
Solution¶
Réponse : les champions locaux sont les nombres \(\pm(ax - by)\) avec \(0 < x < b\) et \(x + y = \left\lfloor \frac{a + b}{2} \right\rfloor\) ; il y en a \(b - 1\) si \(a\) et \(b\) sont impairs, et \(2(b - 1)\) sinon.
On appelle représentation de \(c\) un couple d'entiers \((x, y)\) tel que \(ax + by = c\) et que \(\lvert x \rvert + \lvert y \rvert\) ait la plus petite valeur possible, c'est-à-dire \(\lvert x \rvert + \lvert y \rvert = w(c)\).
Caractérisons les champions locaux par les trois observations suivantes.
Lemme 1. Si \((x, y)\) est une représentation d'un champion local \(c\), alors \(xy < 0\).
Preuve. Supposons par l'absurde que \(x \geq 0\) et \(y \geq 0\), et considérons les valeurs \(w(c)\) et \(w(c + a)\). Toutes les écritures des nombres \(c\) et \(c + a\) sous la forme \(au + bv\) s'écrivent
où \(k\) est un entier quelconque. Comme \(\lvert x \rvert + \lvert y \rvert\) est minimal, on a
pour tout \(k\). D'autre part, \(w(c + a) \leq w(c)\), donc il existe un \(k\) tel que
Alors
En comparant le premier et le troisième membre, on trouve \(k(a - b) + 1 \leq 0\), ce qui implique \(k < 0\). En comparant le deuxième et le quatrième, on obtient \(\lvert x + 1 - kb \rvert \leq \lvert x - kb \rvert\), donc \(kb > x\) ; c'est une contradiction.
Si \(x, y \leq 0\), on se ramène au cas précédent avec \(-c\), \(-x\) et \(-y\). \(\square\)
À partir de maintenant, on écrit \(c = ax - by\) au lieu de \(c = ax + by\), et l'on ne considère que les cas où \(x\) et \(y\) sont non nuls et de même signe. D'après le lemme 1, il n'y a pas de perte de généralité.
Lemme 2. Soit \(c = ax - by\) avec \(\lvert x \rvert + \lvert y \rvert\) minimal et \(x\), \(y\) de même signe. Le nombre \(c\) est un champion local si et seulement si \(\lvert x \rvert < b\) et \(\lvert x \rvert + \lvert y \rvert = \left\lfloor \frac{a + b}{2} \right\rfloor\).
Preuve. Sans perte de généralité, on peut supposer \(x, y > 0\). Les nombres \(c - a\) et \(c + b\) s'écrivent
et l'on a trivialement \(w(c - a) \leq (x - 1) + y < w(c)\) et \(w(c + b) \leq x + (y - 1) < w(c)\) dans tous les cas.
Supposons maintenant que \(c\) soit un champion local et considérons \(w(c + a)\). Comme \(w(c + a) \leq w(c)\), il existe un entier \(k\) tel que
Cette inégalité ne peut pas être vraie si \(k \leq 0\), donc \(k > 0\). Montrons qu'on peut choisir \(k = 1\). Considérons la fonction \(f(t) = \lvert x + 1 - bt \rvert + \lvert y - at \rvert - (x + y)\). C'est une fonction convexe, et l'on a \(f(0) = 1\) et \(f(k) \leq 0\). Par l'inégalité de Jensen, \(f(1) \leq \left(1 - \frac{1}{k}\right)f(0) + \frac{1}{k}f(k) < 1\). Mais \(f(1)\) est entier. Donc \(f(1) \leq 0\) et
Sachant que \(c = a(x - b) - b(y - a)\), on a aussi
En combinant ces deux inégalités, on obtient \(\lvert x + 1 - b \rvert \leq \lvert x - b \rvert\), ce qui équivaut à \(x < b\). En considérant \(w(c - b)\), on obtient de même \(y < a\).
Maintenant, \(\lvert x - b \rvert = b - x\), \(\lvert x + 1 - b \rvert = b - x - 1\) et \(\lvert y - a \rvert = a - y\), donc on a
Donc \(x + y = \left\lfloor \frac{a + b}{2} \right\rfloor\).
Pour la réciproque, supposons \(0 < x < b\) et \(x + y = \left\lfloor \frac{a + b}{2} \right\rfloor\). Comme \(a > b\), on a aussi \(0 < y < a\). Alors
et
donc \(c\) est bien un champion local. \(\square\)
Lemme 3. Soit \(c = ax - by\), avec \(x\) et \(y\) de même signe, \(\lvert x \rvert < b\), \(\lvert y \rvert < a\) et \(\lvert x \rvert + \lvert y \rvert = \left\lfloor \frac{a + b}{2} \right\rfloor\). Alors \(w(c) = x + y\).
Preuve. Par définition, \(w(c) = \min\{\lvert x - kb \rvert + \lvert y - ka \rvert : k \in \mathbb{Z}\}\). Si \(k \leq 0\), alors évidemment \(\lvert x - kb \rvert + \lvert y - ka \rvert \geq x + y\). Si \(k \geq 1\), alors
Donc \(w(c) = x + y\). \(\square\)
Les lemmes 1, 2 et 3 donnent ensemble que l'ensemble des champions locaux est
Notons \(C^+\) et \(C^-\) les deux ensembles engendrés par les expressions \(+(ax - by)\) et \(-(ax - by)\) respectivement. On voit facilement que ces deux ensembles sont des progressions arithmétiques de longueur \(b - 1\) et de raison \(a + b\).
Si \(a\) et \(b\) sont impairs, alors \(C^+ = C^-\), car \(a(-x) - b(-y) = a(b - x) - b(a - y)\) et \(x + y = \frac{a + b}{2}\) équivaut à \((b - x) + (a - y) = \frac{a + b}{2}\). Dans ce cas, il y a \(b - 1\) champions locaux.
Si \(a\) et \(b\) sont de parités différentes, la réponse est différente. Pour tous \(c_1 \in C^+\) et \(c_2 \in C^-\),
et
Le nombre \(a + b\) est impair et premier avec \(a\) ; les éléments de \(C^+\) et de \(C^-\) appartiennent donc à deux classes de restes différentes modulo \(a + b\). L'ensemble \(C\) est donc la réunion de deux progressions arithmétiques disjointes, et le nombre total de champions locaux est \(2(b - 1)\).
Le nombre de champions locaux est donc \(b - 1\) si \(a\) et \(b\) sont tous deux impairs, et \(2(b - 1)\) sinon. \(\blacksquare\)
Remarque¶
La question originale, telle que posée par le proposant, était : (a) montrer qu'il n'y a qu'un nombre fini de champions locaux ; (b) montrer qu'il existe au moins un champion local.