Jogo das luzes (lights out)

Este jogo é conhecido como lights out e tem vários sites dedicados a ele. Um deles é o site com o jogo programado por este autor.

O jogo

• Num tabuleiro \(n\times n\) de botões luminosos, alguns ou todos acesos, ao clicar num botão, ele troca o estado (aceso/apagado) de si e de seus vizinhos na vertical e horizontal.
• O objetivo é apagar todos os botões.

Solução utilizando sistemas lineares

Cada botão pode ser visto como um elemento de \(\mathbb{Z}_2\), onde apagado=0 e aceso=1. Somar em \(\mathbb{Z}_2\) é muito fácil: \[ \begin{gathered} 0+0=0\\ 0+1=1\\ 1+0=1\\ 1+1=0 \end{gathered}\tag{S} \]

Se não tem costume, pense \(0\) como par e \(1\) como ímpar. Temos que

• par+par=par
• par+ímpar=ímpar
• ímpar+par=ímpar
• ímpar+ímpar=par

o que justifica (S).

Caso 2×3

Chame os botões por letras como em \(\begin{pmatrix}a&b&c\\d&e&f\end{pmatrix}\).

É mais fácil trabalharmos com vetor coluna por podermos escrever um sistema linear. Assim, o estado atual \(x\) pode ser visto como um vetor de 6 elementos em \(\mathbb{Z}_2\):

Cada botão apertado corresponde a somar, em \(\mathbb{Z}_2^6\), um vetor. Por exemplo, se apertarmos o botão \(d\), trocam os valores de \(x_a\), \(x_d\) e \(x_e\), o que equivale a somar ao vetor \(x\) de estado atual o vetor \[ v_d = \begin{pmatrix}1\\0\\0\\1\\1\\0\end{pmatrix} \] Marque o estado inicial \(x_0\) como \[ x_0 = \begin{pmatrix} A\\ B\\ C\\ D\\ E\\ F \end{pmatrix}, \] e seja \(v_\alpha\) o vetor que dá a ação do botão \(\alpha\). Então resolver o jogo equivale a encontrar escalares \(a,b,c,d,e,f\in\mathbb{Z}_2\) tais que \[ x_0 +av_a+bv_b+cv_c+dv_d+ev_e+fv_f = 0 \] que equivale ao sistema linear (pois \(-1=1\) em \(\mathbb{Z}_2\)) \[ av_a+bv_b+cv_c+dv_d+ev_e+fv_f = x_0 \] Colocando o sistema em forma matricial, \[ \begin{pmatrix} 1&1&0&1&0&0\\ 1&1&1&0&1&0\\ 0&1&1&0&0&1\\ 1&0&0&1&1&0\\ 0&1&0&1&1&1\\ 0&0&1&0&1&1 \end{pmatrix} \begin{pmatrix}a\\b\\c\\d\\e\\f\end{pmatrix} = \begin{pmatrix}A\\B\\C\\D\\E\\F\end{pmatrix} \] que, como matriz aumentada, fica \[ \begin{pmatrix} 1&1&0&1&0&0&A\\ 1&1&1&0&1&0&B\\ 0&1&1&0&0&1&C\\ 1&0&0&1&1&0&D\\ 0&1&0&1&1&1&E\\ 0&0&1&0&1&1&F \end{pmatrix} \sim \begin{pmatrix} 1&0&0&0&1&1&B+C\\ 0&1&0&0&1&0&A+D\\ 0&0&1&0&1&1&A+C+D\\ 0&0&0&1&0&1&B+C+D\\ 0&0&0&0&0&0&A+B+C+E\\ 0&0&0&0&0&0&A+C+D+F \end{pmatrix} \] Portanto, das duas últimas linhas do sistema escalonado, desde que \[\tag{*} \begin{gathered} 0 = A+B+C+E\\ 0 = A+C+D+F \end{gathered} \] estejam satisfeitas para o sistema ser combatível, podemos escolher os valores de \(e\) e \(f\) e resolver \(a\), \(b\), \(c\), \(d\) como \[ \begin{align*} a&=e+f+B+C\\ b&=e+A+D\\ c&=e+f+A+C+D\\ d&=f+B+C+D \end{align*} \]

Para o caso do primeiro jogo \(2\times3\) inicialmente com todas acesas (\(A=B=C=D=E=F=1\)), temos que as condições (*) estão satisfeitas e obtemos as 4 possíveis soluções (uma para cada escolha dos valores de \(e\) e \(f\)), onde \(\bullet\) indica botão a acionar: \[ \begin{pmatrix} & &\bullet\\ \bullet& & \end{pmatrix},\quad \begin{pmatrix} \bullet&\bullet& \\ \bullet&\bullet& \\ \end{pmatrix},\quad \begin{pmatrix} \bullet&& \\ &&\bullet\\ \end{pmatrix},\quad \begin{pmatrix} &\bullet&\bullet\\ &\bullet&\bullet\\ \end{pmatrix} \]

Já o caso com uma acesa,em que \(B=0\), a 1ª equação de (*) fica \[ 0=A+B+C+E=1+0+1+1=1, \] e portanto o sistema é impossível!

Para os jogos \(3\times3\) e \(5\times5\), podemos agir analogamente, montar os sistemas (respectivamente \(9\times9\) e \(25\times25\)) e se quisermos, com o auxílio de um programa, escalonar as matrizes aumentadas, como faremos a seguir. Também, poderíamos economizar muitas contas notando que as matrizes são matrizes de blocos e escaloná-as.

Caso 3×3

Usaremos as letras \(a\), \(b\), \(c\), \(d\), \(e\), \(f\), \(g\), \(h\), \(i\) para as luzes, como abaixo: \[ \begin{pmatrix} a&b&c\\ d&e&f\\ g&h&i \end{pmatrix}. \]

O esquema de apagamento de luzes gera a matriz aumentada abaixo. Por exemplo, ao clicarmos no botão \(a\), trocamos o estado de \(a\), \(b\) e \(d\), o que se vê pelos 1 na primeira linha do sistema: \[ \begin{pmatrix} 1&1&0&1&0&0&0&0&0&A\\ 1&1&1&0&1&0&0&0&0&B\\ 0&1&1&0&0&1&0&0&0&C\\ 1&0&0&1&1&0&1&0&0&D\\ 0&1&0&1&1&1&0&1&0&E\\ 0&0&1&0&1&1&0&0&1&F\\ 0&0&0&1&0&0&1&1&0&G\\ 0&0&0&0&1&0&1&1&1&H\\ 0&0&0&0&0&1&0&1&1&I \end{pmatrix} \sim \begin{pmatrix} 1&0&0&0&0&0&0&0&0&A+C+F+G+H\\ 0&1&0&0&0&0&0&0&0&E+G+H+I\\ 0&0&1&0&0&0&0&0&0&A+C+D+H+I\\ 0&0&0&1&0&0&0&0&0&C+E+F+I\\ 0&0&0&0&1&0&0&0&0&B+D+E+F+H\\ 0&0&0&0&0&1&0&0&0&A+D+E+G\\ 0&0&0&0&0&0&1&0&0&A+B+F+G+I\\ 0&0&0&0&0&0&0&1&0&A+B+C+E\\ 0&0&0&0&0&0&0&0&1&B+C+D+G+I \end{pmatrix} \]

Note que o sistema 3×3 é sempre possível!.

Pensando um pouco, concluímos que só necessitamos resolver a primeira linha, e indo da segunda linha para baixo sempre apagando o que está aceso na linha anterior, técnica chamada “apagar acima”.

Assim, a primeira linha é \[ \begin{pmatrix}(A+C+F+G+H) & (E+G+H+I) & (A+C+D+H+I) \end{pmatrix} \] No caso acima com todas acesas de início, a solução é fazer a 1ª linha \(\begin{pmatrix}\bullet& &\bullet\end{pmatrix}\).

Caso 5×5

Usaremos as letras de \(a\) até \(y\) para as luzes, como abaixo: \[ \begin{pmatrix} a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y \end{pmatrix}. \]

Para esse jogo de luzes, a matriz aumentada do sistema \(5\times5\) é \[ \small \begin{pmatrix} 1&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&A\\ 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&B\\ 0&1&1&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&C\\ 0&0&1&1&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&D\\ 0&0&0&1&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&E\\ 1&0&0&0&0&1&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&F\\ 0&1&0&0&0&1&1&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&G\\ 0&0&1&0&0&0&1&1&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&H\\ 0&0&0&1&0&0&0&1&1&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&I\\ 0&0&0&0&1&0&0&0&1&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&J\\ 0&0&0&0&0&1&0&0&0&0&1&1&0&0&0&1&0&0&0&0&0&0&0&0&0&K\\ 0&0&0&0&0&0&1&0&0&0&1&1&1&0&0&0&1&0&0&0&0&0&0&0&0&L\\ 0&0&0&0&0&0&0&1&0&0&0&1&1&1&0&0&0&1&0&0&0&0&0&0&0&M\\ 0&0&0&0&0&0&0&0&1&0&0&0&1&1&1&0&0&0&1&0&0&0&0&0&0&N\\ 0&0&0&0&0&0&0&0&0&1&0&0&0&1&1&0&0&0&0&1&0&0&0&0&0&O\\ 0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&1&0&0&0&1&0&0&0&0&P\\ 0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&1&1&0&0&0&1&0&0&0&Q\\ 0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&1&1&0&0&0&1&0&0&R\\ 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&S\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&1&0&0&0&0&1&T\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&1&0&0&0&U\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&1&1&0&0&V\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&1&1&0&W\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&1&1&X\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&1&Y \end{pmatrix} \]

Com o auxílio de um programa, calcula-se o escalonamento da matriz que resolve este sistema \(5\times 5\). Aqui, as coordenadas de \(x_0\) são as 25 letras maiúsculas \(A\) até \(Y\). Note que o sistema não é determinado, podendo ser impossível dependendo dos dados iniciais (ver últimas duas linhas abaixo). A matriz escalonada fica: \[\small \begin{pmatrix} 1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&B\!+\!C\!+\!D\!+\!H\!+\!J\!+\!N\!+\!O\!+\!T\\ 0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&A\!+\!B\!+\!D\!+\!E\!+\!G\!+\!M\!+\!N\!+\!O\!+\!S\\ 0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&A\!+\!C\!+\!D\!+\!E\!+\!F\!+\!H\!+\!I\!+\!M\!+\!N\!+\!P\!+\!Q\!+\!R\!+\!S\!+\!T\!+\!V\\ 0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&A\!+\!D\!+\!F\!+\!G\!+\!H\!+\!J\!+\!K\!+\!L\!+\!N\!+\!O\!+\!P\!+\!Q\!+\!R\!+\!T\!+\!U\!+\!X\\ 0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&B\!+\!C\!+\!E\!+\!F\!+\!K\!+\!M\!+\!O\!+\!R\!+\!T\!+\!U\!+\!V\\ 0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&C\!+\!E\!+\!G\!+\!H\!+\!J\!+\!M\!+\!S\!+\!T\\ 0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&B\!+\!D\!+\!F\!+\!G\!+\!I\!+\!J\!+\!N\!+\!P\!+\!Q\!+\!R\!+\!V\\ 0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&A\!+\!B\!+\!D\!+\!I\!+\!J\!+\!K\!+\!L\!+\!N\!+\!U\!+\!V\!+\!X\\ 0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&B\!+\!D\!+\!F\!+\!G\!+\!I\!+\!J\!+\!L\!+\!R\!+\!S\!+\!T\!+\!X\\ 0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&A\!+\!B\!+\!C\!+\!D\!+\!G\!+\!H\!+\!J\!+\!L\!+\!M\!+\!N\!+\!P\!+\!Q\!+\!V\!+\!X\\ 0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&E\!+\!I\!+\!J\!+\!M\!+\!O\!+\!P\!+\!Q\!+\!R\!+\!S\!+\!V\\ 0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&B\!+\!C\!+\!D\!+\!F\!+\!H\!+\!J\!+\!K\!+\!L\!+\!N\!+\!O\!+\!P\!+\!Q\!+\!R\!+\!T\!+\!U\!+\!X\\ 0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&B\!+\!C\!+\!E\!+\!F\!+\!J\!+\!K\!+\!M\!+\!N\!+\!R\!+\!U\!+\!V\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&A\!+\!B\!+\!C\!+\!G\!+\!I\!+\!M\!+\!N\!+\!O\!+\!S\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&A\!+\!B\!+\!E\!+\!H\!+\!I\!+\!J\!+\!K\!+\!N\!+\!O\!+\!P\!+\!Q\!+\!S\!+\!U\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&1&B\!+\!D\!+\!F\!+\!G\!+\!I\!+\!J\!+\!L\!+\!N\!+\!U\!+\!V\!+\!X\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&B\!+\!F\!+\!G\!+\!H\!+\!N\!+\!P\!+\!Q\!+\!S\!+\!T\!+\!V\!+\!X\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&1&C\!+\!E\!+\!G\!+\!H\!+\!J\!+\!K\!+\!M\!+\!P\!+\!Q\!+\!S\!+\!T\!+\!U\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&D\!+\!H\!+\!I\!+\!J\!+\!L\!+\!P\!+\!Q\!+\!S\!+\!T\!+\!V\!+\!X\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&1&A\!+\!B\!+\!D\!+\!E\!+\!K\!+\!L\!+\!N\!+\!O\!+\!U\!+\!V\!+\!X\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&D\!+\!E\!+\!H\!+\!L\!+\!M\!+\!O\!+\!P\!+\!R\!+\!T\!+\!U\!+\!V\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&1&0&B\!+\!E\!+\!F\!+\!G\!+\!H\!+\!I\!+\!J\!+\!M\!+\!N\!+\!O\!+\!P\!+\!R\!+\!T\!+\!U\!+\!X\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&1&D\!+\!H\!+\!I\!+\!J\!+\!L\!+\!P\!+\!Q\!+\!S\!+\!T\!+\!V\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&B\!+\!C\!+\!D\!+\!F\!+\!H\!+\!J\!+\!K\!+\!L\!+\!N\!+\!O\!+\!P\!+\!R\!+\!T\!+\!V\!+\!W\!+\!X\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&A\!+\!B\!+\!D\!+\!E\!+\!K\!+\!L\!+\!N\!+\!O\!+\!U\!+\!V\!+\!X\!+\!Y \end{pmatrix}\]

A solução encontrada foi confirmada utilizando o software wxMaxima. A verificação pode ser rodada por você.

Para sistemas possíveis, isto é, quando \[ \begin{gathered} 0=B+C+D+F+H+J+K+L+N+O+P+R+T+V+W+X\\ 0=A+B+D+E+K+L+N+O+U+V+X+Y, \end{gathered}\tag{**} \] a primeira linha pode ser tomada como \[ \begin{pmatrix} B+C+D+H+J+N+O+T\\ A+B+D+E+G+M+N+O+S\\ A+C+D+E+F+H+I+M+N+P+Q+R+S+T+V\\ A+D+F+G+H+J+K+L+N+O+P+Q+R+T+U+X\\ B+C+E+F+K+M+O+R+T+U+V \end{pmatrix}^t\tag{1} \]

No site, quando o nível difícil 5×5 está selecionado, das três primeiras opções mostradas, o terceiro (com luzes apagadas em \(A\), \(J\) e \(P\) é impossível (2ª equação de (**) é incompatível). As soluções da 1ª linha para o primeiro jogo \(5\times5\) (todas acesas) e do segundo jogo (1º, 10º e 15º apagados) são, respectivamente, \[ \text{1º}: \quad \begin{pmatrix} 0&\bullet&\bullet&0&\bullet\end{pmatrix} \] \[ \text{2º}: \quad \begin{pmatrix} 0&\bullet&0&\bullet&0\end{pmatrix}, \] novamente, usando a técnica “apagar acima”.

Resolução pela técnica “apagar acima”

Nas resoluções acima, obtivemos as soluções gerais em todos os casos. Para reduzir os casos ao máximo, podemos utilizar a técnica “apagar acima” (“light chasing” em inglês), isto é, apagar as luzes da 1ª linha clicando nas correspondentes luzes da 2ª linha, então apagar as luzes da 2ª linha clicando nas luzes da 3ª, etc, até que somente haja luzes acesas na última linha. Dessa forma, em cada solução apresentada nos escalonamentos acima, reduzimos as soluções a apenas as últimas 3 ou 5 variáveis. A tabela a seguir compila essas soluções (1) e (2), após o primeiro “apagar acima”: