84 Eteindre la lumière

Chapitre 84
Eteindre la lumière

Résumé : Ligths Out est un jeu fabriqué par Tiger Toys. Il consiste en un tableau contenant 25 lampes/boutons disposés en cinq lignes et cinq colonnes. Au départ certaines lampes sont allumées et d’autres sont éteintes au hasard. Une lampe allumée peut être éteinte en l’enfonçant ; une lampe éteinte peut être allumée en l’enfonçant. Le but du jeu consiste à les éteindre toutes le plus rapidement possible. Les mathématiques peuvent nous aider à résoudre ce problème et même nous donner la solution la plus rapide.

Mots-clés : matrice, linéarité.

Enoncé

L’exercice s’inspire de l’article Two Reflected Analyses of Lights Out de Oscar Martin Sanchez et Cristobal Pareja-Flores, Mathematics Magazine, Vol. 74, Madrid, Spain, No. 4, octobre 2001. Cet article est particulièrement intéressant car il est écrit dans un format utilisant deux colonnes. La colonne de gauche s’adresse à une personne intéressée par une recherche de solution méthodique, la colonne de droite s’adresse au mathématicien. Le lecteur est encouragé à passer d’une colonne à l’autre pour le plaisir et pour mieux comprendre.

Le jeu Lights out est un puzzle sous forme d’échiquier de dimension cinq sur cinq. Chaque case est formée à la fois d’un bouton et d’une ampoule. Chaque ampoule peut être allumée ou éteinte. En enfonçant le bouton, l’ampoule change d’état ainsi que les ampoules voisines horizontalement et verticalement. Dans l’exemple ci-dessous, les ampoules sont toutes éteintes au départ. Si l’on enfonce les boutons marqués par des croix, on obtient la configuration à droite.

Le but du jeu est, partant d’une configuration initiale aléatoire, d’éteindre toutes les ampoules. Ce jeu peut être généralisé à un échiquier quelconque de dimension m × n.

Indications

Comme indiqué plus haut, les auteurs de l’articles ont donné deux solutions. Elle seront décrites ci-après séparément.

Pour ceux intéressés par la méthode

Pour résoudre le puzzle, on doit enfoncer un certain nombre de boutons ; pendant ce processus, certaines ampoules sont commutées plusieurs fois mais on n’est intéressé que par le résultat final.

Enfoncer un bouton deux fois de suite n’a pas d’effet. De même résoudre un état donné revient au même que de le résoudre depuis la position complètement éteinte : les mêmes étapes sont nécessaires.

Enfoncer un bouton puis un autre a le même effet que de les enfoncer dans l’ordre inverse. Cela s’explique par le fait que l’état final ne dépend que du nombre de boutons pressés ; il n’a rien a faire avec l’ordre. Ainsi, un ensemble de pressions a le même effet si l’on élimine toutes les paires de pressions identiques. Un tel ensemble de pressions, dans lequel aucun bouton n’est enfoncé plus d’une fois est appelé une procédure.

Le puzzle peut être résolu en essayant toutes les combinaisons possibles. Comme, pour chaque bouton, on peut choisir de l’enfoncer ou non, il y a un nombre colossal de procédures : 2²⁵. Il est donc conseillé de trouver une méthode de résolution simplifiée.

Soit une configuration initiale quelconque, si l’on enfonce des boutons de la première ligne alors, pour éteindre les ampoules allumées de cette ligne, la seule solution (sans presser à nouveau un bouton dans la ligne 1 et sans allumer de nouvelles ampoules) est d’enfoncer les boutons qui se situent exactement au-dessous des ampoules allumées de la ligne 1. L’état de la ligne 2 détermine les boutons à enfoncer dans la ligne 3, etc. Ainsi, étant donné un état initial quelconque, en choisissant un ensemble de boutons à enfoncer sur la première ligne, le reste de la procédure de récolte est déterminé. Mais cette procédure ne garantit l’extinction que des boutons des quatre premières lignes. Les ampoules de la ligne cinq peuvent rester allumées après la procédure.

On peut alors donner la solution :

premièrement, on applique la procédure de récolte sans modifier la première ligne ;
ensuite, on recherche les pressions à effectuer sur la ligne 1 qui, lorsqu’elles seront récoltées, éteindraient toutes les ampoules ;
finalement, on enfonce les boutons dans la première ligne et on récolte le résultat.

Il se pourrait toutefois qu’aucun ensemble de pressions sur la première ligne ne conduise à une solution.

La question qui reste à résoudre est : quels boutons enfoncer dans la première ligne ? Pour la résoudre, on part d’un jeu complètement éteint et on observe les résultats obtenus sur la dernière ligne pour chaque pression.

On est donc passé de la recherche parmi 25 boutons à enfoncer au cas plus simple d’une recherche parmi 5 boutons et 5 ampoules.

Dans un certain sens, on peut jouer maintenant avec un échiquier de dimension 1 × 5. Ce jeu hérite de certaines propriétés du jeu original : l’ordre des pressions n’est pas important et enfoncer deux fois un bouton n’a pas d’effet.

Chaque solution de ce nouveau jeu donne une solution du jeu original et réciproquement. Les états insolubles correspondent ; il en est de même pour les situations qui offrent plusieurs solutions. Les procédures pour le grand jeu sont appelées expansions de celles du petit jeu.

En observant le tableau ci-dessus, on constate que certaines configurations sont identiques :

On peut en tirer des conclusions particulièrement utiles. Ces équivalences montrent qu’il n’est jamais nécessaire d’enfoncer les deux boutons à droite : une solution faisant appel à ces deux boutons peut être remplacée par une solution équivalente ne faisant pas appel à eux. On pourrait prétendre qu’ils sont endommagés.

On constate que si deux procédures équivalentes sont exécutées à tour de rôle, une annule l’autre et le résultat final est nul. La composition des deux procédures est appelée procédure neutre.

La combinaison de n’importe quelle paire de procédures équivalentes donne deux procédures neutres. Une troisième est obtenue en combinant les deux. Il y également une quatrième procédure triviale, dans laquelle aucun bouton n’est enfoncé. Une recherche systématique montre qu’il n’y en a pas d’autres.

Une procédure quelconque suivie d’une procédure nulle est équivalente en terme de résultat obtenu. Ainsi, lorsqu’une solution est trouvée pour un état initial donné, il y a quatre autres solutions équivalentes.

On peut désormais savoir si un état est résoluble avec seulement huit essais. Mais on peut encore améliorer la solution en faisant appel à un raisonnement subtil. D’abord, le jeu a une certaine symétrie : si un bouton x permute la lumière y, alors le bouton y permute la lumière x. N’importe quelle procédure neutre fait pression sur un nombre pair de boutons dans le voisinage de n’importe quelle case en la laissant inchangée. Mais alors, par symétrie, enfoncer n’importe quel bouton permute un nombre pair de cases dans N, l’ensemble de cases enfoncées par une procédure neutre. Ainsi la parité de cases allumées dans N ne peut pas être changée par n’importe quelle pression.

De la sorte, depuis l’état complètement éteint, on ne peut obtenir des états avec un nombre pair de cases en commun avec n’importe quelle procédure neutre de N. Donc un état est résoluble seulement s’il a un nombre pair d’intersections avec n’importe quelle procédure neutre.

Pour une procédure neutre donnée, ce test diminue de moitié le nombre d’états possibles. Comme n’importe quelle procédure neutre est la composition de deux autres, il suffit de la tester pour deux d’entre elles. Ainsi, on peut diminuer de moitié le nombre d’état résolubles deux fois, et marquer trois quarts des états comme insolubles.

D’un autre côté, chaque état résoluble peut être résolu, en moyenne, par quatre différentes procédures. Ainsi un quart de états est résoluble : ceux qui passent le test précédent.

On peut choisir ces deux procédures neutres pour effectuer le test de parité :

On peut utiliser ces résultats pour montrer que l’exemple utilisé précédemment est résoluble. L’état cible avait les ampoules 1, 3 et 4 allumées ; en comparant ceci avec le premier état neutre ci-dessus, on trouve deux ampoules en commun : la troisième et la quatrième ; en comparant avec le second on obtient également un nombre pair : le premier et le troisième bouton. Ainsi l’état est résoluble :

Comment procéder alors pour résoudre un puzzle ? On sait que l’on ne s’intéresse qu’aux trois boutons à gauche de la première ligne. Leurs effets sont donnés par :

Parmi les huit possibilités de combiner les pressions sur ces trois boutons, les trois dernières combinaisons du tableau ci-dessus se distinguent. Chacune est utile puisqu’elle permute seulement une des trois lumières à gauche. Ceci procure la première façon de trouver un candidat pour une solution, sans utiliser les boutons 4 et 5. Ce candidat dépend uniquement de l’état des trois premières lumières. On l’appelle candidat plutôt que solution car on n’a aucune certitude que les derniers boutons tourneront correctement.

Une autre façon de trouver une solution consiste à observer les effets des pressions sur les trois premiers boutons.

Pour ceux intéressés par les aspects mathématiques

Lights out est un problème d’algèbre matricielle. On travaille avec des vecteurs appartenant à (ℤ₂)²⁵. Soit la matrice R qui contient les règles du puzzle :

( ) ( ) A I O O O 1 1 0 0 0 || I A I O O || || 1 1 1 0 0 || R = || O I A I O || , A = || 0 1 1 1 0 || . ( O O I A I ) ( 0 0 1 1 1 ) O O O I A 0 0 0 1 1

où I et O sont les matrices identité et zéro de dimension 5 × 5. Pour un vecteur , que l’on appelle vecteur de pression, on calcule R , appelé l’effet de . L’effet de est ajouté (modulo 2) au vecteur , l’état initial, pour obtenir le nouvel état R + . Par exemple, avec le vecteur de pression qui dispose de uns seulement dans le premier et le quatorzième composant, l’état nul est modifié comme suit :

(1 0 0 0 0 (1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 R × 0 0 0 1 0 + ⃗0 = 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0) 0 0 0 0 0)

Lorsque nécessaire, les vecteurs de 25 éléments sont arrangés sous la forme 5 × 5. Le but est, étant donné un état , de trouver tel que R + = . Bien que l’on ne parle ici que de vecteurs de 25 éléments, les méthodes peuvent être appliquées aux vecteurs de n’importe quelle taille m × n et aux matrices ressemblant à R.

Une forme équivalente du problème est, étant donné , de trouver tel que R = . Ceci est un problème bien connu d’algèbre. On observe que, modulo 2, = -.

On observe qu’il est intéressant de résoudre le problème, pour un état donné , en plusieurs étapes : en partant de l’état nul, , on peut presser ₁, de sorte que le nouvel état, ₁, soit plus simple à écrire ; on presse ensuite ₂, etc. :

⃗p1 ⃗p2 ⃗0 -→ ⃗s1 -→ ⃗s2 ... - → ⃗s

La solution serait la somme des _i :

⃗p1+⃗p2+... ⃗0 -------→ ⃗s

On peut utiliser les méthodes traditionnelles pour résoudre ce problème comme le calcul matriciel. Mais on essaie ici d’exploiter les particularités de R.

Le problème peut être écrit comme suit :

( ⃗p ) ( ⃗s ) | 1∙| | 1∙| || ⃗p2∙|| || ⃗s2∙|| R ⋅| ⃗p3∙| = | ⃗s3∙| ( ⃗p4∙) ( ⃗s4∙) ⃗p5∙ ⃗s5∙

où, pour raison de clarté, et ont été divisés en sous-vecteurs _i∙ et _i∙, chacun étant composé de cinq éléments.

On manipule l’équation précédente pour la mener vers une version plus pratique : une expression pour _1∙ qui ne dépend que de , et d’autres expressions pour _2∙… _5∙ ne dépendant que de _1∙ et .

L’équation R = est équivalente à J = (R + J) + pour n’importe quelle matrice J. Si l’on prend en particulier :

( ) O I O O O || O O I O O || J = || O O O I O || ( O O O O I ) O O O O O

on trouve :

( ) ( ) ( ) ( ) ⃗p2∙ A O O O O ⃗p1∙ ⃗s1∙ || ⃗p3∙ || || I A O O O || || ⃗p2∙|| || ⃗s2∙ || || ⃗p4∙ || = || O I A O O || || ⃗p3∙|| + || ⃗s3∙ || ( ⃗p5∙ ) ( O O I A O ) ( ⃗p4∙) ( ⃗s4∙ ) ⃗0 O O O I A ⃗p5∙ ⃗s5∙

Ici, chaque _i∙ dépend seulement des sous-vecteurs de et avec des indices plus petits que le sien. Ainsi, on peut utiliser l’équation de la première ligne pour ôter _2∙ de la deuxième ensuite, on utilise la deuxième ligne pour éliminer _3∙ de la troisième, etc.

Ainsi, _2∙… _5∙ sont définis uniquement par et _1∙ :

( ) ( ) ( ) ⃗p2∙ B1 B0 O O O O ⃗p1∙ | ⃗p3∙ | | B2 B1 B0 O O O | || ⃗s1∙ || || ⃗p || = || B B B B O O || || ⃗s2∙ || |( 4∙ |) |( 3 2 1 0 |) || ⃗s3∙ || ⃗p5∙ B4 B3 B2 B1 B0 O ( ⃗s4∙ ) ⃗0 B5 B4 B3 B2 B1 B0 ⃗s5∙

où B₀ = I, B₁ = A et B_n+2 = A × B_n+1 + B_n. Maintenant l’équation

B5⃗p1∙ = B4⃗s1∙ + B3⃗s2∙ + B2 ⃗s3∙ + B1 ⃗s4∙ + B0⃗s5∙

prise de la dernière ligne de la matrice précédente, ne tient compte que de _i∙, partie de .

On peut donc travailler avec cette équation en trois étapes :

premièrement, on calcule la partie droite de l’équation, qui ne dépend que de ; on appelera ce vecteur, récolte() ;
ensuite, on essaie de trouver _1∙ tel que B₅ _1∙ est égal à récolte() qui est connu ;
finalement, on calcule _2∙… _5∙ directement depuis _1∙ et , en utilisant les équations des quatre lignes du haut de la matrice précédente.

Il existe des pour lesquels aucun _1∙ ne satisfait l’équation ci-dessus. Dans ces cas, le problème n’a pas de solution.

La question qui reste est de savoir comment obtenir _1∙ qui satisfasse l’équation

B5⃗p1∙ = récolte(⃗s).

La matrice B₅ est la suivante :

( ) 0 1 1 0 1 || 1 1 1 0 0 || B5 = A5 + A = || 1 1 0 1 1 || ( 0 0 1 1 1 ) 1 0 1 1 0

Les dépendances linéaires trouvées nous permettent de voir le problème en dimension 25 comme un problème de dimension 5. Comme exemple, l’état suivant est réduit afin de passer à un problème plus simple :

(0 1 1 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0)

après récolte :

( ) 1 0 1 1 0

Chaque solution à ce problème donne une et une seule solution au problème original et vice versa. On appelle les vecteurs de 25 éléments des extensions des vecteurs de 5 éléments :

⃗p = extension (⃗p ,⃗s). 1∙

On peut exécuter une réduction de Gauss-Jordan sur B₅ pour obtenir XB₅ = E et on obtient :

( ) 1 1 0 0 0 || 1 1 1 0 0 || X = | 0 1 1 0 0 | |( 0 1 1 1 0 |) 1 0 1 0 1

( ) 1 0 0 0 1 || 0 1 0 1 0 || E = || 0 0 1 1 1 || ( 0 0 0 0 0 ) 0 0 0 0 0

On note que null(E) égale null(B₅) et sa dimension est 2, donc c’est le cas pour null(R). Les vecteurs suivant produisent une base de null(E) :

( ) ( ) 0 1 | 1 | | 0 | ⃗i = || 1 || et ⃗j = || 1 || |( 1 |) |( 0 |) 0 1

Ceci nous permet de générer d’autres solutions : si est une solution pour , alors les trois autres solutions sont :

⃗p+ ⃗i ⃗p+ ⃗j ⃗p+ ⃗i+ ⃗j

En observant les vecteurs ⃗
i et ⃗
j , on remarque qu’une de ces solutions aura des zéros dans les quatrième et cinquième éléments.

On peut réduire la recherche des solution aux vecteurs de dimension trois. Ainsi, seulement 2³ états peuvent être recherchés parmi le total possible de 2⁵. En d’autres mots, l’image de notre matrice a une dimension trois ; on le sait car l’ordre de la matrice carrée (de dimension 5 dans l’exemple) égale la dimension de son espace nul (2) plus la dimension de son image. Chaque état n’est pas résoluble ; il est donc intéressant d’identifier des critères pour trouver les états résolubles.

L’algèbre nous dit que, étant donné une matrice symétrique (comme B₅), son image est orthogonale à son espace nul. Ainsi, pour un état donné , il existe une solution pour l’équation B₅ = si et seulement si est orthogonal à l’espace nul de la matrice. Le produit scalaire × doit être égal à zéro pour chaque null(B₅). Ceci concerne les équations suivantes :

s2 + s3 + s4 = 0 s1 + s2 + s5 = 0

Considérons cette explication pour montrer que l’exemple montré plus haut est résoluble. On calcule le produit scalaire de l’état considéré avec les deux procédures neutres. On trouve pour chacun un résultat nul, ce qui signifie que les deux équations ci-dessus sont satisfaites. Donc l’état est résoluble.

(1,0,1,1,0)⋅ (0,1,1,1,0) = 0+ 0 + 1 + 1+ 0 (s2 + s3 + s4 = 0)

(1,0,1,1,0)⋅ (1,0,1,0,1) = 1+ 0 + 1 + 0+ 0 (s1 + s3 + s5 = 0)

En utilisant la réduction de Gauss-Jordan pour B₅, on a obtenu :

⃗p = E⃗p = XB5 ⃗p = X ⃗s

Ceci permet de calculer une solution aisément ; les trois autres sont obtenues en additionnant les vecteurs de l’espace nul de la matrice .

En reprenant la matrice

( 1 1 0 |0 0 ) | 1 1 1 |0 0 | || | || X = | -0--1--1-|0--0--| . || 0 1 1 |1 0 || ( 1 0 1 |0 1 )

On peut exprimer les solutions comme suit :

p1 = s1+ s2 p = s + s + s 2 1 2 3 p3 = s2 + s3

En résumé, pour calculer la solution d’un état de 25 éléments du problème non réduit, on calcule les trois premiers éléments de récolte() ; ensuite on recherche p₁, p₂ et p₃ ; ensuite, finalement la solution expansion( _1∙,).

Solutions

La solution actuellement proposée est donnée par les fichiers MatLab : ligthsOut.m et c_ligthsout.m.