Shortlist 2021, A6¶

Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : non indiqué

Solution officielle : Shortlist officielle 2021 (avec solutions), p. 21 (page 21 du PDF)

Problème 6 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 6 (jour 2).

Énoncé¶

Let \(A\) be a finite set of (not necessarily positive) integers, and let \(m \geq 2\) be an integer. Assume that there exist non-empty subsets \(B_1, B_2, B_3, \ldots, B_m\) of \(A\) whose elements add up to the sums \(m^1, m^2, m^3, \ldots, m^m\), respectively. Prove that \(A\) contains at least \(m/2\) elements.

Indices : les idées clés

Combinaisons à coefficients en base \(m\) : on considère les \(m^m\) sommes \(c_1 s_1 + \cdots + c_m s_m\) avec \(0 \leq c_i \leq m - 1\).
Principe des tiroirs : ces sommes s'écrivent aussi \(\alpha_1 a_1 + \cdots + \alpha_k a_k\) avec \(0 \leq \alpha_i \leq m(m-1)\), ce qui fait moins de \(m^m\) valeurs si \(k < m/2\) ; deux d'entre elles coïncident.
Unicité de l'écriture en base \(m\) : comme \(s_i = m^i\), deux combinaisons distinctes ne peuvent pas être égales.

Solutions

La solution ci-dessous suit la solution officielle de la Shortlist 2021 (une solution et deux remarques).

Solution¶

Soit \(A = \{a_1, \ldots, a_k\}\) et supposons au contraire que \(k = |A| < m/2\). Notons

\[s_i := \sum_{j :\, a_j \in B_i} a_j\]

la somme des éléments de \(B_i\). Par hypothèse, \(s_i = m^i\) pour \(i = 1, \ldots, m\).

Considérons les \(m^m\) expressions de la forme

\[f(c_1, \ldots, c_m) := c_1 s_1 + c_2 s_2 + \cdots + c_m s_m, \qquad c_i \in \{0, 1, \ldots, m - 1\} \text{ pour tout } i = 1, 2, \ldots, m.\]

Chaque nombre \(f(c_1, \ldots, c_m)\) est de la forme

\[\alpha_1 a_1 + \cdots + \alpha_k a_k, \qquad \alpha_i \in \{0, 1, \ldots, m(m - 1)\}\]

(chaque \(a_j\) apparaît dans au plus \(m\) des \(B_i\), avec un coefficient au plus \(m - 1\) à chaque fois). Il y a donc au plus

\[\left(m(m - 1) + 1\right)^k < m^{2k} < m^m\]

valeurs distinctes de nos expressions ; par le principe des tiroirs, deux d'entre elles (pour des \(m\)-uplets \((c_i)\) différents) coïncident.

Comme \(s_i = m^i\), cela contredit l'unicité de l'écriture des entiers positifs en base \(m\). \(\blacksquare\)

Remarques¶

Remarque 1. Pour d'autres suites de sommes des \(B_i\) à croissance rapide, le même argument fournit aussi des minorations de \(k = |A|\). Par exemple, si les sommes des \(B_i\) valent \(1!, 2!, 3!, \ldots, m!\), alors pour tout \(\varepsilon > 0\) fixé et \(m\) assez grand, on obtient \(k \geq (1/2 - \varepsilon)m\). La preuve utilise le fait que les combinaisons \(\sum c_i\, i!\) avec \(c_i \in \{0, 1, \ldots, i\}\) sont toutes distinctes.

Remarque 2. L'énoncé reste vrai si \(A\) est un ensemble de nombres réels (non nécessairement entiers) : la preuve ci-dessus fonctionne aussi dans le cas réel.