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 !

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 +A₁. 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 +A₁appuyer 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 +A₁, nous leur laissons en exercice modéliser les actions élémentaires +A₂, +A₃ et +A₄. 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 +A_i, 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 +A_i.

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 +A₁ (qui a été déterminée précédemment) et c’est ensuite l’addition +A₂ 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 +A₁+A₂, 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 +A₁ +A₁appuyer deux fois sur le premier interrupteur et +A₁ +A₁ +A₁appuyer 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.

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 A₁), puis on appuie y fois sur l’interrupteur 2 (ce qui correspond à faire +yA₂), 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.

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 :

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.