martes, 30 de mayo de 2017
Martes de Combi - Matrices
Todas las entradas de una matriz de $n \times n$ son todas números enteros positivos. Se permite realizar las siguientes operaciones: multiplicar por 2 todos los números de una fila, o bien, restarle 1 a todos los números de una columna. Prueba que mediante estas operaciones podemos llegar a que todas las entradas de la matriz sean 0.
Suscribirse a:
Comentarios de la entrada (Atom)
2 comentarios:
Sketch:
Vas llevando las columnas a columnas de puros ceros una por una. Para hacer eso con cierta columna, si todas las entradas son mayores que 1, le restas 1 a todos, y si no, duplicas todas las filas cuya entrada en esa columna sea 1, y luego le restas 1 a todos. Eso reduce la suma a menos que todas las entradas de la columna sean 1, y entonces eventualmente llegas a eso, le restas 1 a esa columna y ya.
Entonces tienes una columna de puros ceros y la operación de multiplicar por 2 no la afecta. Sigues haciendo eso y ganas
Consideremos una columna cualquiera y restemos $1$ a todas sus entradas hasta que aparezcan algunos $1$'s por primera vez, digamos que hay $k$. Entonces las las entradas son $1,1,\dots 1, c_{k+1}, \dots, c_{n}$ n ese momento (no necesariamente en ese orden) multiplicamos por 2 todas las filas que tengan a los 1 de esta columna y luego restamos uno de nuevo a todos los elementos de esta columna. Esto transforma las entradas en $1,1,\dots, 1,c_{k+1}-1, \dots , c_{n}-1$. Como $c_i >1$ para todo $k+1 \le i \le n$ todas las entradas siguen siendo positivas pero la suma decreció $n-k$. Es claro que este proceso no puede seguir por siempre entonces en algún momento los únicos elementos de la columna van a ser unos y restando $1$ a todos obtenemos una columna que sólo tiene ceros. Haciendo el mismo proceso con las demás columnas podemos concluir.
Publicar un comentario