Exercice 3 — Batailles interminables

Sujet

amis jouent à la bataille avec \(n\) cartes numérotées de 1 à \(n\). Les cartes sont mélangées puis réparties en deux paquets, qui peuvent être de tailles différentes. Chaque joueur prend un paquet. Les tours de jeu se déroulent alors de la manière suivante, jusqu'à ce qu'un des joueurs (déclaré perdant) n'ait plus de cartes : Chaque joueur tire la carte du dessus de son paquet. Celui qui a tiré la carte avec le plus grand numéro remporte le pli : il prend les deux cartes et les replace en dessous de son propre paquet.
Remarquons que le joueur qui possède la carte numéro \(n\) ne peut jamais perdre.
Pour autant, gagnera-t-il systématiquement ? Encore faut-il que la partie se termine !

1. Tête la première. On ajoute temporairement la règle suivante : le joueur qui remporte un pli replace d'abord sa propre carte puis celle de son adversaire sous le paquet (la plus forte se retrouve donc au-dessus de la plus faible). Exemple : si une partie commence avec les paquets \(\begin{array}{ll}4 & \\ 4 \\ 3\end{array}\) et \(\begin{aligned} & 1 \\ & 2\end{aligned}\), alors le premier tour sera

\[ \left|\begin{array}{ll} 4 & 1 \\ 3 & 2 \\ & 5 \end{array}\right| \rightarrow\left|\begin{array}{ll} 3 & 2 \\ 4 & 5 \\ 1 & \end{array}\right| . \]

a. La partie de l'exemple se terminera-t-elle? Représenter les tours successifs en complétant le diagramme.
b. Une partie commence avec les paquets \(\frac{5}{3}\) et \(\frac{2}{4}\).

Quel sera l'état du jeu après 6 tours ? Après 2018 tours ? La partie se terminera-t-elle ?
c. Montrer que toutes les parties se terminent lorsque \(n \leq 4\).
d. Construire une partie sans fin pour \(n=7\). Généraliser à tout entier impair \(n \geq 5\).
e. Trouver une répartition des cartes conduisant à une partie sans fin pour \(n=10\).
2. Retour aux règles de base. Après chaque pli, les deux cartes peuvent être replacées dans un ordre quelconque.

Exemple : les tours \(\left|\begin{array}{ll}4 & 1 \\ 3 & 2\end{array}\right| \rightarrow\left|\begin{array}{ll}3 & 2 \\ 4 & 5 \\ 1 & \end{array}\right|\) et \(\left|\begin{array}{ll}4 & 1 \\ 3 & 2 \\ & 5\end{array}\right| \rightarrow\left|\begin{array}{ll}3 & 2 \\ 1 & 5 \\ 4 & \end{array}\right|\) sont tous les deux possibles.
On dira qu'une répartition est de type \(T\) s'il est possible de terminer la partie en choisissant convenablement, à chaque tour, l'ordre dans lequel les deux cartes sont replacées. Lorsque la partie est interminable (quels que soient les choix effectués), on dira que la répartition est de type \(I\).
a. Justifier qu'on ne peut pas passer en un tour d'une répartition de type I à une répartition de type \(T\).
b. Pour une répartition donnée, combien de répartitions sont possibles (au maximum) au tour précédent ? En déduire qu'on ne peut pas passer en un tour d'une répartition de type \(T\) à une répartition de type \(I\).
c. Démontrer enfin que toutes les répartitions sont de type \(T\).