Shortlist 2018, C4¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Iran
Concepts : Principe extrémal
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).
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
Une pyramide anti-Pascal est un ensemble fini de nombres disposés en triangle : la première ligne contient un nombre, la deuxième deux nombres, la troisième trois nombres, et ainsi de suite ; et, sauf pour les nombres de la ligne du bas, chaque nombre est égal à la valeur absolue de la différence des deux nombres situés juste en dessous. Par exemple, le triangle ci-dessous est une pyramide anti-Pascal à quatre lignes, dans laquelle chaque entier de \(1\) à \(1 + 2 + 3 + 4 = 10\) apparaît exactement une fois :
Peut-on former une pyramide anti-Pascal à \(2018\) lignes, utilisant chaque entier de \(1\) à \(1 + 2 + \cdots + 2018\) exactement une fois ?
Énoncé original (anglais)
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:
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 ci-dessous). 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) 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,
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
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.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2020 N5 ★★★☆☆ : Trouver les fonctions additives sur les produits, à valeurs entières, symétriques sur une infinité d'intervalles \([0, n]\).
- 2014 C5 ★★★☆☆ · OIM P6 : Parmi \(n\) droites, on peut en colorier \(\lceil \sqrt{n/2} \rceil\) en bleu sans qu'aucune région bornée ait un bord tout bleu.
- 2024 C7 ★★★★☆ · OIM P3 : Chaque terme compte les apparitions du précédent : l'une des deux sous-suites de parité finit par être périodique.
- 2023 A6 ★★★★☆ · OIM P3 : Trouver les suites d'entiers pour lesquelles \(P(a_n)\) est le produit des \(k\) termes suivants, pour un polynôme unitaire de degré \(k\).