Une activité dès la maternelle autour des graphes : le jeu de Sprouts

Piste verte Le 28 avril 2019  - Ecrit par  Alain Busser Voir les commentaires (1)

Le jeu de Sprouts se joue avec un crayon et une feuille de papier. Il consiste à construire un graphe planaire et est donc une excellente occasion pour se familiariser avec des notions de théorie des graphes comme les graphes planaires et le degré d’un sommet. La pratique de ce jeu révèle chez des enfants parfois très jeunes une connaissance intuitive du théorème de Jordan.

Le jeu de Sprouts se joue avec un (ou de préférence deux) crayon(s) et une feuille de papier initialement vierge, hormis un certain nombre (« nuage ») de points. Il consiste à construire un graphe sous certaines contraintes. D’apprentissage immédiat et de caractère addictif, il s’inscrit pleinement dans le thème « jouons ensemble avec les mathématiques » de la fête de la science 2019.

Il a donc été testé

  • en juillet 2018, pendant les vacances, avec des enfants (issus de grande section ou de CE2) ;
  • le 3 octobre 2018 au séminaire de l’IREM de La Réunion, avec des animateur.trice.s de l’IREM (dont l’enthousiasme a égalé celui des enfants) ;
  • lors de la semaine des maths 2019 (deux journées en collège - cycle 4 - et une journée en école élémentaire - cycle 3 - ) ;
  • puis à l’occasion du colloque MATh.en.JEANS de l’océan indien, avec les participants au colloque (collégiens, lycéens, accompagnateurs et chercheur.se.s).

Le but de cet article est de permettre, grâce à l’expérience acquise au cours de ces nombreuses parties, de démarrer immédiatement des activités ludo-éducatives basées sur ce jeu.

Sprouts et les graphes

Le jeu de Sprouts est basé sur deux notions de théorie des graphes (en fait le jeu consiste à construire un graphe) :

  • la notion de graphe planaire (une arête ne doit jamais croiser une autre arête : cela forcerait l’une des deux à « sortir du plan ») ;
  • la notion de degré (théorie des graphes) (chaque sommet du graphe doit être de degré inférieur ou égal à 3).

Le jeu démarre par un nuage de points (qui sont des sommets de degré zéro dans le futur graphe). Alors chaque joueur à son tour va :

  • ajouter une arête joignant soit deux sommets (ce qui augmente leur degré d’une unité chacun) soit un sommet à lui-même (ce qui augmente son degré de 2 unités) ;
  • puis ajouter sur cette arête un nouveau sommet au graphe (lequel est donc de degré initial 2).

Mais il faut respecter les deux contraintes citées ci-dessus (graphe planaire [1] et aucun degré supérieur à 3). De ce fait le jeu a une durée de vie finie, et le premier joueur ne pouvant plus ajouter d’arête au graphe perd le jeu. Voici par exemple un jeu dont le nuage initial est formé des 3 points plus gros et plus foncés que les autres. La joueuse qui joue en rouge [2] a gagné :

PNG - 156.1 ko

Pourquoi a-t-elle gagné ?

Tout d’abord, on compte qu’elle a tracé 4 arêtes alors que son adversaire n’a jusqu’ici tracé que 3 arêtes : ce n’est donc pas à elle de jouer.

Ensuite, en regardant les degrés des divers sommets du graphe, on voit qu’ils valent tous 3 sauf

  • le sommet tout en haut (une des trois sommets initialement présents ; degré 2)
  • un autre sommet de degré 2, colorié en rouge au milieu d’un segment (vers le bas à droite)

Par conséquent l’adversaire de la jeune joueuse ne peut plus jouer, au mieux, qu’un tracé d’arête joignant ces deux sommets de degré 2. Or ceci n’est pas possible sans croiser deux arêtes, ce qui est contraire à la règle du jeu : le graphe ne serait plus planaire.

Ne pouvant jouer, l’adversaire a perdu ce jeu.

Degré d’un sommet

En jouant à des jeux sur un graphe préconstruit, les enfants découvrent vite l’intérêt que présente la notion de degré d’un sommet :

  • dans des jeux de poursuite comme le jeu du lièvre et du chien, le nombre de prédateurs (chiens) nécessaire pour équilibrer un tant soit peu le jeu, dépend du degré minimal des sommets du graphe ;
  • dans les jeux de Col et Snort, une heuristique gagnante est basée sur la notion de degré maximal d’un sommet du graphe ;
  • il en est de même pour le jeu des deux parkings dont on ne connaît pas, à l’heure actuelle, de stratégie gagnante.

En plus, le simple décompte des degrés des sommets d’un graphe est une activité arithmétique praticable dès la Grande Section. Par la suite on peut envisager des procédés de vérification comme le lemme des poignées de mains. On peut même imaginer toute une batterie d’exercices (ou jeux ?) consistant à donner les degrés des sommets du graphe, et demander de compléter le graphe, en traçant les arêtes manquantes.

Créé par les mathématiciens John Conway et Michael S. Paterson au début des années 1960, le jeu de Sprouts est très facile à apprendre dès le cycle 2, mais reste l’objet de recherches à l’heure actuelle. Y jouer se fait par la manipulation d’un crayon sur une feuille de papier, et ce jeu est donc emblématique de la méthode de Singapour.

Analyse avec n=1

Si le début du jeu est formé d’un seul sommet, le jeu est court et aboutit automatiquement à la victoire du second joueur. En effet, si on représente en noir le premier sommet (en bas), le seul mouvement possible pour le premier joueur est de tracer une arête joignant ce sommet à lui-même, ce qui lui donne un degré 2 :

Le second joueur ne peut pas alors refaire de boucle, parce que cela augmenterait de 2 unités le degré d’un des sommets :

Le seul coup permis au second joueur est donc de joindre les deux sommets par une arête, faisant alors passer leurs degrés à 3 :

Mais comme il n’y a qu’un seul sommet de degré inférieur à 3, et que son degré est supérieur à 1, le premier joueur ne peut plus jouer. En effet s’il fait passer une boucle par le nouveau sommet il lui attribue le degré 4 :

Et s’il joint le nouveau sommet à un autre, c’est cet autre qui aura un degré 4 :

Ni trop ni trop peu : c’est le choix de 3 sommets au départ qui a été fait pour initier les enfants à ce jeu.

La joueuse citée précédemment a aussi gagné ce jeu, en effet aucun coup n’est plus jouable :

PNG - 401.6 ko

Pour se convaincre qu’elle a a gagné, elle a écrit à côté de chaque sommet, son degré.

Ce réflexe (compter les arêtes) est présent dès la grande section et on le retrouvera de façon récurrente en collège et en lycée, avec des améliorations substantielles.

Lors du séminaire IREM de la rentrée 2018, a donc été présenté aux animateurs IREM, le jeu de Sprouts. Les participants ont tout de suite joué mais certains l’ont fait si vite qu’ils n’ont pas vu que certains sommets étaient de degré 4.

Cette erreur de vision est apparue aussi le mardi 26 mars au collège Gaston-Crochet, et même plusieurs fois sur certains graphes :

JPEG - 65.5 ko

Comment animer un jeu de Sprouts

L’idée de jouer sur papier avec deux stylos de couleur différente a été abandonnée, le jeu se fait désormais au tableau. Chaque joueu.se.r dessine un trait et un point avec un feutre de couleur différente ce qui permet de mieux voir qui a fait l’erreur de comptage et donc de savoir qui a perdu la partie. En effet l’animation se fait ainsi :

  • L’animateur invite un.e élève au tableau et lui confie un feutre (par exemple rouge) puis dessine quelques points (en noir) au tableau blanc ;
  • l’animateur et l’élève jouent alors une partie et en même temps l’animateur explique les règles à l’élève ainsi qu’aux autres élèves présent.e.s ;
  • une fois ce jeu terminé, peu importe qui a gagné, l’animateur confie à un.e autre élève le feutre bleu et les deux élèves jouent une partie ; à partir de là l’animateur est libre d’animer une autre activité ;
  • à chaque fin de partie, le gagnant ou la gagnante affronte un.e autre élève, qui regardait le jeu.

Les noms des gagnant.e.s peuvent être écrits au tableau (ici, des élèves de 6e) :

JPEG - 94 ko

Comme le tableau se voit de loin, la curiosité amène assez spontanément des élèves à venir voir ce qui se passe, et comme une fois qu’ils ont appris en regardant les autres jouer, ils sont amenés à jouer à leur tour, il se déclenche assez rapidement une épidémie de Sprouts, sans que l’animateur ait à intervenir.

L’apparition de sommets de degré 4, surtout présente sur des nuages de beaucoup de points, n’est pas la seule erreur qui se produit au cours du jeu : Ici un trait croise un cercle, ce qui est interdit par la règle du jeu :

JPEG - 68 ko

Le trait noir en cours de tracé joint deux sommets rouges de degré 2, ce qui est parfaitement conforme à la règle du jeu. Mais en allant tout droit, il passe tout près d’un sommet de degré 3 ce qui semble donner à celui-ci un degré 5.

Une fois l’erreur repérée [3], elle est vite corrigée :

JPEG - 57.2 ko

Ce qui n’empêche pas l’adversaire de gagner :

JPEG - 78.1 ko

En effet le sommet de degré 2 qu’il vient de créer est le seul du genre et ne peut donc être joint à aucun autre.

Le succès de ce jeu, et plus particulièrement de la version feutre sur tableau blanc au collège, a incité à répéter l’expérience en école primaire, le jeudi 28 mars 2019, à l’école Louis-Clerc Fontaine. La prise d’initiative semble plus présente chez les enfants que chez les adolescents, ainsi, en constatant que l’on voit mal certains sommets de degré 3 (et qu’on les joue par erreur), les élèves de CM1-CM2 ont spontanément écrit le nombre 3 à côté de chaque sommet de degré 3 :

JPEG - 272 ko

avec mise à jour au cours du jeu :

JPEG - 261.6 ko

Ci-dessus il manque le nombre 3 à côté de deux sommets sur la gauche. La mise à jour de l’affichage n’a pas été nécessaire parce qu’il est apparu évident aux deux joueu.se.rs que la partie est finie : les deux seuls sommets de degré 2 qui restent sont dans des composantes connexes différentes, ce qui est perçu d’instinct par les enfants.

3 partout

L’inconvénient de laisser les élèves en autonomie sur ce jeu est qu’à la longue certains finissent par ne plus comprendre à quoi servent ces chiffres 3 et finissent par croire que c’est un geste à effectuer chaque fois qu’on vient de joindre deux sommets, selon le caprice d’une mystérieuse règle du jeu. Ici un joueur a oublié d’écrire ce 3 ce qui a incité son adversaire (en bas) à jouer un sommet de degré 3 et y inscrire 3 alors que son degré est 4 :

JPEG - 283.2 ko

D’autres ont cru que l’écriture du 3 est à peu près systématique et ont mis ce nombre à côté d’un sommet de degré 2 :

JPEG - 250.4 ko

Le jeu ci-dessus comporte une autre bizarrerie : la première arête n’a pas joint deux sommets existants (en noir) mais a mené à la création d’un sommet, ce qui n’est pas conforme à la règle du jeu initiale.

On constate également qu’en cycle 3 le tracé de trait est moins sûr qu’au collège, comme le montre l’angle droit dû au fait que l’élève avait visé trop bas. Ceci dit, il est possible qu’il s’agisse de dyspraxie.

Une autre présentation du jeu

Certains enfants ont oublié qu’il fallait aussi rajouter un sommet au milieu de l’arête, après avoir dessiné celle-ci. Il leur a alors été proposé une variante urbaine du jeu :

Le jeu se joue sur une carte. Au départ il n’y a que des villes isolées. Chaque joueu.se.r à son tour va construire une route joignant deux villes (ou une ville avec elle-même) mais :

  • Il ne doit jamais y avoir plus de 3 routes qui partent d’une ville donnée ;
  • deux routes ne doivent jamais se croiser ;
  • chaque fois qu’on construit une route, on construit une ville sur cette route.

Avec cette version de la règle du jeu, le réseau routier devient bien plus cohérent :

JPEG - 278.8 ko

La joueuse ci-dessus constate qu’elle a perdu la partie : elle cherche à construire une route entre les deux seules villes dont le réseau routier est encore incomplet, et elle voit que cela n’est pas possible sans croiser une autre route. Elle stoppe donc le tracé et admet avoir perdu.

Cet autre jeu est terminé parce qu’il ne reste plus qu’une ville de laquelle on peut encore tracer une route et cette route n’aboutirait nulle part :

JPEG - 279.8 ko

On constate, en particulier dans le premier degré, que

  • les enfants jouent vite
  • le jeu est addictif
  • la règle s’apprend en regardant jouer les autres enfants
  • les parties durent peu de temps.

Ceci fait que le jeu de Sprouts est remarquablement adapté aux enfants souffrant de troubles de l’attention. D’autant que ceux-ci sont valorisés lorsqu’ils gagnent et lorsqu’ils expliquent la règle du jeu à leurs camarades.

Le succès de la version tableau du jeu a amené à répéter une dernière fois l’expérience, devant un public allant de la classe de 5e jusqu’à l’âge adulte, au congrès de MATh.en.JEANS de l’océan indien, le 29 mars 2019, sur le campus de l’université du Moufia. La salle affectée aux jeux sur graphes était dotée d’un tableau noir et le jeu s’est fait à la craie :

JPEG - 138.6 ko

Un autre style

Comme on le voit, les étudiants de L3 qui animaient cet atelier ont trouvé une autre manière de représenter le jeu :

  • Les sommets ne sont plus coloriés mais représentés par des cercles relativement grands ;
  • lorsqu’on trace un trait entre deux cercles, on l’interrompt pendant le tracé pour y ajouter un nouveau cercle ;
  • lorsqu’un sommet est de degré 3, on le barre d’une croix ou on le colorie, pour qu’il saute aux yeux que ce sommet n’est plus jouable.

Effectivement cette technique s’avère efficace, on voit par exemple immédiatement ci-dessous comment finira le jeu :

JPEG - 112.2 ko

La croix à gauche est en cours de marquage. Une fois celui-ci effectué, on voit qu’il ne reste que 3 sommets encore libres, mais celui du bas n’est joignable à aucun des deux autres : le prochain joueur n’aura d’autre choix que joindre ces deux-là, créant alors un ultime sommet de degré 2, situé dans une autre composante que celui du bas, donc injoignable avec lui : celui qui est en train de tracer une croix sera perdant de ce jeu.

Ici on voit que trois sommets sont encore jouables :

JPEG - 88.1 ko

Le prochain joueur bénéficie d’un coup gagnant. Voyez-vous lequel ?

Solution

En joignant par l’extérieur le sommet à gauche et celui en bas, il crée un sommet de degré 2 qui est injoignable avec celui de l’intérieur, parce que justement l’un est à l’extérieur et l’autre à l’intérieur.

Conclusion

Le jeu de Sprouts est un jeu. De ce fait, il est de nature à intéresser des élèves bien plus jeunes que les créateurs du jeu. Ceci, dès la grande section. Mais sans oublier les classes ultérieures : le jeu a été testé lors du congrès MATh.en.JEANS de l’Océan Indien les 29 et 30 mars 2019 (thème de la semaine des maths : « jouons ensemble avec les mathématiques » ). Le jeu de Sprouts est également un jeu « papier-crayon » (ou « tableau-craie »). Il illustre donc plutôt bien la méthode dite « de Singapour » : aller vers l’abstraction (les graphes) en commençant par la manipulation (dessin sur papier ou tableau).

Le mot de la fin revient à un collégien, sous la forme d’une question (posée pendant la récréation) à laquelle la réponse n’est pas encore connue :

Pourquoi n’arrive-t-on pas à arrêter de jouer à Sprouts ?

Post-scriptum :

Le jeu de Sprouts et son ancêtre probable Lucasta ont déjà été décrits dans cet article. Le présent article doit beaucoup (si ce n’est tout) aux relecteurs Clément Caubel, Thomas Rataud (qui conseille cette lecture), Véronique Vanackère et Philippe Colliard. Sans oublier qu’il bénéficie du redoutable privilège d’avoir été édité par Christian Mercat et Andrès Navas !

Article édité par Andrés Navas

Notes

[1ce qui avant l’âge de sept ans est automatique

[28 ans

[3le fait que les règles du jeu sont expliquées oralement par les élèves entre eux aboutit parfois à une transmission incomplète de l’information ; l’animateur doit quand même de temps en temps intervenir pour rappeler les règles.

Partager cet article

Pour citer cet article :

Alain Busser — «Une activité dès la maternelle autour des graphes : le jeu de Sprouts » — Images des Mathématiques, CNRS, 2019

Commentaire sur l'article

  • Une activité dès la maternelle autour des graphes : le jeu de Sprouts

    le 29 avril à 11:25, par Diego

    Merci pour cette belle idée d’activité ! Attention, le lien conseillé par Thomas Rataud n’est pas utilisable, ci-après le lien corrigé :
    https://catalogue.bnf.fr/ark :/12148/cb375931095

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?