Aller au contenu

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,

\[a_1 + a_4 \mid a_2 + a_3 \text{ et } a_2 + a_3 \mid a_1 + a_4, \qquad a_1 + a_2 \mid a_3 + a_4 \text{ et } a_3 + a_4 \nmid a_1 + a_2, \qquad a_1 + a_3 \mid a_2 + a_4 \text{ et } a_2 + a_4 \nmid a_1 + a_3.\]

Il existe donc des entiers \(m\) et \(n\) avec \(m > n \geq 2\) tels que

\[\begin{cases} a_1 + a_4 = a_2 + a_3, \\ m(a_1 + a_2) = a_3 + a_4, \\ n(a_1 + a_3) = a_2 + a_4. \end{cases}\]

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

\[6a_1 + 2a_3 = 4a_2,\]

tandis que la somme de la première et de la deuxième donne

\[(m + 1)a_1 + (m - 1)a_2 = 2a_3.\]

En additionnant ces deux dernières équations, on obtient

\[(m + 7)a_1 = (5 - m)a_2.\]

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.