Shortlist 2018, C3¶

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

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 26 (page 28 du PDF)

Énoncé¶

Let \(n\) be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of \(n + 1\) squares in a row, numbered \(0\) to \(n\) from left to right. Initially, \(n\) stones are put into square \(0\), and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with \(k\) stones, takes one of those stones and moves it to the right by at most \(k\) squares (the stone should stay within the board). Sisyphus' aim is to move all \(n\) stones to square \(n\).

Prove that Sisyphus cannot reach the aim in less than

\[\left\lceil \frac{n}{1} \right\rceil + \left\lceil \frac{n}{2} \right\rceil + \left\lceil \frac{n}{3} \right\rceil + \cdots + \left\lceil \frac{n}{n} \right\rceil\]

turns. (As usual, \(\lceil x \rceil\) stands for the least integer not smaller than \(x\).)

Indices : les idées clés

Choisir quelle pierre déplacer : les pierres étant indiscernables, on les numérote et on décide de toujours déplacer la pierre de plus grand numéro de la case choisie.
Majorer chaque pas : la pierre \(k\) ne partage alors sa case qu'avec des pierres de numéro inférieur, donc avance d'au plus \(k\) cases à chaque coup, et il lui faut au moins \(\lceil n/k \rceil\) coups.
Double comptage : compter les coups pierre par pierre et sommer sur \(k\).

Solutions

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

Solution¶

Les pierres sont indiscernables, et elles ont toutes la même position de départ et la même position d'arrivée. On peut donc, à chaque coup, prescrire quelle pierre de la case choisie est déplacée. On procède ainsi : on numérote les pierres de \(1\) à \(n\) et, à chaque coup, une fois la case choisie, Sisyphe déplace la pierre de plus grand numéro présente sur cette case.

De cette façon, quand la pierre \(k\) est déplacée depuis une case, cette case contient au plus \(k\) pierres (car toutes ont un numéro au plus égal à \(k\)). Par conséquent, à chaque coup, la pierre \(k\) avance d'au plus \(k\) cases. Comme son déplacement total vaut exactement \(n\), la pierre \(k\) doit être déplacée au moins \(\lceil n/k \rceil\) fois, pour tout \(k = 1, 2, \ldots, n\).

En comptant les coups pierre par pierre et en sommant sur \(k = 1, 2, \ldots, n\), le nombre total de coups est au moins

\[\left\lceil \frac{n}{1} \right\rceil + \left\lceil \frac{n}{2} \right\rceil + \cdots + \left\lceil \frac{n}{n} \right\rceil,\]

ce qui est l'estimation voulue. \(\blacksquare\)

Remarques¶

Remarque 1. La proposition originale comportait une seconde partie : pour quelles valeurs de \(n\) l'égalité peut-elle être atteinte ? La réponse est \(n = 1, 2, 3, 4, 5, 7\). Le comité de sélection a jugé cette partie moins adaptée à la compétition, pour des raisons techniques.