Combien retirer :
Historique
Qu'est-ce que le Jeu de Bachet ?
Le Jeu de Bachet (aussi appelé Jeu de Soustraction) est un jeu mathématique à deux joueurs à information parfaite. Il y a N objets et deux joueurs alternent en prenant entre 1 et M objets. Le joueur qui prend le dernier objet gagne.
La règle (M+1)
L'idée clé : le premier joueur a une stratégie gagnante si et seulement si N n'est PAS un multiple de (M+1). Si N mod (M+1) = 0, le second joueur gagne toujours avec un jeu optimal.
N mod (M+1) ≠ 0 → Premier joueur gagne
N mod (M+1) = 0 → Second joueur gagne
Stratégie gagnante
Si c'est votre tour et que les objets restants N ne sont pas un multiple de (M+1), prenez exactement N mod (M+1) objets. Cela laisse votre adversaire avec un multiple de (M+1), une position perdante. Quoi qu'il prenne (k objets), vous prenez (M+1-k) au tour suivant.
Lien avec l'arithmétique modulaire
Le Jeu de Bachet repose fondamentalement sur l'arithmétique modulaire. Les positions « sûres » sont celles où le compte est 0 mod (M+1). Chaque paire de coups peut totaliser M+1, donc si vous laissez votre adversaire à 0 mod (M+1), il ne peut s'échapper.
Lien avec Nim
Le Jeu de Bachet est un cas particulier du jeu mathématique Nim. Le théorème de Sprague-Grundy fournit une solution complète pour tous les jeux impartiaux, y compris le Jeu de Bachet. La valeur Grundy d'une position avec n objets est n mod (M+1).
Applications
- Fondamentaux de la théorie des jeux combinatoires
- Conception d'algorithmes et programmation dynamique
- Théorie des nombres et arithmétique modulaire
- Pensée stratégique dans les scénarios compétitifs
- Enseignement du raisonnement mathématique et des preuves
Convention Misère
Dans la version misère, le joueur qui prend le DERNIER objet PERD. La stratégie change : si N mod (M+1) = 1, vous êtes en position perdante ; sinon, prenez des objets pour laisser un compte de 1 mod (M+1).
Maximum variable
Au lieu d'un M fixe, le retrait maximum pourrait augmenter à chaque tour (ex. doublement). Ces variantes créent des structures mathématiques plus riches.
Jeux d'ensemble de soustraction
Généralisez au-delà de 1 à M : permettez le retrait d'un ensemble spécifique S de nombres (ex. S = {1, 3, 4}). L'analyse utilise le théorème de Sprague-Grundy.
Versions multi-tas
Avec plusieurs tas, le jeu devient équivalent à Nim. La stratégie gagnante utilise le XOR binaire (nim-sum) des tailles de tas. Si le nim-sum est non nul, le premier joueur gagne.
Nim Fibonacci
Une belle variante où le maximum que vous pouvez retirer est le double de ce que votre adversaire vient de prendre. Le théorème de Zeckendorf fournit la stratégie gagnante.
Claude Gaspard Bachet de Méziriac (1581-1638)
Bachet était un mathématicien, linguiste et poète français. Il est connu pour son livre de 1612 « Problèmes plaisants et délectables qui se font par les nombres », l'un des premiers livres de mathématiques récréatives.
Contributions aux mathématiques
- A écrit l'un des premiers livres de mathématiques récréatives (1612)
- A étudié les suites de type Fibonacci et leurs propriétés
- A traduit l'« Arithmetica » de Diophante en latin (1621)
- Sa traduction a inspiré Fermat à écrire le Dernier Théorème de Fermat en marge
- A étudié les carrés magiques et les puzzles numériques
Histoire de la théorie des jeux
Bien que Bachet ait décrit le jeu en 1612, l'analyse mathématique formelle est venue bien plus tard. John von Neumann et Oskar Morgenstern ont établi la théorie des jeux en 1944. Le théorème de Sprague-Grundy (1935-1939) a fourni des outils pour analyser les jeux combinatoires impartiaux.
Origine chinoise
Dans la tradition mathématique chinoise, ce jeu est connu sous le nom de « Ba Shang Bo Yi ». Il est largement utilisé dans l'enseignement des mathématiques en Chine pour enseigner la pensée stratégique et l'arithmétique modulaire.