Aller au contenu

Shortlist 2018, C3

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

Concepts : Double comptage

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

Énoncé

Soit \(n\) un entier strictement positif donné. Sisyphe effectue une suite de tours sur un plateau formé de \(n + 1\) cases alignées, numérotées de \(0\) à \(n\) de gauche à droite. Au départ, \(n\) pierres sont posées sur la case \(0\), et les autres cases sont vides. À chaque tour, Sisyphe choisit une case non vide, contenant disons \(k\) pierres, prend l'une de ces pierres et la déplace vers la droite d'au plus \(k\) cases (la pierre doit rester sur le plateau). Le but de Sisyphe est d'amener les \(n\) pierres sur la case \(n\).

Montrer que Sisyphe ne peut pas atteindre son but en moins de

\[\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\]

tours. (Comme d'habitude, \(\lceil x \rceil\) désigne le plus petit entier supérieur ou égal à \(x\).)

Énoncé original (anglais)

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.

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2024 C3 ★★☆☆☆ : Des chevaliers en cercle échangent leurs places pour serrer la main de leur partenaire : combien d'échanges ?
  • 2016 C3 ★★☆☆☆ : Les sommets d'un \(n\)-gone régulier sont coloriés en trois couleurs, chacune en nombre impair : un triangle isocèle est tricolore.
  • 2016 C4 ★★☆☆☆ · OIM P2 : Pour quels \(n\) peut-on remplir un tableau \(n \times n\) de \(I\), \(M\), \(O\) équilibrés sur les lignes, colonnes et certaines diagonales ?
  • 2012 C3 ★★☆☆☆ : Coloriage d'un tableau \(999 \times 999\) : maximiser le nombre de triplets blanc-rouge-blanc en équerre.