par François Desnoyer
Résumé.
Quelques utilisations du codage binaire en particulier dans le jeu de Nim tel qu’on le trouve dans certains manuels. On proposera deux situations “hors-classe” concernant le Binaire et le Jeu de Nim qui ouvrent la voie à une ludification.
Introduction et remerciements.
Une partie importante du texte sur les Nim-sommes provient des travaux de Mme Lisa Rougetet (cf la section 6) et je la remercie de sa relecture et de ses suggestions.
Les programmes de mathématiques expertes sont l’occasion d’aborder des notions comme la division euclidienne, les congruences qui mènent naturellement au codage binaire. En particulier, on trouve dans certaines manuels des exercices autour du jeu de Nim qui peuvent ouvrir la porte à des approfondissements que nous nous proposons d’évoquer ici. Même si la première idée que l’on propose dans ce texte provient de programmes de fin du secondaire, on proposera aussi des situations didactiques à d’autres niveaux.
1. Première situation ludique en binaire.
1.1. Mathématiques du binaire.
Il est bien connu que le codage binaire est d’un usage courant en informatique. Rappelons-en ici les bases :
\(n=\overline{a_{k}a_{k-1}\ldots a_{0}}^{10}\) signifie que \(n=a_{k}\times10^{k}+\ldots+a_{0}\times10^{0}\) avec \(a_{i}\in\{0,\ldots,9\}\). On peut de la même façon écrire \(n=\overline{b_{p}b_{p-1}\ldots b_{0}}^{3}=b_{p}\times3^{p}+\ldots+b_{0}\times3^{0}=\overline{c_{q}\ldots c_{0}}^{2}\) avec \(b_{i}\in\{0,1,2\}\) et \(c_{i}\in\{0,1\}\).
Le codage par les chiffres \(b_{i}\) est appelé codage ternaire et intervient dans l’étude de certaines structures fractales (ensemble triadique de Cantor par exemple, voir 5). On sait que les considérations sur les chiffres comme unité, dizaines, centaines etc. sont manipulées quotidiennement par élèves depuis les classes élémentaires en identifiant les chiffres à la puissance de \(10\) qu’ils caractérisent dans la numération de position. Nous souhaitons montrer ici une situation ludique dans laquelle le binaire devient la clé du raisonnement. Cette situation peut être d’abord abordée dans la numération décimale dans un premier temps en jouant sur une variable didactique.
On peut bien évidemment jeter un pont entre ce chiffre binaire \(c= 0\) ou \(1\) et l’absence ou la présence d’un courant électrique devenant ainsi le fondement de l’informatique “classique”.
Bien sûr, on sait que certains nombres ont des représentations binaires qui ne sont pas exactes et que cela peut engendrer des erreurs.
En particulier si une valeur est trop proche de \(0\), l’erreur va se propager : on peut essayer de programmer sur un tableur la suite \(\left\{\begin{array}{ccc}u_0=0.3\\u_{n+1}=17u_{n}-4.8\end{array}\right.\)
Un calcul immédiat montre qu’il s’agit de la suite constante mais le tableur ne sera pas d’accord !
1.2. Une situation ludique.
Il y a \(7\) paquets de café de deux marques Lava LL et Maxou LL, les étiquettes sont toutes identiques et neutres. Un grain de Lava LL pèse \(50\ mg\) contre \(51\ mg\) pour un grain de Maxou LL. Il faut renvoyer les paquets de Maxou LL car ce n’est pas la bonne marque. On dispose d’une balance mais la pile est faible et ne pourra pas supporter plus d’une dernière pesée.
Comment faire ? (Exemple issu de Tangente Sup no 60, 2011, Évariste Galois p 17 cf 6)
1.3. Proposition de solution.
On choisit alors \(1\) grain dans le premier paquet, \(2\) grains dans le 2e, \(4\) grains dans le suivant etc. En effet, si l’on prend \(1\) grain puis \(2\) puis \(3\) etc. la pesée ne nous donnera l’information souhaitée que si l’on sait qu’un seul paquet est mauvais mais si plusieurs le sont, on tombe dans une impasse : par exemple s’il y a une erreur de \(3\ mg\) on peut avoir de mauvais paquets \(1\) et \(2\) ou uniquement le paquet \(3\).
Ici le système décimal est mis en défaut.
En revanche, supposons avoir prélevé \(1,\ 2,\ 4,\ 8,\ 16,\ 32\) puis \(64\) grains dans nos paquets, faisons la pesée et regardons la différence avec la théorie. Si c’est \(n\) alors \(n =\overline{ a_0\ldots a_6}^{2}\) et tous les chiffres égaux à \(1\) désignent alors les mauvais paquets.
Exemple : la différence constatée est de \(35\ mg\) or \(35 =\overline{ 1100100}^{2}\) donc les mauvais paquets sont le \(1\), le \(2\) et le \(6\).
2. Une situation en classe.
2.1. Situation en Terminale Experte.
Sur une table, on place 20 bâtonnets côte à côte. Deux joueurs prennent chacun, à tour de rôle, un, deux ou trois bâtonnets. Le joueur qui prend le dernier bâtonnet perd de la partie. La partie oppose Sophie à Karim.
Sophie commence et prend 3 bâtonnets et il reste donc 17 bâtonnets sur la table.
Karim s’exclame: « Bien joué, comme 17 est congru à 1 modulo 4, alors en adoptant la bonne stratégie, tu es sûre de gagner la partie! »
Karim a-t-il raison? Expliquer.
(Source : Option Mathématiques Expertes, Collection Barbazo, Hachette Education, ed 2020 p 131)
Une méthode simple pour répondre est de reprendre le calcul à l’envers, puisque \(17 = 4 \times 4 + 1\), à chaque étape Karim a bien compris que Sophie prendrait le complément à \(4\) de son choix et qu’il perdrait forcément.
Le jeu présenté ci-dessus se nomme le jeu de Nim (c’est la variante bien connue des amateurs de l’émission Fort Boyard).
2.2. Petite Histoire du jeu de Nim.
(Cette partie est issue des travaux de Mme Rougetet, cf 6).
Lorsque l’on recherche les origines du jeu de Nim – aussi appelé jeu de Marienbad d’après le film d’Alain Resnais L’année dernière à Marienbad, \(1961\) – on découvre que jusqu’au nom du jeu pose des questions.
En effet, dans son article de \(1901\), Charles Bouton, ancien élève de Sophus Lie, expose et solutionne le jeu qu’il baptise Nim. L’hypothèse retenue ici est celle de l’impératif du verbe allemand nehmen qui est nimm “prend”. Donc, ce jeu serait originaire de l’Allemagne du début du siècle dernier…
Mystère levé !
Ce serait compter sans l’un des pionniers des récréations mathématiques, l’italien Luca Pacioli. Nous voilà sur les rives de la Méditerranée… au tournant du XVe et du XVIe siècles ! ! ! Car le traité qui nous intéresse a été écrit entre \(1496\) et \(1508\) et, dans son problème XXXIII évoque la question de “finir n’importe quel nombre avant son adversaire sans pouvoir prendre plus qu’un nombre donné”.
Derrière cet énoncé cryptique, on pourrait imaginer bien des choses mais la solution est bien plus éclairante : “deux joueurs doivent atteindre le nombre \(30\) en ajoutant des nombres de \(1\) à \(6\) ” et l’on reconnaît là ce que l’on pourrait désormais baptiser jeu de “prendi” (ce qui semble moins poétique, certes).
Notons qu’un tel énoncé apparaît en \(1612\) sous la plume de Claude-Gaspard Bachet de Méziriac dans ses Problèmes plaisans et délectables qui se font avec les nombres et qu’on retrouve un tel jeu chez André-Joseph Pancoucke en \(1749\) sous le nom de jeu des cavaliers car les cavaliers pouvaient y jouer à cheval sans avoir besoin de cartes qui n’auraient pas été pratiques du tout. Par la suite, ce même jeu apparaît sous la plume de William Hooper en \(1774\), même si sa version utilisait des éléments visuels comme support. En \(1820\), on retrouve une nouvelle version sous la plume de John Badcock qui se contente de reprendre ce qu’avait fait William Hooper.
Laissons la solution de Pacioli nous donner les éléments les plus importants de la stratégie du jeu de Nim :
— Il existe des positions de sauvegarde
— Ces valeurs sont celles qui vont empêcher votre adversaire de gagner ou encore celles qui vous assurent la victoire
— Pour calculer ces valeurs, on divise le nombre à atteindre \(n\) par \(k + 1\) et le reste est alors la première de ces valeurs. (Si \(n\) est multiple de \(k + 1\), on pourra prendre \(k + 1\).)
En particulier, remarquons que le premier joueur à atteindre une position de sauvegarde a, dès lors, une stratégie gagnante. On pourra explorer les références (cf 6) pour en apprendre plus.
Remarquons que des jeux associés au jeu de Nim existent aussi en Chine (jeu de Fan-Tan) ou en Afrique (jeu de Tiouk-Tiouk) mais il n’est pas évident d’en trouver l’origine historique.
2.3. Deux exemples :
Premier exemple : On doit atteindre le nombre 93 en ajoutant \(1,\ 2,\ 3\) ou \(4\). On divise \(93\) par \(4 + 1 = 5,\ 93 = 18 \times 5 + 3 \) donc la première ”position de sauvegarde” est \(3\) (puis \(8,\ 13,\ 18, \ 23, \ 28,\ 33,\ 38,\ 43,\ 48,\ 53,\ 58,\ 63,\ 68,\ 73,\ 78,\ 83,\ 88\)).
Deuxième exemple : On doit atteindre le nombre \(20\) en ajoutant \(1,\ 2\) ou \(3\).
\(20\) étant un multiple de \(3 + 1 = 4\), on choisira donc \(4\) comme première ”position de sauvegarde” (puis \(8, 12, 16\)).
2.4. Le Jeu de Nim dans la version de Bouton.
Dans son article, en fait, Charles Bouton propose une autre version du jeu de Nim qui est celle qui est considérée comme le jeu de Nim original, dans cette version des allumettes sont disposées en rangées dans lesquelles chaque joueur peut piocher autant d’allumettes qu’il le souhaite. La victoire est pour celui qui réussit à vider la table.
Bouton propose alors le critère suivant : chaque rangée contenant respectivement a, b, c allumettes, on suppose écrire alors \(a = a^{*}\) en binaire et de même \(b = b^{*}\)et \(c = c^{*}\). On définit alors ce que l’on appelle depuis la Nim-somme (\(⊕\)) des nombres comme la somme de leurs chiffres dans \(\mathbb{Z}/2\mathbb{Z}\) c’est-à-dire une somme sans retenue. Dès lors Bouton annonce le critère pour reconnaître une ”position de sauvegarde” : \(a^{*}⊕ b^{*}⊕ c^{*}= 0\). Remarquons que le vocabulaire de Bouton n’est, bien sûr, pas celui plus algébrique choisi ici mais il introduit explicitement les “safe combinations”.
2.5. Adaptation à d’autres niveaux.
On peut revenir sur la version Fort Boyard de ce jeu qui est une version ”misère” (qui perd gagne) c’est-à-dire où celui qui aurait gagné avec la règle classique devient le perdant.
Ici, il y a \(21\) bâtonnets que l’on retire par \(1,\ 2\) ou \(3\) mais il ne faut pas être contraint de retirer le dernier bâtonnet présent. (Le nombre des bâtonnets a été modifié dans le jeu télévisé, nous ne gardons ici que la dernière version, des indications ont été données dans le deuxième exemple.)
1. Jouer contre les élèves en leur laissant le temps de calculer ou de noter pour qu’ils puissent entrevoir la régularité des positions et la stratégie pour les obtenir. (Lycée)
2. Commencer par plusieurs parties avec un élève puis mener une étude rapide des positions successives du jeu. (Collège)
Positions de sauvegarde : Remarquons que \(21 = 5 \times 4 + 1\) donc, selon la règle de Bouton rappelée ci-dessus, les positions de sauvegarde sont donc \(1,\ 5,\ 9,\ 13,\ 17\) puisque qu’en fin de compte on pourra après cette dernière position laisser une seule allumette et remporter la victoire.
3. Retour vers l’informatique.
Ivan, Dimitri et Youri sont des espions qui s’ennuient. Ivan propose alors un défi à ses deux camarades. Il dispose d’un échiquier et de 64 pièces de monnaie. Il met au point sa stratégie avec Youri et le fait sortir de la pièce.
Il donne alors la consigne suivante à Dimitri : ”Dispose les pièces sur les cases comme tu le souhaites et désigne-moi une case que je dois faire deviner à Youri. Je te demanderai alors de retourner une pièce, je sortirai par le fond et Youri devinera la case secrète en regardant l’échiquier.”
Quelle peut bien être sa stratégie ? (énigme n° 95 du livre de messieurs Deslandes, cf 5)
3.1. Une propriété fondamentale de la Nim-somme.
On note d´esormais \(a ⊕ b\) pour la Nim-somme de deux nombres (supposés écrits en binaire). Proposition : Si \(a, b, c \in \mathbb{N}\) vérifient \(c = a ⊕ b\) alors \(a = c ⊕ b\).
(Tout nombre est son propre symétrique pour l’opération \(⊕\).)
3.2. Le secret d’Ivan le Terrible.
Le secret d’Ivan repose tout entier sur la propriété ci-dessus. En effet, il commence par faire le total (au sens de la Nim-somme) des cases de l’échiquier (modulo \(64\) éventuellement). Il sait alors quelle case est ”codée” dans l’échiquier par la disposition choisie par Dimitri.
Il convertit alors sa case \( »mystère »\) en base \(2\) et n’a plus qu’à l’ajouter (au sens de la Nim-somme) à son total, puisque \( »total » ⊕ »mystère »\) donnera une case \(C\) (numérotée de \(0\) à \(63\)) qui vérifie bien \( »total » ⊕ C = »mystère »\) donc lorsque Youri se livrera au même exercice du la Nim-somme totale de l’échiquier, il tombera sur la case \( »mystère »\) choisie par Dimitri.
On peut imaginer que cette méthode est difficile à mettre en œuvre concrètement mais il peut être instructif d’en proposer une implémentation sur ordinateur
3.3. Un exemple concret.
On se donne l’échiquier ci-contre, on souhaite donc désigner la case en rouge à l’aide de la technique d’Ivan consistant à retourner une et une seule pièce de façon opportune.
Situation de départ.
(a) On va commencer par transcrire en binaire chaque numéro de case et additionner (au sens de la Nim-somme) les cases portant Pile :
\(0010⊕ 0011⊕ 0101⊕ 0111⊕ 1000⊕ 1011⊕ 1101⊕ 1110 =
0011 = \overline3^{10}\).
(b) Donc la case actuellement désignée par la configuration est la case \(3\). (en vert).
(c) Selon la stratégie du terrible Ivan, on souhaite cibler la case 5, on doit donc retourner la case \(0011 ⊕ 0101 = 0110 = \overline6^{10}\) (en bleu).
Solution et vérification.
Vérification
(a) \(0010 ⊕0011 ⊕ 0101 ⊕0110⊕0111 ⊕ 1000 ⊕1011 ⊕1101⊕ 1110 = 0101 =\overline 5^{10}\).
(b) La case désignée par le tableau est donc la case \(5\).
(c) La case désignée est bien la case ciblée.
4. Algorithme, programmes Python, applications.
4.1. Mise en œuvre algorithmique.
Les fonctions proposées ci-dessous en Python répondent au problème de la façon suivante :
— Calculer la Nim-somme de nombres entiers (il s’agit de l’opération informatique notée ”XOR” ou encore ”Ou
Exclusif”).
— Transformer une matrice de 0 et de 1 en une liste.
— Parcourir une liste et calculer la Nim-somme cumulée de ses éléments (de fait ses indices selon la stratégie choisie par Ivan).
— (Enfin) désigner la pièce à modifier (ce qui est assez trivial une fois la procédure précédente exécutée).
4.2. Programmes Python.
#### Les Nim-sommes en action
def Nim_somme(a,b): # La fonction de base de calcul de la Nim-somme de nombres
# en binaire
return (a+b)%2
def complete(A,n): # complete un tableau (binaire) avec des zeros AU DEBUT
a=len(A)
return [0]*(n-a)+A
def NSB(a,b): # Nim_somme_bin = Nim-somme de termes convertis en
# binaire
A=list(bin(a))[2:]
B=list(bin(b))[2:]
N=[]
if len(A)>len(B):
B=complete(B,len(A))
if len(B)>len(A):
A=complete(A,len(B))
for i in range(len(A)):
t=Nim_somme(int(A[i]),int(B[i]))
N.append(t)
n=0
N.reverse()
for i in range(len(N)):
n=n+N[i]*2**i
# on retourne la nim-somme N pour avoir les puissances de 2 dans l'ordre
# des indices
return n
def deploi(T,n): # transforme une ligne en une matrice
DT=[]
for i in range(n):
for j in range(n):
DT.append(T[i][j])
return DT
def ploi(DT,n): # transforme une matrice en une ligne
P=[[0]*n for i in range(n)]
s=0
i=0
Ind=[]
while i<n:
j=0
while j<n:
Ind.append(s)
j=j+1
s=s+1
i=i+1
s=0
for i in range(n):
for j in range(n):
P[i][j]=DT[s]
s=s+1
return P
def codage(T,n):
L=deploi(T,n)
k=len(L)
cible=0
for i in range(k):
if L[i]==1:
cible=NSB(cible, i)
return cible%(k-1) # je n'ai pas trouvé de theoreme assurant que la Nim-somme
# des termes soient dans l'intervalle voulu
def car(myst,T,n): # Case A Retourner
# on applique la pcp prop de la NS qui est A + B = A - B
c=codage(T,n)
r=NSB(c,myst)
return r
def retourne(myst,T,n):
r=car(myst,T,n)
L=deploi(T,n)
L[r]=1-L[r]
DL=ploi(L,n)
return DL 4.3. Applications.
In[3]:T=[[0,0,1,1],[0,1,0,1],[1,0,0,1],[0,1,1,0]]
In[4]:T
Out[4]:[0,0,1,1],[0,1,0,1],[1,0,0,1],[0,1,1,0] In[8]:codage(T,4)
Out[8]:3 In[9]:car(5,T,4)
Out[9]:6 In[11]:TR=retourne(5,T,4)
In[12]:TR
Out[12]:[0,0,1,1],[0,1,1,1],[1,0,0,1],[0,1,1,0] 5. En guise de conclusion.
La théorie des Jeux Combinatoires est un théorie fascinante qui peut être une excellente source pour la ludification de certaines notions (ici la Division Euclidienne). Je ne peux que vous recommander les articles de Lisa Rougetet cités en référence (cf 6) qui comportent des bibliographies assez fournies. Deux références pourront intéresser tous les niveaux :
— ”Winning ways for your mathematical plays” par messieurs Berkelamp, Conway et Guy en 4 volume. Une bible qui n’existe qu’en anglais et couvre une variété incroyable de problèmes mais aussi de mathématiques autour des Jeux Combinatoires.
— ”Le Cercle des Problèmes incongrus” d’Alex Bellos, beaucoup de problèmes connus (la chèvre, le chou et le loup par exemple) mais traités aussi dans un contexte historique (le susdit problème remonte au Roi Dagobert par exemple) et avec des méthodes et des sources très intéressantes (on peut très bien exploiter au Collège la résolution
géométrique des exercices où l’on doit remplir une jarre à l’aide de deux jarres non-graduées par la méthode de Tweedie…).
L’objectif de cet article était surtout de montrer ce qui peut se cacher dans des problèmes à l’aspect récréatif mais qui recèlent énormément de subtilités mathématiques et, au cours de ce – bref – survol, donner envie à “l’amatheur” curieux d’aller plus loin pour enrichir une pratique ou découvrir de nouveaux cieux.
6. Sources et compléments.
• Conférence donnée par Mme Lisa Rougetet à Toulouse le 15/03/2019 dans le cadre du séminaire Histoire des
Mathématiques de l’IREM : “La place des jeux combinatoires dans la construction des nombres surréels de Conway (1976)”.
• Un article de Mme Lisa Rougetet : http ://images.math.cnrs.fr/Autour-du-theoreme-de-Sprague-Grundy (2016)
• “A prehistory of Nim”, Lisa Rougetet in “Best writings in mathematics 2016”, Mircea Patici (ed).
• Tangente Sup no 60,“Évariste Galois, Un génie romantique” (2011)
• “Énigmes Mathématiques Corrigées (du lycée à Normale Sup’)”, Guillaume et Clément Deslandes, ed. Ellipses (2014).
• Sur l’ensemble triadique de Cantor et l’écriture des nombres en base 3 : https://fr.wikipedia.org/wiki/Ensemble_de_Cantor
• Deux documents complémentaires :
https ://interstices.info/jeux-de-nim : une analyse du jeu de Nim basée sur d’autres considérations que celles
mises en avant ici (noyau d’un graphe).
https ://www.pedagogie.ac-nice.fr/mathematiques/ wp-content/uploads/sites/30/2020/04/jeu nim O-Ginola final.pdf : encore une analyse du Jeu de Nim menée à partir d’expérimentation en classe et avec un programme Scratch.