Shortlist 2015, C1¶

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

Concepts : Principe extrémal · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2015 (avec solutions), p. 24 (page 25 du PDF)

Énoncé¶

In Lineland there are \(n \geq 1\) towns, arranged along a road running from left to right. Each town has a left bulldozer (put to the left of the town and facing left) and a right bulldozer (put to the right of the town and facing right). The sizes of the \(2n\) bulldozers are distinct. Every time when a right and a left bulldozer confront each other, the larger bulldozer pushes the smaller one off the road. On the other hand, the bulldozers are quite unprotected at their rears; so, if a bulldozer reaches the rear-end of another one, the first one pushes the second one off the road, regardless of their sizes.

Let \(A\) and \(B\) be two towns, with \(B\) being to the right of \(A\). We say that town \(A\) can sweep town \(B\) away if the right bulldozer of \(A\) can move over to \(B\) pushing off all bulldozers it meets. Similarly, \(B\) can sweep \(A\) away if the left bulldozer of \(B\) can move to \(A\) pushing off all bulldozers of all towns on its way.

Prove that there is exactly one town which cannot be swept away by any other one.

Indices : les idées clés

Observation de base : si \(T_i\) peut balayer \(T_j\), il peut balayer toutes les villes situées entre \(T_i\) et \(T_j\).
Principe extrémal : considérer le plus grand bulldozer (solutions 1 et 3), ou la ville la plus à gauche qui ne peut pas être balayée par la droite (solution 2).
Récurrence forte (solution 1) : le plus grand bulldozer permet de supprimer tout un côté sans changer le statut des autres villes.
Deux villes ne peuvent pas se balayer mutuellement : cela donnerait \(r_i > \ell_j > r_i\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (trois solutions et trois remarques).

Dans toutes les solutions, on note \(T_1, T_2, \ldots, T_n\) les villes de gauche à droite.

Solution 1¶

Observation. Si la ville \(T_i\) peut balayer la ville \(T_j\), alors \(T_i\) peut aussi balayer toutes les villes situées entre \(T_i\) et \(T_j\).

On démontre l'énoncé par récurrence forte sur \(n\). Le cas \(n = 1\) est évident.

Pour l'hérédité, remarquons d'abord que le bulldozer gauche de \(T_1\) et le bulldozer droit de \(T_n\) ne servent à rien : on les oublie. Parmi les \(2n - 2\) bulldozers restants, on choisit le plus grand. Sans perte de généralité, c'est le bulldozer droit d'une ville \(T_k\) avec \(k < n\).

Avec ce gros bulldozer, \(T_k\) peut balayer toutes les villes situées à sa droite. De plus, aucune de ces villes ne peut balayer \(T_k\) ; d'après l'observation, elles ne peuvent donc balayer aucune ville située à gauche de \(T_k\). Ainsi, si l'on supprime les villes \(T_{k+1}, T_{k+2}, \ldots, T_n\), aucune des villes restantes ne change de statut (balayable ou non par les autres).

L'hypothèse de récurrence, appliquée aux villes \(T_1, \ldots, T_k\), fournit une unique ville parmi elles qui ne peut pas être balayée. D'après ce qui précède, c'est aussi l'unique telle ville dans la situation initiale (les villes \(T_{k+1}, \ldots, T_n\) étant toutes balayées par \(T_k\)). \(\blacksquare\)

Solution 2¶

On garde la numérotation et l'observation de la solution 1. Notons \(\ell_i\) et \(r_i\) les tailles des bulldozers gauche et droit de \(T_i\). Deux villes \(T_i\) et \(T_j\) avec \(i < j\) ne peuvent pas se balayer l'une l'autre : cela donnerait \(r_i > \ell_j > r_i\).

Aucune ville ne peut balayer \(T_n\) par la droite. On peut donc choisir la ville \(T_k\) la plus à gauche qui ne peut pas être balayée par la droite. Aucune ville \(T_i\) avec \(i > k\) ne peut balayer une ville \(T_j\) avec \(j < k\), sinon (observation) \(T_i\) pourrait aussi balayer \(T_k\).

Montrons deux affirmations qui, ensemble, prouvent que \(T_k\) est l'unique ville qui ne peut pas être balayée.

Affirmation 1. \(T_k\) ne peut pas non plus être balayée par la gauche.

Preuve. Soit \(T_m\) une ville à gauche de \(T_k\). Par le choix de \(T_k\), \(T_m\) peut être balayée par la droite par une ville \(T_p\) avec \(p > m\). Comme on vient de le voir, \(p\) ne peut pas dépasser \(k\). D'autre part, \(T_m\) ne peut pas balayer \(T_p\) (deux villes ne se balaient pas mutuellement), donc a fortiori elle ne peut pas balayer \(T_k\) (qui est \(T_p\) ou se trouve au-delà). \(\square\)

Affirmation 2. Toute ville \(T_m\) avec \(m \neq k\) peut être balayée par une autre ville.

Preuve. Si \(m < k\), \(T_m\) peut être balayée par la droite, par le choix de \(T_k\). Supposons donc \(m > k\). Soit \(T_p\) la ville parmi \(T_k, T_{k+1}, \ldots, T_{m-1}\) dont le bulldozer droit est le plus grand. Montrons que \(T_p\) peut balayer \(T_m\). Sinon, \(r_p < \ell_q\) pour un certain \(q\) avec \(p < q \leq m\). Mais alors \(\ell_q\) est plus grand que tous les \(r_i\) pour \(k \leq i \leq m - 1\), donc \(T_q\) peut balayer \(T_k\) : cela contredit le choix de \(T_k\). \(\square\) \(\blacksquare\)

Solution 3¶

On montre séparément (i) qu'il existe une ville qui ne peut pas être balayée, et (ii) qu'il y en a au plus une. On utilise les deux observations des solutions précédentes.

(i) Supposons par l'absurde que toute ville puisse être balayée. Soit \(t_1\) la ville la plus à gauche ; pour \(k = 1, 2, \ldots\), on choisit par récurrence une ville \(t_{k+1}\) qui peut balayer \(t_k\). Montrons que pour tout \(k\), la ville \(t_{k+1}\) est à droite de \(t_k\) ; c'est une contradiction, puisque le nombre de villes est fini.

Par récurrence sur \(k\). Le cas \(k = 1\) est clair par le choix de \(t_1\). Supposons que pour tout \(j < k\), \(t_{j+1}\) est à droite de \(t_j\). Si \(t_{k+1}\) était à gauche de \(t_k\), elle serait située entre \(t_j\) et \(t_{j+1}\) (éventuellement confondue avec \(t_j\)) pour un certain \(j < k\). Alors \(t_{k+1}\) pourrait être balayée par \(t_{j+1}\), donc ne pourrait pas balayer \(t_{j+1}\) ; a fortiori, elle ne pourrait pas balayer \(t_k\) (qui est \(t_{j+1}\) ou se trouve au-delà). Contradiction.

(ii) Supposons par l'absurde que deux villes \(A\) et \(B\), avec \(A\) à gauche de \(B\), ne peuvent pas être balayées. Considérons le plus grand bulldozer \(b\) situé entre elles (en comptant le bulldozer droit de \(A\) et le bulldozer gauche de \(B\)). Sans perte de généralité, \(b\) est un bulldozer gauche ; il appartient alors à une ville située à droite de \(A\), et cette ville peut balayer \(A\) puisque rien ne l'en empêche. Contradiction. \(\blacksquare\)

Remarques¶

Remarque 1 (version par récurrence de la solution 2). Supposons qu'il existe une unique ville \(T_i\) qui ne peut pas être balayée parmi \(T_1, \ldots, T_{n-1}\). Il faut montrer que, parmi \(T_1, \ldots, T_n\), exactement une des villes \(T_i\) et \(T_n\) ne peut pas être balayée.

Si \(T_n\) ne peut pas balayer \(T_i\), il reste à voir que \(T_n\) peut être balayée par une autre ville ; cela se prouve comme dans le second paragraphe de la preuve de l'affirmation 2.
Si \(T_n\) peut balayer \(T_i\), elle peut balayer toutes les villes \(T_i, \ldots, T_{n-1}\), qui ne peuvent donc pas la balayer. Et aucune des villes \(T_1, \ldots, T_{i-1}\) ne peut balayer \(T_i\), donc aucune ne peut balayer \(T_n\).

Remarque 2 (une autre récurrence). Pour \(n > 1\), on trouve une ville qui peut être balayée par chacun de ses voisins (chaque ville a deux voisins, sauf les deux extrêmes) : un perdant. Il en existe un, car il y a \(n - 1\) paires de villes voisines et dans chacune exactement une ville peut balayer l'autre ; il y a donc une ville qui ne gagne dans aucune de ces paires. Un perdant peut être balayé, mais ne peut balayer aucune autre ville (ses voisins le protègent). On supprime un perdant, en proposant son bulldozer gauche à son voisin de droite (s'il existe) et son bulldozer droit à son voisin de gauche (s'il existe) ; une ville accepte la proposition si le bulldozer proposé est plus grand que le sien de même orientation. Ces bulldozers proposés sont inutiles en attaque (par définition d'un perdant) mais servent en défense, et protègent exactement les mêmes paires de villes restantes qu'avant la suppression. Par hypothèse de récurrence, la nouvelle configuration contient exactement une ville qui ne peut pas être balayée, et il en va donc de même de la configuration initiale.

Remarque 3 (énoncé original). Le comité de sélection a reformulé le problème. L'énoncé original était : on a un paquet de \(n\) cartes numérotées de \(1\) à \(n\) de bas en haut ; la carte \(i\) porte un nombre pair \(a_i\) sur sa face inférieure et un nombre impair \(b_i\) sur sa face supérieure. La carte \(i\) ouvre la carte \(j\) si \(i < j\) et \(b_i < a_k\) pour tout \(k = i+1, \ldots, j\) ; la carte \(i\) ferme la carte \(j\) si \(i > j\) et \(a_i < b_k\) pour tout \(k = i-1, i-2, \ldots, j\). Montrer que le paquet contient exactement une carte qui n'est ni ouverte ni fermée par une autre carte.