URL originale : https://books.openedition.org/ugaeditions/44856

Les jeux combinatoires ou comment tisser un lien entre mathématiques, algorithmique et programmation
p. 181-202
Texte intégral
1Même si le terme « jeux combinatoires » date de la fin des années 1970 en France (traduction du terme anglais combinatorial games, qui lui apparaît au début des années 1970), ces jeux aux propriétés bien définies – que nous détaillons ci-dessous – existent depuis au moins le début du xvie siècle.
2Les jeux combinatoires ont cette spécificité d’avoir encouragé les mathématiciens à se pencher sur leur résolution, au point de devenir de véritables objets d’analyse mathématique et de permettre le développement de la théorie actuelle qui porte leur nom : la théorie des jeux combinatoires.
3Les premières références retrouvées sur les jeux combinatoires correspondent à des ouvrages de récréations mathématiques – dont les premières éditions datent du milieu du xviie siècle. Les solutions données sont alors très simples, mais aujourd’hui leur théorie avancée tisse des liens étroits avec la théorie des graphes et l’informatique.
4Au vu des nouveaux programmes de mathématiques dans le secondaire, et de la place importante attribuée aux jeux et à la dimension ludique dans l’apprentissage des mathématiques – notamment au cycle 4 –, l’objectif de cette contribution est d’apporter quelques éclairages historiques sur les jeux combinatoires et leur résolution. Cela permettra, d’une part, de donner des clés de compréhension épistémologiques sur le développement de la théorie mathématique des jeux combinatoires et, d’autre part, de fournir des recommandations pour leur utilisation en classe, fondées sur ce qui a déjà pu être testé en contexte d’animation scientifique, ainsi que sur des témoignages recueillis au cours d’ateliers pour la formation des enseignants.
5Dans un premier temps, nous présentons les caractéristiques des jeux combinatoires et donnons quelques exemples connus. Nous soulignons leur intérêt mathématique et expliquons en quoi consiste leur résolution. Ensuite, nous expliquons quand et comment les mathématiciens se sont intéressés à ces jeux pour tenter de les résoudre, en illustrant nos propos par l’étude détaillée du jeu de Nim et du jeu de Kayles. La troisième partie est consacrée à l’étude d’un jeu entièrement mécanique : Dr. Nim. Enfin, nous concluons sur les apports de l’utilisation de ces différents jeux en classe pour aborder certaines notions du programme de mathématiques au cycle 4.
Introduction
6Les jeux combinatoires – tels qu’ils sont définis dans la littérature actuelle1 – vérifient les propriétés suivantes : ils se jouent alternativement à deux joueurs, sans hasard, et ils sont à information complète (pas de cartes cachées, par exemple). Par ailleurs, le nombre de coups est fini, il n’y a pas de partie nulle et le gagnant (il y en a toujours un) est uniquement déterminé par le dernier coup de la partie2. En réalité, les jeux qui admettent des parties nulles, comme les échecs, ou les jeux à score, comme le jeu de go, entrent dans la catégorie des jeux combinatoires étendus, et seront également considérés dans ce texte.
7Les jeux combinatoires les plus populaires sont le Puissance 4, le Morpion, le jeu de Dames, les échecs, le go, mais aussi le jeu des bâtonnets à Fort Boyard3 ou le jeu des petits carrés4. Il en existe bien d’autres, souvent moins connus, qui trouvent leurs origines dans les ouvrages de récréations mathématiques publiés à partir des xvie et xviie siècles. Nous les présentons dans la première partie de la section suivante, car ils permettent une approche relativement simple des jeux combinatoires et de leur analyse en classe.
8De par l’alternance des coups entre les deux joueurs, et par l’absence de hasard, il est possible, en théorie, de dénombrer toutes les positions pouvant se présenter durant une partie de jeu et envisager un chemin optimal pouvant mener à la victoire. Mais on comprend rapidement que le nombre total de positions possibles dans un jeu est considérablement élevé ; des méthodes d’analyse autres que le dénombrement s’avèrent nécessaires, comme nous allons le voir.
Naissance de la théorie des jeux combinatoires
9Avant que ne paraisse en 1901 le premier article consacré à l’analyse mathématique complète d’un jeu combinatoire – le jeu de Nim, que nous abordons ultérieurement (Bouton 1901) – on trouve dans des ouvrages de récréations mathématiques des « problèmes arithmétiques », qu’on qualifierait aujourd’hui de « jeux combinatoires ». Nous présentons ici les problèmes recueillis par Luca Pacioli (1445-1517) et Claude-Gaspard Bachet de Méziriac (1581-1638).
Prémices : les récréations mathématiques aux xvie et xviie siècles
10Les ouvrages de récréations mathématiques du début du xviie siècle constituent en France un genre littéraire et éditorial nouveau, qui propose une pratique fondée sur le défi à l’entendement et « qui consiste à créer pour un public l’illusion d’un pouvoir extraordinaire » (Chabaud 1994 : 13). Ce sont des collections de problèmes arithmétiques et géométriques (puis physiques, mécaniques, optiques, etc.) dont le but est avant tout de « piquer la curiosité » (Barbin 2007 : 14).
11Un des premiers ouvrages entièrement consacrés à ce type de problèmes divertissants (Singmaster 2008) est le De Viribus Quantitatis du mathématicien italien Fra Luca Bartolomeo de Pacioli (1496-1508). Parmi les 120 récréations arithmétiques de la première partie de l’ouvrage, se trouve le problème suivant : « finir n’importe quel nombre avant l’autre, sans prendre plus qu’un certain nombre limité » (Pacioli 1496-1508 : 073v). Par exemple, Pacioli propose à deux personnes d’atteindre le nombre 30 en additionnant à tour de rôle des nombres compris entre 1 et 6, et demande s’il y a un avantage à commencer la partie ou non. Pacioli explique que pour gagner, il faut atteindre les paliers 2, 9, 16 et 235. Le joueur qui atteint le premier un de ces paliers pourra ensuite atteindre les autres, et ce jusqu’à 30. De manière générale, pour trouver les paliers qui permettent de gagner quels que soient les nombres cibles choisis, Pacioli explique qu’il faut « toujours diviser le nombre auquel on veut arriver par un de plus que ce qui peut être enlevé et le reste de ladite division sera toujours le premier palier de la progression » (Pacioli 1496-1508 : 074r). Le palier suivant se déduit en additionnant « un de plus que ce qui peut être enlevé » du palier précédent6.
Fig. 1 – Problème proposé par Bachet dans ses Problemes plaisans et delectables, qui se font par les nombres (Bachet 1612 : 99).

[Ghent University Library, BIB.MA.000910].
12Une variante de la récréation proposée par Pacioli est celle donnée par Claude-Gaspard Bachet dans ses Problemes plaisans et delectables, qui se font par les nombres (1612) et qui consiste à atteindre 100 en additionnant des nombres compris entre 1 et 10 (voir fig. 1). Cette récréation peut en effet se décliner avec n’importe quelles valeurs pour le nombre à atteindre et pour les nombres qu’on peut additionner7. Par ailleurs, elle peut également se jouer en version « soustractive » : au lieu d’additionner mentalement des valeurs, les joueurs ont à leur disposition un ensemble de jetons duquel chacun retire le nombre voulu à chaque tour. Cette version, combinée à l’usage de jetons qu’on peut manipuler, est davantage adaptée à une activité en classe, car elle permet une meilleure représentation des situations de jeu et facilite leur analyse.
13Dans les ouvrages de récréations mathématiques des xvie et xviie siècles, les problèmes sont traités essentiellement dans des cas particuliers, sur des exemples. On ne trouve pas de généralisation pour un nombre n à atteindre en additionnant des valeurs entre 1 et k. La première analyse mathématique complète d’un jeu combinatoire sera donnée au début du xxe siècle dans l’article de Charles Bouton (1869-1922) sur le jeu de Nim.
Avancées théoriques : le jeu de Nim et le jeu de Kayles
Le jeu de Nim et ses variantes
14Les règles du jeu de Nim données par Bouton (1901) sont les suivantes : on dispose sur une table trois rangées d’objets de toute sorte, chacune contenant un nombre quelconque d’objets. Les deux joueurs sélectionnent à tour de rôle une des rangées et retirent autant d’objets qu’ils veulent : un, deux, trois… ou la rangée entière, mais au moins un objet doit être retiré. Le joueur qui prend le(s) dernier(s) objet(s) gagne la partie (version normale). La résolution théorique présentée par Bouton (1901) repose sur l’écriture du nombre d’objets de chaque rangée en binaire, et sur la « Nim-somme »8, qui correspond à la fonction booléenne OU exclusif : les nombres d’objets contenus dans chaque rangée sont d’abord écrits en binaire, puis ils sont additionnés – en faisant attention de bien aligner les mêmes unités entre elles – modulo 2, sans tenir compte des retenues9. Si le résultat des sommes de chaque colonne est égal à 0, la position est dite perdante10. Le joueur qui laisse cette position à son adversaire se met alors en situation de force et peut remporter la victoire.
15L’article de Bouton (1901) est considéré comme fondateur pour la théorie des jeux combinatoires, car il est le premier à analyser un jeu combinatoire dans un cadre général, avec des données numériques quelconques. Il est par ailleurs publié dans un journal de mathématiques américain renommé : Annals of Mathematics. Ceci explique très certainement pourquoi d’autres mathématiciens après Bouton se sont intéressés au jeu de Nim, en apportant de légères modifications dans les règles initiales, ce qui aboutit à de nouvelles résolutions n’impliquant plus nécessairement le système binaire ; c’est le cas du Nim de Wythoff. Ce dernier fut introduit en 1907 par le mathématicien néerlandais Willem Abraham Wythoff (1865-1939) dans la revue Nieuw Archief voor Wiskunde (Wythoff 1907).
Fig. 2 – Les différents déplacements possibles de la reine sur le plateau de jeu.

16Dans le Nim de Wythoff, il y a exactement deux tas d’objets sur la table, et les joueurs peuvent, à tour de rôle, enlever un nombre quelconque d’objets d’un seul tas, OU enlever le même nombre d’objets dans les deux tas. Le gagnant est celui qui prend le(s) dernier(s) objets(s) (Wythoff 1907 : 199-200). Cette variante est théoriquement analogue au jeu appelé « la reine de Wythoff » (Wythoff’s Queen) qui se joue sur un plateau11 : une reine est placée n’importe où sur un plateau de jeu quadrillé, et l’objectif pour les deux joueurs est d’amener la reine sur la case en bas à gauche. Le premier qui y arrive remporte la partie. La reine peut se déplacer uniquement vers l’ouest (horizontalement), vers le sud (verticalement) ou vers le sud-ouest (diagonalement) d’autant de cases voulues, comme le montre la figure 2.
17En quoi le Nim de Wythoff (avec les deux tas d’objets) est équivalent, dans sa résolution, à la reine de Wythoff jouée sur un plateau avec un seul pion ? D’emblée la correspondance n’est pas immédiate, car les mécanismes du jeu et le matériel utilisé diffèrent grandement. Il se trouve que les coordonnées de la reine sur le plateau correspondent aux deux tas d’objets dans le Nim de Wythoff : quand on retire des objets d’un seul tas, la reine se déplace horizontalement ou verticalement (seule son abscisse ou son ordonnée varie, selon le tas choisi), et quand on retire un même nombre d’objets des deux tas, la reine se déplace en diagonale (l’abscisse et l’ordonnée varient simultanément). Ainsi, les deux jeux, malgré des différences de mécanismes et de matériel, s’analysent de la même façon.
18Après quelques parties jouées sur le plateau, avec pour consigne d’essayer de trouver quelles cases il faut atteindre pour être sûr de gagner, il est possible de déterminer les premières positions perdantes, représentées en hachuré sur la figure 3.
Fig. 3 – Les cases hachurées sont les positions perdantes sur lesquelles il faut amener la reine pour pouvoir gagner la partie. Les cases noires et grises (clair et foncé) sont les cases qu’il faut éviter, au risque de laisser notre adversaire atteindre une case hachurée. Pour une analyse détaillée de la recherche des positions perdantes au jeu de la reine de Wythoff, et de leurs propriétés, voir (Rougetet 2016b).

19Il faut ici souligner l’importance de la symétrie par rapport à une diagonale, afin de pas oublier de positions perdantes ; en effet, autant la configuration (1, 2) dans le Nim de Wythoff (un objet dans un tas, deux dans l’autre) est la même que la configuration (2, 1), autant dans la reine de Wythoff ce sont deux positions distinctes. Le tableau, déterminé itérativement, avec l’ensemble des positions perdantes est représenté ci-dessous.
Tableau 1 – Tableau représentant les abscisses (ligne A) et ordonnées (ligne B) des positions perdantes, en prenant l’abscisse inférieure à l’ordonnée, et en leur assignant un rang (n). Les positions symétriques n’ont pas été intégrées.
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
A | 0 | 1 | 3 | 4 | 6 | 8 | 9 | 11 | 12 | 14 | … |
B | 0 | 2 | 5 | 7 | 10 | 13 | 15 | 18 | 20 | 23 | … |
20La variante « géométrique » du Nim de Wythoff permet, selon nous, une analyse plus visuelle de ce qui se passe au cours de la partie (anticipation des coups de l’adversaire par exemple). Un travail possible en classe avec cette activité serait de demander aux élèves de conjecturer les positions perdantes au vu des positions qui ont déjà été trouvées, et de tester directement sur le plateau (en prévoir un de grande taille) pour valider ou invalider la conjecture.
21D’autres mathématiciens après Wythoff se sont également intéressés au jeu de Nim de Bouton en y apportant des modifications, faisant ainsi avancer la théorie des jeux combinatoires vers le formalisme qu’on connaît actuellement. Le jeu de Kayles, présenté dans la section suivante, va nous permettre de montrer l’émergence et l’utilisation d’une notion essentielle dans la résolution de ces jeux, celle des Nimbers.
Le jeu de Kayles : illustration des Nimbers
22Le jeu de Kayles est une adaptation de salon d’un jeu d’adresse venant d’Angleterre datant du xive siècle, dont le but était de renverser un maximum de quilles initialement disposées d’une certaine manière (parfois alignées, parfois en carré) à l’aide d’une boule lancée à la main ou au moyen d’une canne en bois. Le jeu de Kayles, tel qu’il est présenté dans le Canterbury Puzzles du puzzlist12 britannique Henry Dudeney (1857-1930) de 1908 et dans le Cyclopedia of Puzzles du puzzlist Samuel Loyd (1841-1911) de 1914, se joue ainsi : 13 quilles sont alignées sur une même rangée et la deuxième quille est renversée (voir fig. 4). À tour de rôle, les joueurs peuvent faire tomber une quille, ou deux quilles adjacentes. Celui qui renverse la (les) dernière(s) quille(s) remporte la partie. Ce jeu peut bien évidemment se jouer sur une table avec des jetons, car aucune habileté physique n’entre en jeu. C’est donc un jeu combinatoire qu’il est possible d’analyser mathématiquement.
23Les solutions données par Dudeney et Loyd sont particulières à la configuration initiale et ne sont ni expliquées dans un cadre général, ni même justifiées. Pour être sûr de remporter la victoire écrivent-ils, il faut abattre la sixième ou la dixième quille et laisser « tôt ou tard » (Dudeney 1908 : 220) un nombre pair de groupes similaires de quilles. Ainsi, quoi que joue l’adversaire, il suffit de répéter son action dans un groupe similaire.
Fig. 4 – Illustration du jeu proposé par Samuel Loyd (Loyd 1914 : 232). C’est à Rip Van Winkle de jouer après qu’un nain a abattu la 2e quille, que doit-il jouer pour remporter la victoire ?

24L’analyse complète du jeu de Kayles, ainsi qu’un grand nombre d’autres jeux combinatoires, sera donnée en 1955 par Richard Guy et Cedric Smith (Guy et Smith 1955), dans laquelle ils montrent comment la résolution de ce jeu se ramène à analyser une configuration particulière du Nim de Bouton.
25Tout d’abord, Guy et Smith (1955) reprennent la fonction introduite par Patrick Grundy en 1939 (Grundy 1939) : ils la notent G(P) avec P une position possible du jeu combinatoire dont il est question. Ensuite, ils attribuent aux positions finales (qui sont perdantes) la valeur G(P) = 0. Pour les positions P non-finales, ils attribuent à G(P) le plus petit entier différent des valeurs G(Qi), où les Qi sont les coups possibles à partir de la position P (appelés les coups descendants de P). Cette règle est aujourd’hui appelée « la règle du Mex » (pour Minimum EXclus13) en théorie des jeux combinatoires, et les valeurs prises par la fonction de Grundy sont aussi nommées Nimbers. On travaille alors par raisonnement rétrograde, en remontant des positions finales (qui ont un Nimber égal à 0) aux positions dont on cherche le Nimber. Voyons comment procéder sur un exemple simple : la figure 5 représente l’arbre des différentes possibilités de jeu à partir de la position 1-2 au jeu de Kayles jusqu’aux positions finales (par souci de place, nous n’avons pas représenté les dernières branches qui, de la position 1, arriveraient à la position finale 0).
Fig. 5 – Arbre de jeu au Kayles à partir de la position 1-2.

Fig. 6 – On assigne aux positions finales un Nimber égal à 0.

Fig. 7 – Les Nimbers des positions menant à une position finale sont égaux à 1.

Fig. 8 – L’arbre de jeu de Kayles à partir de la position initiale 1-2, avec leurs Nimbers.

26On commence par assigner aux positions finales un Nimber égal à 0, représenté en gris sur la figure 6.
27Puis, le Nimber d’une position qui mène à une position finale est égal au plus petit entier différent du Nimber de la position finale, c’est-à-dire le plus petit entier différent de 0, donc 1. On complète alors l’arbre pour obtenir la figure 7.
28En réitérant ce processus, on trouve que la position 2 a un Nimber égal à 2, que la position 1-1 a un Nimber égal à 0 (car la seule position suivante possible, 1, a un Nimber égal à 1), et que donc la position initiale 1-2 a un Nimber égal à 3, comme le montre la figure 8.
29À présent, le Nimber d’une position donnée plus complexe que 1-2, qui n’est autre qu’une somme disjointe de positions plus simples P1, P2, … Pm, est déterminé en calculant la Nim-somme des Nimbers des différentes positions P1, P2, … Pm. Et si cette Nim-somme est nulle, comme dans la résolution du Nim de Bouton, la position est une position perdante.
30Ainsi, l’utilisation des Nimbers permet de ramener tout jeu combinatoire à une configuration particulière du Nim de Bouton, et l’analyse d’une position revient finalement au calcul d’une Nim-somme. Ce résultat fondamental pour la théorie des jeux combinatoires porte aujourd’hui le nom du « théorème de Sprague-Grundy »14.
31Les fonctions de Grundy sont toujours étudiées actuellement, notamment pour leurs propriétés de périodicité selon les jeux considérés ; l’utilisation de l’outil informatique (et de calculateurs électroniques tel que l’EDSAC de Cambridge au début des années 1950) devient fondamentale pour effectuer les calculs sans erreurs.
Liens avec l’algorithmique et la programmation
La programmation des jeux combinatoires
32L’aspect « déterminé »15 des jeux combinatoires et leur analyse faisant appel au système binaire et à la Nim-somme favorisent une modélisation informatique et la construction d’un programme de résolution. Le programme de cycle 4 suggère d’ailleurs d’approcher la nouvelle thématique « algorithmique et programmation » par des activités ludiques, notamment via certains jeux combinatoires comme le Tic-Tac-Toe ou le jeu de Nim. Pour ce faire, une des modalités de l’apprentissage correspondant proposée est le travail en mode débranché, c’est-à-dire sans l’utilisation d’un dispositif informatique.
Fig. 9 – Support en plastique rouge du Dr. Nim. Les billes sont placées initialement dans la gouttière en haut du support. Le joueur actionne la gâchette en bas à droite du plateau pour faire descendre la bille qui passe par le chemin déterminé selon la position des différents flip-flops.

33Dans le cadre du 22e colloque inter-IREM d’épistémologie et d’histoire des mathématiques dont le présent ouvrage est issu, nous avons montré comment l’analyse et la programmation des jeux combinatoires ont permis certaines améliorations algorithmiques et techniques dans le domaine informatique, notamment à travers l’histoire de la programmation du jeu d’échecs. Par manque de place, nous ne détaillerons pas ici les faits marquants de cette histoire, préférant nous attarder plus en détail sur la dernière activité qui a été présentée au cours de l’atelier et qui porte sur un jeu mécanique commercialisé à la fin des années 1960 destiné à jouer au jeu de Pacioli en version soustractive : Dr. Nim. Pour le lecteur qui souhaite consulter une étude détaillée des avancées algorithmiques et techniques liées à la programmation du jeu d’échecs, nous renvoyons à l’article (Rougetet 2016a).
Le jeu de Pacioli en version mécanique : Dr. Nim
34Dr. Nim est un jeu fabriqué et commercialisé dans le milieu des années 1960 par E.S.R., Inc., entreprise spécialisée dans la manufacture de jeux éducatifs. Il se joue à un joueur, qui joue contre Dr. Nim, en version normale ou misère, et se ramène au jeu de Pacioli à une rangée contenant jusqu’à 20 jetons, dont on peut en retirer un, deux ou trois.
35Le jeu se présente sous la forme d’un support en plastique rouge (voir fig. 9), laissant tomber un ensemble de billes à travers divers leviers de couleur blanche, chacun pouvant se positionner de deux façons différentes. Ce dispositif de commutation est un montage flip-flop (bascule à deux états stables, tel un interrupteur) et permet de réaliser la numération binaire (un état représente le 0 et l’autre état représente le 1).
36Le joueur qui affronte Dr. Nim choisit de faire tomber une, deux ou trois billes dans le système (le levier situé en bas à gauche du support permet de choisir quel joueur a la main, Dr. Nim ou Player) en actionnant une, deux ou trois fois la gâchette située en bas à droite du support. Quand c’est à Dr. Nim de jouer, il suffit d’actionner la gâchette une seule fois et il décide lui-même de faire tomber une, deux ou trois billes16.
37La version classique du jeu consiste à placer initialement 15 billes dans la gouttière en haut du support, à positionner les leviers comme le montre la figure 10, et à jouer en version misère.
Fig. 10 – Position initiale des leviers pour jouer en version misère à Dr. Nim avec 15 billes placées initialement dans la gouttière. Le levier de droite ainsi placé permet au joueur qui défie Dr. Nim, qu’il joue en premier ou non, de prendre la main sur la partie (à condition de bien jouer, auquel cas Dr. Nim prend la main et gagne la partie à coup sûr).

[© L'inventeur du jeu : John Thomas Godfrey ; Crédit photo : Andrew Beck].
38De manière générale, quand le jeu est présenté en atelier ou en conférence, les participants développent un intérêt manifeste pour Dr. Nim ; il est vrai que son fonctionnement purement mécanique, ses composantes en matière plastique bon marché, et le fait qu’il descende lui-même le nombre de billes choisi (nous vous invitons vraiment à visionner la vidéo du lien donné à la note 16 !) impressionnent l’utilisateur de prime abord. Mais une fois la surprise retombée, l’analyse du jeu et des mécanismes du support peuvent commencer, grâce au travail préliminaire qui aurait été mené sur le jeu de Pacioli en version soustractive avec des jetons17.
39Il s’agit avant tout de faire le rapport entre le jeu de Pacioli préalablement analysé et cette configuration du Dr. Nim où le nombre de billes initial change, ainsi que le nombre de billes qu’on peut retirer. D’autre part, le jeu est joué en version misère (il faut donc laisser la dernière bille à Dr. Nim pour gagner, et non plus faire tomber la (ou les) dernière(s) bille(s)). Les différentes positions perdantes sont donc : 1, 5, 9 et 13. Il est alors préférable de commencer la partie et de faire tomber deux billes, puis de se ramener à 9, 5 et 1 pour être certain de remporter la partie18.
40Dans le cas d’une activité en classe, les élèves peuvent émettre des conjectures sur la stratégie gagnante et sur le nombre de billes qu’il faut laisser sur le support pour gagner. Ils peuvent ensuite immédiatement les tester face à Dr. Nim, et par différentes phases d’essai-erreur valider ou invalider leurs hypothèses. Cette activité favorise le travail collectif, par petits groupes (pour chercher ensemble une stratégie de jeu), mais aussi en classe entière (pour confronter les différentes idées), et permet d’aborder les compétences requises dans la résolution de problèmes : chercher, raisonner, communiquer, largement mobilisées aux cycles 2 et 3.
Fig. 11 – Liste des instructions suivies par le programme au cours d’une partie de Dr. Nim (1968 : 14).

[© L'inventeur du jeu : John Thomas Godfrey ; Crédit photo : Andrew Beck].
41Lors de sa commercialisation dans les années 1960, Dr. Nim était accompagné d’un manuel d’utilisation (E.S.R., Inc. et John Thomas Godfrey 1966) – 23 pages au format A4 – riche en contenu pédagogique ; en effet, ce document a pour objectif de faire comprendre aux joueurs, quel que soit leur âge, le fonctionnement du jeu ainsi que le raisonnement sous-jacent au mécanisme19. Le manuel présente, au- delà des règles du jeu et des positions des leviers selon le nombre initial de billes, le programme et la liste des instructions suivies par Dr. Nim au cours d’une partie. Nous avons reproduit ci-dessous la liste des instructions fournies dans le manuel (voir fig. 11 pour la source historique en anglais et l’annexe A pour le document traduit), et leur exécution par le programme grâce au tableau fourni en annexe B (voir fig. 12 pour la source historique).
42L’utilisation de ces supports permet un réel travail en mode débranché avec les élèves, en rapport direct avec le matériel qu’ils ont devant eux, qu’ils peuvent manipuler et dont ils peuvent constater physiquement les résultats.
Fig. 12 – Tableau pour exécuter les instructions suivies par le programme au cours d’une partie de Dr. Nim (1968 : 13).

[© L'inventeur du jeu : John Thomas Godfrey ; Crédit photo : Andrew Beck].
Conclusion
43Les jeux combinatoires, et plus précisément les jeux que nous avons abordés dans cette contribution, présentent des intérêts réels pour la classe, en offrant une grande diversité d’activités, notamment autour du calcul, de l’algorithmique et de la programmation. Ils donnent une large place au potentiel ludique dans des situations de recherche en classe20, et permettent aux élèves d’être acteurs de leurs apprentissages dans des activités mathématiques où ils peuvent tester directement leurs hypothèses en jouant et construire ainsi leurs connaissances. La manipulation d’objets et la visualisation concrète d’une suite d’instructions génèrent une approche nouvelle de certaines notions, qui peuvent parfois sans cela être mal ressenties par les élèves.
44Les liens que tissent les jeux combinatoires entre les mathématiques, l’algorithmique et la programmation se révèlent davantage perceptibles et accessibles grâce aux éclairages historiques apportés par les sources exploitées dans cette contribution. L’histoire permet de voir que les savoirs mathématiques sous-jacents aux jeux n’ont pas toujours été là, qu’ils ont été inventés, modifiés au cours du temps pour résoudre des problèmes, et qu’ils résultent d’un processus qui s’inscrit dans le temps et dans l’espace. Ces jeux prennent leurs sources dans des ouvrages de récréations mathématiques dès le début du xviie siècle et continuent d’intéresser et de mettre au défi mathématiciens puis informaticiens pour les résoudre. Intégrer cette histoire dans un enseignement permet une approche culturelle de la discipline qui nous paraît indispensable à la construction des connaissances ; la maîtrise des savoirs sous-jacents (qu’ils soient d’ordre disciplinaire, didactique, historique) aux activités proposées aux élèves par l’enseignant (ou dans le cadre d’une action de médiation scientifique) permettant un recul nécessaire et bénéfique à la cohérence de l’apprentissage visé.
Annexe A : liste des instructions suivies par le programme de Dr. Nim en français
45Programmation Dr. Nim pour 15 billes initiales en version misère (2/2)
Programme pour jouer au Dr. Nim contre une personne
(Qui prend la dernière bille perd.)
Liste des instructions suivies par le programme de Dr. Nim en français.
Numéro de l’instruction | Instruction |
1 | Commençons un nouveau jeu avec 15 billes. |
2 | Écrivez un 15 dans la colonne M et un 2 dans la colonne R. |
3 | Si vous souhaitez jouer en premier, allez à l’Instruction 6. |
4 | Je vais prendre 1 bille, écrivez 1 dans la colonne N, Soustrayez aussi 1 de R et réécrivez dans la colonne R |
5 | Si M est maintenant égal à 0, allez à l’Instruction 15. Sinon continuez. |
6 | Combien de billes souhaitez-vous prendre ? Écrivez la réponse dans la colonne P. |
7 | Soustrayez P de M et réécrivez dans M. |
8 | Si M est maintenant égal à zéro, allez en 16. Sinon continuez. |
9 | Si P est inférieur ou égal à R, allez en 11. |
10 | Ajoutez 4 à R et réécrivez dans R. |
11 | Soustrayez P de R et réécrivez dans R. |
12 | Si R n’est pas égal à zéro, allez en 14. |
13 | Écrivez un 4 dans R. Allez en 4. |
14 | Je vais prendre R billes. Écrivez R dans N. Écrivez 4 dans R. Soustrayez N de M. Allez en 6. |
15 | Vous avez gagné ! Retournez en 1. |
16 | Vous avez perdu ! Retournez en 1. |
Annexe B : tableau pour exécuter la liste des instructions
46Programmation Dr. Nim pour 15 billes initiales en version misère (1/2)
« Le programme a été écrit de sorte que 4 nombres aient besoin d’être changés de façon répétitive et d’être mémorisés durant la partie de jeu en cours. Nous appellerons ces nombres :
M : le nombre de billes restantes dans le jeu (15 au départ).
R : un nombre « de rappel » dont le programme a besoin.
P : le nombre de billes que le JOUEUR (player) choisit à un tour donné.
N : le nombre de billes que le Programme choisit à un tour donné.
Afin de mémoriser ces nombres au fur et à mesure de la partie, prenez une feuille de papier blanc et écrivez les lettres données en tête de quatre colonnes comme ci-dessous. »
Tableau pour exécuter la liste des instructions.
M | R | P | N |
Références bibliographiques
Albert, M. H., Nowakowski, R. J. et Wolfe, D. (2007). Lessons in play: an introduction to combinatorial game theory. Wellesley : A. K. Peters Ltd.
Bachet, C.-G. (1612). Problemes plaisans et delectables, qui se font par les nombres. Lyon : Pierre Rigaud.
Barbin, E. (2007). Les Récréations : des mathématiques à la marge. Les génies de la science, 30, 14-17.
Berge, C. (1967). Théorie des graphes et ses applications (2e édition). Paris : Dunod.
Berlekamp, E. R., Conway, J. H. et Guy, R. K. (2001). Winning Ways for Your Mathematical Plays (vol. 1, 2e édition). Natick, Massachusetts : A. K. Peters Ltd.
Bouton, C. L. (1901). Nim, a Game with a Complete Mathematical Theory. The Annals of Mathematics, 3(1/4), 35-39.
Brousseau, G. (1998). Théorie des situations didactiques. Grenoble : La Pensée Sauvage.
Chabaud, G. (1994). Sciences en jeux. Les récréations mathématiques et physiques en France du xviie au xviiie siècle (Thèse de doctorat). EHESS, Paris.
Colipan, X. (2014). Étude didactique des situations de recherche pour la classe concernant des jeux combinatoires de type Nim (Thèse de doctorat). Université de Grenoble, Grenoble.
Dudeney, H. E. (1908). The Canterbury Puzzles and Other Curious Problems. New York : E. P. Dutton and company. 2e édition, avec quelques solutions plus completes et des notes supplémentaires (1919). Londres, Edimbourg, New York : Thomas Nelson and sons, Ltd.
E.S.R., Inc. et John Thomas Godfrey (1966). How to play Dr. NIM (manuel d’instructions du jeu). Disponible en ligne sur le site <http://www.one-leggedsandpiper.com/Christmas/Presents/Dr-Nim-Manual.pdf> (consulté le 1er octobre 2018).
Grundy, P. M. (1939). Mathematics and Games. Eureka, 2, 6-9.
Guy, R. K. et Smith, C. A. B. (1955). The G-Values of Various Games. Mathematical Proceedings of the Cambridge Philosophical Society, 52(3), 514-526.
Loyd, S. (1914). Cyclopedia of Puzzles. New York : The Lamb Publishing Company.
Pacioli, L. (1496-1508). De Viribus Quantitatis. Disponible en ligne sur le site d’Uriland (Dario Uri) : <http://www.uriland.it/matematica/DeViribus/Pagine/index.html> (consulté le 1er octobre 2018).
Rougetet, L. (2016a). Un ordinateur champion du monde d’échecs : histoire d’un affrontement homme-machine. Sciences du Jeu, 5, 1-16.
Rougetet, L. (2016b). Raconte-moi une NIMstoire. Repères IREM, 105, 21-36.
Rougetet, L. (2017). Les jeux de combinaisons en France à la fin du xixe et au début du xxe siècle. Dans É. Barbin, C. Goldstein, M. Moyon, S. R. Schwer et S. Vinatier (dir.), Les travaux combinatoires en France (1870-1914) et leur actualité. Un hommage à Henri Delannoy (p. 145-166). Limoges : Presses universitaires de Limoges.
Singmaster, D. (2008). De Viribus Quantitatis by Luca Pacioli: The First Recreationnal Mathematics Book. Dans E. D. Demaine, M. L. Demaine et T. Rodgers (dir.), A Lifetime of Puzzles (77-122). Wellesley, Massachusetts : A. K. Peters Ltd. and CRC Press.
Wythoff, W. A. (1907). A Modification of the Game of Nim. Nieuw Archief voor Wiskunde, 2(VI), 199-202.
Zermelo, E. (1912). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. Dans Proceedings of the Fifth International Congress of Mathematicians, Cambridge, 22-28 August 1912 (p. 436-460). Cambridge : University Press.
Notes de bas de page
1Voir par exemple la définition donnée par (Albert Nowakowski et Wolfe 2007 : 3).
2Par convention, on dit que le jeu est joué en « version normale » lorsque le dernier joueur à jouer gagne la partie, sinon on parle de « version misère », lorsque que le dernier joueur à jouer perd la partie.
3Dans ce jeu, les joueurs peuvent retirer alternativement 1, 2 ou 3 bâtonnets d’une rangée en contenant 20. Celui qui prend le dernier bâtonnet perd la partie.
4Appelé Dots-and-Boxes en anglais, ce jeu consiste à tracer alternativement les côtés de cases situées sur une feuille de papier quadrillé. Quand un joueur a fermé une case, il la marque de son initiale et peut rejouer. Le joueur qui à la fin de la partie possède le plus de cases avec ses initiales remporte la victoire. Pour une étude historique détaillée du jeu des petits carrés et de son analyse, voir (Rougetet 2017).
5En effet, en raisonnant par la fin, si un joueur ne veut pas que son adversaire gagne en atteignant 30, il doit lui proposer le plus grand nombre tel qu’en lui ajoutant 1, 2, 3, 4, 5 ou 6 il ne puisse atteindre 30. Ce nombre est 23, car quel que soit le nombre que l’adversaire ajoute à 23, il obtiendra un nombre supérieur ou égal à 24, mais inférieur ou égal à 29. Le joueur pourra alors compléter la somme jusqu’à 30 au tour suivant. En raisonnant de la même façon avec 23, on trouve que le palier précédent est 16, puis 9, puis 2.
6Ainsi, pour atteindre 35 en additionnant des nombres compris entre 1 et 6, il faudra d’abord atteindre 7, puis 14, 21, 28 et 35 (le reste de la division euclidienne de 35 par 7 = 6 + 1 étant nul).
7« La course à 20 » développée par Guy Brousseau (1998) pour introduire sa théorie des situations didactiques en est un exemple.
8Cette expression, absente de l’article de Bouton, est introduite par Patrick Grundy (Grundy 1939) qui emploie le terme Nim Addition en anglais.
9Nous ne rentrerons pas ici dans les détails de la résolution du jeu de Nim, faute de place, mais le lecteur désirant en savoir plus pourra consulter (Rougetet 2016b). Une ressource éduscol dédiée au jeu de Nim au cycle 3 (intentions pédagogiques, proposition de séquence, prolongements possibles) est également disponible : Éduscol (2016) Jeu de Nim. Disponible en ligne sur <http://cache.media.eduscol.education.fr/file/Mettre_en_oeuvre_son_enseignement_dans_la_classe/68/3/RA16_C3_ST_jeu_de_nim_N.D_586683.pdf> (consulté le 1er octobre 2018). Une référence utilisant des outils mathématiques actuels accessibles aux enseignants est proposée par Baptiste Gorin (IREM de la Réunion) : Gorin, B (2009) Jeux de Nim. Disponible en ligne sur le site de l’IREM de la Réunion : <http://irem.univ-reunion.fr/IMG/pdf/Gorin_Jeux_de_Nim.pdf> (consulté le 1er octobre 2018).
10On dit qu’une position est « perdante » si elle ne permet pas au joueur dont c’est le tour de jouer un coup qui le mette en position de force.
11Le jeu en question est décrit dans l’ouvrage de Claude Berge (1926-2002) sur la Théorie des graphes et de ses applications (Berge 1967 : 52), mais il ne lui donne pas de nom précis et ne fait aucune référence à Wythoff. L’appellation Wythoff’s Queen (ou encore Wyt Queens dans sa forme abrégée) apparaît dans l’ouvrage Winning Ways for Your Mathematical Plays, dont la 1re édition est parue en 1982 par les mathématiciens Elwyn Berlekamp, John Conway et Richard Guy (2001 : 59).
12Un puzzlist est un terme anglais qui, à ma connaissance, ne connaît pas d’équivalent français. On pourrait le traduire littéralement par inventeur d’énigmes ou de casse-têtes, celles-ci étant de nature numérique et logique. Dudeney et Loyd ont contribué très régulièrement dans des journaux anglais et américain respectivement, et publié plusieurs ouvrages reprenant l’ensemble de leurs énigmes, destinés au grand public et aux amateurs de casse-têtes, voir (Dudeney 1908) et (Loyd 1914).
13Minimum Excluded value en anglais, mentionnée dans (Berlekamp, Conway et Guy 2001 : 56).
14L’Allemand Roland Sprague (1864-1967) et le Britannique Patrick Grundy (1917-1959) ayant chacun découvert indépendamment ce résultat.
15De par l’absence de hasard, les jeux combinatoires sont dits « déterminés », c’est-à-dire qu’ils satisfont toujours une des trois conditions suivantes : soit les Blancs peuvent gagner quelle que soit la manière dont les Noirs jouent, soit les Noirs peuvent gagner quelle que soit la manière dont les Blancs jouent, soit chaque joueur peut arriver à un nul quelle que soit la manière dont l’adversaire joue. Cette propriété – qui semble évidente et qu’intègre très rapidement n’importe quel joueur d’échecs par exemple – a été explicitée pour la première fois par le mathématicien allemand Ernst Zermelo, qui était un fervent joueur d’échecs, dans un article Sur une application de la théorie des ensembles à la théorie du jeu d’échecs (Zermelo 1912). Par la suite, d’autres mathématiciens se sont intéressés au caractère déterminé du jeu d’échecs, notamment jusque dans les années 1930 ; c’est le cas par exemple des Hongrois Dénes König et Lászlo Kalmár qui reprennent et approfondissent les résultats développés par Zermelo, du Néerlandais Max Euwe qui envisage l’analyse du jeu d’échecs sous l’angle de la théorie des ensembles et de l’Allemand Emanuel Lasker qui consacre un chapitre de son ouvrage sur les jeux de plateau aux Mathematische Kampfspiele en reprenant l’analyse du jeu de Nim et d’autres variantes.
16Une démonstration beaucoup plus parlante d’une partie de jeu est disponible sur le site de l’éditeur UGA Éditions : <https://www.uga-editions.com/menu-principal/collections-et-revues/collections/enseigner-les-sciences-/enseigner-les-sciences-413082.kjsp?RH=1506349688943>.
17Nous recommandons d’ailleurs vivement d’aborder cette activité avec un travail de pratique et d’analyse du jeu de Pacioli avec une rangée de 30 jetons, de laquelle on peut en retirer entre un à six.
18La détermination des positions perdantes dans cette configuration (et pour le jeu de Pacioli de manière générale) se fait par un raisonnement rétrograde, qui consiste à analyser le jeu en partant de la position perdante finale (ici 1) et de « remonter » les positions pour déterminer quelles sont les positions perdantes antérieures (5, 9, et 13). Il est important de montrer que l’écart entre deux positions successives est toujours de 4, c’est-à-dire le nombre maximal de billes qu’on peut retirer, incrémenté de 1.
19Faute de place, nous ne détaillons pas ici le raisonnement présenté dans le manuel et invitons le lecteur à le consulter à cette adresse : <http://www.one-leggedsandpiper.com/Christmas/Presents/Dr-Nim-Manual.pdf>.
20Nous reprenons ici les propos développés par Colipan dans son travail de thèse (2014), qui voit les jeux combinatoires de type Nim comme des problèmes de recherche en mathématiques, dont la résolution permet de mettre en œuvre des SiRC (Situations de Recherche en Classe) liées à l’activité mathématique en général.
Le texte seul est utilisable sous licence Licence OpenEdition Books. Les autres éléments (illustrations, fichiers annexes importés) sont « Tous droits réservés », sauf mention contraire.
Mathématiques récréatives
Ce livre est diffusé en accès ouvert freemium. L’accès à la lecture en ligne est disponible. L’accès aux versions PDF et ePub est réservé aux bibliothèques l’ayant acquis. Vous pouvez vous connecter à votre bibliothèque à l’adresse suivante : https://freemium.openedition.org/oebooks
Si vous avez des questions, vous pouvez nous écrire à access[at]openedition.org
Mathématiques récréatives
Vérifiez si votre bibliothèque a déjà acquis ce livre : authentifiez-vous à OpenEdition Freemium for Books.
Vous pouvez suggérer à votre bibliothèque d’acquérir un ou plusieurs livres publiés sur OpenEdition Books. N’hésitez pas à lui indiquer nos coordonnées : access[at]openedition.org
Vous pouvez également nous indiquer, à l’aide du formulaire suivant, les coordonnées de votre bibliothèque afin que nous la contactions pour lui suggérer l’achat de ce livre. Les champs suivis de (*) sont obligatoires.
Veuillez, s’il vous plaît, remplir tous les champs.
La syntaxe de l’email est incorrecte.
Référence numérique du chapitre
Format
Référence numérique du livre
Format
1 / 3