La Gaceta de la RSME, Vol. 19 (2016), Núm. 1, Págs.

83–97 83

Las matemáticas del juego «Lights Out!»

por
Vicente Muñoz

Resumen. Lights Out! es un juego consistente de un tablero cuadrado

n × n de casillas que se encienden y apagan al presionarlas según ciertas reglas.
Estudiamos matemáticamente el problema con álgebra lineal sobre el cuerpo
de dos elementos F2 . En la determinación de los valores n para los que el juego
tiene solución única aparecen de forma crucial los polinomios irreducibles en
F2 [x] y su comportamiento por la involución x 7→ x + 1.

1. Introducción
Lights Out! es un juego electrónico que fue comercializado por una firma de
juguetes, Tiger Electronics, en el año 1995. Como correspondía a la época, el juego
estaba diseñado en un pequeño dispositivo parecido a una calculadora con botones
que se presionaban y se encendían y apagaban1 . El juego consiste de un tablero de
botones de tamaño 5 por 5. Al presionar el botón de comienzo, aparece iluminado
un patrón (prealmacenado en la memoria del dispositivo) de botones. Cada vez que
apretamos un botón, su estado cambia (si estaba iluminado se apaga, y si estaba
apagado se enciende) y lo mismo ocurre con los botones adyacentes (el que está
arriba, el de abajo suyo, el que está a su derecha, y el de su izquierda). El objetivo es
conseguir apagar todas las luces. En la página de Wikipedia [19] se dan más detalles
al respecto.

El juego Lights Out!. Imagen de Wikipedia [19].

Desde entonces, se han escrito un buen número de artículos y páginas web sobre
el tema, que se enmarcan dentro del área conocida como «Matemáticas Recreativas».
Algunas referencias básicas aparecen en MathWorld [2]. La página web [12] recoge
1 Hoy en día hay numerosas apps para tableta Android, iPad o móvil, que se pueden descargar

gratuitamente buscando bajo el nombre Lights Out.

84 El juego «Lights Out!»

un gran número de referencias, así como extensiones del juego a otros ámbitos (un
rectángulo, un toro, un tablero hexagonal, luces que cambian de color cíclicamente,
etc.) y enlaces a aplicaciones Java.
En [1], el juego es analizado usando álgebra lineal en un tablero 5 × 5. En [9]
se compara una estrategia conocida como «chasing lights» (consistente en apagar
las luces fila a fila presionando las casillas justo debajo de las luces encendidas en
la fila más alta con luces aún encendidas) con su versión matemática. En el caso
de un tablero n × n, hay dos tipos de cuestiones que han atraído principalmente la
atención. Por un lado, tenemos el problema all-ones off consistente en determinar
en qué tableros (o más en general, grafos) tiene solución el desafío de empezar con
todas las luces encendidas y apagarlas todas. Por otro lado, tenemos el problema de
contar cuántas soluciones hay para un tablero de tamaño dado. Comenzando con
el trabajo fundacional [17] en el que se prueba que el problema all-ones off tiene
solución en todo tablero n × n, estos problemas y muchas cuestiones relacionadas
se han analizado usando teoría de grafos, álgebra lineal, σ-autómatas (teoría de
algoritmos), etc. [3, 4, 5, 7, 6, 8, 18, 20].
En el presente artículo, estudiaremos la cuestión del número de soluciones Nn
del problema all-ones off en un tablero n × n. La sucesión que aparece se puede
encontrar en la Enciclopedia de Sucesiones Enteras [13]. Como veremos, Nn = 2dn
para cierto natural dn ≥ 0, lo cual da lugar a una sucesión para los dn (cf. [16]).
Determinaremos dn en función de ciertos polinomios de Chebyshev módulo 2. No
obstante, la determinación explícita de los factores irreducibles de tales polinomios
no es fácil de entender en general. Por ejemplo, la lista de los valores n ≥ 2 para los
que dn = 1 (es decir, cuando el problema tiene solución única) está dada en [15].
No se conoce ninguna manera no algorítmica de determinar dicho conjunto (o, más
bien, su complementario).
Queremos hacer notar, para el lector interesado, que el grupo de simetrías del
cuadrado, el grupo diédrico D8 , actúa en el tablero. Esto hace al problema susceptible
de ser analizado desde el punto de vista de la teoría de representaciones (de grupos
finitos), algo que parece ser no ha sido explorado hasta el momento.
Desde un punto de vista más recreativo, el autor ha propuesto un Desafío Mate-
mático en el periódico El País (versión online), que se puede encontrar en [10]. De
hecho, la solución propuesta para dicho problema usa la simetría. El lector también
puede echar un vistazo al Juego Matemático propuesto en [11], donde se plantea un
juego del tipo Lights Out! en el que las luces se encienden según las piezas del
ajedrez.

Agradecimientos. Me interesé por el juego Lights Out! cuando lo usé para

preparar unas clases para los alumnos del Proyecto Estalmat-Madrid. Tras leer al-
gunos artículos de carácter divulgativo sobre el tema, me entretuve en calcular el
número de soluciones al juego para un tablero n × n, lo que dio lugar a una prime-
ra versión de este artículo, escrita en inglés. Envié aquella versión a M. Alekseyev,
J. Scherphuis y K. Sutner, quienes, muy amablemente, me indicaron que la mayor
parte de los cálculos que había hecho ya estaban en la literatura y me dieron las
referencias que aquí incluyo. No obstante, aunque los presentes resultados no son en
La Gaceta ? Artículos 85

absoluto novedosos, el estilo y enfoque con que están escritos es personal. Agradezco
a M. Alekseyev, J. Scherphuis, K. Sutner, y también a G. Navarro, sus comentarios
e interés por el texto.

2. Álgebra lineal sobre F2

Comencemos con algunas notaciones. En primer lugar, F2 es el cuerpo de dos
elementos, formado por {0, 1}, con la suma y la multiplicación módulo 2. En muchas
ocasiones, se suele usar la notación Z2 , pensándolo más como grupo abeliano. Pero
en estas páginas veremos la importancia de usar la estructura de cuerpo.
Consideramos un tablero n × n. El estado de un cuadrado en el tablero está dado
por un bit en F2 = {0, 1}, donde 0 significa «apagado» y 1 significa «encendido».
Por tanto, el conjunto de todas las posibles configuraciones del tablero está dado por
2
el F2 -espacio vectorial V = (F2 )n . Si v = (v1 , . . . , vn2 ) ∈ V es una configuración, el
bit vi se corresponde con el estado del cuadradito i-ésimo, donde los cuadrados se
ordenan de izquierda a derecha, línea a línea, de arriba a abajo.
En relación con la dinámica del juego, si apretamos el cuadradito i-ésimo, en-
tonces el estado de 5 cuadraditos cambia (4 si está en el borde y 3 si está en una
esquina). Este cambio se corresponde con sumar +1 a las 5 entradas correspon-
dientes, dado que si estaba apagada (0) quedará encendida (0 + 1 = 1) y si estaba
encendida (1) quedará apagada (1 + 1 = 0). Por tanto, hay un vector mi ∈ V con
5 unos, en los correspondientes lugares, y la configuración v ∈ V se transformará
en v + mi . Así, si apretamos un cuadradito una cantidad par de veces, no tiene
efecto alguno (v + mi + mi = v). Si lo apretamos una cantidad impar de veces, el
efecto es el mismo que si lo apretamos una vez. Además no importa el orden en que
apretamos los cuadrados (v + mi + mj = v + mj + mi ). Esto quiere decir que las
2
posibilidades de apretar cuadrados están dadas de nuevo por V = (F2 )n , donde
(i)
ei = (0, . . . , 1 , . . . , 0) significa «apretar el cuadrado i-ésimo».
Por tanto, el efecto de apretar cuadrados en una configuración está dado por una
función F2 -lineal
fn : V → V, (1)
donde el espacio vectorial origen V es el espacio de todos los patrones de presión
y el espacio vectorial final V es el espacio de P configuraciones de luces. Sea a =
(a1 , . . . , an2 ) ∈ V un patrón, es decir a = ai ei . Supongamos que v0 = 0 =
(0, . . . , 0) ∈ V es el estado de Ptodas las luces apagadas. Entonces, apretando el
patrón a el resultado es fn (a) = ai mi ∈ V . Si la configuración inicial es v ∈ V , el
resultado será v + fn (a).
La matriz de la aplicación lineal (1) se obtiene escribiendo los vectores m1 , . . . , mn2
en columnas de longitud n2 . Escribiendo cada columna en n porciones de longitud
86 El juego «Lights Out!»

n cada una (correspondientes a cada una de las filas del tablero), queda
 
Bn In 0 ... 0 0
 In Bn In ... 0 0 
 
 0
 In Bn ... 0 0  
 .. .. .. .. .. ..  ,
Mn =  . . . . . .  (2)
 
 0
 0 . . . B n In 0  
 0 0 ... In Bn In 
0 0 ... 0 In Bn

donde In es la matriz identidad n × n y

 
1 1 0 ... 0 0
1 1 1
 ... 0 0 
0 1 1
 ... 0 0 
Bn =  ... ... . . . .. .. ..  . (3)

 . . .
0 0 . . . 1 1 0
 
0 0 . . . 1 1 1
0 0 ... 0 1 1

El funcionamiento del juego Lights Out! está así controlado por la matriz
Mn . Si det(Mn ) = 1, entonces toda configuración se puede alcanzar a partir de la
configuración inicial v0 = 0, y además de una única forma. Si det(Mn ) = 0, entonces
fn tiene núcleo no trivial ker(fn ) ⊂ V e imagen propiamente contenida en V . Es
decir, no toda configuración es alcanzable y las que son alcanzables lo son de varias
formas2 .
Para cada n ≥ 2, sea
dn = dim ker(fn ).
Estamos interesados en calcular dn . La dimensión de im(fn ) es n2 − dn . Por tanto,
el número de configuraciones alcanzables desde una configuración dada inicial es el
2
cardinal de im(fn ), 2n −dn (es decir una fracción 1/2dn del total). Cada configuración
alcanzable lo es de 2dn formas, el cardinal de ker(fn ).
Tal como hemos comentado en la introducción, el problema all-ones off (que es
equivalente al problema de llegar al tablero v1 = 1 = (1, 1, . . . , 1) a partir de v0 = 0)
tiene siempre solución [17]. El número de sus soluciones es

Nn = 2dn .

La sucesión dn aparece en [16] y la sucesión Nn en [13].

Teorema 1. Sea Pn (t) = det(Bn − tIn ) ∈ F2 [t] el polinomio característico de Bn .
Se tiene que dn es el grado de mcd(Pn (t), Pn (t + 1)).
2 Este hecho es una manifestación de un principio genérico que también aparece como el principio

del palomar en matemática discreta, o la alternativa de Fredholm en análisis funcional.

La Gaceta ? Artículos 87

Demostración. El polinomio característico Pn ∈ F2 [t] de (3) es un polinomio

de grado n. Por el teorema de Cayley-Hamilton, Pn (Bn ) = 0. Veamos que Pn es
también el polinomio mínimo, es decir, el polinomio P de grado mínimo tal que
P (Bn ) = 0. Si v1 = (1, 0, 0, . . . , 0), entonces v2 = Bn (v1 ) = (∗, 1, 0, . . . , 0), v3 =
Bn (v2 ) = (∗, ∗, 1, 0, . . . , 0) y así sucesivamente. Por tanto, v1 , . . . , vn = Bnn−1 (v1 )
son linealmente independientes. De aquí se sigue que I, Bn , . . . , Bnn−1 también son
linealmente independiente, y Pn (t) será el polinomio mínimo.
La consecuencia es que todos los autovalores de Bn que estén repetidos apare-
cen en bloques de Jordan de tamaño máximo. Los autovalores de Bn (las raíces
del polinomio característico) aparecen en un cierre algebraico del cuerpo sobre el
que trabajamos, F2 . El cierre algebraico se denota habitualmente por F2 . Denote-
mos λ1 , . . . , λr ∈ F2 los autovalores (distintos) de Bn , y sea di la multiplicidad del
autovalor λi . En una base adecuada (sobre F2 ) podemos escribir
   
J1 0 . . . 0 λi 0 . . . 0
 0 J2 . . . 0   1 λi . . . 0 
Bn ∼ Bn0 =  . , con J = .  , i = 1, . . . , r.
   
. .
.. . . . ..  i  .. . . ..
 .. . .. 

. .
0 0 ... Jr 0 ... 1 λi
2
Consideremos ahora la matriz (2), que es un endomorfismo de V = Fn2 = Fn2 ⊕ .(n)
..
n
⊕F2 . En la clausura algebraica F2 , usando la base que hemos encontrado arriba en
cada copia de Fn2 , tenemos
 0 
Bn In 0 ... 0 0
 In Bn0 In . . . 0 0 
0
 
 0
 I n B n . . . 0 0 
Mn ∼ Mn0 =  ... .. .. .. .. ..  .

 . . . . . 

0
 0
 0 . . . Bn In 0 
 0 0 . . . In Bn0 In 
0 0 ... 0 In Bn0

Ahora reordenamos la base, tomando el primer vector de cada uno de los sumandos
Fn2 , continuando con el segundo vector de cada uno de los sumandos, y así sucesiva-
mente. La matriz resultante es
 
  Λλi 0 0 ... 0
K1 0 . . . 0  I
 0 K2 . . . 0   Λλi 0 ... 0 
Mn ∼ Mn00 =  .

. .

, con Ki =  0
 I Λλi . . . 0 ,
 .. .. . .. .. 

 .. .. .. .. .. 
 . . . . . 
0 0 . . . Kr
0 0 ... I Λλi
88 El juego «Lights Out!»

donde hemos escrito  

λ 1 0 ... 0
1
 λ 1 ... 0 
Λλ =  0
 1 λ ... 0 .
 .. .. .. .. .. 
. . . . .
0 0 ... 1 λ
Fijémonos que Λλ = Bn + (λ − 1)In , luego la misma base que sirve para poner
Bn en forma de Jordan también pone Λλ en su forma de Jordan, que es Λ0λ =
Bn0 + (λ − 1)In . Por tanto,
 0 
K1 0 . . . 0
 0 K20 . . . 0 
000
Mn ∼ Mn =  . ..  ,
 
.. ..
 .. . . . 
0 0 ... Kr0

donde
Bn0 + (λi − 1)In
 
0 ... 0

 I Bn0 + (λi − 1)In ... 0 

0
Ki = 
 0 I ... 0 ,

 .. .. .. .. 
 . . . . 
0 0 ... Bn0 + (λi − 1)In

cuyos bloques de la diagonal son

 
Ji1 0 ... 0
0 Ji2 ... 0 
Bn0 + (λi − 1)In =  . ,
 
.. .. ..
 .. . . . 
0 0 ... Jir

donde  
λj + λi − 1 0 ... 0
 1 λj + λi − 1 ... 0

Jij =  .
 
.. .. .. ..
 . . . .
0 ... 1 λj + λi − 1
Recolocando los bloques vemos que Mn ∼ Mn000 , una matriz n2 × n2 formada por
una colección de bloques, para pares (i, j), de la forma
 
Jij 0 . . . 0
 I Jij . . . 0 
Tij =  . ..  . (4)
 
 .. .. ..
. . . 
0 ... I Jij
La Gaceta ? Artículos 89

El tamaño de la matriz Jij es igual a la multiplicidad del autovalor λj en el polinomio

Pn (t), y el número de bloques Jij en (4) es igual a la multiplicidad del autovalor λi .
Para calcular dn = dim ker Mn , necesitamos sumar las dimensiones de los núcleos
de cada Tij . Claramente sólo hay contribución al núcleo cuando λi − λj = 1. Supon-
gamos que tenemos λi − λj = 1, y sea v un vector en el núcleo de Tij . Escribimos
v = v1 + · · · + vdi , de acuerdo a la descomposición en (4). Entonces, abreviando
J = Jij , tenemos que

Tij (v) = 0 =⇒ Jv1 = 0, Jv2 = v1 , . . . , Jvdi = vdi −1 .

Si di ≤ dj , el núcleo está determinado por el dato w = vdi sujeto a la condición

J di w = 0. Tal espacio tiene dimensión di . Si dj < di , podemos elegir w = vdi
libremente, con lo que la dimensión es dj . Por tanto, dim ker Tij = mı́n{di , dj } y
X
dn = dim ker Mn = dim ker Tij
λi =λj +1
X

= mı́n{di , dj } = grado mcd(Pn (t), Pn (t + 1)) .
λi =λj +1

Una consecuencia directa3 del Teorema 1 es que

dn ≤ n.

Inicialmente
P sólo se sabe que dn ≤ n2 . Otra consecuencia de la fórmula dn =
λi =λj +1 mı́n{di , dj } es que dn es par.

3. Polinomios en F2 [t]
Ahora pasamos al cálculo explícito del polinomio Pn (t). Recordemos que vive en
F2 [t], es decir, sus coeficientes son números módulo 2.
P[n/2] n−b
n−2b
Proposición 2. Pn (t) = b=0 b (1 + t) . Además, los Pn satisfacen la
relación recursiva Pn+1 (t) = (1 + t)Pn (t) + Pn−1 (t).
Demostración. Por definición, el polinomio Pn (t) es el determinante de
 
1−t 1 0 ... 0 0
 1
 1−t 1 ... 0 0 
 0 1 1 − t . . . 0 0 
Bn − tIn =  . ..  .
 
.. .. .. ..
 .. . . . . . 
 
 0 0 ... 1 1−t 1 
0 0 ... 0 1 1−t
3 Esto es una manifestación algebraica del método chasing lights explicado en [1, 19].
90 El juego «Lights Out!»

Nos fijamos en la clausura algebraica F2 de F2 , que es un cuerpo de cardinal infinito,

y calculamos el determinante de arriba para un t ∈ F2 genérico. Por el método de
eliminación de Gauss, partiendo de la matriz Bn − tIn llegamos a la matriz
 
c1 0 0 ... 0 0
 ∗ c2 0 . . . 0 0
 
 ∗ ∗ c3 . . . 0 0
..  ,
 
 .. .. . . . . ..
.
 . . . . .
 ∗ ∗ . . . ∗ cn−1 0 
∗ ∗ ... ∗ ∗ cn

donde

c1 = 1 − t,
ck+1 = 1 − t − c−1
k , k ≥ 1.

El polinomio característico de Bn es
n
Y
Pn (t) = det(Bn − tI) = ck .
k=1
Qs
Escribiendo ds = k=1 ck , tenemos que

ds+1 = cs+1 ds = (1 − t)ds − ds c−1

s = (1 − t)ds − ds−1 ,

donde Pn (t) = dn . La recursión se sigue directamente de aquí (observando que, al

estar en un cuerpo de característica 2, los signos no son P relevantes).
Consideremos ahora la función generatriz g(x) = s≥0 ds xs . La recurrencia an-
terior se reescribe ahora, en términos de g(x), como g(x) = 1 + x(1 − t)g(x) − x2 g(x).
Por tanto,
1
g(x) =
1 − x(1 − t) + x2
y
Pn (t) = Coeff xn g(x).
Al desarrollar g(x) en serie de potencias, tenemos
a  
X
2 a
XX a
g(x) = (x(1 − t) − x ) = (−1)b (1 − t)a−b xa+b .
b
a≥0 a≥0 b=0

Recordando de nuevo que estamos en característica 2, con lo que ±1 = 1, podemos

escribir
[n/2] 
X n − b
Pn (t) = (1 + t)n−2b .
b
b=0
La Gaceta ? Artículos 91

Los polinomios Pn (t) se conocen en la literatura con el nombre de polinomios de

Fibonacci [7, 6, 20] o con el de polinomios de Chebyshev [8, 18] debido a la recursión
que satisfacen (Proposición 2).
Vamos a cambiar ahora el polinomio Pn (t) por su transformado mediante la
involución t 7→ t + 1,
[n/2]  
X n − b n−2b
Qn (t) = Pn (t + 1) = t . (5)
b
b=0

Este polinomio también verifica dn = grado(mcd(Q n (t), Qn (t + 1))). Además, sus

m


coeficientes, los coeficientes binomiales k módulo 2, son fácilmente calculables. De
m


hecho, k = 1 si, escribiendo m y k en binario, cada vez que tenemos un dígito 1
para k, tenemos también un 1 en la misma posición para m. En otro caso, m


k = 0.
Esto permite escribir un programa que calcule dn para un n fijo y grande, sin tener
que ir a través de la recursión o calcular una serie de Taylor para la función g(x) de
la Proposición 2.
Damos una lista de los polinomios Rn (t) = mcd(Pn (t), Pn (t + 1)) para n ≤ 59:

R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
1 1 1 (1 + t + t2 )2 t(1 + t) 1 1 1 (1 + t + t2 )4 1
R11 R12 R13 R14 R15 R16 R17 R18
t (1 + t)3
3
1 1 (1 + t + t2 )2 1 (1 + t + t4 )2 t(1 + t) 1
R19 R20 R21 R22 R23 R24 R25 R26 R27
(1 + t + t2 )8 1 1 1 t7 (1 + t)7 (1 + t + t2 )2 1 1 1
R28 R29 R30 R31
1 t(1 + t)(1 + t + t2 )4 (1 + t3 + t5 )2 (1 + t2 + t3 + t4 + t5 )2 1
R32 R33 R34
(1 + t + t + t + t ) (1 + t + t3 + t4 + t5 )2
2 3 5 2
(1 + t + t4 )4 (1 + t + t2 )2
R35 R36 R37 R38 R39 R40 R41 R42 R43
t (1 + t)3
3
1 1 1 (1 + t + t2 )16 1 t(1 + t) 1 1
R44 R45 R46 R47 R48 R49 R50 R51
(1 + t + t2 )2 1 1 t (1 + t)15
15
1 (1 + t + t2 )4 (1 + t + t4 )2 1
R52 R53 R54 R55 R56 R57 R58 R59
1 t(1 + t) (1 + t + t2 )2 1 1 1 1 t3 (1 + t)3 (1 + t + t2 )8

Hemos factorizado los polinomios en polinomios irreducibles en F2 [t]. Claramente,

cada vez que aparece un polinomio irreducible F (t) como factor de Rn (t), también
aparece el polinomio F (t + 1) (que puede coincidir o no con F (t)) como factor de
Rn (t). Vemos patrones de repetición para cada polinomio irreducible concreto F (t)
que fijemos. De hecho, esto se puede formalizar como vemos a continuación.
92 El juego «Lights Out!»

Recordemos primero algunos resultados básicos sobre polinomios irreducibles en

F2 [t]. Si F (t) es un polinomio irreducible de grado α, entonces F2 [t]/(F ) es un
cuerpo de 2α elementos, luego isomorfo al único cuerpo de esa cardinalidad, F2α . En
α α
F2α , todos los elementos satisfacen ξ 2 − ξ = 0. Por tanto, F (t) | (t2 − t). Como
consecuencia, todos los polinomios irreducibles de grado α aparecen como factores
irreducibles del polinomio α
Vα (t) = t2 − t.
Esto proporciona un método efectivo de obtenerlos todos recursivamente. Ade-
más, si β | α entonces Vβ | Vα . Por tanto, si Wα (t) denota Q el producto de todos
los polinomios irreducibles de grado α, se tiene que Vα = β|α Wβ . Nótese que
W1 (t) = t(t − 1) = t2 − t. Si ϕ(α) es el grado de Wα , entonces β|α ϕ(β) = 2α . La
P
fórmula de inversión de Möbius nos da que
X
ϕ(α) = µ(d)2α/d ,
d|α

donde µ es la función de Möbius: µ(d) = 1 si d es libre de cuadrados y tiene un

número par de factores primos, µ(d) = −1 si d es libre de cuadrados y tiene un
número impar de factores primos, y µ(d) = 0 si d es divisible por un cuadrado. Esto
nos proporciona el número de polinomios irreducibles de grado α, Nα = ϕ(α)/α. La
lista de los primeros polinomios irreducibles (hasta grado 5) es

t, t + 1, t2 + t + 1, t3 + t + 1, t3 + t2 + 1, t4 + t + 1, t4 + t3 + 1,
t4 + t3 + t2 + t + 1, t5 + t2 + 1, t5 + t3 + 1, t5 + t3 + t2 + t + 1,
t5 + t4 + t2 + t + 1, t5 + t4 + t3 + t + 1, t5 + t4 + t3 + t2 + 1, . . .

4. Computación de los dn
S
Consideremos el conjunto de todos los polinomios irreducibles I = Iα , donde
Iα = {Fα,j : 1 ≤ j ≤ Nα } son los de grado α. Si F ∈ I entonces hay dos casos:
Si F (t) 6= F (t + 1), como ambos son polinomios irreducibles, si F (t) | Rn (t)
entonces F (t + 1) | Rn (t).
Si F (t) = F (t + 1), entonces F (t) puede aparecer (solo, sin pareja) como factor
de Rn (t). En este caso, las raíces de F (t) (que viven en el cierre algebraico)
vienen en pares (λ, λ + 1). Por tanto el grado de F (t) es par.
l
Teorema 3. La mayor potencia de t(1 + t) que divide a Rn−1 es (t(1 + t))2 −1
l
para n = 3 · 2 · (2k + 1).
Sea F = Fα,j ∈ Iα , con α > 1. Hay un número impar s = sα,j | 4α − 1 tal
que F | Rn−1 si y sólo si s | n. Además, la máxima potencia de F que divide
l+1
a Rn−1 es F 2 para n = s · 2l · (2k + 1).
La Gaceta ? Artículos 93

Demostración. Es más fácil (y en todo caso equivalente) trabajar con el polino-

mio Qn (t) definido en (5). La Proposición 2 dice que Qn satisface la recurrencia
Qn+1 (t) = tQn (t) + Qn−1 (t) con Q0 (t) = 1. De aquí deducimos que

Qn+a = Qn Qa + Qn−1 Qa−1 ,

para cualesquiera n, a ≥ 1. (El caso a = 1 es la recurrencia inicial, y por inducción,

asumiendo la igualdad para a, tenemos que, para a + 1, Qn+a+1 = Qn+1 Qa +
Qn Qa−1 = (tQn + Qn−1 )Qa + Qn Qa−1 = Qn (tQa + Qa−1 ) + Qn−1 Qa = Qn Qa+1 +
Qn−1 Qa .)
Las siguientes igualdades se siguen inmediatamente:
(
Q2n = Q2n + Q2n−1 = (Qn + Qn−1 )2 ,
Q2n+1 = Qn+1 Qn + Qn Qn−1 = tQ2n .

Con esto ya podemos probar el enunciado del teorema:

1. Fácilmente se ve que Q2n no es divisible por t y que Q2n+1 sí es divisible por t.
2. Qn y Qn+1 son coprimos para todo n ≥ 0.
3. Una inducción fácil muestra que para 2n = 2l (2k + 1), tenemos que Q2n−1 =
l l
t2 −1 (1 + · · · ). Equivalentemente, 2l k 2n ⇔ t2 −1 k Q2n−1 (donde k denota
«la máxima potencia que divide a»). El resultado es claro para l = 1, pues en
este caso n es impar y Qn−1 = 1 + · · · , con lo que Q2n−1 = tQ2n−1 = t(1 + · · · ).
Para l ≥ 2, tenemos que 2l k 2n ⇔ 2l−1 k n, y que n es par (escribamos
l−1 l−1 l
n = 2t). Así, t2 −1 k Qn−1 , lo cual es equivalente a t(t2 −1 )2 = t2 −1 k
tQ2n−1 = Q2n−1 .
4. Sea ahora F (t) un polinomio irreducible distinto de t. Entonces F | Qn−1 ⇔
F 2 | Q2n−1 . Como F | Rn−1 ⇔ F (t) | Qn−1 , F (t + 1) | Qn−1 , deducimos que
F | Rn−1 ⇔ F 2 | R2n−1 . Por tanto, si F p k Rn−1 para n impar, entonces
l
F 2 p k R2l n−1 (aún queda por comprobar que p = 2).
5. Supongamos que F | Qa−1 y F | Qb−1 . Entonces F | Qa+b−1 , como se sigue de
la fórmula Qa+b−1 = Qb−1 Qa +Qb−2 Qa−1 . También, si F | Qa+b−1 y F | Qa−1
entonces F | Qb−1 , dado que F - Qa (por el punto 2). La consecuencia es que
{a : F | Qa−1 } es un ideal de Z, intersecado con Z>0 . Sea sF > 0 el generador
de este ideal.
6. Por el punto 4, sF es impar. Sea p > 0 el entero tal que F p k QsF −1 . Entonces
F p | QksF −1 , para cualquier k ≥ 1. Es más, F 2p | Q2sF −1 , con lo que F 2p |
Q2ksF −1 para k ≥ 1. Usando que Q(2k+1)sF −1 = Q2ksF −1 QsF +Q2ksF −2 QsF −1 ,
tenemos que F p es la máxima potencia que divide a Q(2k+1)sF −1 para todo
l
k ≥ 0. Por tanto, F 2 p k Q2l (2k+1)sF −1 .
7. Aplicando el punto 6 a F = 1 + t, vemos que Q2 = 1 + t2 = (1 + t)2 . Deducimos
que sF = 3. Por el punto 1, Qn−1 es divisible por t solamente para n par. Por
tanto, t(1 + t) | Qn−1 para n múltiplo de 6. Sea n = 2l 6(2k + 1). Entonces
l+1 l+1 l+1
(1 + t)2 k Qn−1 y t2 −1 k Qn−1 . Es decir, (t(1 + t))2 −1 k Qn−1 .
94 El juego «Lights Out!»

8. Sea ahora F ∈ Iα con α > 1. Sólo nos queda comprobar que p = 2. Un cálculo
explícito (usando los valores de los coeficientes binomiales módulo 2) nos da
α−1 α−1
+2α−2 α−1
Q2α −2 = 1 + t2 + t2 + . . . + t2 +...+2
,
2α −1
Q2α −1 = t ,
α−1 α−1
+2α−2 α−1 α
Q2α = 1 + t2 + t2 + . . . + t2 +...+2
+ t2 ,
α α
de donde sale t2 Q2α −2 Q2α = t4 + t2 = (t2 + t)2 .
α
Un polinomio irreducible F de grado α satisface F 2 k (t2 + t)2 . Entonces
2
F k Q2α −2 Q2α . Los polinomios Qn y Qn−2 no pueden compartir un factor
irreducible diferente de t, con lo que o bien F 2 k Q2α −2 o bien F 2 k Q2α . En
el primer caso, sF | 2α − 1 y p = 2; en el segundo, sF | 2α + 1 y p = 2.
9. Finalmente, para n impar, F 2 k Rn−1 si y sólo si F (t)2 k Qn−1 (t) y F (t +
1)2 k Qn−1 (t) simultáneamente. Sea G(t) = F (t + 1). Si G = F entonces
el enunciado se sigue tomando sα,j = sF , F = Fα,j . Si G 6= F , entonces
consideramos los enteros sF , sG . Hay varias posibilidades: Si F 2 , G2 k Q2α −2 ,
entonces sF , sG | 2α − 1, y sα,j = mcm(sF , sG ). Si F 2 , G2 k Q2α , entonces
sF , sG | 2α + 1, y sα,j = mcm(sF , sG ). Si F 2 k Q2α −2 y G2 k Q2α , entonces
sα,j = sF sG , pues sF | 2α − 1, sG | 2α + 1, y 2α − 1, 2α + 1 son coprimos. En
todos los casos, sα,j | 4α − 1.

P da los valores dn en forma compacta. Consideremos la función

El Teorema 3 nos
generatriz D(x) = n≥0 dn xn . Si introducimos la función
n
2 3 4 5 6 7 8 9
X 2 n x2
S(x) = x + 2x + x + 4x + x + 2x + x + 8x + x + · · · = ,
1 − x2n+1
n≥0

entonces
 
6
x X
D(x) = x 4S(x6 ) − 2 + 2αS(xsα,j ) .
1 − x6
α>1,1≤j≤Nα

Para tener la información completa, necesitamos calcular los números sα,j aso-
ciados a cada polinomio irreducible F = Fα,j con α > 1. De ellos, sabemos que son
números impares con sα,j | 4α − 1. Por tanto, una manera efectiva de encontrar-
los es testeando (computacionalmente) cuál es el primer divisor n de 4α − 1 tal que
F (t), F (t+1) dividen simultáneamente a Qn−1 (t). Los argumentos del Teorema 3 nos
proporcionan un método aún más eficiente (computacionalmente hablando): consi-
deremos divisores de ambos 2α − 1, 2α + 1, y busquemos sF , sG independientemente.
Entonces sα,j = mcm(sF , sG ). Un notebook de Mathematica para hacer esto sería:
P[n_, t_] := Factor[
Sum[Binomial[n − k, k]t∧ (n − 2k), {k, 0, Floor[n/2]}],
Modulus → 2];
La Gaceta ? Artículos 95

Irreducibles = {t2 + t + 1, t3 + t + 1, t3 + t2 + 1, t4 + t + 1, t4 + t3 + 1,
t4 + t3 + t2 + t + 1, t5 + t2 + 1, t5 + t3 + 1, t5 + t3 + t2 + t + 1,
t5 + t4 + t2 + t + 1, t5 + t4 + t3 + t + 1, t5 + t4 + t3 + t2 + 1};
Irreducibles2 = PolynomialLCM[Irreducibles /. t → t + 1, 1,
Modulus → 2];
NN = Length[Irreducibles];
F[n_] := Extract[Irreducibles, {n}];
G[n_] := Extract[Irreducibles2, {n}];
Divis[n_] := Flatten[{Divisors[2∧ Exponent[F [n], t] − 1],
Divisors[2∧ Exponent[F [n], t] + 1]}];
EF[n_, k_] := Exponent[PolynomialGCD[P [n, t], F [k], Modulus → 2], t];
EG[n_, k_] := Exponent[PolynomialGCD[P [n, t], G[k], Modulus → 2], t];
k = 1;
While[k < NN + 1, z = 2;
While[EF[Extract[Divis[k], z] − 1, k] == 0, z++];
w = z;
z = 2;
While[EG[Extract[Divis[k], z] − 1, k] == 0, z++];
Print[F [k], ",", LCM[Extract[Divis[k], w], Extract[Divis[k], z]]];
k++]
Este método es mucho más eficiente que métodos más directos como el propuesto
en [16], y permite calcular dn hasta valores n muy grandes.
El comportamiento de los valores sα,j es errático como lo muestra la siguiente
lista:

Fα,j (t) sα,j .. ..

. .
t(1 + t) 6
1 + t + t2 5 1 + t2 + t3 + t5 + t9 262143
1 + t + t3 63 1 + t + t4 + t5 + t9 513
1 + t2 + t3 63 1 + t + t3 + t6 + t9 171
1 + t + t4 17 1 + t3 + t4 + t6 + t9 511
1 + t3 + t4 255 1 + t + t2 + t3 + t4 + t6 + t9 513
1 + t2 + t5 341 1 + t2 + t5 + t6 + t9 511
1 + t3 + t5 31 1 + t3 + t5 + t6 + t9 37449
1 + t + t2 + t3 + t5 33 1 + t + t2 + t3 + t5 + t6 + t9 29127
.. .. .. ..
. . . .

La sucesión de valores n + 1 para los cuales dn = 1 (es decir, para los que el juego
Lights Out! tiene solución única) es la sucesión que aparece en [15] desplazada una
unidad: 5, 6, 10, 12, 15, 17, 18, 20, 24, 25, 30, 31, 33, 34, 35, 36, 40, 42, 45, 48, 50, 51, . . .
Está generada por los valores sα,j . El reconocido investigador en Ciencias de la
Computación D. Knuth planteó si tal sucesión es infinito-generada, problema que
fue resuelto afirmativamente en 2006 (agradezco a K. Sutner el comentario).
96 El juego «Lights Out!»

5. Acción del grupo diédrico D8

Cerramos estas páginas con una observación que puede abrir una línea de trabajo
2
futura. El tablero n × n, V = Fn2 , tiene una acción del grupo de simetrías del
cuadrado, el grupo diédrico D8 . La aplicación (1) es claramente D8 -equivariante.
Por tanto, el núcleo ker fn es una D8 -representación. Si podemos caracterizar ker fn
en el anillo de representaciones F2 [D8 ], entonces podríamos describir el número de
soluciones al juego Lights Out! contando sólo soluciones salvo rotación y simetría.
La sucesión de tales números aparece en [14].
Claramente, la teoría de representaciones sobre F2 [D8 ] tiene sus propias pecu-
liaridades, dado que nos encontramos en el caso más alejado al que habitualmente
se estudia en la literatura (orden del grupo y característica del cuerpo coprimos).
En nuestro caso char F2 = 2 | #D8 = 8. No obstante, la simplicidad del grupo D8
(resoluble en dos pasos) lo hace accesible a un estudio más directo.

Referencias
[1] M. Anderson y T. Fell, Turning Lights Out with Linear Algebra, Mathe-
matics Magazine 71 (1998), 300–303.
[2] M. Barile, Lights Out Puzzle, MathWorld, [Link]
[Link], 2014.
[3] R. Barua y S. Ramakrishnan, σ-game, σ + -game and two-dimensional au-
tomata additive cellular, Theor. Computer Sci. 154 (1996), 349–366.
[4] H. Eriksson, K. Eriksson y J. Sjöstrand, Note on the Lamp Lighting
Problem, Advances Applied Math. 27 (2001), 357–366.
[5] R. Fleischer y J. Yu, A Survey of the Game “Lights Out!”, Lecture Notes
in Computer Science 8066 (2013), 176–198.
[6] J. Goldwasser, W. Klostermeyer y G. Trapp, Characterizing switch-
setting problems, Linear and Multilinear Algebra 43 (1997), 121–136.
[7] J. Goldwasser, W. Klostermeyer y H. Ware, Fibonacci polynomials
and parity domination in grid graphs, Graphs and Combinatorics 18 (2002),
271–283.
[8] M. Hunziker, A. Machiavelo y J. Park, Chebyshev polynomials over finite
fields and reversibility of σ-automata on square grids, Theor. Computer Sci. 320
(2004), 465–483.
[9] O. Martín-Sánchez, Two reflected analyses of lights out, Mathematics Ma-
gazine 74 (2001), 295–304.
[10] V. Muñoz, Una carita feliz, Desafío matemático del verano, El País, 28
de agosto de 2014, [Link]
videos/1409217029_700583.html. Solución en [Link]
com/sociedad/2014/09/02/videos/1409675199_646974.html
[11] V. Muñoz, El juego de las luces, En conmemoración del centenario del naci-
miento de Martin Gardner, Biblioteca Estímulos Matemáticos, RSME y Edi-
ciones SM, en prensa, 2015.
La Gaceta ? Artículos 97

[12] J. Scherphuis, The Mathematics of Lights Out, [Link]

puzzles/[Link], 2014.
[13] N.J.A. Sloane, Sequence A075462, The On-Line Encyclopedia of Integer Se-
quences, [Link] 2014.
[14] N.J.A. Sloane, Sequence A075463, The On-Line Encyclopedia of Integer Se-
quences, [Link] 2014.
[15] N.J.A. Sloane, Sequence A076436, The On-Line Encyclopedia of Integer Se-
quences, [Link] 2014.
[16] N.J.A. Sloane, Sequence A159257, The On-Line Encyclopedia of Integer Se-
quences, [Link] 2014.
[17] K. Sutner, Linear Cellular Automata and the Garden-of-Eden, Math. Intelli-
gencer 11 (1989), no. 2, 49–53.
[18] K. Sutner, σ-Automata and Chebyshev-polynomials, Theor. Computer Sci.
230 (2000), 49–73.
[19] Wikipedia, [Link] 2014.
[20] H. Ware, Divisibility properties of Fibonacci polynomials over GF (2), MSc.
Thesis, West Virginia University, 1997.

Vicente Muñoz, Facultad de Ciencias Matemáticas, Universidad Complutense de Madrid,

Plaza de Ciencias 3, 28040 Madrid, e Instituto de Ciencias Matemáticas (CSIC-UAM-
UC3M-UCM), C/ Nicolas Cabrera 15, 28049 Madrid
Correo electrónico: [Link]@[Link]
Página web: [Link]