ArithmétiqueNotion · Glossaire
jeu de Cram
Le jeu de Cram est un jeu combinatoire fini à deux joueurs sur une grille rectangulaire : à tour de rôle, chacun couvre deux cases libres partageant un côté avec un domino horizontal ou vertical. Dans la règle normale, le joueur sans coup légal perd ; le jeu est impartial, car les coups possibles dépendent seulement de la position et non du joueur. Cette impartialité permet d’analyser les positions avec le théorème de Sprague-Grundy, notamment lorsqu’un coup sépare la grille en zones indépendantes.
Sommaire
Ce que vous allez apprendre
- Identifier les coups légaux et les deux conventions de fin.
- Vérifier une stratégie gagnante sur un plateau de 2 × 3 cases.
- Relier l'impartialité du jeu au théorème de Sprague-Grundy.
- Repérer les limites d'un argument de parité ou de symétrie.
En clair
Imaginez un petit damier vide et une réserve de dominos. À son tour, chaque joueur couvre deux cases voisines avec un domino horizontal ou vertical. Une case déjà couverte ne peut plus servir. Dans la règle normale, celui qui se retrouve sans emplacement libre a perdu.
Les deux joueurs regardent la même grille et peuvent choisir les mêmes placements : le jeu est donc impartial. Pourtant, un seul domino peut couper le plateau en plusieurs zones et changer toute la suite.
Définition
Le jeu de Cram est un jeu combinatoire fini pour deux joueurs sur une grille rectangulaire. À chaque tour, le joueur choisit deux cases libres partageant un côté et les couvre par un domino. Le domino peut être horizontal ou vertical. Les pièces viennent d'une réserve commune, et les deux joueurs ont toujours accès au même ensemble de coups légaux : c'est le sens précis du mot impartial.
Dans la convention normale, l'absence de coup légal fait perdre le joueur qui doit jouer. Dans la convention misère, elle le fait gagner. La parité des deux dimensions du rectangle intervient dans l'identité du joueur gagnant, mais elle ne remplace pas l'analyse de la position. La stratégie optimale normale n'est établie que dans certains cas, tandis que la version misère demeure en grande partie non résolue. Le jeu a été popularisé sous le nom de Cram par Martin Gardner en 1974.
Pour la règle normale, le théorème de Sprague-Grundy associe à chaque position, notée P, un entier appelé nombre de Grundy. Si O(P) désigne l'ensemble des positions accessibles en un coup, ce nombre s'écrit , où mex est le plus petit entier absent. Une position de nombre 0 est perdante sous jeu optimal. Quand le plateau se sépare en zones indépendantes, leurs nombres se combinent par ou exclusif.
Un exemple, pas à pas
On joue selon la règle normale sur un plateau de 2 lignes et 3 colonnes. Données : 6 cases libres au départ ; un domino couvre 2 cases voisines ; les deux orientations sont permises ; trois dominos sont disponibles.
1. Le premier joueur place un domino vertical dans la colonne centrale. Il reste deux colonnes libres, séparées l'une de l'autre.
2. Le second joueur n'a que deux coups : couvrir entièrement la colonne de gauche ou celle de droite avec un domino vertical.
3. Le premier joueur couvre la colonne restée libre. Les 6 cases sont alors occupées après exactement 6 ÷ 2 = 3 coups.
4. Le second joueur ne peut plus poser de domino : il perd. Pour contrôler le raisonnement, on peut refaire les deux choix possibles du deuxième coup ; la réponse est toujours l'autre colonne.
En pratique
Pour découvrir le jeu, on dessine une petite grille et l'on barre deux cases voisines à chaque tour. Cette partie alternée est préférable à un simple problème de pavage lorsque l'objectif observable est de laisser l'adversaire sans coup.
Pour analyser une position courte, on énumère les placements encore légaux. Si un coup sépare visiblement les cases libres en zones sans contact, on étudie ces zones comme des sous-jeux plutôt que de traiter la grille d'un seul bloc.
Avant une partie, on annonce la convention. On choisit la règle normale si l'impossibilité de jouer doit sanctionner le joueur ; on choisit la règle misère si cette même impossibilité doit le faire gagner.
À ne pas confondre
Avec un problème de pavage par dominos. Un pavage demande de couvrir toute la région. Au Cram, le critère décisif est l'existence d'un coup au tour suivant ; une partie peut donc s'arrêter avec des cases isolées non couvertes.
Limites et pièges
Changer la condition de fin change l'analyse. Une stratégie gagnante en règle normale ne se transpose pas automatiquement en règle misère. Le symptôme est simple : le joueur bloqué perd dans un cas et gagne dans l'autre. Il faut donc fixer la convention avant tout calcul ; la version misère reste en grande partie non résolue.
La parité ne constitue pas une recette universelle. Le caractère pair ou impair des deux dimensions influence le gagnant, mais ne justifie pas à lui seul une stratégie pour tout rectangle. Il faut exhiber des réponses légales ou calculer les positions ; la stratégie normale n'est connue que dans certains cas.
Une symétrie dessinée peut être inutilisable. Avant de répondre par le coup symétrique, il faut vérifier que son domino ne recouvre pas le précédent et que ses deux cases sont libres. Si l'image symétrique coïncide avec le premier coup, l'argument de copie échoue.
Une réserve suffisante ne garantit pas un pavage final. Des cases libres peuvent subsister sans former deux cases adjacentes. Le bon test n'est donc pas « reste-t-il une case ? », mais « reste-t-il une paire de cases libres partageant un côté ? ».
Pour aller plus loin
Le théorème de Sprague-Grundy montre comment coder une position impartiale normale et combiner des zones indépendantes.
La notion de jeu impartial précise pourquoi les coups disponibles dépendent de la position, et non de l'identité du joueur.
La théorie des jeux combinatoires replace le Cram parmi les jeux finis à information complète étudiés position par position.
L'article Conway, le joueur mathématicien ouvre sur une approche plus large des jeux comme objets mathématiques.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres