Dans la vidéo ci-dessus, on voit que le garçon (à droite) qui commence la partie, perd le jeu. La fille (à gauche) s’empresse de replacer le pion au départ pour rejouer à ce jeu.

Le garçon propose alors que ce soit elle qui joue en premier, et elle se rend vite compte qu’elle est en train de perdre. Elle essaye alors d’emprunter une arête inexistante (ce qui ne l’empêcherait d’ailleurs pas de perdre quand même) :

puis de remonter une arête en sens interdit :

et ensuite de refaire un passage par l’arête inexistante, puis finalement d’admettre qu’elle a perdu, ce qu’elle fait très vite pour immédiatement recommencer le jeu.

Le garçon a maintenant compris le rôle que joue la parité dans ce jeu et essaye de jouer deux traits d’un coup, mais sa vigilante adversaire l’en empêche :

Ils ont maintenant compris tous les deux l’existence d’une stratégie gagnante pour celui ou celle qui joue en deuxième (ce qui n’est pas étonnant de la part d’élèves de CM2, la créatrice du jeu, en CE2, ayant elle-même compris cette stratégie gagnante). Malgré cela, ils essayent quand même de rejouer à ce jeu, désormais sans intérêt pour eux.

Le garçon qui joue les bleus (CE2) apprend si vite à jouer qu’il explique les règles du jeu à la fille qui joue les rouges :

Mais il est si occupé à remettre au centre de la case un jeton déjà joué, qu’il ne voit pas qu’elle joue en diagonale :

Une fois que cette erreur est corrigée, le jeu reprend et va vite vers sa fin :

En effet, ensuite seul le jeton rouge dans le coin tout à gauche peut bouger, ce qui ne permet qu’un seul mouvement pour les bleus, plaçant un jeton bleu dans le coin désormais inoccupé. Alors c’est la surprise, les rouges ne peuvent plus jouer :

On lit sur les visages la surprise mêlée de déception (parce que le jeu est déjà fini) et de joie chez le vainqueur.

Typiquement les enfants mettent plus de temps à préparer le plateau de jeu qu’à jouer, certaines parties se terminant en quelques secondes.

Ces élèves de CE2 jouent à Col ; Bleu a commencé et déjà posé deux jetons sur des sommets latéraux. Rouge essaye d’abord de jouer un sommet déjà adjacent à un sommet rouge, puis croit ne pas pouvoir jouer, et enfin joue son dernier coup :

Le sommet adjacent à un sommet rouge est par contre jouable pour Bleu et celui-ci pose alors son troisième jeton, il ne reste alors que le sommet central qui est injouable et Rouge a donc perdu ce jeu.

Pourtant c’est souvent celui qui joue en deuxième qui perd ce jeu.

Ci-dessous, une des joueuses (on peut considérer qu’il s’agit d’un jeu collaboratif consistant à colorier à deux un maximum de sommets du graphes) commet l’erreur de ne pas placer les jetons de proche en proche. On lui montre que le choix qu’elle fait empêche de placer un jeton au centre du graphe. Elles essayent alors d’autres positions avant de trouver une position qui fonctionne :

On remarque que le sommet central du graphe est autant que possible évité, c’est peut-être parce qu’au jeu de Col il est un mauvais choix à cause de son degré élevé.

Un élève de CM2 pense pouvoir colorier le graphe de Hajos avec seulement trois couleurs, mais aboutit à une impasse, l’un des sommets (à droite sur la vidéo) étant adjacent à des sommets respectivement rouge, vert et bleu :

Il envisage alors de colorier en trois couleurs les sommets alignés :

Mais « on fait pareil » n’a pas été compris par l’animateur et la technique semblant mener à d’autres impasses, il lui a été suggéré de se concentrer sur les triangles. Didactiquement c’est une erreur :

On constate quand même que la perception du fait qu’il faut 3 couleurs pour colorier (les sommets d’)un triangle, n’est pas aisée. Le regard est donc attiré sur le triangle qu’il avait colorié en premier, et il se propose d’essayer à la place de colorier d’abord le triangle des milieux :

Et l’algorithme fonctionne :

Voici maintenant des exemples de tangrams réalisés dans cette école :

Dans le jeu de Col sur le graphe du poisson, Noir a très mal joué (Grande Section à Grand-Ilet) :

En effet, Vert a joué le seul sommet que Noir pouvait encore jouer (la bouche du poisson) et a ainsi gagné. On constate que le degré du sommet que Noir a joué est 4, et que les autres sommets sont de degré inférieur à 4.

Pareil sur le graphe de Hajos, qui comprend des sommets de degré 2 et 4 :

Bleu a joué un sommet de degré 4 et s’est ainsi privé de 4 sommets pour le coup suivant. De fait, le seul sommet dont il ne s’est pas privé est celui qu’a joué ensuite Rouge.

Pire encore, sur ce graphe, l’unique sommet de degré 5 (les autres sont de degré 2 ou 3) est adjacent à tous les autres, et quel que soit le coup joué par Rouge au prochain tour, Bleu ne peut plus rien jouer :

D’où l’ébauche d’une stratégie gagnante basée sur la notion de degré d’un sommet...

Le degré d’un sommet est le nombre d’arêtes allant vers ce sommet (ou venant du sommet, pour un graphe non orienté cela revient au même).

Malgré cela, sur le même graphe, Vert gagne quand même :

Le nombre minimum de chiens nécessaires pour gagner à chiens et tang est le plus petit degré des sommets du graphe.

Par exemple comme tous les sommets du prisme à base pentagonale sont de degré 3, il faut 3 chiens pour bloquer le tang :

Par contre, la moitié des sommets du graphe de Hajos étant de degré 2, le troisième chien n’est plus nécessaire sur ce graphe :

Idem pour le graphe du poisson :

ou celui-ci :

Ci-dessus, Bleu vient de jouer. Qui a gagné, ou va gagner, ce jeu ?

Dans le jeu ci-dessus, qui a joué en premier ? Qui a gagné ?

Mêmes questions pour le jeu ci-dessous :

Un graphe a été préalablement dessiné à la craie blanche, sur le sol :

Une bonne façon de ne pas se tromper pour le coloriage de ce graphe, est de s’entraîner sur une feuille de papier, puis de poser ce gabarit sur le sol et le recopier :

L’élève à gauche vient de colorier un sommet en bleu et ne souhaite pas changer de craie, elle se déplace donc directement selon ce que le plan indique :

Voici le coloriage du dernier sommet :

Le graphe colorié en rouge-bleu-vert, avec le gabarit :

puis sans le gabarit :

On remarque qu’il s’agit là de calcul parallèle, chaque élève ayant une couleur de craie dans la main.

Pour colorier le graphe du cube, les élèves plus pressés ont opté pour une autre technique, consistant à seulement marquer les sommets avant de passer au coloriage définitif :

Le graphe est alors colorié uniquement en rouge et bleu :

On dit que le nombre chromatique du cube est 2 puisque seules 2 couleurs suffisent.

Le dernier graphe de Nirina (dessiné peu après son 8^e anniversaire) a été reproduit sur le sol, puis marqué de couleurs à essayer :

Ce qui a permis de le colorier en 3 couleurs :

Ce qui prouve que le nombre chromatique de ce graphe est 3 (en effet, on ne peut pas faire mieux puisqu’il y a un triangle dans ce graphe, et ce triangle ne peut être colorié en moins de 3 couleurs).

Un défi a alors été lancé aux élèves :

Le graphe du cube a pour nombre chromatique 2 ; celui que l’on vient de colorier a pour nombre chromatique 3 ; sauriez-vous dessiner un graphe de nombre chromatique 4 ?

Le défi a été relevé avec succès :

La coloration effectuée en bleu-rouge-jaune-vert prouve que le nombre chromatique n’est pas plus que 4. Le défi suivant a été :

Pouvez-vous enrichir ce graphe de manière à avoir un nombre chromatique de 5 ?

Voici la tentative :

Or le sommet ajouté peut être colorié en jaune ce qui n’augmente pas le nombre chromatique du graphe.

Les patrons de polyèdres ont été faits avec soin :

puis assemblés avec autant de soin :

Le hasard de la disposition des ateliers a fait que des mots comme « sommet » et « arête » ont été prononcés simultanément dans l’atelier des polydrons et dans celui des graphes.

S’il y a 12 pièces au départ du jeu, on peut soit les aligner toutes les 12 et en prélever soit une seule soit toutes les douze, soit les aligner 2 par 2 :

ce qui permet d’en retirer seulement 2 :

(et après ça l’adversaire peut en retirer 1, 2, 5 ou 10)

ou alors d’en retirer 6 et en laisser 6 :

(et après ça l’adversaire peut en retirer 1, 2, 3 ou 6)

Mais aussi, les 12 pièces peuvent être placées par rangées de 4 :

ce qui permet d’en retirer 4 :

(et l’adversaire peut alors en retirer 1, 2, 4 ou 8)

ou d’en retirer 3 :

(et l’adversaire peut ensuite en prélever 1, 3 ou 9)

La question était de calculer, par l’algorithme de Pick, l’aire de ce polygone :

Pour cela il a été proposé d’utiliser des boîtes comme variables, étiquetées respectivement C (comme « sur le côté ») et i (comme « à l’intérieur »). Comme on compte 12 points sur le côté du polygone, on place 12 jetons dans le registre C :

Mais pour aller plus vite, les registres ont ensuite été dessinés avec leur contenu donné en chiffres :

Ensuite on a compté 5 points à l’intérieur du polygone :

Après il faut

• diviser par 2 le registre C (ce qui se fait en enlevant la moitié des jetons qu’il contient)
• additionner les contenus des deux registres (ce qui se fait en transférant un des registres dans l’autre)
• enlever un jeton au résultat.

Dans le jeu de Col ci-dessus, qui a commencé le jeu ? Qui va gagner ?

Qui a perdu ce jeu ? Qui a joué en premier ?

Qui est en train de jouer ? Qui a commencé le jeu ? Qui sera le perdant ?

Qui a perdu le jeu ci-dessus ? Qui a joué en premier ?

Mêmes questions pour le jeu ci-dessous :

Combien de jetons doit-on déplacer à partir de ce jeu de Col terminé, pour avoir une 3-coloration du graphe ci-dessous (bleu-blanc-rouge) ?

Dans le jeu de Col ci-dessous, qui a perdu ? Qui a joué en premier ?

Qui va gagner le jeu ci-dessous ?

Combien de jetons dois-on déplacer pour transformer le jeu de Col ci-dessous en une 3-coloration du graphe de Bidiakis ?

Qui va gagner le jeu de Col ci-dessus ? Qui a joué en premier ?

Colorier patiemment avec les crayons ne met pas les élèves de grande section à l’abri d’erreurs :

(le sommet à gauche et celui en bas sont adjacents et pourtant tous les deux en mauve)

(ce coloriage est empêché par la présence d’un sommet cyan en bas à droite, lequel est adjacent au sommet en cours de coloriage)

(les erreurs se voient sous forme de traits qui dénotent des débuts de coloriage).

Les élèves de moyenne et grande section sont unanimement tombés d’accord sur le fait qu’en cas d’erreur de coloriage non corrigée à temps, le jeu est perdu ; ce qui permet par exemple de gagner même si on a joué en premier.

Et voici le retour de la rubrique tant attendue :

Qui gagnera cette partie de Col ?

Qui a joué en premier ? Qui gagnera ce jeu ?

Le nombre chromatique d’un graphe est le nombre minimum de couleurs qu’il faut pour le colorier.

En jouant à Col, certains élèves de Grande Section ont découvert une coloration minimale du graphe sur lequel ils jouaient.

Par exemple en finissant la partie de Col sur le graphe de Herschel, ils ont prouvé par coloriage que son nombre chromatique est 2 :

En jouant au jeu de Col sur le prisme pentagonal ils ont prouvé que son nombre chromatique est au maximum 3 :

Il en est de même pour le graphe de Bidiakis :

le graphe de Hajos :

ou le graphe de Frucht :

et même le dodécaèdre :

Problème ouvert :

1. Combien y a-t-il de fins de parties possibles au jeu de Col sur le dodécaèdre ?
2. Parmi celles-ci, combien ont-elles au moins deux sommets blancs adjacents ?

Le hasard fait parfois bien les choses, et ceci, rappelons-le, en Grande Section !