Shortlist 2018, C4¶

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

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

Problème 3 de l'OIM 2018

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2018, où il était le problème 3 (jour 1).

Énoncé¶

An anti-Pascal pyramid is a finite set of numbers, placed in a triangle-shaped array so that the first row of the array contains one number, the second row contains two numbers, the third row contains three numbers and so on; and, except for the numbers in the bottom row, each number equals the absolute value of the difference of the two numbers below it. For instance, the triangle below is an anti-Pascal pyramid with four rows, in which every integer from \(1\) to \(1 + 2 + 3 + 4 = 10\) occurs exactly once:

\[\begin{array}{ccccccc} & & & 4 & & & \\ & & 2 & & 6 & & \\ & 5 & & 7 & & 1 & \\ 8 & & 3 & & 10 & & 9 \end{array}\]

Is it possible to form an anti-Pascal pyramid with \(2018\) rows, using every integer from \(1\) to \(1 + 2 + \cdots + 2018\) exactly once?

Indices : les idées clés

Suivre le plus grand des deux nombres : depuis le sommet, on descend en prenant à chaque étape le plus grand voisin ; il vaut la somme \(a_1 + \cdots + a_k\) des « petits » voisins rencontrés.
Encadrement : comme la somme \(a_1 + \cdots + a_n\) ne dépasse pas \(1 + 2 + \cdots + n\), les \(a_k\) forment une permutation de \(1, \ldots, n\).
Principe extrémal : on choisit le plus grand des deux sous-triangles laissés de côté ; ses nombres sont tous \(> n\), ce qui force un nombre trop grand.

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2018 (une solution et une remarque).

Réponse : non, ce n'est pas possible.

Solution¶

Soit \(T\) une pyramide anti-Pascal à \(n\) lignes contenant chaque entier de \(1\) à \(1 + 2 + \cdots + n\), et soit \(a_1\) le nombre au sommet de \(T\) (voir la figure 1 du livret officiel). Les deux nombres situés sous \(a_1\) sont un certain \(a_2\) et \(b_2 = a_1 + a_2\) (le plus grand des deux). Les deux nombres sous \(b_2\) sont un certain \(a_3\) et \(b_3 = b_2 + a_3 = a_1 + a_2 + a_3\), et ainsi de suite jusqu'à la ligne du bas, où \(a_n\) et \(b_n = a_1 + a_2 + \cdots + a_n\) sont les deux voisins sous \(b_{n-1} = a_1 + \cdots + a_{n-1}\).

Les \(a_k\) sont \(n\) entiers strictement positifs deux à deux distincts, donc leur somme vaut au moins \(1 + 2 + \cdots + n\) ; or cette somme \(b_n\) ne dépasse pas le plus grand nombre de \(T\), qui est \(1 + 2 + \cdots + n\). Par conséquent, les \(a_k\) forment une permutation de \(1, 2, \ldots, n\).

Considérons maintenant (figure 2 du livret officiel) les deux sous-triangles « équilatéraux » de \(T\) dont les lignes du bas sont formées des nombres situés respectivement à gauche et à droite de la paire \(a_n, b_n\) dans la ligne du bas. (L'un d'eux peut être vide.) Leurs lignes du bas totalisent \(n - 2\) nombres, donc l'un d'eux, disons \(T'\) (principe extrémal : on prend le plus grand), a un côté de longueur \(\ell \geq \lceil (n-2)/2 \rceil\).

Comme \(T'\) obéit lui aussi à la règle anti-Pascal, le même raisonnement montre qu'il contient \(\ell\) entiers strictement positifs deux à deux distincts \(a'_1, a'_2, \ldots, a'_\ell\), où \(a'_1\) est son sommet et où \(a'_k\) et \(b'_k = a'_1 + a'_2 + \cdots + a'_k\) sont les deux voisins sous \(b'_{k-1}\), pour \(k = 2, 3, \ldots, \ell\). Les \(a_k\) sont tous situés hors de \(T'\) et forment une permutation de \(1, 2, \ldots, n\) : les \(a'_k\) sont donc tous strictement supérieurs à \(n\). Par conséquent,

\[b'_\ell \geq (n+1) + (n+2) + \cdots + (n+\ell) = \frac{\ell(2n + \ell + 1)}{2} \geq \frac{1}{2} \cdot \frac{n-2}{2}\left(2n + \frac{n-2}{2} + 1\right) = \frac{5n(n-2)}{8},\]

ce qui, pour \(n = 2018\), est strictement supérieur à \(1 + 2 + \cdots + n = \frac{n(n+1)}{2}\) (en effet \(5 \cdot 2016 / 8 = 1260 > 2019/2\)). C'est une contradiction, car aucun nombre de \(T\) ne dépasse \(\frac{n(n+1)}{2}\). \(\blacksquare\)

Remarques¶

Remarque 1. On peut améliorer légèrement l'estimation en remarquant que \(b'_\ell \neq b_n\). Cela donne

\[\frac{n(n+1)}{2} = b_n > b'_\ell \geq \frac{\lceil (n-2)/2 \rceil \left(2n + \lceil (n-2)/2 \rceil + 1\right)}{2},\]

donc \(n \leq 7\) si \(n\) est impair et \(n \leq 12\) si \(n\) est pair. Il semble que la plus grande pyramide anti-Pascal dont les nombres sont une permutation des entiers de \(1\) à \(1 + 2 + \cdots + n\) ait \(5\) lignes.