Découverte ludo-éducative de la divisibilité

dimanche 9 février 2020
par  Alain BUSSER

Un jeu sérieux est un outil d’apprentissage. Par exemple dans le cas de la divisibilité on se familiarise avec les notions de divisibilité et de diviseur en jouant à l’un de ces 4 jeux :

  • Le jeu de Chomp où l’on ne voit même pas qu’il y a des diviseurs.
  • Le jeu de Juniper Green où l’on choisit à chaque étape un multiple ou un diviseur du nombre précédemment joué.
  • Le jeu du trésor du pirate (« des parties aliquotes ») où l’on soustrait des diviseurs successifs.
  • Le jeu divalea dont le but est d’engranger un maximum de diviseurs.

Remarque sur les noms des jeux

« Nim » est le nom d’un jeu où on prélève des objets parmi plusieurs tas, comme c’est expliqué dans cette Nimstoire. La version à un seul tas où on enlève 1, 2 ou 3 objets, est appelée par Conway et al, « jeu de la soustraction ». Conway définit Nim comme « somme de jeux de soustraction ». Dans cet article on va donc décrire un « jeu de division » (chomp) et un mix de soustraction et division (aliquote).

Relation d’ordre partiel

Les trois premiers jeux présentés ci-dessous utilisent le fait que la divisibilité est une relation d’ordre partiel. Que c’est une relation d’ordre signifie les trois choses suivantes :

  • tout entier non nul est un diviseur de lui-même (réflexivité) ;
  • si un entier est à la fois un multiple de a et un diviseur de b alors a est un diviseur de b (transitivité) ;
  • si deux entiers a et b sont tels que chacun des deux divise l’autre alors a=b (antisymétrie).

Que la relation d’ordre est partielle, signifie qu’il y a des entiers (comme 12 et 18 par exemple) dont aucun ne divise l’autre.

L’inclusion en théorie des ensembles est un autre exemple de relation d’ordre partiel. C’est donc une notion importante en mathématiques.

Chomp

C’est dans un article de janvier 1973 (dans scientific american) que Martin Gardner présentait le jeu suivant, qu’il a baptisé chomp pour suggérer l’idée de croquer dans les biscuits (cliquer dessus pour jouer en ligne) :

HTML - 3.4 ko
le jeu de Chomp
Chaque joueur croque non seulement le biscuit de son choix, mais aussi tous les biscuits qui sont en-dessous et à droite de celui-ci. Le joueur qui croque le biscuit moisi perd.

En fait, le jeu a été inventé par David Gale [1] sous le nom de « une curieuse variante du jeu de Nim » :

C’est une variante de Nim parce que, au lieu de mettre les pièces en tas, on les dispose en rectangle avec la règle selon laquelle chaque fois qu’on ramasse une pièce, on ramasse aussi celles qui sont à sa droite et au-dessous d’elle (compris), alors qu’à Nim, lorsqu’on ramasse une pièce, on ramasse aussi celles qui sont au-dessus d’elle dans le tas de pièces.

En mai 1973, Martin Gardner explique qu’en fait le jeu de Chomp existait déjà en 1952 avec un article de Fred Schuh titré Spel van delers et portant sur un jeu dit de division :

On part d’un nombre entier strictement supérieur à 1 ; chaque joueur à son tour choisit un diviseur du nombre courant, dont aucun multiple n’a déjà été choisi au cours du jeu. Le premier joueur qui ne peut jouer que 1, perd.

En fait, Chomp (jeu) est un cas particulier du jeu de la division, lorsque le nombre de départ n’a que deux facteurs premiers comme 2 et 3 :

HTML - 3.3 ko
chomp avec biscuits numérotés
Chaque joueur à son tour mange un biscuit ainsi que tous ceux dont le numéro est un multiple du numéro choisi. Le premier qui mange le biscuit numéro 1, perd.

Chaque biscuit porte le double du biscuit à sa gauche et le triple de celui de dessus. On a ainsi un tableau des diviseurs de 576, placés de manière que les multiples de l’un de ces diviseurs se trouvent à sa droite et en-dessous. On a donc bien un jeu analogue à celui de la soustraction, mais où on effectue des divisions successives au lieu de soustractions. Ce jeu, surtout dans sa version « calcul mental », est donc un jeu sérieux sur la divisibilité (savoir reconnaître un multiple du nombre joué à l’instant).

Stratégie gagnante

En inventant Chomp, Gale a prouvé l’existence, pour le premier joueur, d’une stratégie gagnante. Mais sa preuve est non constructive, puisqu’elle ne permet pas de trouver comment gagner :

On raisonne par cas, en se concentrant sur le coup consistant à enlever en premier le biscuit tout en haut à droite :

  • ou bien ce coup est gagnant pour le premier joueur, et dans ce cas il existe une stratégie gagnante, qui commence par « enlever le biscuit en haut à droite » (exemple ci-dessous) ;
  • ou bien ce coup est perdant pour le premier joueur, ce qui signifie que le second joueur peut enlever un autre biscuit en guise de coup gagnant. Mais dans ce cas, le premier joueur aussi pouvait arriver directement à cette position gagnante, dès le premier coup. Dans ce cas aussi, il existe une stratégie gagnante pour le premier joueur.

Le problème est qu’on ne peut pas savoir d’avance si on est dans le premier cas ou le second. Du moins, pas facilement. Pour le Chomp 3×2 on peut faire le graphe du jeu :

Et on peut y jouer comme aux jeux de Nim avec pion, en déplaçant alternativement (chaque joueur à son tour) un unique pion sur ce graphe. En faisant comme les élèves de la fête de la science et de la semaine des maths, on peut marquer (ici en noir) les cases « gagnantes », c’est-à-dire celles où veut aller chaque joueur pour gagner :

Ceci permet de verbaliser la stratégie gagnante pour le premier joueur :

  • enlever le biscuit tout en haut à droite (dans le jeu 3×2 c’est un coup gagnant) ;
    • si l’adversaire n’enlève qu’un biscuit, jouer ce qu’il faut pour qu’il ne reste que 3 biscuits non alignés (case au milieu tout à droite du graphe)
    • sinon il ne reste plus qu’une ligne de biscuits ; les manger tous sauf celui qui est empoisonné

Le problème pour généraliser cette stratégie est de nature combinatoire : Le graphe devient vite tellement compliqué qu’il est concrètement impossible de trouver la stratégie gagnante par coloration du graphe. Il est d’ailleurs même difficile de dessiner le graphe !

pour aller (beaucoup) plus loin

C’est même un jeu « plus que sérieux » puisqu’on peut aisément le généraliser [2] à des notions post-bac : Le jeu de Fred Schuh utilise le fait que la divisibilité est une relation d’ordre partiel et peut se généraliser à n’importe quelle autre relation d’ordre partiel, comme l’inclusion ou la notion de sous-espaces vectoriels.

Par exemple, la version « inclusion d’ensembles » peut se jouer avec un jeu de 32 cartes (un ensemble fini) ; voici une partie typique :

  • Le joueur A extrait du jeu de cartes, un sous-ensemble : Les cartes rouges ;
  • Le joueur B extrait de cet ensemble, un sous-ensemble : Les cartes de carreau ;
  • Le joueur A extrait de cet ensemble (de 8 cartes), le sous-ensemble « figures de carreau » ;
  • Le joueur B extrait de ces figures (3 cartes), la paire dame-roi (de carreau) ;
  • Le joueur A extrait de cette paire, le roi de carreau ; comme il ne reste alors qu’une carte, il perd le jeu.

Et comme une relation d’ordre partiel peut être représentée par son diagramme de Hasse (qui est un graphe), on généralise Chomp à des « chomp sur graphe » (orienté), ce qui a permis d’étudier chomp sur solide platonique et même des jeux logiques, en prenant comme relation d’ordre l’implication dans l’algèbre de Lindenbaum. Ce jeu n’est-il alors pas « plus que sérieux » ?

Juniper Green

Le successeur de Martin Gardner dans scientific american, Ian Stewart, a publié en 1996 un article sur une généralisation du jeu de Fred Schuh, qu’il a baptisée « diviser ou multiplier pour régner » mais aussi « juniper green », du nom de l’école où travaillait l’auteur du jeu (le fils d’un collègue de Stewart), un certain Richard Porteous, dont Stewart dit qu’il a inventé le jeu vers 1985. Voici la description de Juniper Green (jeu) par Julien Pavageau :

Le jeu se joue à deux, avec un plateau composé des 25, 50 ou 100 premiers nombres entiers et selon les règles suivantes :

  • le premier joueur coche un nombre.
  • chaque joueur coche un nombre parmi les multiples ou les diviseurs du nombre choisi par son adversaire au coup précédent.
  • un joueur est déclaré gagnant si son adversaire ne peut plus jouer.

Noter que dans l’article de Stewart (dans scientific american), on remplace les biscuits numérotés par des cartes portant les entiers successifs :

Deux différences par rapport à Chomp :

  1. On peut aussi choisir un multiple du nombre précédent (et pas seulement un diviseur) ;
  2. On peut jouer un multiple d’un nombre précédemment joué, du moment que ce multiple n’a pas déjà été joué auparavant (carte retournée dans le dessin ci-dessus).

Juniper Green n’en est pas moins un jeu sur la divisibilité. On peut aussi s’y intéresser en algorithmique. Voici la description du jeu dans le manuel sésamath 3e :

PNG - 166.3 ko

Le jeu de Juniper Green a même été donné en BTS SIO :

PDF - 40.3 ko

Cela a donné à Boris Laval et Olivier Sicard l’envie de développer une IA pour ce jeu qu’ils ont présentée ici.

Le jeu aliquote

Le « jeu de Nim à un seul tas » est appelé par Berlekamp, Conway et Guy « jeu de soustraction » : On a un tas de pièces, et chaque joueur à son tour enlève un certain nombre de pièces de ce tas, pourvu que ce nombre appartienne à un ensemble fixe :

  • Dans le jeu « de Fort Boyard », l’ensemble est formé des nombres 1, 2 et 3
    HTML - 78.5 ko
    jeu de la soustraction
    cliquer-glisser le pion pour jouer

 ;

  • Dans la variante « soustrais un carré », l’ensemble est formé des carrés parfaits
    HTML - 72.9 ko
    soustrais un carré
    cliquer-glisser le pion pour jouer

.

Conway et al proposent alors une variante appelée « dim- » (mélange de « diviseur » et « nim »), où le nombre de pièces prélevées du tas est un diviseur du nombre actuel de pièces. Ce jeu est gagnant pour le premier joueur, puisque n étant divisible par n, il suffit d’enlever toutes les pièces d’un coup ! Deux variantes peuvent alors rendre le jeu plus intéressant :

  • « qui perd gagne » ( on dit aussi « misère »), où le but de jeu est de ne pas être celui qui vide le tas ;
  • restreindre les coups possibles aux diviseurs propres (ou « parties aliquotes ») de n, c’est-à-dire n exclu.

Le jeu des parties aliquotes combine ces deux choix. Il a été publié en octobre 1970 par David L. Silverman dans le Journal of Recreational Mathematics.

sa description

Two players start with a positive integer and alternately subtract any aliquot part (factor) with the exception of the number itself from the number left by the opponent. Winner is the last player able to perform such a subtraction.
By way of example, if the original number is 12, first player may subtract either 1, 2, 3, 4, or 6 (but not 12). If he subtracts 2, leaving 10, second player may subtract 1, 2, or 5.
The objective is to leave your opponent without a move. This can only be done by leaving him a 1, since it is the only positive integer with no aliquot part other than itself.

Ce jeu a déjà été présenté sur ce site et on peut y jouer en ligne, en mode « plateau » [3] :

HTML - 2.4 ko

Mais, à la thématique des biscuits dont le dernier est moisi, a été préférée ici celle des pièces d’or dont la dernière est maudite. Ce qui permet deux améliorations du plateau de jeu :

  1. dessiner les pièces disposées en rectangle pour rendre visible la divisibilité du nombre total par le nombre choisi ;
  2. proposer un choix parmi les diviseurs propres, sous forme d’un menu déroulant.

Avec ces améliorations, le jeu se prête à une implémentation sur tablette tactile, et même sur DGPad. Les lecteurs munis de tablette peuvent tenter la connexion avec ce code :

Voici d’ailleurs le fichier DGPad pour ceux qui préfèrent jouer en local [4] :

Zip - 948.1 ko

Cela donne envie de développer des jeux sur DGPad [5] ! Un aspect intéressant de cette version du jeu est le changement automatique d’avatar selon le joueur dont c’est le tour. Les deux joueurs s’appellent respectivement Barberousse et Jabuse, et voici leurs avatars respectifs :

Barberousse Jabuse

Quand c’est au tour de Jabuse de jouer, on voit le visage de Jabuse, et quand c’est au tour de Barberousse de jouer, on voit le visage de Barberousse. De cette manière, on joue de la façon suivante :

  • Le joueur « Barberousse » commence, en prenant la tablette et en choisissant parmi les diviseurs du menu, celui qu’il veut jouer. Une fois ce choix effectué, il valide puis passe la tablette à l’autre joueur ;
  • La tablette indique que c’est au tour de Jabuse de jouer, il choisit donc un diviseur à l’aide du menu déroulant puis passe la tablette à Barberousse ;
  • retour au premier point, jusqu’à ce que l’un des joueurs ait perdu, ce qui s’annonce par un message d’alerte modal (il empêche de continuer à jouer).

C’est ce qu’on entend par « mode plateau ». Pour pratiquer ce jeu en classe, il faut donc placer les élèves à deux par tablette, ce qui nécessite donc une douzaine de tablettes en classe entière. Par la suite, on peut faire d’autres séances du jeu sans tablette, lors de séances de calcul mental.

La pratique de ce jeu sérieux amène rapidement à faire des constatations concernant la divisibilité :

  1. 1 est toujours présent dans la liste des diviseurs d’un nombre : Tout entier supérieur à 1 est divisible par 1.
  2. Certains nombres n’ont pas d’autres parties aliquotes : Ce sont les nombres premiers.
  3. On ne change pas la divisibilité par un nombre en soustrayant ce nombre. Par exemple, en soustrayant 13 à 65, on obtient encore un multiple de 13.
  4. Un nombre impair n’a que des diviseurs impairs.
  5. On change la parité d’un nombre en lui soustrayant un nombre impair ; on conserve la parité d’un nombre en lui soustrayant un nombre pair.

Ces remarques peuvent mener à la découverte de l’algorithme d’Euclide ; ce jeu est un entraînement aux critères de divisibilité, et enfin, il possède une stratégie gagnante très simple, basée sur la notion de parité, c’est-à-dire, de divisibilité par 2.

Pour finir, voici la version Android du jeu des parties aliquotes pirates, à utiliser sur un smartphone ou une tablette pour deux joueurs (en mode avion de préférence). Il faut décompresser le fichier zip pour récupérer un fichier apk qui fait tout seul l’installation Android :

Zip - 1.7 Mo
pirates Android
le jeu à installer sur Android. Pour recommencer une partie, revenir en arrière sur le smartphone et retoucher l’icône représentant un coffre.

divalea

Ce jeu a été créé lors de la rédaction de cet article (comme exemple de variable aléatoire en 1re).

Il se joue à plusieurs joueurs (pas nécessairement 2) avec un dé (de préférence icosaédrique). Chaque joueur à son tour lance le dé, puis compte (sous vérification des autres joueurs) les diviseurs du résultat affiché par le dé, et marque autant de points que le résultat du dé a de diviseurs. Par exemple si le dé tombe sur 9 (dont les diviseurs sont 1, 3 et 9) le joueur marque 3 points car 9 a 3 diviseurs.

On lance le dé plusieurs (par exemple 8) fois et chaque joueur accumule les points obtenus ainsi. Le joueur ayant obtenu le plus grand total à l’issue des 8 lancers de dés est le gagnant du jeu. En cas d’ex-aequo les joueurs ayant le plus de points continuent seuls à jouer jusqu’à ce que le sort les départage.

Outre la pratique de l’addition pour compter les points et la vérification mentale des diviseurs d’un nombre, la pratique de ce jeu amène à ceci :

  • Compter les diviseurs de 8 se fait de plus en plus vite, avec l’expérience : au début on vérifie (mentalement) que 3 n’est pas un diviseur de 8, après on finit par retenir suite aux calculs précédents, que les diviseurs de 8 sont 1, 2, 4 et 8 et qu’il y en a donc 4.
  • À la longue on finit même par retenir le nombre de diviseurs de chacun des entiers entre 1 et 20.
  • Les nombres 2, 3, 5, 7, 11, 13, 17 et 19 ressortent du lot car chacun d’entre eux ne rapporte que 2 points. Ce sont les nombres premiers que l’on découvre ainsi par le jeu.
  • La situation la pire est lorsque le dé tombe sur 1 qui n’a qu’un seul diviseur : cela habitue les enfants dès le cycle 3 à l’idée que 1 n’est pas un nombre premier.

Voici la présentation du jeu avec la liste des items du programme de cycle 4 concernés :

PDF - 77 ko

Mais dès le cycle 3 ce jeu peut être source de joie et d’apprentissage simultanés !

Théorie du jeu

Voici la loi de la variable aléatoire nombre de diviseurs pour un dé icosaédrique :

Nombre de diviseurs 1 2 3 4 5 6
probabilité 0,05 0,4 0,1 0,25 0,05 0,15

Cette loi est plutôt complexe comme on le voit sur son diagramme en bâtons :

0123456

Le théorème central limite suggère de répéter plusieurs fois le lancer pour avoir une loi de probabilité plus régulière. Pour 8 lancers on a ce diagramme en bâtons :

0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748

On voit que le score le plus probable est 26 points (pour 8 lancers de dés). La loi de probabilité pour 8 lancers est donnée numériquement ici :

total possible probabilité d’avoir ce total
8 3,90625×10-11
9 2,5×10-9
10 7,0625×10-8
11 0,0000011565625
12 0,0000121321875
13 0,0000852303125
14 0,00041009171875
15 0,0013844778125
16 0,00348032703125
17 0,00727115
18 0,0134808214063
19 0,021906401875
20 0,0334953011719
21 0,0455553634375
22 0,0601756439063
23 0,071195180625
24 0,0834425272656
25 0,0876475303125
26 0,0925726096875
27 0,0874008184375
28 0,0840410041406
29 0,0717815190625
30 0,06323229875
31 0,04899957875
32 0,0396970567578
33 0,027886503125
34 0,0208134667188
35 0,0132016325
36 0,00907874929688
37 0,0051549578125
38 0,00326086859375
39 0,001634096875
40 0,000947705429687
41 0,0004088315625
42 0,0002161490625
43 0,000076933125
44 0,000036785390625
45 0,000009871875
46 0,00000421453125
47 6,834375×10-7
48 2,562890625×10-7

Avec cette loi, on peut calculer la probabilité qu’il y ait un ex aequo au huitième lancer : on trouve 0,06516829817111869 soit environ 3 chances sur 46.


[1également inventeur de bridg-it et du jeu de 21 entre autres

[2déjà, avec la divisibilité, si le nombre de départ a plus que deux facteurs premiers, les biscuits ne sont plus disposés dans un plan et Gardner parle de « chomp cubique » lorsqu’il y a 3 facteurs premiers

[3ou « mode plato », c’est-à-dire que l’ordinateur ne sert que comme plateau de jeu et on joue à deux joueurs humains sur ordi, et non à un joueur humain contre ordi

[4la wifi étant un rayonnement électromagnétique à 2,4 GHz, le principe de précaution recommande d’utiliser au maximum le mode avion en présence d’élèves qui sont encore en période de croissance ; d’ailleurs la borne wifi du collège a vocation à être éteinte la plupart du temps, selon les préconisations de la loi Abeille

[5Pour réaliser ce fichier, l’auteur du logiciel a amélioré DPad, permettant maintenant à la tortue de déposer des images sur la figure


Commentaires

Annonces

Prochains rendez-vous de l’IREM

En raison de la pandémie, aucune activité en présentiel n’est prévue dans l’immédiat.


Brèves

Décès de 2 spécialistes des jeux mathématiques

dimanche 29 mars

Après Elwyn Berlekamp l’année dernière, c’est au tour du centenaire Richard Guy et de l’immense John Conway. Ce document de Richard Guy (une mise en garde contre le raisonnement inductif) montre bien le style unique de son auteur, en plus d’être une mine de ressources pour des exercices. Conway, outre son jeu de la vie, a créé des dizaines de jeux, dont Sprouts, très populaire dès le CP.

Python au bac 2019

vendredi 31 mai 2019

C’est une brève de MathemaTICE

La question 4b de l’exercice 3 du bac S Amérique du Nord ne pouvait être résolue sans utiliser Python.

Elwyn Berlekamp

jeudi 18 avril 2019

Elwyn Berlekamp, connu des lecteurs de ce site pour son jeu des interrupteurs, était un spécialiste du jeu de Go ainsi que de la Pipopipette, d’Édouard Lucas que Berlekamp admirait énormément.

Notation au bac

lundi 11 décembre 2017

Une nouvelle notation sera pratiquée à partir de la session 2018 pour les algorithmes au bac. Elle est décrite avec de nombreux exemples, ici.

Décès de Roger Mohr

mardi 27 juin 2017

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Statistiques

Dernière mise à jour

jeudi 28 mai 2020

Publication

863 Articles
Aucun album photo
142 Brèves
11 Sites Web
151 Auteurs

Visites

100 aujourd'hui
2203 hier
3396528 depuis le début
14 visiteurs actuellement connectés