Blet, un jeu pas bête

dimanche 6 juin 2010
par  Alain BUSSER

Le jeu Blet a été inventé au début du millénaire par F. Rodriguez Villegas, L. Sadun et J.F. Voloch, de l’université d’Austin, Tx, USA. Le point de départ était des recherches sur les codes correcteurs d’erreur et sur la fonction êta de Dedekind !

Le jeu

Les auteurs du jeu ont oublié de dire comment ils ont inventé son nom... En tout cas voici la règle du jeu, qui se joue avec un nombre pair de pièces de monnaie, disposées en cercle, en alternant les pile et les face :


À chaque tour, on retourne une pièce qui est encerclée par deux pièces différentes d’elle (face-pile-face ou pile-face-pile). Dans ce cas on retourne aussi les deux pièces voisines. Le but du jeu est d’obtenir le plus grand nombre possible de « pile ».

Blet est donc un casse-tête. On appelle blet-2n le jeu avec 2n pièces. Au bas de cette page on peut télécharger les jeux à 4, 6, 8, 10 ou 12 pièces, mais voici les jeux à 4, 6 ou 8 pièces, jouables en ligne (pour lancer le jeu, utiliser le script en haut à gauche, et pour retourner une pièce, cliquer en son centre) :

CarMetal - 218.8 ko
le jeu en ligne

Il est clair que pour blet-4 on ne peut pas se débarasser de la dernière pièce qui est sur « face ». On essaye toutes les possibilités, et aucune ne permet de dépasser les 3 « pile ». Ce phénomène est d’ailleurs général, puisque le dernier coup ne peut être que le passage de « face-pile-face » à « pile-face-pile » qui laisse un « face »...

Dans blet-6 par exemple, on ne peut pas dépasser les 5 « pile ». En fait, en essayant toutes les possibilités, on n’arrive même pas à dépasser les 4 « pile » !

La théorie du jeu consiste donc à déterminer, en fonction de n, le nombre maximal de « pile » qu’on peut obtenir à blet-2n, c’est-à-dire le nombre de « pile » à partir duquel on considère le jeu comme gagné. Pour ce faire, les inventeurs du jeu ont utilisé des calculs d’angle !

algèbre

Pour une implémentation sur ordinateur telle que celle de GtkBoard, il est commode de dérouler le cercle des pièces en écrivant une suite de P et de F. Alors le jeu blet peut être considéré comme une sorte de grammaire formelle, avec les règles de transformation suivantes :

PFP \rightarrow FPF

FPF \rightarrow PFP

Ces règles de transformation évoquent fortement la principale relation de la théorie des tresses fondée il y a une centaine d’années par Emil Artin... La « grammaire » évoquée ici n’est pas un langage rationnel pour autant, parce qu’après la dernière lettre (prise dans l’alphabet \left\{P,F \right\}) se trouve la première lettre à nouveau...

Il est vraisemblable que le jeu blet ait trouvé sa genèse dans ces considérations de grammaires transformationnelles.

géométrie

Pour déterminer le minimum du nombre de « face » restant à la fin du jeu, ses créateurs utilisent la géométrie : À chaque mot de 2n lettres formé de P et de F ils associent deux chemins, l’un représenté en bleu, l’autre en rouge, avec les transformations

\left\{\begin{array}{l}x'=x \\ y'=x+y \end{array}\right.

pour la lettre P (pour « pile »), et

\left\{\begin{array}{l}x'=x-y \\ y'=y \end{array}\right.

pour la lettre F (pour « face »).

Le chemin bleu commence par (1,0) et le chemin rouge par (0,1) :

CarMetal - 12.8 ko
les chemins en ligne

Lorsque les chemins reviennent à leur point de départ, on dit que le mot est fermé (exemple : PFPFPFPFPFPF). Dans ce cas, on démontre que les chemins bleu et rouge tournent de 60n degrés. Or chaque fois que le chemin bleu tourne, c’est sur un P et chaque fois que le chemin rouge tourne, c’est sur un F. Et comme à chaque fois, l’angle de rotation est strictement inférieur à 180°, on en déduit que le nombre de P et le nombre de F sont tous les deux strictement supérieurs à \frac{n}{6}. Et cette propriété reste vraie pour les mots dont une puissance est « fermée », comme la configuration de départ de blet-2n. Par exemple,

  • pour blet-4, l’angle est de 120°, ce qui veut dire au moins une rotation : Au moins un « face » donc au plus 3 « pile » ;
  • pour blet-6, l’angle est de 180°, donc il faut au moins 2 « face », soit au plus 4 « pile » ;
  • pour blet-8, l’angle est de 240° ce qui nécessite aussi au moins deux « face » soit au plus 6 « pile » ;
  • pour blet-10, l’angle de 300° est atteint en au moins 2 rotations aussi, soit encore au moins 2 « face », ou au plus 8 « pile » ;
  • et pour blet-12, un tour complet est effectué, ce qui nécessite au moins trois rotations d’angles inférieurs à 180°, donc au moins 3 « face », soit au maximum 9 « pile ».

On récapitule dans le tableau suivant :

Nombre de pièces Nombre maximal de « pile »
4 3
6 4
8 6
10 8
12 9
14 11
16 13
18 14
20 16
22 18
24 19
26 21
28 23
30 24
32 26
34 28

SL(2,Z)

Les chemins ci-dessus ont été choisis de manière que les matrices de « pile » et de « face » soient toutes les deux dans SL(2,\Z) (matrices à coefficients entiers, de déterminant 1). Or ces matrices opèrent sur le demi-plan de Poincaré en représentant la matrice \left(\begin{array}{rr}a & b \\ c & d \end{array}\right) par la fonction z \mapsto \frac{az+b}{cz+d}. Ci-dessous, on a représenté l’image d’un quadrilatère par cette transformation. On peut déplacer les sommets du quadrilatère avec la souris (ou en cliquant sur le singe) ou déplacer le quadrilatère entier avec la souris :

CarMetal - 6.5 ko
illustration dans le demi-plan de Poincaré

Cette voie n’a semble-t-il pas été explorée par les créateurs du jeu, et il n’a pas évident de voir si elle mène à quelque chose d’intéressant ou de novateur...

jeux de pièces

blet16 a été implémenté dans le jeu Enigma :

Le principe consistant à retourner des jetons évoque un célèbre jeu de stratégie (à deux joueurs celui-là) : reversi-Othello.

D’autres jeux utilisent des jetons, parfois juste comme marqueurs pour remplir des tableaux booléens, comme ce jeu qui figurera dans la prochaine version d’Enigma (1.1) :

Il s’agit juste d’un jeu de logique style intégramme, où on trouve 5 personnages (M. BouleNoire, M. BouleBlanche, M. Billeblanche etc.), 5 métiers (écrivain, hacker, serrurier etc.) et 5 ustensiles, et où on doit trouver qui fait quoi et qui porte quoi. Très classique, mais au lieu de cocher des cases, on place des pièces dessus.

Enfin les pièces ayant plusieurs valeurs fiduciaires mènent à d’intéressantes questions comme la recherche du nombre de manières de constituer 37 centimes uniquement avec des pièces de 10, 5 ou 2 centimes...


Documents joints

blet 4 à 12 pièces, à jouer sous CaRMetal
blet 4 à 12 pièces, à jouer sous CaRMetal

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 12 avril 2017, 14h-18h, campus du Tampon, amphi 120C
- Mercredi 3 mai 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mardi 13 juin 2017, 14h-18h, campus du Tampon
- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6


Brèves

À 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

jeudi 27 avril 2017

Publication

740 Articles
Aucun album photo
130 Brèves
11 Sites Web
126 Auteurs

Visites

1125 aujourd'hui
1189 hier
1994675 depuis le début
33 visiteurs actuellement connectés