Tout éteindre

Appuyer sur une lampe l'inverse, ainsi que ses voisines ; il faut tout éteindre, sur un plateau de 2 à 7 lignes et colonnes. Le jeu est un système linéaire sur le corps à deux éléments, que le pivot de Gauss résout.

Sur un plateau de $2$ à $7$ lignes et colonnes, appuyer sur une case inverse sa lampe et celles de ses voisines immédiates. On part d'une position mélangée, du plateau tout allumé ou de lampes tirées au hasard, et il faut tout éteindre ; un bouton ramène à la position de départ pour réessayer. La page dit si la position a une solution, combien d'appuis il faut au minimum, et peut montrer où appuyer.

Ce que cela signifie : l'ordre des appuis ne compte pas et appuyer deux fois sur une case ne fait rien. En codant allumé par $1$ et éteint par $0$ et en calculant modulo $2$, éteindre la position $b$ revient à résoudre le système linéaire $Ax = b$ sur le corps $\mathbb F_2$, où $A$ est la matrice carrée de taille $N$ (le nombre de cases) qui décrit l'effet de chaque appui. Si le noyau de $A$ est de dimension $k$, le théorème du rang dit qu'une position sur $2^k$ est soluble, chacune ayant $2^k$ solutions. Pour le plateau de $3$ sur $3$, $k = 0$ ; pour celui de $5$ sur $5$, le rang vaut $23$ et $k = 2$ ; pour celui de $4$ sur $4$, $k = 4$.

Le piège le plus courant est de chercher une stratégie ordonnée, alors qu'une solution n'est qu'un ensemble de cases, et de croire toute position soluble : sur le plateau de $5$ sur $5$, trois positions sur quatre ne le sont pas.