Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°54 - mars 2017 > Le Jeu du Lights Out

Le Jeu du Lights Out
une approche visuelle des mathématiques au travers d’un atelier
Moteur de recherche
Mis en ligne le 10 février 2017, par Florent Dewez, Thibault Defourneau, Valentin Montmirail

Les auteurs :

Cet article peut être librement diffusé et son contenu réutilisé pour une utilisation non commerciale (contacter les auteurs pour une utilisation commerciale) suivant la licence CC-by-nc-sa (http://creativecommons.org/licenses/by-nc-sa/3.0/fr/legalcode)

Introduction

Dans cet article, nous décrivons un atelier réalisé à l’Institut des Sciences et Techniques de Valenciennes (Université de Valenciennes et du Hainaut-Cambrésis) lors du stage « Faire des Maths autrement... », éditions 2015 et 2016. Ce stage, labellisé MathC2+ par Animath, est destiné à des élèves en classe de seconde et se déroule habituellement début juin pendant quatre jours. Des ateliers d’une durée de 1h30 à 3h sont proposés et visent à faire découvrir aux élèves les mathématiques sous un autre angle ainsi que l’environnement de l’université. Pour plus d’informations, voir la page web du stage édition 2016 [3].

L’idée de créer cet atelier provient du fait que l’on entend souvent que les mathématiques sont trop abstraites, déconnectées de la réalité, provoquant peu d’engouement auprès des élèves mais aussi du grand public, médias et politiques ne volant que très peu au secours de cette science ancestrale (voir par exemple la conclusion de [2]). Alors comment expliquer ce désintérêt ? La difficulté de cette question est certainement équivalente à celle d’un problème de recherche et nous ne prétendons pas avoir la réponse. Cependant une idée peut être avancée : nous pensons (assez fortement d’ailleurs) que l’intérêt pour une matière donnée peut naître en prenant conscience des applications potentielles que cette matière peut avoir dans notre monde. Les mathématiques n’échappent pas à cette règle bien entendu. Ainsi les applications de notions abstraites ne devraient pas être vues exclusivement comme de simples conséquences (parfois bâclées) de la théorie mais également comme une réelle motivation à l’étude de celle-ci. On peut conseiller la lecture de l’article [1] dans lequel l’auteur illustre très bien cette idée.

Dans ce sens, les jeux peuvent fournir une grande variété de problèmes très accessibles, simples à formuler et potentiellement attrayants, et parfois difficiles à résoudre. Cette difficulté peut motiver l’introduction de notions abstraites afin d’aborder un jeu sous un nouvel angle et d’améliorer sa compréhension. Dans ce contexte, on peut espérer qu’une partie non-négligeable des notions abstraites existantes s’illustre sur certains jeux, renforçant ainsi l’intérêt et la compréhension des élèves.
Le jeu que nous proposons dans l’atelier s’appelle le "Lights Out" : il consiste en une grille de 5 par 5 interrupteurs, certains étant allumés et d’autres éteints au début de la partie. Sachant qu’appuyer sur un interrupteur change son état ainsi que ceux qui lui sont adjacents, le but du jeu est d’éteindre tous les interrupteurs, préférablement avec un nombre de coups le plus petit possible. Bien qu’en apparence simple, ce jeu s’avère être dans la pratique un vrai casse-tête...

Par conséquent, notre atelier est dédié à une étude mathématique de ce jeu. Disposant d’un temps relativement limité (3 heures), la modélisation que nous proposons aux élèves est fortement encadrée. Chaque étape de celle-ci va à l’essentiel, sans s’attarder sur un formalisme trop abstrait qui pourrait perdre l’élève, et chaque notion mathématique introduite est illustrée autant que possible sur le jeu. Finalement, nous montrons que trouver une solution du jeu, c’est-à-dire trouver les interrupteurs sur lesquels appuyer pour tout éteindre, est équivalent à résoudre un système linéaire (notion déjà étudiée par les élèves) dans l’ensemble {0,1} tel que 1+1=0 !
A la fin de l’atelier, nous enfonçons le clou : étant donné que les solutions d’un système linéaire (et donc d’un problème de Lights Out) peuvent être calculées explicitement à l’aide du pivot de Gauss, nous présentons aux élèves une version du jeu qui contient un programme que nous avons réalisé. Celui-ci, basé essentiellement sur la méthode du Pivot de Gauss, est capable d’éteindre tous les interrupteurs allumés au début de la partie (peu importe leur nombre et leur disposition) en fournissant non seulement toutes les solutions mais en affichant également à l’écran une des meilleures solutions, celles qui nécessitent le moins de coups. Ceci permet de concrétiser la modélisation et l’étude que nous avons faites mais également de mettre en avant un exemple d’interaction entre les mathématiques et l’informatique.

Nous commencerons logiquement cet article par une description du Lights Out. Puis nous détaillerons le déroulement de l’atelier que nous avons réalisé. Diverses réactions et remarques des élèves seront également rapportées. Dans la dernière Section « Pour en savoir plus... », destinée au lecteur motivé, nous reprenons la modélisation faite dans l’atelier mais de manière plus poussée dans le but de montrer les concepts abstraits que nous avons implicitement utilisés devant les élèves. De même, les grandes lignes de l’algorithme que nous avons utilisé pour créer le programme résolvant le jeu sont données.

Le cadre de l’atelier

Les règles du Lights Out

Le jeu consiste en une grille de 5 par 5 interrupteurs qui peuvent être soit allumés (en jaune), soit éteints (en noir). Quand le jeu démarre, certains interrupteurs sont allumés, leur disposition et leur nombre étant aléatoires. Le but du jeu est alors d’éteindre tous les interrupteurs, de préférence avec un nombre minimal de coups, en utilisant la règle suivante :

Appuyer sur un interrupteur change son état et l’état de ses voisins situés au nord, au sud, à l’est et à l’ouest si ces derniers existent.

En effet, précisons que si nous appuyons sur un interrupteur situé sur le bord ou dans un coin, alors on ne change l’état que de ce dernier et des interrupteurs voisins existants. Une petite illustration est souvent bien meilleure qu’un grand discours :

Les conditions de l’atelier

L’atelier que nous proposons a été réalisé dans le cadre du stage « Faire des Maths autrement... » se déroulant à l’ISTV. Ce stage est destiné à des lycéens en classe de seconde sur la base du volontariat. Durant cette semaine, différents ateliers de vulgarisation d’une durée de 1h30 à 3h environ sont proposés (voir [3]).

Notre atelier a une durée de 3 heures environ et se déroule dans une salle informatique munie d’un projecteur.

Les élèves se répartissent en binôme, chaque binôme disposant d’un ordinateur dans lequel est installé le dossier contenant les quatre versions du jeu utilisées lors de l’atelier (pour information, ce dossier est téléchargeable en bas de l’article). Durant nos différentes sessions, nous avions face à nous une vingtaine d’élèves. Une fiche de questions est distribuée à chaque élève : elle a pour but de structurer le déroulement de l’atelier. Cette fiche possède des phrases à trous, remplies avec les encadrants durant l’atelier, et des exercices, destinés à être réalisés en autonomie et corrigés ensuite. La fiche de questions est disponible en téléchargement ainsi que sa version corrigée en bas de l’article.

Le déroulement de l’atelier

Dans cette section, nous expliquons le déroulement de l’atelier. Celle-ci a été découpée en sous-sections et une interactivité a été insérée : du texte en vertcorrespond à une explication supplémentaire et en bleucorrespond à une remarque de notre part.

Découverte

L’atelier démarre par une brève description du Lights Out : règles du jeu, objectif,... Ceci étant relativement simple à comprendre, nous laissons rapidement aux élèves l’opportunité de manipuler le jeu par eux-mêmes sur l’ordinateur. Pour cela, nous leur faisons utiliser la version du jeu « Classical Lights Out », qui laisse en particulier la possibilité de tester des configurations prédéfiniesqui sont en fait relativement simples car possédant beaucoup de symétries et des configurations générées aléatoirement par l’ordinateur.
Les lycéens prennent vite en main le jeu, qui leur semble d’ailleurs assez facile à résoudre... ce qui n’est pas le cas ! Effectivement, parmi les quatre groupes de vingt élèves que nous avons encadrés sur les deux années, peu d’élèves ont réussi à résoudre un jeu généré aléatoirement et aucun n’a trouvé une méthode qui marche à coup sûr, malgré l’acharnement de certains...

La difficulté à résoudre le jeu, qui engendre au passage une certaine frustration commune, permet de faire sentir progressivement la nécessité de prendre un peu de recul et de regarder le jeu sous un autre angle... l’angle des mathématiques bien sûr !

Du jeu aux maths

Suite à cette manipulation du jeu, nous attaquons la fiche de questions, distribuée au début de l’atelier.
Nous expliquons à nos mathématiciens en herbe que le premier objectif va être de ramener le jeu (et toutes les règles qui l’accompagnent) à un cadre mathématique approprié, c’est-à-dire faire une modélisation.

Le calcul binaire en mathématiques

Dans un premier temps, nous introduisons une nouvelle addition + sur l’ensemble {0,1} qui vérifie :

0 + 0 = 0 0 + 1 = 1
1 + 0 = 1 1 + 1 = 0


On explique oralement la dernière relationqui est en fait la moins naturelle des quatre à l’aide du jeu : appuyer deux fois sur un même interrupteur revient à ne rien faire. Contrairement à nos craintes, la plupart des lycéens ont compris rapidement cette nouvelle addition.

Les états d’un interrupteur et la configuration d’un jeu

On continue avec la modélisation de l’état d’un interrupteur : on choisit ici que la valeur 0 correspond au fait que l’interrupteur est éteint, tandis que la valeur 1 est associée au fait que l’interrupteur est allumé. Ce choix arbitraire des valeurs 0 et 1 a été facilement accepté par les élèves.

Avant de continuer, on procède à une simplification : pour réduire la taille des calculs durant l’atelier avec les lycéens (autrement dit, pour éviter de les faire fuir), on étudie le jeu à 2 par 2 interrupteurs au lieu de la version classique 5 par 5. Bien entendu, nous leur expliquons que la modélisation dans le cas 5 par 5 suit le raisonnement qui va être présenté.

La configuration d’un jeu, c’est-à-dire l’état de tous les interrupteurs de la grille, se modélise aisément : elle est associée à une colonne (en termes mathématiques, un vecteur colonne). Pour cela, nous définissons une numérotation sur la grille d’interrupteurs de la façon suivante :

et nous construisons la colonne comme suit : la valeur de la j-ième ligne de la colonnej = 1,2,3 ou 4 est donnée par l’état du j-ième interrupteur. Nous proposons aux élèves quelques exemples pour illustrer cela ; en voici un :

Nous précisons au passage que le gris (dans les illustrations ici et dans la fiche de questions) indique un interrupteur allumé, alors que le blanc indique qu’il est éteint. Ce choix est une conséquence directe de notre sens de l’écologieet économie : nous ne pouvions imprimer autant de fiches de questions en couleurs... Dans l’exemple ci-dessus, le premier et le dernier interrupteur sont allumés, il y a donc un 1 dans la première et dernière ligne de la colonne, ailleurs ce sont des 0. Et on comprend bien ici la raison pour laquelle nous avons réduit la taille du jeu : travailler avec une colonne à 25 lignes devant des lycéens peut être apparenté à une douce folie...

Les actions élémentaires

Jouer au Lights Out ne consiste pas qu’à regarder la grille d’interrupteurs mais également à interagir avec elle ! Le but de cette partie est de modéliser ces interactions. Plus précisément, nous commençons par modéliser le fait d’appuyer sur un seul interrupteur, ce que nous appellerons une action élémentaire. Comme il y a quatre interrupteurs, il y a quatre actions élémentaires, que nous notons comme suit :


On remarque que la notation "+" est utilisée pour véhiculer l’idée d’une interactionappuyer un interrupteur. Afin qu’ils comprennent le principe, nous prenons le temps de décrire la modélisation de l’action élémentaire +A1. Pour cela, nous regardons les deux exemples suivants :


Nous montrons aux élèves que le passage de la colonne de gauchela colonne associée à la configuration de départ à la colonne de droitela colonne associée à la configuration d’arrivée (dans les deux exemples) se fait à l’aide d’additions sur les lignes de la colonne de gauche. Pour bien expliquer ce principe, nous détaillons proprement au tableau les calculs en exploitant la nouvelle addition. Précisément, la j-ième ligne de la colonne de gauche reçoit +1 si le j-ième interrupteur est connecté au premier interrupteur : en effet, en appuyant sur le premier interrupteur, nous changeons l’état de ceux qui lui sont connectés. Et il vient que ces quatre additions peuvent être codées dans l’addition de la colonne suivante :

Ceci nous permet de conclure que l’action élémentaire +A1appuyer sur le premier interrupteur est modélisée par l’addition de la colonne ci-dessus. Remarquons que ce passage de quatre additions scalaires à une seule addition vectorielle n’a pas été un obstacle pour les lycéens : nous avons insisté sur le fait que c’est une simple définition qui ne cache rien de compliqué.

Les élèves ayant vu comment modéliser l’action élémentaire +A1, nous leur laissons en exercice modéliser les actions élémentaires +A2, +A3 et +A4. Nous leur donnons une astuce supplémentaire pour déterminer les colonnes à additionner : En partant de la configuration où tous les interrupteurs sont éteints et en appuyant sur l’interrupteur i, c’est-à-dire en réalisant l’action élémentaire +Ai, on obtient une configuration avec certains interrupteurs allumés dont la colonne associée est en fait la colonne que l’on additionnera à chaque fois que l’on réalisera l’action élémentaire +Ai.

Les actions

Quand on joue au Lights Out, il est souvent nécessaire d’appuyer sur plusieurs interrupteurs pour tout éteindreles élèves ont bien pris conscience de cela dès le début de l’atelier. Le fait d’appuyer successivement sur plusieurs interrupteurs (c’est-à-dire faire une succession d’actions élémentaires) est appelé une action, ce que nous allons modéliser à présent.

Nous utilisons une nouvelle fois un exemple : l’action "appuyer sur le premier interrupteur puis sur le deuxième". Pour cela, nous partons de la configuration où tous les interrupteurs sont éteints, nous appuyons sur le premier interrupteur puis sur le deuxième interrupteur et nous observons la configuration finale. La colonne associée à cette dernière configuration est celle utilisée pour modéliser l’action "appuyer sur le premier interrupteur puis sur le deuxième interrupteur", d’après l’astuce expliquée ci-dessus.

Nous faisons les calculs pas à pas au tableau en nous aidant du schéma ci-dessus : pour passer de la colonne de gauche à la colonne centrale, nous avons fait l’addition +A1 (qui a été déterminée précédemment) et c’est ensuite l’addition +A2 qui a été effectuée sur la colonne centrale pour obtenir la colonne de droite. Ainsi l’action "appuyer sur le premier interrupteur puis sur le deuxième", que l’on peut noter +A1+A2, correspond à l’addition de la colonne de droite ci-dessus.

Nous laissons ensuite nos apprentis-mathématicien modéliser différentes actions demandées dans la fiche de questions en appliquant le raisonnement ci-dessus. En particulier, nous les encourageons à utiliser la version du jeu "Small Lights Out" afin qu’ils développent leur intuition en visualisant leurs calculs. Parmi ces questions, il leur est demandé de calculer +A1 +A1appuyer deux fois sur le premier interrupteur et +A1 +A1 +A1appuyer trois fois sur le premier interrupteur dans le but d’illustrer mathématiquement le fait qu’appuyer un nombre pair de fois sur un même interrupteur ne modifie pas la configuration alors qu’appuyer un nombre impair de fois revient à n’appuyer qu’une seule fois. Il leur est également demandé d’appuyer sur les interrupteurs 1, 2 et 3 dans différents ordres et de modéliser ces différentes actions. Ceci permet d’illustrer le fait que l’ordre des interrupteurs sur lesquels on appuie n’a pas d’importance, ce qui est à mettre en lien avec le fait que l’ordre des termes dans une addition ne change pas le résultat.

Grâce aux questions précédentes, nous sommes en mesure de leur expliquer qu’une action peut se décomposer sous la forme suivante :

Cette écritureun peu complexe au premier abord nous dit qu’il suffit de savoir combien de fois nous appuyons sur chaque interrupteur pour décrire l’action considérée. Ici, les quantités x, y, z et t correspondent aux nombres de coups que l’on fait sur les interrupteurs 1, 2, 3 et 4 respectivement. Remarquons par ailleurs que ces quatre nombres appartiennent à l’ensemble {0, 1} : ceci provient du fait qu’appuyer plus de deux fois sur un même interrupteur produit des coups inutiles. Les élèves ont eu quelques difficultés à comprendre cette écriture abstraite (mais indispensable pour la suite de la modélisation). Nous avons donc passé du temps à l’expliquer à l’aide d’exemples simples.

Un problème mathématique

Dans cette courte mais importante sous-section, nous utilisons toute la modélisation faite précédemment pour transformer le problème du « Lights Out » en un problème mathématique que les élèves connaissent.
Pour cela, il faut bien entendu définir précisément ce qu’est le problème du « Lights Out » : à l’aide d’un simple exemple (voir l’image ci-dessous), nous leur expliquons que la question est de trouver une action (notion définie dans la sous-section précédente) qui permet de tout éteindre étant donnée une configuration de départ. En termes mathématiques, il s’agit de trouver une action +A qui permet de passer de la colonne donnée par la configuration de départ à la colonne composée que de zéros.


A présent, nous utilisons la dernière remarque de la sous-section précédente : toute action peut se décomposer en une somme d’actions élémentaires :

où les quantités x, y, z et t représentent le nombre de fois où l’on doit appuyer sur l’interrupteur 1,2,3 et 4 respectivement. Cela nous mène à l’égalité suivante :


La précédente égalité peut s’interpréter comme suit : à partir de la configuration de départ, on appuie x fois sur l’interrupteur 1 (ce qui correspond à faire + x A1), puis on appuie y fois sur l’interrupteur 2 (ce qui correspond à faire +yA2), et ainsi de suite pour obtenir au finale la configuration où tout est éteint, c’est-à-dire la colonne composée uniquement de 0. Remarquons que nous avons une nouvelle fois utilisé le fait que l’ordre dans lequel nous appuyons sur chaque interrupteur n’a pas d’importance.
Bien qu’en apparence effrayante, cette égalité n’a pas démoralisé les élèves, bien au contraire. La seule difficulté consistait à expliquer (voire ré-expliquer) progressivement comment une telle égalité s’interprète en termes du jeu.
Et l’égalité ci-dessus donne le système linéaire suivant où x, y, z et t sont les inconnues :


En écrivant au tableau un exemple de système linéaire à deux équations et deux inconnues, nos apprentis mathématiciens se rendent compte que ce qu’ils voient n’est qu’un système linéaire à quatre équations et quatre inconnuesune généralisation de ce qu’ils connaissent.
Après un petit rafraîchissement de leur mémoire sur la méthode par élimination (ou la méthode du Pivot de Gauss) sur un exemple simple, nous leur expliquons que cette méthode fonctionne également pour résoudre le gros système à 4 équations et 4 inconnus. Mais étant donné le peu de temps dont nous disposons, nous sautons cette étape de calculsà la plus grande joie des lycéens et nous leur donnons le résultat :

x = 0 , y = 0 , z = 1 , t = 1

Nous évitons de rester dans l’abstraction : nous montrons que si nous appuyons effectivement sur les interrupteurs 3 et 4 alors nous éteignons la configuration de départ ci-dessus.
En résumé, nous leur avons montré que le problème du jeu était équivalent à un problème de résolution d’un système linéaire, problème résolu depuis bien longtemps grâce au Pivot de Gauss.

Exploitation du modèle

Le but principal de cette sous-section est de montrer aux élèves que le jeu peut posséder plusieurs solutions et comment celles-ci peuvent être déterminées. Tout cela provient en fait de l’étude abstraite réalisée dans la section « Pour en savoir plus... », Partie Mathématique, qui est inaccessible à un niveau lycéen. Néanmoins des principes mathématiques généraux s’illustrent sur le jeu, comme le fait que toutes les solutions d’un système linéaire peuvent être obtenues à partir d’une solution particulière à laquelle on ajoute toutes les combinaisons des solutions du système homogène associé.

Des actions particulières

Précisons avant toute chose que nous allons utiliser le jeu à 4 par 4 interrupteurs car le jeu en 2 par 2 n’est pas suffisamment grand pour posséder plusieurs solutions. En particulier, les élèves vont utiliser la version « Intermediate Lights Out ».

Pour commencer, nous leur donnons deux actions +A’ et +A’’ définies ci-dessous,

qu’ils doivent appliquer sur le jeu : il s’avère que ces actions ne changent pas la configuration du jeu, peu importe celle que l’on choisit ! En réalité, elles sont données par des vecteurs du noyau la matrice associée au jeu (mais ça nous ne le disons pas aux lycéens).

Après leur avoir demandé une petite réflexion sur la nature de +A’+A’’qui est encore un vecteur du noyau (+A’ et +A’’ ne modifiant pas la configuration du jeu, la succession de ces deux actions ne la modifiera pas non plus), nous leur définissons ce type d’action : on les appellera des actions nulles !

L’existence de plusieurs solutions

Les actions nulles définies précédemment ne sont pas si inutiles que ce que leur nom pourrait laisser penser : elles servent à trouver toutes les actions qui vont éteindre une configuration de départ donnée. Pour illustrer cette idée, nous utilisons la configuration de départ suivante :

qui peut être éteinte par l’action particulière :

La fin de cette partie de l’atelier consiste à faire additionner aux élèves toutes les actions nulles données ci-dessus à l’action particulière, et à leur faire tester les résultats sur le jeu : les actions obtenues restent des solutions du jeu associé à la configuration de départ ci-dessus. En particulier, ils peuvent se rendre compte que le nombre de solutions d’un jeu ne dépend pas de la configuration de départ mais uniquement des dimensions du jeu lui-même (car le nombre d’actions nulles ne dépend que de la taille du jeu) !

Les meilleures solutions

Pour terminer, une question naturelle consiste à se demander quelle est (ou quelles sont) la (les) meilleure(s) solution(s) du jeu associée(s) à la configuration de départ ci-dessus ? C’est-à-dire celle(s) qui comporte(nt) le moins d’actions élémentaires ?
Étant donné que nous avons à disposition toutes les solutions, les lycéens devinent facilement la réponse : ils comptent le nombre de coups de chaque solution et choisissent celles qui en possèdent le moins, à savoir les deux ci-dessous dans notre exemple :

Des maths au jeu

Dans cette dernière partie de l’atelier, nous montrons enfin aux élèves une concrétisation de ce qui peut être fait avec les mathématiques vues dans l’atelier.


Nous leur présentons la version « Advanced Lights Out » qui contient de nouvelles fonctionnalités par rapport aux autres versions déjà utilisées. En particulier, elle dispose de deux intelligences artificielles qui permettent d’éteindre les configurations proposées par le jeu.

- La première méthode est totalement indépendante de l’étude mathématique précédente ; elle repose sur un algorithme de minimisation de coûts et est de nature itérative. En exécutant à plusieurs reprises cette intelligence artificielle devant les élèves, ils voient que cette méthode résout toujours le jeu. Cependant elle peut fournir non seulement des solutions de plus de 25 coups mais en plus, pour une même configuration de départ, elle peut donner des solutions différentes. Cette IA nous sert principalement à montrer que l’on peut se passer des mathématiques pour résoudre le jeu du ’’Lights Out’’ mais que la méthode proposée juste ici est en fait loin d’être satisfaisante...

- La seconde méthode est celle construite en utilisant toute la modélisation mathématique présentée dans l’atelier ainsi que le pivot de Gauss. En faisant quelques exemples, les élèves découvrent que ce programme calcule non seulement toutes les solutions (qui s’affichent à l’écran dans des fichiers .txt) mais qu’en plus de cela, il est capable de choisir l’une des meilleures solutions. Par ailleurs en comparant les résultats fournis par la méthode informatique et par la méthode mathématique, ils se rendent très vite compte que cette dernière est bien plus performante.

Enfin pour enfoncer le clou, nous montrons que la méthode mathématique peut également résoudre le jeu dans d’autres dimensions et avec plus de couleurs. Par exemple, la règle du jeu à 5 couleurs est la suivante : en cliquant sur un interrupteur noir, nous obtenons un interrupteur vert, puis rouge, puis bleu, puis jaune et enfin noir. Autrement dit, il faut appuyer 5 fois sur un même interrupteur pour faire une boucle.



Si le temps le permet, l’atelier se conclut par un temps libre laissé aux élèves pour qu’ils jouent à nouveau au « Lights Out » avec, en tête, tout ce qu’ils viennent de découvrir.

Pour en savoir plus

Partie mathématique

Dans la première partie de cette section, nous détaillons l’étude mathématique qui nous a permis de comprendre et de résoudre le Lights Out. Notons que cette partie est en fait une simple annexe qui peut aider le lecteur à mieux comprendre les mathématiques qui se cachent derrière le Lights Out. Le niveau nécessaire pour comprendre les résultats est plus ou moins équivalent au programme d’algèbre étudiée en première année universitaire.

On commence par rappeler que Z2, ou plus couramment Z/2Z, est l’ensemble {0, 1} muni de la loi additive + telle que 1 + 1 = 0Cela correspond à ce que l’on appelle le calcul binaire..

1 Modélisation des règles du jeu

État d’un interrupteur

On démarre naturellement avec la modélisation des règles qui constituent le jeu. Ceci nous permettra de modéliser le problème du jeu en termes mathématiques.

La première modélisation est celle de l’état d’un interrupteur : ceci sera modélisé par un élément de l’ensemble Z2. Tout comme dans l’atelier, on choisit arbitrairement la valeur 0 pour désigner un interrupteur éteint, et 1 pour désigner un interrupteur allumé.

Configuration du jeu

Dans tout ce qui va suivre, le nombre entier m désignera à des fins de lisibilité le nombre d’interrupteurs constituant la grille du jeu (dans la version classique du jeu, m = 25 mais m peut être égal à n’importe quel carré parfait). Tout d’abord, fixons une numérotation arbitraire (mais en un sens logique) sur les interrupteurs : le premier interrupteur est choisi comme étant celui en haut à gauche, puis nous numérotons par ordre croissant de gauche à droite, jusqu’à arriver au dernier interrupteur (le m-ième) situé en bas à droite de la grille.

Modélisons maintenant la configuration d’un jeu, c’est-à-dire l’état de la grille d’interrupteurs. Comme dans l’atelier, ceci sera donné par un vecteur colonne dépendant bien entendu du nombre d’interrupteurs m :

La configuration d’un jeu est donnée par le vecteur C = (c1,...,cm) ∈ (Z2)m défini comme suit :

  • si le i-ième interrupteur du jeu est allumé, alors ci = 1 ;
  • si le i-ième interrupteur du jeu est éteint, alors ci = 0.

Notons que l’ensemble (Z2)m correspond mathématiquement au produit cartésien de Z2 m fois. Autrement dit, une configuration d’un jeu n’est rien d’autre qu’un vecteur à m composantes ayant pour valeur 0 ou 1.


Exemple : le cas m = 4.

Remarque : On peut voir l’ensemble (Z2)m comme étant l’ensemble de toutes les configurations possibles.

Actions élémentaire

La définition d’action élémentaire que nous utilisons dans cette partie est la même que celle utilisée durant l’atelier : une action élémentaire correspond simplement au fait d’appuyer sur un interrupteur. Comme nous l’avons vu dans l’atelier, une façon simple de décrire une action élémentaire est de la modéliser par l’addition d’un vecteur précis de Z2.
Par ailleurs, il est clair qu’il existe m actions élémentaires pour une grille possédant m interrupteurs. Ainsi m vecteurs doivent être déterminés pour définir mathématiquement ces actions :

Pour i ∈ {1, ..., m}, appuyer sur le i-ième interrupteur correspond mathématiquement à additionner à la configuration du jeu C ∈ (Z2)m le vecteur vi = (vi,1, ..., vi,m) défini par :

  • vi,j prend la valeur 1 si l’état du j-ième interrupteur change après avoir appuyé sur le i-ième interrupteur, autrement dit si l’interrupteur j est connecté à l’interrupteur i ;
  • vi,k prend la valeur 0 si l’état du k-ième interrupteur reste inchangé après avoir appuyé sur le i-ième interrupteur, autrement dit si l’interrupteur k n’est pas connecté à l’interrupteur i.

Par conséquent, la configuration du jeu après avoir appuyé sur l’interrupteur i à partir de la configuration C = (c1, ..., cm) est donnée par :

fi(C) = C + vi = (c1 + vi,1, ..., cm + vi,m) .

Autrement dit, l’action élémentaire "Appuyer sur le i-ième interrupteur" définit une fonction fi : (Z2)m → (Z2)m qui est uniquement déterminée par le vecteur vi. A noter qu’il nous arrivera de dire que fi est simplement l’action élémentaire "Appuyer sur le i-ième interrupteur".
Maintenant, observons que ces actions élémentaires fi vérifient des relations qui s’interprètent visuellement dans le jeu :

  • fi o fi = id, pour tout i ∈ {1,...,m} ;
  • fi o fj = fj o fi, pour tout i,j ∈ {1,...,m}.

La première relation nous indique qu’appuyer deux fois sur le même interrupteur correspond à ne rien faire et la seconde relationcommutativité des fi montre que l’ordre dans lequel nous appuyons sur les interrupteurs n’a pas d’incidence sur le résultat.

Nous définissons la matrice A carrée d’ordre m comme suit A = (v1, ..., vm), écrite ici comme une liste de colonnes. En particulier, si ei est le vecteur de (Z2)m dont toutes les composantes contiennent la valeur 0 sauf la i-ième qui contient la valeur 1, alors on a la relation :

vi = A ei .

On remarque donc que la matrice A permet de regrouper tous les vecteurs associés aux actions élémentaires en un seul et même objet.

Actions

Rappelons avant toute chose qu’une action correspond au fait d’appuyer sur plusieurs interrupteurs. Intuitivement, une action signifie que l’on fait une succession d’actions élémentaires. Par exemple, la configuration C3 obtenue après avoir appuyé sur les trois premiers interrupteurs du jeu à m interrupteurs à partir de la configuration C = (c1, ..., cm) s’obtient de la manière suivante :

C3 = ((C + v1) + v2) + v3 .

Autrement dit, nous avons

C3 = C + v1 + v2 + v3 ,

montrant qu’une action en général correspond à faire la somme des vecteurs associés aux actions élémentaires composant l’action considérée. En particulier, si on pose le vecteur X = e1 + e2 + e3, alors la configuration C3 peut s’écrire en fonction de la matrice A définie ci-dessus :

C3 = C + Ae1 + Ae2 + Ae3 = C + A(e1 + e2 + e3) = C + AX .

2 Résolution du problème du jeu

Rappelons que le problème du Lights Out consiste à trouver (si possible) une action qui permet d’éteindre tous les interrupteurs d’une configuration de départ (dite initiale) donnée. Pour une telle configuration CI ∈ (Z2)m, l’action recherchée sera appelée solution du jeu relativement à CI.

Existence d’une solution du jeu

Contrairement à ce que l’atelier peut laisser croire, il existe des configurations initiales qui ne peuvent être éteintes avec les règles du jeu... Le but de cette sous-section est de déterminer un critère d’existence d’au moins une solution du jeu relativement à une configuration initiale, c’est-à-dire l’existence d’une action qui permet d’éteindre cette configuration.
On se donne une configuration initiale CI que l’on cherche à éteindre. Pour cela, nous allons appuyer x1 fois sur l’interrupteur 1, x2 fois sur l’interrupteur 2, ..., et xm fois sur l’interrupteur m, ce qui se traduit mathématiquement par :

CI + x1v1 + x2v2 + ... + xmvm = 0(Z2)m ,  (0)

où 0(Z2)m est le vecteur nul de (Z2)m : c’est la configuration associée au jeu ne contenant que des interrupteurs éteints. De plus, avec les notations de la sous-section précédente, l’égalité (0) est équivalente à

CI + A(x1e1 + x2e2 + ... + xmem) = 0(Z2)m .

Et en définissant X = (x1, x2, ..., xm), nous trouvons que l’égalité (0) est équivalente à l’égalité (1) suivante :

CI = AX ,  (1)

où nous avons utilisé le fait que -1 = 1 dans Z2. Par conséquent :

Il existe au moins une solution du jeu relativement à une configuration initiale CI si et seulement s’il existe un vecteur X qui satisfait l’équation : CI = A X.

En particulier, le vecteur X nous renseigne sur les interrupteurs sur lesquels nous devons appuyer pour éteindre tous les interrupteurs à partir de la configuration initiale CI :

  • si xi = 1 alors nous devons appuyer sur le i-ième interrupteur ;
  • si xi = 0 alors nous n’avons pas à appuyer sur le i-ième interrupteur.

Pour conclure ce point, remarquons que l’existence d’une solution d’une équation du type (1) est équivalente au fait que CI appartienne à l’image de la matrice A (notée Im(A)), par définition même de cet ensemble. Nous obtenons donc

Critère d’existence : Il existe au moins une solution du jeu relativement à configuration initiale CI si et seulement si CI ∈ Im(A).

A la recherche des meilleures solutions

Nous venons donc de voir que le problème du Lights Out relativement à une configuration initiale CI admet une solution si et seulement si CI est dans l’image de A. Dans ce cas, le (ou les) solution(s) X satisfont l’équation CI = AX.
Or, un résultat d’algèbre linéaire nous fournit la structure de toutes les solutions de cette équation connaissant au moins une particulière X0 : l’ensemble de toutes les solutions de l’équation CI = AX est donné par

{ X0 } + Ker(A) ,

où Ker(A) est l’ensemble formé des vecteurs X ∈ (Z2)m tels que AX = 0(Z2)m.
Ce résultat explique théoriquement ce qui a été fait durant l’atelier, dans la sous-section "Exploitation des résultats". Effectivement on remarque que les vecteurs du noyau de A modélisent les actions nullesles actions qui laissent la configuration initiale inchangée. Et le résultat théorique nous dit que, dès que nous disposons d’une action particulière qui éteint le jeu relativement à une configuration initiale donnée, il suffit de combiner cette action particulière avec tous les vecteurs du noyau de la matrice A pour obtenir toutes les solutions.

Grâce à cela, nous sommes en mesure de déterminer les meilleures solutions du jeu relativement à une configuration initiale, c’est-à-dire celles qui nécessitent le moins de coups possible pour éteindre tous les interrupteurs.
Pour déterminer ces meilleures solutions, nous utilisons le fait que nous pouvons calculer théoriquement toutes les solutions du jeu relativement à une configuration CIvoir la section suivante pour un algorithme permettant de les calculer. Puisque les solutions du jeu sont données par des vecteurs de (Z2)m dont les composantes nous indiquent les interrupteurs sur lesquels appuyer, il suffit simplement de choisir les vecteurs qui contiennent le moins de 1 dans leurs composantes pour obtenir les meilleures solutions.

Partie informatique

Dans cette sous-partie, nous présentons les grandes lignes d’un algorithme permettant de calculer toutes les solutions du jeu. Nous faisons remarquer que cet algorithme n’a pas vocation à être optimal par rapport au temps de calcul : nous l’avons réalisé de telle sorte à ce qu’il reste le plus intuitif possible.
Par souci de simplicité, nous allons illustrer les grandes étapes de l’algorithme à l’aide d’un exemple : on se donne la configuration initiale suivante, dans le cadre du jeu à 5 par 5 interrupteurs et 2 couleurs :

1 Les données du problème

La première étape consiste à récupérer sous la forme d’un vecteur CI de taille 25 la configuration initiale ci-dessus que l’on essaie d’éteindre. Comme dans l’atelier, 0 va signifier que l’interrupteur est éteint et 1 qu’il est allumé, et la numérotation des interrupteurs reste la même. Dans notre exemple, nous avons :

Ci = ( 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0 ) .

Ensuite, il va nous falloir la matrice qui décrit les connexions entre les interrupteurs. Il est intéressant de remarquer que cette matrice est indépendante des configurations du jeu. Elle est donnée par la matrice A suivante :

2 Calcul d’une solution particulière

En appliquant un Pivot de Gauss, nous obtenons une matrice échelonnée en ligne équivalente à la matrice A ; on la notera Aéchelonnée. Par ailleurs, nous appliquons exactement les mêmes opérations élémentaires sur la matrice identité 25 par 25, ce qui donne la matrice Iéchelonnée.

A présent, nous allons nous attarder sur les deux dernières lignes de la matrice Aéchelonnées qui sont en fait des lignes nulles, c’est-à-dire des lignes ne contenant que des 0. Étant donné que la i-ième ligne de la matrice Iéchelonnée nous indique les opérations à faire sur les lignes de A pour obtenir la i-ième ligne de la matrice Aéchelonnée, nous voyons donc que les deux dernières lignes de la matrice Iéchelonnée correspondent en réalité à deux vecteurs du noyau de A, XN(1) et XN(2) (correspondant aux actions nulles décrites dans l’atelier) :

Les vecteurs du noyau permettent notamment de supprimer les lignes et colonnes de la matrice A pour obtenir une sous-matrice de A qui soit inversible. Plus précisément, ils nous indiquent les combinaisons linéaires entre les lignes de A et donc de trouver deux lignes qui peuvent s’exprimer en fonction des autres (car le noyau est de dimension 2 d’après le pivot de Gauss). Il faut simplement faire attention à ne pas exprimer la ligne i en fonction de la ligne j et inversement, auquel cas nous supprimerions deux lignes liées entre elles... Pour cela, une idée consiste à appliquer un simple pivot de Gauss sur les vecteurs du noyau, considérés comme une matrice de type (2, 25), afin de supprimer ces combinaisons linéaires cachées. Ce procédé permettant d’exprimer certaines lignes en fonction des autres peut s’interpréter en termes du jeu : si par exemple la ligne 3 s’exprime en fonction des lignes 5 et 6, alors cela signifie que l’action élémentaire "appuyer sur l’interrupteur 3" peut être remplacée par l’action "appuyer sur les interrupteurs 5 et 6".

Après avoir trouvé 2 lignes (dont les indices vont être gardés en mémoire pour la suite) qui sont combinaisons linéaires des 23 autres, nous supprimons dans la matrice A ces deux lignes ainsi que les colonnes associées, puisque la matrice est symétrique. La matrice de taille 23 par 23 que l’on obtient, notée Aréduit, est alors inversible !


Ensuite, nous inversons cette matrice Aréduit par le pivot de Gauss :



Pour calculer une solution particulière du jeu, on va procéder comme suit : on supprime dans le vecteur CI les deux premières lignes, autrement dit les mêmes lignes que celles supprimées dans la matrice A (d’où l’intérêt d’avoir gardé en mémoire ces lignes). Le vecteur que l’on obtient sera noté CI,réduit :

CI,réduit = -, -, ( 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 ) .


On multiplie à présent la matrice Aréduit-1 par CI,réduit, ce qui nous donne le vecteur Xréduit suivant :

Xréduit = -, -, ( 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0 ) .


Il ne nous reste qu’à augmenter de 0 la solution Xréduit aux indices qui ont été supprimés, à savoir 1 et 2 :

X = ( 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0 ) .


Ce vecteur X est alors une solution particulière et ainsi, en appuyant sur les interrupteurs 3, 5, 7, 13, 15, 16, 17, 23 (les indices du vecteur X où il y a des 1), le jeu passera à l’état tout éteint.



3 Calcul de toutes les solutions

D’après la section "Partie mathématiques", nous savons que pour trouver toutes les solutions du jeu, il suffit d’additionner à une solution particulière les vecteurs du noyau. Le noyau de A étant de dimension 2 et les vecteurs XN(1) et XN(2) n’étant pas colinéaires, ils forment alors une base du noyau : il suffit donc de calculer toutes les combinaisons linéaires de ces deux vecteurs pour obtenir tous les vecteurs du noyau. Dans notre cas, nous avons :

0, XN(1), XN(2), (XN(1) + XN(2)) .


Par conséquent, toutes les solutions permettant d’éteindre la configuration initiale considérée dans cette partie sont données par :

X + 0, X + XN(1), X + XN(2), X + (XN(1) + XN(2)) .


4 Un algorithme généralisable

L’algorithme présenté n’est pas spécifique au cas 5 par 5 interrupteurs avec deux couleurs : il est applicable dans n’importe quelle taille du jeu et avec n’importe quel nombre de couleurs, pourvu que celui-ci soit un nombre premier ! Effectivement des problèmes pourraient se poser lors de l’application du pivot de Gauss : un produit de deux termes non nul pourrait être égal à 0... Par exemple, 2 x 2 = 4 = 0 dans Z4.

Par exemple, on peut considérer la règle à 5 couleurs suivante :

Dans ce cas, nous obtenons une nouvelle fois des matrices composées comme précédemment de 0 et de 1 uniquement mais vus comme des éléments de Z5. L’algorithme, quant à lui, reste le même bien qu’il faille lui indiquer que les calculs se font modulo 5.


5 Cas particulier de l’algorithme

Il est intéressant de noter que, dans certains cas, la matrice A associée au jeu est inversible. Par exemple, cela est vrai dans le cas 10 par 10 interrupteurs avec 2 couleurs. Dans le cas où A est inversible nous avons Aéchelonnée = Aréduit selon les notations précédentes. Et donc, l’algorithme consiste simplement à calculer l’inverse de A et de multiplier cet inverse par le vecteur CI. Il est en autre inutile de chercher les lignes à supprimer, de calculer le noyau,...

6 Précisions techniques et légales

Des soucis au niveau de l’affichage ont été détectés quand la version de Java installée sur la machine ne provient pas d’Oracle. Nous vous conseillons donc de télécharger ici le Java SE d’Oracle afin de n’avoir aucun problème lors de l’exécution du jeu.

De plus, le code est open-source et est soumis à la licence GNU/GPL v3.0, ce qui brièvement signifie que :

  1. Toute personne est libre d’exécuter le logiciel, pour n’importe quel usage ;
  2. Toute personne est libre d’étudier le fonctionnement du programme et de l’adapter à ses besoins ;
  3. Toute personne est libre de redistribuer des copies ;
  4. Toute personne a interdiction d’en faire un usage commercial sans l’accord explicite des auteurs ;
  5. Toute personne a l’obligation de faire bénéficier à la communauté des versions modifiées.


Conclusion

L’objectif de notre atelier est triple : montrer la pertinence de l’utilisation des mathématiques dans la résolution d’un problème concret sous réserve d’une modélisation appropriée, illustrer des concepts mathématiques abstraits au travers d’un jeu et souligner l’importance de l’interaction des mathématiques et de l’informatique.

Nous espérons qu’une telle approche puisse augmenter la sensibilité de certains élèves vis-à-vis des mathématiques (bien que, dans notre atelier, nous avions un public globalement conquis dès le début). En effet, nous partageons le point de vue (ou les arguments) donné(s) dans [5] : La manipulation de concepts abstraits au travers de jeux développe une attitude positive des élèves envers ces concepts.

Nous avons essayé de leur faire sentir que le temps de réflexion sur la modélisation mathématique permet d’améliorer la compréhension du jeu et permet également d’obtenir une méthode de résolution robuste basée, ici, sur le Pivot de Gauss.

Pour terminer, nous faisons remarquer que, cet atelier peut être réalisé de bien d’autres façons. Par exemple, on peut l’axer plutôt vers l’informatique avec la mise en œuvre de l’algorithme, ce qui se destine dans ce cas à des élèves de plus haut niveau, par exemple des étudiants de 1ère année de mathématique ou informatique. Ceci est notamment en cohérence avec les idées énoncées dans [4] qui affirment que l’introduction de l’algorithmique dans les programmes de mathématiques tend à favoriser l’hybridation mathématique-informatique. Une autre façon de réaliser cet atelier peut consister à laisser plus d’autonomie aux élèves, ce qui correspond plutôt à des stages de recherche ou des activités du type MATh.en.JEANS, ce qui a déjà été fait pour des problèmes très similaires au Lights Out (voir par exemple [6], [7], [8]).


ps

Pour tout renseignement sur le programme développé en Java, merci de contacter Valentin Montmirail.

Documents associés à l'article
  Fiche Questions   |   (PDF - 321.6 ko)
  Fiche Questions Corrigée   |   (PDF - 322.5 ko)
  Jeu compressé   |   (Zip - 1.2 Mo)
Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197