Exercice 3 — Le jeu de Nim

Sujet

On considère une rangée de jetons. Chacun à son tour, deux joueurs prélèvent 1,2 ou 3 jetons. Le joueur qui prend le dernier jeton a perdu.
Vous êtes l'un des deux joueurs.

1. On suppose qu'il y a 7 jetons sur la table, et que c'est à vous de jouer. Combien devez-vous prendre de jetons pour être sûr de gagner la partie quelle que soit la façon de jouer de votre adversaire?
2. On suppose maintenant qu'il y a 9 jetons, et que c'est à vous de jouer. Montrer que votre adversaire peut gagner, quel que soit le nombre de jetons que vous prenez.
3. La partie suivante se joue avec 2015 jetons. Décidez-vous de joueur en premier? Si oui, combien prenez-vous de jetons, si non pourquoi? Justifiez votre stratégie.
4. Il y a maintenant 5041 jetons sur la table, et c'est à vous de commencer.
   a) Expliquez pourquoi, contre un très bon joueur, vous allez perdre.
   b) Vous décidez alors de modifier les règles : chaque joueur ne sera plus limité à 3 jetons au maximum, mais à un nombre \(p\) que vous devez choisir en début de partie.
   Quelle est la plus petite valeur de \(p\) que vous devez choisir pour être sûr de gagner, quelle que soit la façon de jouer de votre adversaire?
   c) Avec cette nouvelle règle, combien de jetons allez-vous prendre pour commencer? Et les coups suivants?
5. On appelle \(N\) le nombre de jetons restant sur la table, et \(p\) le nombre maximal de jetons qu'on peut retirer à chaque coup.
   a) Indiquer pour quels nombres de jetons restant vous êtes certains de pouvoir faire perdre votre adversaire si c'est à lui de jouer.
   b) A quelle condition sur \(N\) et \(p\) décidez-vous de commencer la partie? Comment jouez vous alors pour être sûr de gagner?