La solution du jeu des lumières

 

Considérer le casse-tête suivant:

 

Le jeu est une grille 5 par 5 de boutons qui peuvent s'allumer.  Le fait d’appuyer sur un bouton changera sa lumière, mais il changera également les lumières des boutons adjacents tout autour. Chaque problème vous présente un certain modèle de boutons allumés et pour résoudre la casse-tête, vous devez éteindre toutes les lumières (ce qui n'est pas facile parce que si vous ne faites pas attention, plus de lumières seront allumées qu'éteintes). C'est le but primaire, le but secondaire est d'accomplir ceci avec un nombre minimal de mouvements (appuyer sur un bouton est un mouvement).

 

La solution présentée ici utilise la notion algébrique d’un "corps". Un corps est un ensemble muni de deux opérations : une addition et une multiplication telles que les axiomes suivants sont satisfaits:

 

                           1.  Fermeture sous l’addition.

                           2.  Fermeture sous la multiplication.

                           3.  Associativité de l’addition.

                           4.  Associativité de la Multiplication.

                           5.  La distributivité.

                           6.  L’existence de 0.

                           7.  L’existence de 1.

8.      L’existence des inverses  additifs (négatives).

9.      L’existence des inverses  multiplicatifs (réciproques), à l’exception   de l’élément nul 0.

                           10. La commutativité de l’addition.

                           11. La commutativité de la multiplication.

 

Exemples des corps : Q (les rationnels), R (les réels), C (les complexes), et Z/pZ (les entiers modulo un nombre premier  p).

 

En particulier, Z/2Z (souvent dénoté par Z2) est un corps contenant deux éléments seulement  0 et 1. On peut parler d’un espace vectoriel sur un corps k. Un exemple d’un tel espace est knn est un entier positif.

 

Retournons maintenant à notre casse-tête. On présentera une solution suggérée par Carsten Haese.

 

Le but ici est de trouver une solution universelle au casse-tête, c.-à-d.  Trouver un algorithme général qui vous indiquera quels boutons vous devez appuyer étant donné un certain modèle initial. Les questions centrales au sujet de cette solution universelle sont

 

 

 

a) Y a-t-il une solution pour n’importe quel modèle initial? Si oui, pourquoi? Si non, décrivez l'ensemble de modèles initiaux qui ont une solution.

 

b) En supposant  qu’une solution pour un modèle initial donné existe, comment cette solution peut-elle être dérivée du modèle?

 

Cette approche à ce casse-tête consiste à  trouver une équation qui décrit comment appuyer sur les boutons affectera les lumières. D'abord, je dois représenter les lumières numériquement. Une représentation évidente, qui par ailleurs sera également algébriquement très utile, doit représenter un bouton non-allumé avec 0 et un bouton allumé  avec 1. J'énumère les 25 buttons/lumières de gauche à droite, du haut en bas et chaque modèle des lumières est représenté ainsi par un 25-uplets de 0 et de 1, c.-à-d. par un élément de l'ensemble

 

 

.

 

Pour représenter la manière dont appuyer sur un bouton affecte le modèle des lumières, je définis un opérateur d'addition sur l'ensemble

 

 

comme suit:

 

 

 

 

 

 

 

Ceci décrit exactement le mécanisme de commutation lorsqu’une composante représente l'état d'une lumière et l'autre représente si cette lumière est allumée.  L'addition sur Z2  induit une adition sur Z225 d’une manière naturelle.

 

Naturellement, pour  profiter de cette addition dans Z225, je voudrai représenter l'effet d'appuyer sur un bouton par un élément de Z225. Je fais ceci d’une manière évidente. Chaque bouton a son propre modèle de quelles lumières il allumera et quelles lumières il éteindra. En écrivant 0 pour éteindre et 1 pour allumer, chacun des boutons (ou plutôt l'"action de bouton", c.-à-d. l'effet d'appuyer sur ce bouton) est décrit par un élément de Z225. Soit ai l’élément de Z225  (i=1.., 25) qui décrit la situation de la grille qui est provoquée en appuyant sur le ième bouton. Par exemple,

a2 = (1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),

 

a19 = (0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,0,0,0,1,0).

 

 

Je peux maintenant commencer la première tentative d’écrire une équation qui résoudra le casse-tête. Soit y dans Z225  le modèle  initial du casse-tête. Je pourrais jouer autour avec les boutons, par exemple en appuyant sur le 21ème bouton je transformerais le modèle y en a21 + y. Ensuite, je pourrais appuyer sur le 15ème bouton, ayant pour résultat a15 + (a21 + y) et ainsi de suite. L'addition étant associative, je peux enlever les parenthèses sans ambiguïté. Le but est de trouver une suite (finie !) (n(1),n(2),...,n(N)) tels que

 

an(N) + an(N-1) + ... + an(1) + y = (0,0,...,0).

 

 

L'addition dans Z225 est commutative, ainsi sans perte de généralité la suite n(1)...n(N) peut être choisie d’être non décroissante. En outre, comme ai + ai = 0 pour tout i=1.., 25 (en fait, v + v = 0 pour tout v dans Z225), la suite peut même être choisie strictement croissante puisque aucune action de bouton ne doit être effectuée plus d'une fois. Évidemment ceci signifie que N≤25. Pour réaliser une forme élégante de l'équation avec exactement 25 composantes, je définis un opérateur de multiplication sur Z2 qui me permettra de sauter ces actions de bouton qui ne sont pas nécessaires dans la solution. Je définis 0*0 : = 0*1 : = 1*0 : = 0 et 1*1 : = 1. On  sait que (Z2,+,*) est un corps, et avec la multiplication naturelle s*(v1 ,, v25) : = (s*v1,…, s*v25), (Z225,+,*)   est un espace vectoriel sur le corps Z2. 

 

 

 

Maintenant, l'équation ci-dessus peut être récrite d'une manière équivalente comme :

 

x1*a1 + ... + x25*a25 + y = (0,0,...,0)

 

x=(x1,...,x25) est un élément de Z225. En ajoutant y aux deux membres de l’équation, on obtient :

 

x1*a1 + ... + x25*a25 = y.

 

 

Maintenant je veux écrire le côté gauche comme un produit matriciel. Je devrais mentionner à ce point que tous les vecteurs sont censés être des colonnes, même je les écris comme des lignes pour la simplicité. Si je laisse M être la matrice dont la ième ligne est ai (transposée), mon équation devient

 

 

Mx = y.

 

Il est facile de vérifier que M est la matrice en blocs suivante :

 

 

 

avec

 

 

,

 

 

 

I est la matrice identité 5x5 et 0 est la matrice nulle 5x5.

 

Maintenant j'ai accompli la tâche de trouver une équation qui décrit la solution des lumières non allumées. Une suite d’actions de bouton qui est décrit par x=(x1,...,x25) dans Z225 fera le modèle initial y dans Z225 disparaître si et seulement si Mx = y. C'est une équation linéaire dans un espace vectoriel. Ainsi, malgré que l'équation ne traite pas de nombres réels, je peux appliquer les techniques standard de résolution des systèmes linéaires.

 

Les questions ci-dessus peuvent maintenant être résolues en étudiant les propriétés de la matrice M.

 

J'ai écrit un petit programme d’ordinateur qui résout simultanément les 25 équations

 

Mx = bi

 

(où { bi | i=1,...,25} est la base  canonique de Z225) en utilisant l’élimination Gaussienne. Si vous voulez résoudre l'équation à la main, veuillez essayer)

 

Je n'inonderai pas cet article avec la matrice résultante, bien que les résultats principaux suivants ne puissent pas vraiment être vérifiés sans elle.

 

 

Les résultats principaux sont:

 

* dim image M = 23, dim ker M = 2.

Par conséquent il y a des casse-tête qui ne peuvent pas être résolues. Celles qui peuvent être résolues ont 4 solutions différentes parce que (x24, x25)  peut être choisi arbitrairement dans Z22.

 

* L’observation les deux dernières lignes dans la matrice finale rapporte un critère pour l'existence d'une solution. Avec les vecteurs

 

 

k1=(1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1,0,1),

 

k2=(1,1,0,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,1,0,1,1).

 

 le critère peut être écrit comme 0 = <y, k1> = <y, k2>, où < . , . > est le produit scalaire canonique de  Z225. On peut montrer que { k1, k2 } est une base du ker M, ce qui n'est pas vraiment surprenant parce que la compatibilité de Mx=y est équivalente à y étant dans l’image de M (car M est symétrique) ce qui est équivalent à y étant orthogonal au ker M.

 

* Un algorithme de solution général (c.-à-d. une formule qui exprime x en termes de y) peut également être trouvé facilement en évaluant la matrice résultante. Un tel algorithme conviendrait seulement à un ordinateur, cependant. Si vous êtes intéressés à une solution qu'un humain peut facilement exécuter, je suggère les exercices suivants:

 

  1) Prouvez que pour n'importe quel modèle initial il y a une suite des mouvements qui ramène le modèle à la première ligne.

  2) En assumant la compatibilité du système, prouver qu'il y a 7 modèles non triviaux qui ont des lumières seulement dans la première ligne.

 3) Déduire les solutions de ces sept modèles de la matrice finale.

 4) Apprenez-les par cœur et impressionnez vos amis.

 

 Cette approche ne rapporte jamais une solution minimale parce que très probablement, vous appuierez des boutons deux fois, mais c'est une solution néanmoins.