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)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

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