¿Cuál sería un algoritmo para apagar todas las lámparas?

Question

He encontrado un problema de algoritmos que no he podido resolver de http://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=muslam . Supongo que como requiere álgebra lineal, este podría ser un lugar correcto para pedir un algoritmo.

Tenemos $n$ para formar un bucle circular con $n$ interruptores de encendido/apagado. Al principio, algunas lámparas están encendidas, denotadas por el bit 1 y otras están apagadas, denotadas por el bit 0. Nos han dado un número entero $m$ . Al pulsar cada interruptor cambia el estado de la lámpara que corresponde al interruptor y su $m$ lámparas más cercanas en cada dirección. Averigua cuántos interruptores hay que pulsar para apagar todas las lámparas y da una lista de los interruptores pulsados.

Traté de pensar que necesito resolver una ecuación matricial sobre $\mathbb Z/2\mathbb Z$ pero descubrí que la matriz de coeficientes que hice no tiene inversa. He pensado que necesito una matriz de coeficientes tal que $A_{i,j}=1$ si se pulsa el interruptor $i$ cambia el estado de la lámpara $j$ y $A_{i,j}=0$ si no cambia.

Aquí está mi código para el caso de que haya seis lámparas con estados iniciales 101101 y cada interruptor afecte a la lámpara dada y a una de sus lámparas más cercanas en ambas direcciones.

# Generate the zero matrix
def generate_matrix(w, h):
    return [[0 for x in range(w)] for y in range(h)]

# Print matrix
def print_matrix(A):
    for row in range(0,len(A[0])):
        line = ""
        for col in range(0,len(A[0])):
            line += str(A[row][col])
            if col == len(A[0]):
                line += "\n"
        print(line)

# Swap two rows
def swap_rows(A,i,j):
    for k in range(0,len(A[0])):
        temp = A[k][i]
        A[k][i] = A[k][j]
        A[k][j] = temp
    return A

# Add one row to another
def mult_rows(A,i,j):
    for k in range(0,len(A[0])):
        A[k][j] += A[k][i]
    return A

# Distance between two indices
def dist(i,j,n):
    d1 = max(i-j,j-i)
    dist_beg = min(i,j)
    dist_end = n-max(i,j)
    d2 = dist_beg + dist_end
    return min(d1,d2)

# Initialize the coefficient matrix
def gen_coeff_matrix(n,effect_width):
    A = generate_matrix(n,n)
    for i in range(0,n):
        for j in range(0,n):
            if dist(i,j,n) <= effect_width:
                A[i][j] = 1
    return A

# Initialize the unit matrix
def init_unit_matrix(n):
    A = generate_matrix(n,n)
    for i in range(0,n):
        A[i][i] = 1
    return A

# Inverse of the matrix
def inv(M):
    n = len(M[0])
    U = init_unit_matrix(n)
    for column in range(0,n):
        if M[column][column] == 0:
            i = 1
            while M[column+i][column+i] != 0:
                ++i
            swap_rows(A,column,column+i)
            swap_rows(U,column,column+i)
        for c in range(0,n):
            if M[c][column] == 1:
                if c != column:
                    mult_rows(M,c,column)
                    mult_rows(U,c,column)
    return U

A = init_unit_matrix(5)
B = gen_coeff_matrix(6,1)
print_matrix(B)

Da la matriz

110001
111000
011100
001110
000111
100011

pero no es invertible según Sage:

sage: F = FiniteField(2)
sage: C = Matrix(F,[[1,1,0,0,0,1],[1,1,1,0,0,0],[0,1,1,1,0,0],[0,0,1,1,1,0],[0,0,0,1,1,1],[1,0,0,0,1,1]])
sage: C
[1 1 0 0 0 1]
[1 1 1 0 0 0]
[0 1 1 1 0 0]
[0 0 1 1 1 0]
[0 0 0 1 1 1]
[1 0 0 0 1 1]
sage: C^(-1)
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-4-48e78ab0a5de> in <module>()
----> 1 C**(-Integer(1))

sage/matrix/matrix0.pyx in sage.matrix.matrix0.Matrix.__pow__ (/usr/lib/sagemath//src/build/cythonized/sage/matrix/matrix0.c:36015)()

sage/structure/element.pyx in sage.structure.element.generic_power_c (/usr/lib/sagemath//src/build/cythonized/sage/structure/element.c:29266)()

sage/matrix/matrix_mod2_dense.pyx in sage.matrix.matrix_mod2_dense.Matrix_mod2_dense.__invert__ (/usr/lib/sagemath//src/build/cythonized/sage/matrix/matrix_mod2_dense.c:7868)()

ZeroDivisionError: Matrix does not have full rank.

También he probado con el siguiente comando:

sage: V=Matrix(F,[[1,0,1,1,0,1]])
sage: C\V

ValueError: number of rows of self must equal number of rows of B

Preguntas: ¿Es esta la forma correcta de pensar en el problema? ¿Hay un error en el razonamiento de cómo hacer la matriz de coeficientes? ¿Es sólo un error tonto en mi código?

Answer 1

Estás pensando en ello exactamente de la manera correcta. La multiplicación de la matriz por un vector mostrará qué luces están encendidas si se empieza con las luces apagadas y se accionan los interruptores representados por $1$ s en el vector. Entonces, si inviertes la matriz y la multiplicas por el estado inicial, descubrirás cómo pasar de tu estado inicial a todo apagado. El hecho de que tu matriz no sea invertible dice que hay estados desde los que no puedes llegar al estado inicial. Puedes ver que la matriz no es invertible porque las líneas primera y cuarta suman $[1\ 1\ 1\ 1\ 1\ 1]$ al igual que el segundo y el quinto y el tercero y el sexto. Todavía se puede hacer la eliminación gaussiana para ver de su estado inicial puede llegar a todos fuera. El problema viene porque el número de luces afectadas no es coprimo con el número de luces. Prueba con ocho luces en lugar de seis y creo que encontrarás una solución que funcione. En tu caso ninguno de los interruptores cambia el número de luces que están encendidas $\bmod 3$ . Como se empieza con cuatro encendidos, no se puede llegar a todos apagados. El álgebra lineal no es necesaria, pero es una buena manera de atacarla. Un enfoque intermedio es tratar de encontrar a mano una manera de apagar una sola lámpara. Cualquier lámpara dada puede ser apagada girando el conjunto de interruptores que usas para la primera lámpara. Si tienes un número de lámparas para apagar, sólo tienes que recopilar la lista de interruptores para cada lámpara, eliminar los duplicados de dos en dos, y ya está. Aquí estás encontrando una base para el espacio vectorial.