allumette

C1-ALGO-03 : Les jeux de Nim#

Objectifs#

  • trouver la seule solution pour gagner à un jeu de stratégie pure, à deux joueurs et à somme nulle

  • construire l’algorigramme correspondant

Jeu de Nim#

Le jeu de Nim est un jeu de stratégie pure qui se joue à deux joueurs. Il y a toujours un gagnant et un perdant et le match nul est impossible.

Règles du jeu de Nim#

  • un certain nombre d’allumettes sont placées entre les deux joueurs. C’est le tas.

  • à chaque tour, un joueur peut retirer 1, 2 ou 3 allumettes du tas.

Fin du jeu#

Deux possibilités :

  1. Le joueur qui prend la dernière allumette perd

  2. Le joueur qui prend la dernière allumette gagne

Exercice 1#

nim1

Dans cet exemple, 16 allumettes ont été placées entre les deux joueurs

Consignes :#

Trouvez et expliquez, sous forme d’algorigramme, votre stratégie gagnante (si possible) pour ces 4 variantes :

  1. l’autre joueur commence et le joueur qui prend la dernière allumette gagne

  2. vous commencez et le joueur qui prend la dernière allumette gagne

  3. vous commencez et le joueur qui prend la dernière alleumete perd

  4. l’autre joueur commence et le joueur qui prend la dernière allumette perd

Exercice 2 : Variante#

Une variante au jeu de Nim existe : celle dite du “Jeu de Marienbad”.

On dispose les 16 allumettes sur 4 rangées comme le dessin ci-dessous. A chaque tour, un joueur peut prendre autant d’allumettes qu’il désire mais toutes sur la même rangée.

Celui qui prend la dernière allumette a perdu

nim2

Consignes#

  1. Vous commencez

  2. Trouvez la stratégie gagnante

Correction exercice 1#

L’algorigramme pour le jeu de Nim est le suivant :

nim3

La version complète est la suivante (avec la possibilité de commencer ou de laisser l’adverssaire commencer)

nim4