Exercice 2 — Jeux de NIM

Sujet

Alice et Bob se détendent avec une petite partie de Nim. Plusieurs tas d'allumettes sont disposés devant eux et ils doivent, chacun leur tour, retirer une ou plusieurs allumettes de l'un des tas. Celui ou celle qui retire la ou les dernières allumettes a gagné.
Nous introduisons quelques notations permettant de décrire avec concision le déroulement d'une partie, à travers un exemple où l'on commence avec trois tas. A chaque étape de la partie, le nombre d'allumettes restant dans chacun des trois tas est noté ( \(a, b, c\) ). Un tel triplet est appelé configuration. Ainsi, s'il y a 2 allumettes dans le premier tas, 4 dans le deuxième, et seulement 1 dans le troisième, la configuration à ce stade de la partie est \((2,4,1)\).
Si, à partir de la configuration \((a, b, c)\), Alice retire \(k\) allumettes du \(1^{\text {er }}\) tas, on se retrouve dans la configuration \((a-k, b, c)\) (il faut bien sûr \(k \leqslant a\) ). Une telle action est notée \(A:(a, b, c) \rightarrow(a-k, b, c)\). Voici un exemple de partie où l'on part de trois tas à 4 allumettes chacun, et où Bob commence

• \(B:(4,4,4) \rightarrow(2,4,4)\) (Bob a retiré 2 allumettes du premier tas)
• \(A:(2,4,4) \rightarrow(2,0,4)\) (Alice a retiré d'un coup les 4 allumettes du \(2^{\text {ème }}\) tas, il ne reste alors en fait plus que 2 tas)
• \(B:(2,0,4) \rightarrow(2,0,1)\) (Bob a retiré 3 allumettes du troisième tas)
• \(A:(2,0,1) \rightarrow(1,0,1)\) (Alice a retiré une allumette du premier tas)
• \(B:(1,0,1) \rightarrow(1,0,0)\) (après cette action, il ne reste en fait qu'un seul tas, constitué d'une seule allumette)
• \(A:(1,0,0) \rightarrow(0,0,0)\) (et Alice a gagné !)

1. Pourquoi le jeu n'a-t-il aucun intérêt s'il n'y a qu'un seul tas d'allumettes au départ?
2. Pour s'échauffer, Alice et Bob décident de commencer avec 2 tas contenant chacun 3 allumettes. La configuration initiale est donc ( 3,3 ). Bob décide de commencer.
   (a) Que signifie le coup \(B:(3,3) \rightarrow(0,3)\) ? Pourquoi est-ce un très mauvais coup?
   (b) Bob, qui n'est pas un joueur (trop) mauvais, décide de jouer \(B:(3,3) \rightarrow(1,3)\).

Donner le coup suivant d'Alice pour qu'elle soit sûre de gagner, et expliquer pourquoi.
(c) Expliquer pourquoi, si Alice joue bien, Bob était sûr de perdre depuis le départ en choisissant de commencer.
3. Mécontent, Bob propose une nouvelle partie, en partant d'une configuration ( 4,4 ). Une fois de plus, il préfère commencer.
(a) Montrer que quelle que soit la façon de jouer de Bob, Alice peut remporter la partie en jouant bien.
(b) Généraliser ce résultat pour n'importe quelle configuration de départ de la forme ( \(n, n\) ), où \(n\) est un entier strictement positif.
4. Bob et Alice commencent une nouvelle partie avec une configuration initiale (4, 6). Bob, grand seigneur, laisse cette fois Alice commencer. Y a-t-il une stratégie permettant à Alice de gagner à coup sûr? Expliquer pourquoi, ou comment.