Exercice 3 — Lights out

Sujet

Un tableau est constitué de boutons. Sur chacun des boutons est affiché un chiffre pouvant prendre la valeur 0 ou 1 . En appuyant sur un bouton, on change la valeur de ce bouton, ainsi que celle des boutons voisins horizontaux et verticaux immédiats (si ceux-ci existent) : un chiffre 1 est remplacé par 0 et viceversa.

But du jeu : à partir d'une configuration initiale donnée, il s'agit, en appuyant sur les boutons, d'obtenir une grille constituée uniquement de zéros.
Pour suivre la séquence donnant la solution éventuelle, on repère les boutons du tableau par des lettres.
Ainsi, un tableau de taille \(4 \times 4\) sera repéré \(\left(\begin{array}{cccc}A & B & C & D \\ E & F & G & H \\ I & J & K & L \\ M & N & O & P\end{array}\right)\)
Exemple : on donne comme tableau initial le tableau \(S=\left(\begin{array}{llll}1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0\end{array}\right)\)
En appuyant successivement sur les boutons G , I et A , on résout le problème, comme le montre la séquence ci-dessous :

\[ \left(\begin{array}{llll} 1 & 1 & 1 & 0 \\ 0 & 1 & \mathbf{1} & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{array}\right) \xrightarrow{\text { bouton } \mathrm{G}}\left(\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \mathbf{1} & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{array}\right) \xrightarrow{\text { bouton } \mathrm{I}}\left(\begin{array}{|cccc|} \hline \mathbf{1} & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \end{array}\right) \xrightarrow{\text { bouton } \mathrm{A}}\left(\begin{array}{cccc} \boxed{0} & \boxed{0} & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right) \]

La suite des lettres associée à la solution est : GIA.

1. Grille \(2 \times 2\)

Les boutons sont repérés ainsi : \(\left(\begin{array}{ll}\mathrm{A} & \mathrm{B} \\ \mathrm{C} & \mathrm{D}\end{array}\right)\)
a) A partir de la configuration \(S=\left(\begin{array}{ll}1 & 0 \\ 0 & 0\end{array}\right)\), proposer une séquence donnant une solution au jeu.
b) Montrer qu'à partir de n'importe quelle configuration initiale, on parvient toujours à une solution au jeu.
2. Grille \(3 \times 3\)

Les boutons sont repérés ainsi : \(\left(\begin{array}{ccc}\mathrm{A} & \mathrm{B} & \mathrm{C} \\ \mathrm{D} & \mathrm{E} & \mathrm{F} \\ G & H & I\end{array}\right)\)
a) Recopier et compléter la séquence suivante qui mène à une solution du jeu :

\[ \begin{aligned} & \left(\begin{array}{ccc} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{array}\right) \xrightarrow{\text { bouton } \mathrm{F}}\left(\begin{array}{ccc} \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots \end{array}\right) \xrightarrow{\text { bouton } \cdots}\left(\begin{array}{lll} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right) \\ & \xrightarrow{\text { bouton } \mathrm{D}}\left(\begin{array}{lll} \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots \end{array}\right) \xrightarrow{\text { bouton }} \cdots\left(\begin{array}{lll} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right) \end{aligned} \]

b) On considère l'algorithme suivant :

Parcourir les boutons D à I successivement.
Pour chaque bouton parcouru
si le chiffre situé immédiatement eu-dessus est égal à 1 alors
Appuyer sur ce bouton
sinon
Ne pas appuyer sur ce bouton
Fin parcours
Montrer qu'en appliquant l'algorithme à la configuration initiale : \(S=\left(\begin{array}{lll}1 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 1\end{array}\right)\), on aboutit à la configuration finale suivante \(T=\left(\begin{array}{lll}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 1\end{array}\right)\)
Donner la suite des lettres associée à cette séquence.
c) Donner une séquence de lettres permettant de passer du tableau final \(T\) au tableau initial \(S\).
d On étudie la configuration finale T obtenue à la question (b).
On applique à cette configuration une «correction d'algorithme » en appuyant tout d'abord sur le bouton A, puis on applique au tableau obtenu l'algorithme précédent.
Montrer qu'avec cette correction d'algorithme on parvient à résoudre le jeu. En déduire la suite de lettres associée donnant la solution du jeu à partir de la configuration initiale S .
e Quelles sont toutes les configurations finales possibles que l'on peut obtenir en appliquant l'algorithme à une configuration initiale quelconque?
f) À partir d'une grille vide, on appuie sur la touche A , puis sur la touche B , et on applique l'algorithme. Quelle configuration finale (parmi celles trouvées à la question (e)) obtient-on? En déduire une «correction d'algorithme» permettant de résoudre cette configuration finale.
g) En s'inspirant de la question précédente, résoudre toutes les configurations finales trouvées à la question (e).