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é

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).

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\).

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\)