Découverte ludo-éducative de la divisibilité

dimanche 23 octobre 2016
par  Alain BUSSER

Tout d’abord, un rappel 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). Les deux jeux font appel à la notion de divisibilité et au fait que cette relation est d’ordre partiel.

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 » ?

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 aliquote

Le « jeu de Nim à un seul tas » est appelé par Belekamp, 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 joueur. 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 la smartphone et retoucher l’icône représentant un coffre.

[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

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


Brèves

Décès de Roger Mohr

mardi 27 juin

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

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

mercredi 9 août 2017

Publication

760 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

403 aujourd'hui
530 hier
2074809 depuis le début
9 visiteurs actuellement connectés