Shortlist 2021, N2¶
Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué
Concepts : Principe des tiroirs · Graphes : degrés, chemins, arbres
Solution officielle : Shortlist officielle 2021 (avec solutions), p. 69 (page 69 du PDF)
Problème 1 de l'OIM 2021
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2021, où il était le problème 1 (jour 1).
Énoncé¶
Let \(n \geq 100\) be an integer. The numbers \(n, n + 1, \ldots, 2n\) are written on \(n + 1\) cards, one number per card. The cards are shuffled and divided into two piles. Prove that one of the piles contains two cards such that the sum of their numbers is a perfect square.
Indices : les idées clés
- Principe des tiroirs : trois cartes dont les sommes deux à deux sont des carrés ; deux d'entre elles sont forcément dans le même tas.
- Un « triangle » de carrés (en langage de graphes : un cycle impair dans le graphe « la somme est un carré », qui ne peut pas être 2-colorié) : avec trois carrés consécutifs \((2k-1)^2, (2k)^2, (2k+1)^2\) on trouve \(a, b, c\) explicites.
- Recouvrir tous les \(n\) par des intervalles : chaque \(k\) convient pour un intervalle \(I_k\) de valeurs de \(n\), et ces intervalles se chevauchent pour \(k \geq 9\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (une solution et trois remarques).
Solution 1¶
Il suffit de trouver trois cartes portant des nombres \(a, b, c\) dont les sommes deux à deux \(a + b\), \(b + c\), \(a + c\) sont des carrés parfaits : par le principe des tiroirs, deux de ces trois cartes sont dans le même tas, et leur somme est un carré.
En choisissant les trois carrés consécutifs \((2k-1)^2\), \((2k)^2\), \((2k+1)^2\), on obtient le triplet
En effet \(a + b = 4k^2 - 4k + 1 = (2k-1)^2\), \(a + c = 4k^2 = (2k)^2\) et \(b + c = 4k^2 + 4k + 1 = (2k+1)^2\) ; ces trois nombres sont distincts pour \(k \geq 1\).
Il faut que ces trois nombres soient entre \(n\) et \(2n\), c'est-à-dire trouver \(k\) tel que
Un \(k\) donné convient donc pour tous les entiers \(n\) de l'intervalle
Pour \(k \geq 9\), les intervalles \(I_k\) et \(I_{k+1}\) se chevauchent ou se touchent (aucun entier n'est oublié entre les deux), car
ce qui est vrai pour \(k \geq 9\). Comme \(I_9 = [99, 126]\), les entiers de \(I_9 \cup I_{10} \cup \cdots\) sont exactement tous les entiers \(n \geq 99\), ce qui prouve l'énoncé pour tout \(n \geq 99\), et en particulier pour \(n \geq 100\). \(\blacksquare\)
Remarques¶
Remarque 1 (approches valables seulement pour \(n\) grand). On peut prendre trois cartes \(70k^2\), \(99k^2\), \(126k^2\) : leurs sommes deux à deux \(169k^2 = (13k)^2\), \(196k^2 = (14k)^2\), \(225k^2 = (15k)^2\) sont des carrés, et il suffit de trouver \(k\) avec \(70k^2 \geq n\) et \(126k^2 \leq 2n\), ce qui est possible pour \(n\) assez grand.
Une autre approche montre par l'absurde que \(a\) et \(a - 2\) sont dans le même tas si \(n\) est assez grand et \(a\) assez proche de \(n\). Pour tout \(x\), deux termes voisins de la suite
ont pour somme un carré (\(x^2\), \((x+1)^2\), \((x+2)^2\), \((x+1)^2\)) ; ces termes alternent donc de tas. En choisissant \(x = \lfloor \sqrt{2a} \rfloor + 1\) et \(n\) assez grand, on en déduit que \(a\) et \(a - 2\) sont dans le même tas pour tout \(a \in [n + 2, 3n/2]\). C'est contradictoire, car il est facile de trouver deux nombres de même parité dans \([n + 2, 3n/2]\) dont la somme est un carré. Il reste ensuite à traiter séparément les petites valeurs de \(n\), ce qui semble assez technique.
Remarque 2. On aurait pu demander de prouver l'énoncé seulement pour \(n > 10^6\), ce qui dispense les solutions de la remarque 1 de la partie technique sur les petits \(n\). La formulation originale semble cependant meilleure, car la borne qu'elle donne sur \(n\) est presque optimale (voir la remarque suivante).
Remarque 3. L'énoncé est faux pour \(n = 98\). Contre-exemple : le premier tas contient les nombres pairs de \(98\) à \(126\), les nombres impairs de \(129\) à \(161\) et les nombres pairs de \(162\) à \(196\) (le second tas contient tous les autres).