Shortlist 2019, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Brazil
Concepts : Partie entière et majorations · AM-GM et moyennes · Cauchy-Schwarz et lemme de Titu · Équations diophantiennes : factorisation et encadrement
Solution officielle : Shortlist officielle 2019 (avec solutions), section N6 (livret PDF)
Énoncé¶
Let \(H = \big\{\lfloor i\sqrt{2} \rfloor : i \in \mathbb{Z}_{>0}\big\} = \{1, 2, 4, 5, 7, \ldots\}\), and let \(n\) be a positive integer. Prove that there exists a constant \(C\) such that, if \(A \subset \{1, 2, \ldots, n\}\) satisfies \(|A| \geq C\sqrt{n}\), then there exist \(a, b \in A\) such that \(a - b \in H\). (Here \(\mathbb{Z}_{>0}\) is the set of positive integers, and \(\lfloor z \rfloor\) denotes the greatest integer less than or equal to \(z\).)
Indices : les idées clés
- Parties entière et fractionnaire : un entier \(d > 0\) est dans \(H\) si et seulement si \(\{d/\sqrt2\} > 1 - \frac{1}{\sqrt2}\) ; les parties fractionnaires \(\{a_i/\sqrt2\}\) des éléments de \(A\) sont alors rangées dans le même ordre que les \(a_i\) (solution 1).
- Minoration \(\{d/\sqrt2\} > \frac{1}{2d\sqrt2}\) : \(\sqrt2\) est mal approché par les rationnels, car \(d^2 - 2h^2\) est un entier non nul.
- Inégalité AM-HM (ou Cauchy-Schwarz) (solutions 1 et 2) : \(\sum \frac{1}{d_i} \geq \frac{(k-1)^2}{\sum d_i}\) donne \(k - 1 < \sqrt{2\sqrt2 - 2}\,\sqrt n\).
- Suite de Beatty complémentaire (solution 2) : \(J = \{\lfloor i(2+\sqrt2) \rfloor\}\) est le complémentaire de \(H\).
- Équation de Pell (solutions 3 et 4) : avec un ensemble \(B\) dont toutes les différences sont dans \(H\), les sommes \(a + b\) sont distinctes, donc \(|A| \cdot |B| \leq 2n\) ; on construit \(B\) grâce aux solutions de \(X^2 - 2Y^2 = \pm 1\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (quatre solutions et trois remarques).
Remarque commune. Dans toutes les solutions, on suppose que \(A\) est un ensemble tel que \(\{a - b : a, b \in A\}\) est disjoint de \(H\), et l'on prouve que \(|A| < C\sqrt n\). On note \(\{x\}\) la partie fractionnaire de \(x\).
Solution 1¶
D'abord, un entier \(n > 0\) est dans \(H\) si et seulement si
En effet, \(n \in H\) si et seulement si \(0 < i\sqrt2 - n < 1\) pour un certain \(i \in \mathbb{Z}_{>0}\), autrement dit \(0 < i - n/\sqrt2 < 1/\sqrt2\), ce qui équivaut à (1) (avec \(i = \lceil n/\sqrt2 \rceil\)).
Écrivons \(A = \{a_1 < a_2 < \cdots < a_k\}\), où \(k = |A|\). L'ensemble des différences ne change pas si l'on translate \(A\) ; on peut donc supposer \(A \subseteq \{0, 1, \ldots, n-1\}\) avec \(a_1 = 0\).
D'après (1), \(\{a_i/\sqrt2\} < 1 - 1/\sqrt2\) pour tout \(i > 1\), puisque \(a_i - a_1 \notin H\). De plus, on a nécessairement \(\{a_i/\sqrt2\} < \{a_j/\sqrt2\}\) dès que \(i < j\) : sinon on aurait
et comme alors \(\{(a_j - a_i)/\sqrt2\} = \{a_j/\sqrt2\} - \{a_i/\sqrt2\} + 1\), on obtiendrait \(\{(a_j - a_i)/\sqrt2\} > 1/\sqrt2 > 1 - 1/\sqrt2\), ce qui contredit (1).
On a donc une suite \(0 = a_1 < a_2 < \cdots < a_k < n\) avec
On utilise le fait suivant : pour tout entier \(d > 0\),
En effet, soit \(h = \lfloor d/\sqrt2 \rfloor\), de sorte que \(\{d/\sqrt2\} = d/\sqrt2 - h\). Alors
car le numérateur est un entier strictement positif. Comme \(d/\sqrt2 + h < 2d/\sqrt2\), l'inégalité (2) en découle.
Posons \(d_i = a_{i+1} - a_i\) pour \(1 \leq i < k\). Alors \(\{a_{i+1}/\sqrt2\} - \{a_i/\sqrt2\} = \{d_i/\sqrt2\}\), et
La première inégalité vient de \(\{a_k/\sqrt2\} < 1 - 1/\sqrt2\) (la somme télescope), la deuxième de (2), la troisième d'une application directe de l'inégalité entre moyennes arithmétique et harmonique (ou de Cauchy-Schwarz), et la quatrième de \(\sum_i d_i = a_k < n\).
En réarrangeant, on obtient
ce qui fournit la majoration voulue de \(k\). \(\blacksquare\)
Solution 2¶
Soit \(\alpha = 2 + \sqrt2\), de sorte que \(\frac1\alpha + \frac{1}{\sqrt2} = 1\). Ainsi \(J = \{\lfloor i\alpha \rfloor : i \in \mathbb{Z}_{>0}\}\) est la suite de Beatty complémentaire de \(H\) (autrement dit, \(H\) et \(J\) sont disjoints et \(H \cup J = \mathbb{Z}_{>0}\)).
Écrivons \(A = \{a_1 < a_2 < \cdots < a_k\}\). Si \(A\) n'a aucune différence dans \(H\), toutes ses différences sont dans \(J\), et l'on peut écrire \(a_i - a_1 = \lfloor \alpha b_i \rfloor\) avec \(b_i\) entier (et \(b_1 = 0\)).
Pour \(j > i\), on a \(a_j - a_i = \lfloor \alpha b_j \rfloor - \lfloor \alpha b_i \rfloor\). Comme \(a_j - a_i \in J\), on a aussi \(a_j - a_i = \lfloor \alpha t \rfloor\) pour un certain entier \(t > 0\). Donc \(\lfloor \alpha t \rfloor = \lfloor \alpha b_j \rfloor - \lfloor \alpha b_i \rfloor\). Le membre de droite vaut \(\lfloor \alpha(b_j - b_i) \rfloor\) ou \(\lfloor \alpha(b_j - b_i) \rfloor + 1\), et ce dernier n'appartient pas à \(J\) car \(\alpha > 2\). (Le livret écrit \(\lfloor \alpha(b_j - b_i) \rfloor - 1\) ; il faut lire \(+1\), l'argument restant le même.) Donc \(t = b_j - b_i\) et
Posons \(d_i = b_{i+1} - b_i\) pour \(1 \leq i < k\). En sommant (télescopage),
c'est-à-dire \(\sum_i \{\alpha d_i\} < 1\). On a aussi
donc \(\sum_i d_i \leq n/\alpha\).
Avec ces inégalités, un argument analogue à (3), qui utilise \(\{\alpha d\} = \{d\sqrt2\} > 1/(2d\sqrt2)\) pour tout entier \(d > 0\), donne
ce qui se réarrange à nouveau en \(\sqrt{2\sqrt2 - 2} \cdot \sqrt n > k - 1\). \(\blacksquare\)
Solution 3¶
On pose encore \(J = \mathbb{Z}_{>0} \setminus H\), de sorte que toutes les différences entre éléments de \(A\) sont dans \(J\).
Observation. Si \(B \subseteq \{1, 2, \ldots, n\}\) est un ensemble dont toutes les différences sont dans \(H\), alors \(|A| \cdot |B| \leq 2n\).
En effet, deux sommes \(a + b\) avec \(a \in A\), \(b \in B\) sont toujours différentes : sinon \(a_1 + b_1 = a_2 + b_2\), d'où \(|a_1 - a_2| = |b_2 - b_1|\), le membre de gauche étant dans \(J\) et celui de droite dans \(H\). L'ensemble \(\{a + b : a \in A, b \in B\}\) a donc \(|A| \cdot |B|\) éléments, tous au plus égaux à \(2n\), d'où l'inégalité.
Il suffit donc de construire un ensemble \(B\), dont toutes les différences sont dans \(H\), de taille au moins \(C'\sqrt n\) pour une constante \(C' > 0\).
Pour cela, on utilise des faits bien connus sur l'équation de Pell négative \(X^2 - 2Y^2 = -1\) : elle a une infinité de solutions, et les valeurs de \(X\) sont données par la récurrence \(X_1 = 1\), \(X_2 = 7\), \(X_m = 6X_{m-1} - X_{m-2}\). On peut donc choisir une solution avec \(\sqrt n/6 < X \leq \sqrt n\).
Montrons qu'on peut prendre \(B = \{X, 2X, \ldots, \lfloor \frac13 \sqrt n \rfloor X\}\). On a
donc
d'où \(\{X/\sqrt2\} > 1 - 3/\sqrt{2n}\). Précision ajoutée : pour \(1 \leq i \leq \frac13\sqrt n\), on a alors \(\{iX/\sqrt2\} = 1 - i\,(Y - X/\sqrt2) > 1 - \frac{\sqrt n}{3} \cdot \frac{3}{\sqrt{2n}} = 1 - \frac{1}{\sqrt2}\). Avec (1), cela montre que toutes les différences entre éléments de \(B\) (qui sont de la forme \(iX\)) sont dans \(H\). Comme \(|B| = \lfloor \frac13\sqrt n \rfloor\), on obtient \(|A| \leq 2n/|B|\), qui est bien de l'ordre de \(\sqrt n\). \(\blacksquare\)
Solution 4¶
Comme dans la solution 3, on construit un grand ensemble \(B \subseteq \{1, 2, \ldots, n\}\) dont toutes les différences sont dans \(H\).
Soit \(Y\) une solution de l'équation de type Pell \(X^2 - 2Y^2 = \pm 1\) ; ces solutions sont données par la récurrence \(Y_1 = 1\), \(Y_2 = 2\), \(Y_m = 2Y_{m-1} + Y_{m-2}\), de sorte qu'on peut choisir \(Y\) avec \(n/(3\sqrt2) < Y \leq n/\sqrt2\). De plus, il est connu que, pour un tel \(Y\) et pour \(1 \leq x < Y\),
si \(X^2 - 2Y^2 = 1\), et
si \(X^2 - 2Y^2 = -1\). (Le texte du livret dont nous disposons porte \(Y/\sqrt2\) au membre de droite ; il faut lire \(Y\sqrt2\).) C'est une traduction du fait que \(X/Y\) est une meilleure approximation rationnelle de \(\sqrt2\), par excès dans le premier cas et par défaut dans le second. (Le livret écrit « par défaut dans le premier cas et par excès dans le second » ; or \(X^2 = 2Y^2 + 1\) donne \(X/Y > \sqrt2\).)
Considérons la suite \(\{\sqrt2\}, \{2\sqrt2\}, \ldots, \{(Y-1)\sqrt2\}\). Le théorème d'Erdős–Szekeres affirme que cette suite possède une sous-suite monotone ayant au moins \(\sqrt{Y - 2} + 1 > \sqrt Y\) termes ; si cette sous-suite est décroissante, le livret indique qu'on peut se ramener (grâce à (4) ou (5)) à une sous-suite croissante. (Remarque de la rédaction : la symétrie \(x \mapsto Y - x\) renverse à la fois l'ordre des indices et celui des parties fractionnaires, donc transforme une sous-suite décroissante en une sous-suite encore décroissante ; ce point du livret ne semble pas justifié tel quel, et nous ne le complétons pas.) Notons la sous-suite croissante \(\{y_1\sqrt2\} < \{y_2\sqrt2\} < \cdots < \{y_t\sqrt2\}\), avec \(y_1 < y_2 < \cdots < y_t\) et \(t > \sqrt Y\).
Posons alors \(B = \{\lfloor y_i \sqrt2 \rfloor : 1 \leq i \leq t\}\). Pour \(i < j\), on a
car l'inégalité correspondante entre parties fractionnaires est vraie par le choix de l'ordre des \(\{y_i\sqrt2\}\). Toutes les différences entre éléments de \(B\) sont donc dans \(H\). Comme \(|B| > \sqrt Y > \sqrt n / \sqrt{3\sqrt2}\), c'est l'ensemble voulu, et l'on conclut par l'observation de la solution 3. \(\blacksquare\)
Remarques¶
Remarque 1 (sur les solutions 1 et 2). L'utilisation des suites de Beatty dans la solution 2 est essentiellement une façon de contourner (1). Les solutions 1 et 2 utilisent toutes deux le fait que \(\sqrt2 < 2\) ; l'énoncé resterait vrai sans cette propriété (par exemple si l'on remplaçait \(\sqrt2\) par \(\alpha\)), mais un argument du type des solutions 1 ou 2 serait plus compliqué.
Remarque 2 (optimalité de la constante). Certaines idées de la solution 3 permettent de montrer que la constante \(C = \sqrt{2\sqrt2 - 2}\) des solutions 1 et 2 est optimale : il existe des valeurs de \(n\) arbitrairement grandes et des ensembles \(A_n \subseteq \{1, \ldots, n\}\) de taille environ \(C\sqrt n\) dont toutes les différences sont dans \(J\). Pour cela, on prend une solution assez grande de l'équation de Pell \(X^2 - 2Y^2 = 1\), de sorte que \(\{X/\sqrt2\} \approx 1/(2X\sqrt2)\). Les parties fractionnaires \(\{iX/\sqrt2\}\) pour \(1 \leq i \leq \lfloor 2X\sqrt2\,(1 - 1/\sqrt2) \rfloor\) sont alors toutes inférieures à \(1 - 1/\sqrt2\), donc, par (1), tous ces entiers \(iX\) sont dans \(J\). En posant \(n \approx 2X^2\sqrt2\,(1 - 1/\sqrt2)\), l'ensemble \(A = \{iX : i \leq \lfloor 2X\sqrt2\,(1 - 1/\sqrt2) \rfloor\}\) a environ \(2X\sqrt2\,(1 - 1/\sqrt2)\) éléments, tous au plus égaux à \(n\), toutes ses différences sont dans \(J\), et \(|A| \approx C\sqrt n\) avec \(C = \sqrt{2\sqrt2 - 2}\).
Remarque 3. Toute solution doit utiliser le fait que \(\sqrt2\) est mal approché par les rationnels, directement ou implicitement (par exemple via les équations de type Pell). Si \(\sqrt2\) était remplacé par un nombre \(\theta\) ayant de très bonnes approximations rationnelles (par défaut), un argument du type de la solution 3 donnerait de longues progressions arithmétiques (de premier terme \(0\)) dans \(\{\lfloor i\theta \rfloor : 0 \leq i < n\}\) pour certaines valeurs de \(n\).