Exercice 3 — Énoncé — Olympiades 2016 Paris

Sujet

Un mathématicien décide de jouer avec des cartes. Il choisit \(N\) cartes (où \(N\) est un nombre entier fixé supérieur à 3 ) et avant de commencer, il forme un nombre arbitraire de piles de cartes de tailles variables. Son jeu consiste alors à effectuer le mouvement suivant : il prend une carte dans chaque pile et forme ainsi une nouvelle pile. Il répète alors ce mouvement indéfiniment. L'état du jeu est complètement décrit par la taille des piles et le nombre de piles de chaque taille.

Exemple : supposons qu'il ait décidé de jouer avec \(N=8\) cartes, et que l'état du jeu de départ soit le suivant : deux piles de trois cartes et une pile de deux cartes. Après un mouvement du jeu, il se retrouve dans l'état suivant : il a une pile de trois cartes (constituée des cartes qu'il a prises dans chacune des piles précédentes), deux piles de deux cartes (qui correspondent aux piles de trois cartes de l'état précédent) et une pile d'une carte (qui correspond à la pile de deux cartes de l'état précédent). Après un deuxième mouvement, il obtient une pile de quatre cartes, une pile de deux cartes et deux piles d'une carte.

On suppose dans cette question que le mathématicien joue avec \(N=9\) cartes. L'état initial est constitué d'une pile de quatre cartes, deux piles de deux cartes et une pile d'une carte. Déterminer les six premiers états du jeu. Quels auraient été les six premiers états si le mathématicien avait choisi de commencer à jouer avec trois piles de trois cartes?
Est-il possible d'obtenir l'état à \(N\) piles d'une carte au cours du jeu (après un nombre de mouvements strictement positif)?
Quand est-il possible de voir l'état à une pile de \(N\) cartes?

Le mathématicien s'arrête de jouer quand il voit un état déjà observé. Le mathématicien déclare qu'un état est olympique si après un mouvement l'état du jeu est identique.
4. Démontrer que le mathématicien finit toujours par s'arrêter de jouer.
5. Déterminer une infinité d'entiers \(N\) tels qu'il existe au moins un état initial tel que le mathématicien finisse de jouer dans un état olympique.
6. Le mathématicien décide finalement de jouer avec 2016 cartes. Montrer qu'il existe un état initial tel que le mathématicien finisse de jouer dans un état olympique.

État initial (on note ici uniquement les tailles des piles) : \((1 ; 2 ; 2 ; 4) \rightarrow(1 ; 1 ; 3 ; 4) \rightarrow(2 ; 3 ; 4) \rightarrow(1 ; 2\); \(3 ; 3) \rightarrow(1 ; 2 ; 2 ; 4) \rightarrow(1 ; 1 ; 3 ; 4)\).
État initial : \((3 ; 3 ; 3) \rightarrow(2 ; 2 ; 2 ; 3) \rightarrow(1 ; 1 ; 1 ; 2 ; 4) \rightarrow(1 ; 3 ; 5) \rightarrow(2 ; 3 ; 4) \rightarrow(1 ; 2 ; 3 ; 3) \rightarrow(1 ; 2\); 2;4).
Pour obtenir \(N\) piles d'une carte après un mouvement, il est nécessaire qu'il n'y ait qu'une seule pile à l'étape précédente (sinon la pile créée après ce mouvement aurait plus d'une carte). Or, s'il n'y avait qu'une seule pile avant le mouvement (celle-ci contient ainsi les \(N\) cartes) et après le mouvement, on obtient deux piles : une pile de \(N-1\) cartes et une pile d'une carte. Puisque \(N \geqslant 3\), il est donc impossible d'obtenir \(N\) piles d'une carte après un mouvement
Observons que la configuration d'une seule pile de \(N\) cartes peut être la configuration initiale. De plus, on peut obtenir la configuration d'une seule pile de \(N\) cartes après un mouvement (si la configuration initiale est de \(N\) piles d'une carte). Or, pour obtenir une seule pile de \(N\) cartes après un mouvement, il est nécessaire qu'à l'étape précédente la configuration soit constituée de \(N\) piles d'une carte. En effet, si une pile contient plus de 2 cartes avant un mouvement, alors après ce mouvement, il y a au moins deux piles (la nouvelle pile et la pile qui contenait plus de 2 cartes avant ce mouvement). En utilisant la question précédente, il n'est possible de voir la configuration à une pile de \(N\) cartes qu'au début du jeu ou après un seul mouvement.
Il n'y a qu'un nombre fini de configurations puisque le nombre de cartes est fini. Par conséquent, le mathématicien s'arrête de jouer.
Il suffit de prendre des entiers \(N\) de la forme \(\frac{n(n+1)}{2}\) et comme état initial la configuration à \(n\) piles où la première pile contient 1 carte, la seconde \(2, \ldots\), la \(n\)-ième contient \(n\) cartes (qui est une configuration olympique).
Puisque \(2016=\frac{63 \times 64}{2}\), il suffit de choisir la configuration initiale à 63 piles où la première pile contient 1 carte, la seconde \(2, \ldots\), la 63 -ième contient 63 cartes.