Shortlist 2013, C4

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Germany

Concepts : Principe des tiroirs · Principe extrémal · Double comptage

Solution officielle : Shortlist officielle 2013 (avec solutions), p. 27 (page 27 du PDF)

Énoncé

Let \(n\) be a positive integer, and let \(A\) be a subset of \(\{1, \ldots, n\}\). An \(A\)-partition of \(n\) into \(k\) parts is a representation of \(n\) as a sum \(n = a_1 + \cdots + a_k\), where the parts \(a_1, \ldots, a_k\) belong to \(A\) and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set \(\{a_1, a_2, \ldots, a_k\}\).

We say that an \(A\)-partition of \(n\) into \(k\) parts is optimal if there is no \(A\)-partition of \(n\) into \(r\) parts with \(r < k\). Prove that any optimal \(A\)-partition of \(n\) contains at most \(\sqrt[3]{6n}\) different parts.

Indices : les idées clés

• Principe extrémal : il suffit de trouver deux parties \(X\), \(Y\) de l'ensemble \(S\) des parts distinctes avec \(\lvert X \rvert < \lvert Y \rvert\) et la même somme ; on remplacerait \(Y\) par \(X\).
• Sommes strictement croissantes : pour chaque \(k\), on fait glisser les points vers la droite un par un et l'on obtient \(k(s - k) + 1\) sommes distinctes de parties à \(k\) éléments, toutes entre \(1\) et \(n\).
• Tiroirs : au total \(\frac{s(s^2 + 5)}{6} > \frac{s^3}{6} > n\) sommes, donc deux sont égales, pour des tailles différentes.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2013 (deux solutions et une remarque).

Solution 1

S'il n'y a pas de \(A\)-partition de \(n\), le résultat est vrai. Sinon, soit \(k_{\min}\) le nombre minimal de parts d'une \(A\)-partition de \(n\), et \(n = a_1 + \cdots + a_{k_{\min}}\) une partition optimale. Notons \(s\) le nombre de parts distinctes de cette partition ; on écrit \(S = \{a_1, \ldots, a_{k_{\min}}\} = \{b_1, \ldots, b_s\}\) avec des nombres deux à deux distincts \(b_1 < \cdots < b_s\) de \(A\).

Si \(s > \sqrt[3]{6n}\), on va montrer qu'il existe deux parties \(X\) et \(Y\) de \(S\) telles que \(\lvert X \rvert < \lvert Y \rvert\) et \(\sum_{x \in X} x = \sum_{y \in Y} y\). En retirant alors les éléments de \(Y\) de la partition et en y ajoutant ceux de \(X\), on obtient une \(A\)-partition de \(n\) en moins de \(k_{\min}\) parts, ce qui est la contradiction voulue.

Pour tout entier \(k\) avec \(1 \leq k \leq s\), considérons la partie à \(k\) éléments

\[S_{1,0}^k := \{b_1, \ldots, b_k\},\]

ainsi que les parties à \(k\) éléments suivantes de \(S\) :

\[S_{i,j}^k := \{b_1, \ldots, b_{k-i}, \; b_{k-i+j+1}, \; b_{s-i+2}, \ldots, b_s\}, \qquad i = 1, \ldots, k, \quad j = 1, \ldots, s - k.\]

En représentant les éléments de \(S\) par une suite de points rangés dans l'ordre croissant, et une partie de \(S\) en noircissant les points correspondants, on a

\[S_{i,j}^k = \underbrace{\bullet \bullet \cdots \bullet}_{k - i} \; \underbrace{\circ \circ \cdots \circ}_{j} \; \bullet \; \underbrace{\circ \circ \cdots \circ}_{s - k - j} \; \underbrace{\bullet \bullet \cdots \bullet}_{i - 1}.\]

Notons \(\Sigma_{i,j}^k\) la somme des éléments de \(S_{i,j}^k\). Clairement, \(\Sigma_{1,0}^k\) est la plus petite somme d'une partie de \(S\) à \(k\) éléments. Ensuite, pour tous les indices convenables \(i\) et \(j\),

\[\Sigma_{i,j}^k = \Sigma_{i,j+1}^k + b_{k-i+j+1} - b_{k-i+j+2} < \Sigma_{i,j+1}^k \quad \text{et} \quad \Sigma_{i,s-k}^k = \Sigma_{i+1,1}^k + b_{k-i} - b_{k-i+1} < \Sigma_{i+1,1}^k.\]

Donc

\[1 \leq \Sigma_{1,0}^k < \Sigma_{1,1}^k < \Sigma_{1,2}^k < \cdots < \Sigma_{1,s-k}^k < \Sigma_{2,1}^k < \cdots < \Sigma_{2,s-k}^k < \Sigma_{3,1}^k < \cdots < \Sigma_{k,s-k}^k \leq n.\]

Sur le dessin : on part des \(k\) points les plus à gauche noircis. À chaque étape, on cherche le point noirci le plus à droite qui peut avancer d'un cran vers la droite, et on l'avance. On continue jusqu'à ce que les \(k\) points les plus à droite soient noircis. Les sommes correspondantes augmentent clairement.

Pour chaque \(k\), on a trouvé \(k(s - k) + 1\) entiers distincts de la forme \(\Sigma_{i,j}^k\) entre \(1\) et \(n\). En faisant varier \(k\), le nombre total d'entiers considérés est

\[\sum_{k=1}^{s} \big(k(s - k) + 1\big) = s \cdot \frac{s(s + 1)}{2} - \frac{s(s + 1)(2s + 1)}{6} + s = \frac{s(s^2 + 5)}{6} > \frac{s^3}{6} > n.\]

Comme ils sont entre \(1\) et \(n\), deux d'entre eux au moins sont égaux, par le principe des tiroirs. Il existe donc \(1 \leq k < k' \leq s\) et \(X = S_{i,j}^k\), \(Y = S_{i',j'}^{k'}\) tels que

\[\sum_{x \in X} x = \sum_{y \in Y} y, \quad \text{mais} \quad \lvert X \rvert = k < k' = \lvert Y \rvert,\]

comme voulu. Le résultat suit. \(\blacksquare\)

Solution 2

Supposons au contraire l'énoncé faux, et choisissons le plus petit \(n\) pour lequel il est faux. Il existe donc un ensemble \(A \subseteq \{1, \ldots, n\}\) et une \(A\)-partition optimale \(n = a_1 + \cdots + a_{k_{\min}}\) de \(n\) qui contredit l'énoncé, où \(k_{\min}\) est le nombre minimal de parts d'une \(A\)-partition de \(n\). On définit à nouveau \(S = \{a_1, \ldots, a_{k_{\min}}\} = \{b_1, \ldots, b_s\}\) avec \(b_1 < \cdots < b_s\) ; par hypothèse, \(s > \sqrt[3]{6n} > 1\). Sans perte de généralité, \(a_{k_{\min}} = b_s\). On distingue deux cas.

Cas 1 : \(b_s \geq \frac{s(s-1)}{2} + 1\). Considérons la partition \(n - b_s = a_1 + \cdots + a_{k_{\min} - 1}\) ; c'est clairement une \(A\)-partition minimale de \(n - b_s\), avec au moins \(s - 1 \geq 1\) parts distinctes. De \(n < \frac{s^3}{6}\) on tire

\[n - b_s \leq n - \frac{s(s-1)}{2} - 1 < \frac{s^3}{6} - \frac{s(s-1)}{2} - 1 < \frac{(s - 1)^3}{6},\]

donc \(s - 1 > \sqrt[3]{6(n - b_s)}\), ce qui contredit le choix de \(n\).

Cas 2 : \(b_s \leq \frac{s(s-1)}{2}\). Posons \(b_0 = 0\), \(\Sigma_{0,0} = 0\), et \(\Sigma_{i,j} = b_1 + \cdots + b_{i-1} + b_j\) pour \(1 \leq i \leq j < s\). Il y a \(\frac{s(s-1)}{2} + 1 > b_s\) telles sommes ; deux d'entre elles au moins, disons \(\Sigma_{i,j}\) et \(\Sigma_{i',j'}\) avec \((i, j) \neq (i', j')\), sont donc congrues modulo \(b_s\). Cela signifie que \(\Sigma_{i,j} - \Sigma_{i',j'} = r b_s\) pour un entier \(r\). Pour \(i \leq j < k < s\), on a

\[0 < \Sigma_{i,k} - \Sigma_{i,j} = b_k - b_j < b_s,\]

donc les indices \(i\) et \(i'\) sont distincts, et l'on peut supposer \(i > i'\). Ensuite, \(\Sigma_{i,j} - \Sigma_{i',j'} = (b_{i'} - b_{j'}) + b_j + b_{i'+1} + \cdots + b_{i-1}\) et \(b_{i'} \leq b_{j'}\) impliquent

\[-b_s < -b_{j'} < \Sigma_{i,j} - \Sigma_{i',j'} < (i - i') b_s,\]

donc \(0 \leq r \leq i - i' - 1\).

On peut donc retirer de la \(A\)-partition les \(i\) termes de \(\Sigma_{i,j}\) et les remplacer par les \(i'\) termes de \(\Sigma_{i',j'}\) et \(r\) termes égaux à \(b_s\), soit \(r + i' < i\) termes au total. On obtient une \(A\)-partition de \(n\) en moins de parts, une contradiction. \(\blacksquare\)

Remarque

La proposition d'origine contenait une seconde partie, montrant que l'estimation de l'énoncé a le bon ordre de grandeur :

Pour tout entier \(n \geq 1\), il existe un ensemble \(A\) et une \(A\)-partition optimale de \(n\) qui contient \(\lfloor \sqrt[3]{2n} \rfloor\) parts distinctes.

Le comité a retiré cet énoncé, qui semble moins adapté à la compétition ; en voici une esquisse de preuve. Soit \(k = \lfloor \sqrt[3]{2n} \rfloor - 1\). L'énoncé est évident pour \(n < 4\) ; on suppose donc \(n \geq 4\), d'où \(k \geq 1\). Soit \(h = \left\lfloor \frac{n - 1}{k} \right\rfloor\) ; on a \(h \geq \frac{n}{k} - 1\).

Soit \(A = \{1, \ldots, h\}\), et posons \(a_1 = h\), \(a_2 = h - 1\), \(\ldots\), \(a_k = h - k + 1\), et \(a_{k+1} = n - (a_1 + \cdots + a_k)\). On montre sans difficulté que \(a_k > a_{k+1} \geq 1\), ce qui prouve que

\[n = a_1 + \cdots + a_{k+1}\]

est une \(A\)-partition de \(n\) en \(k + 1\) parts distinctes. Comme \(kh < n\), toute \(A\)-partition de \(n\) a au moins \(k + 1\) parts. Notre \(A\)-partition est donc optimale, et elle a \(\lfloor \sqrt[3]{2n} \rfloor\) parts distinctes, comme voulu.