Shortlist 2011, A1¶
Domaine : Algèbre · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Équations diophantiennes : factorisation et encadrement
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 12 (page 13 du PDF)
Problème 1 de l'OIM 2011
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2011, où il était le problème 1 (jour 1).
Énoncé¶
Pour tout ensemble \(A = \{a_1, a_2, a_3, a_4\}\) de quatre entiers strictement positifs distincts, de somme \(s_A = a_1 + a_2 + a_3 + a_4\), on note \(p_A\) le nombre de couples \((i, j)\) avec \(1 \leq i < j \leq 4\) pour lesquels \(a_i + a_j\) divise \(s_A\). Parmi tous les ensembles de quatre entiers strictement positifs distincts, déterminer ceux pour lesquels \(p_A\) est maximal.
Énoncé original (anglais)
For any set \(A = \{a_1, a_2, a_3, a_4\}\) of four distinct positive integers with sum \(s_A = a_1 + a_2 + a_3 + a_4\), let \(p_A\) denote the number of pairs \((i, j)\) with \(1 \leq i < j \leq 4\) for which \(a_i + a_j\) divides \(s_A\). Among all sets of four distinct positive integers, determine those sets \(A\) for which \(p_A\) is maximal.
Indices : les idées clés
- Divisibilité : \(a_i + a_j \mid s_A\) si et seulement si \(a_i + a_j\) divise la somme des deux autres ; avec \(a_1 < a_2 < a_3 < a_4\), les paires \((a_2, a_4)\) et \((a_3, a_4)\) ne conviennent jamais, donc \(p_A \leq 4\).
- Système : \(p_A = 4\) donne \(a_1 + a_4 = a_2 + a_3\), \(m(a_1 + a_2) = a_3 + a_4\) et \(n(a_1 + a_3) = a_2 + a_4\) avec \(m > n \geq 2\).
- Encadrement : on obtient \(n = 2\), puis \((m + 7)a_1 = (5 - m)a_2\), donc \(m \in \{3, 4\}\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2011 (une solution).
Réponse : les ensembles de la forme \(\{d, 5d, 7d, 11d\}\) et \(\{d, 11d, 19d, 29d\}\), où \(d\) est un entier strictement positif. Pour tous ces ensembles, \(p_A = 4\).
Solution¶
Montrons d'abord que la valeur maximale de \(p_A\) est au plus \(4\). Sans perte de généralité, on peut supposer \(a_1 < a_2 < a_3 < a_4\). Pour toute paire d'indices \((i, j)\) avec \(1 \leq i < j \leq 4\), la somme \(a_i + a_j\) divise \(s_A\) si et seulement si \(a_i + a_j\) divise \(s_A - (a_i + a_j) = a_k + a_l\), où \(k\) et \(l\) sont les deux autres indices. Comme il y a \(6\) paires distinctes, il faut prouver qu'au moins deux d'entre elles ne vérifient pas cette condition. Ce sont les paires \((a_2, a_4)\) et \((a_3, a_4)\) : en effet, \(a_2 + a_4 > a_1 + a_3\) et \(a_3 + a_4 > a_1 + a_2\), donc \(a_2 + a_4\) et \(a_3 + a_4\) ne divisent pas \(s_A\). Cela prouve \(p_A \leq 4\).
Supposons maintenant \(p_A = 4\). Par l'argument précédent,
Il existe donc des entiers \(m\) et \(n\) avec \(m > n \geq 2\) tels que
En additionnant la première et la troisième équation, on obtient \(n(a_1 + a_3) = 2a_2 + a_3 - a_1\). Si \(n \geq 3\), alors \(n(a_1 + a_3) > 3a_3 > 2a_2 + a_3 > 2a_2 + a_3 - a_1\), une contradiction. Donc \(n = 2\). En multipliant par \(2\) la somme de la première et de la troisième équation, on obtient
tandis que la somme de la première et de la deuxième donne
En additionnant ces deux dernières équations, on obtient
Il s'ensuit que \(5 - m \geq 1\), car le membre de gauche et \(a_2\) sont strictement positifs. Comme \(m > n = 2\), l'entier \(m\) ne peut valoir que \(3\) ou \(4\). En remplaçant \((m, n)\) par \((3, 2)\) et \((4, 2)\) et en résolvant le système, on trouve les familles de solutions \(\{d, 5d, 7d, 11d\}\) et \(\{d, 11d, 19d, 29d\}\), où \(d\) est un entier strictement positif quelconque. \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2025 N2 ★☆☆☆☆ : Un koala traverse un tableau \(n \times n\) dont la case \((i, j)\) porte \(\gcd(i, j)\) feuilles : combien peut-il en manger au plus ?
- 2024 N1 ★☆☆☆☆ : Trouver les \(n\) tels que, pour chaque diviseur \(d\), soit \(d + 1\) divise \(n\), soit \(d + 1\) est premier.
- 2021 N3 ★★☆☆☆ : Pour quels \(n\) peut-on ordonner les diviseurs de façon que toutes les sommes partielles soient des carrés ?
- 2016 N4 ★★☆☆☆ : Quand \(n^k + mn^l + 1\) divise-t-il \(n^{k+l} - 1\) ? Deux familles seulement.