martes, 11 de octubre de 2011
Problema del dia (combinatoria) 11/09/11
Sobre los cuadrados de una cuadricula de 4*4 se colocan simbolos 0's y 1's; estos simbolos se cambian, uno por el otro, de acuerdo a las siguientes operaciones. La operacion (A) cambia todos los simbolos de un renglon, la operacion (B) cambia todos los simbolos de una columna, La operacion (C) cambia todos los simbolos de una diagonal (Cualquiera de las 14). Determine cuales son los arreglos de los que se puede partir para que con un numero finito de operaciones se pueda llegar a un arreglo de puros simbolos 0's.
Suscribirse a:
Comentarios de la entrada (Atom)
se colocan como colorcion de ajedrez o como sean
ResponderBorrarSe puede llegar a ese arreglo desde todos excepto cuando en las posiciones de las $X$ en la siguiente coloraciones hay una cantidad impar de 1's:
ResponderBorrar$ \begin{pmatrix}O&X&X&O\\X&O&O&X\\X&O&O&X\\O&X&X&O\end{pmatrix}$
Primero vemos porque estas no se puede. Cada que tomamos una columna, un renglon o una diagonal tomamos cero o dos de estos cuadros, entonces al cambiarlo, la paridad de la cantidad de 1's se va a mantener, entonces si al principio era impar, no se puede llegar a 0 porque es par.
Ahora encontrar una forma de llegar de todos los demas arreglos.
Esto lo voy a hacer en 3 etapas, (A) los que estan en las Xs de la coloracion anterior, (B) las cuatro esquinas y (C) el cuadrado de 2x2 del centro.
(A), nos damos cuenta que hay una columna, renglon o diagonal con la que podemos cambiar el numero a dos de estos cuadrados que estan consecutivos (comparten lado o esquina). Asi, si tomamos uno de los que sean 1, y lo cambiamos junto con el cuadrado de enseguida en sentido de las manecillas del reloj, los 1s se van recorriendo hasta llegar a donde hay otro 1, donde al cambiarlos se haran 0 ambos. Asi podemos hacer que estos 8 sean 0 si al principio habia una cantidad par de unos.
(B) Hay cuatro diagonales que cambian unicamente las cuatro esquinas, asi que estas se pueden transformar en 0s.
(C) Vamos a cambiar cada cuadrado del centro individualmente a 0 sin afectar los demas, que vamos a hacer con los siguientes pasos:
$\begin{pmatrix}0&0&0&0\\0&1&X&0\\0&X&X&0\\0&0&0&0\end{pmatrix} \rightarrow \begin{pmatrix}0&0&1&0\\0&0&X&0\\1&X&X&0\\0&0&0&0\end{pmatrix}$
$\rightarrow \begin{pmatrix}1&1&0&1\\0&0&X&0\\1&X&X&0\\0&0&0&0\end{pmatrix} \rightarrow \begin{pmatrix}0&1&0&1\\1&0&X&0\\0&X&X&0\\1&0&0&0\end{pmatrix}$
$\rightarrow \begin{pmatrix}0&0&0&1\\0&0&X&0\\0&X&X&0\\1&0&0&0\end{pmatrix} \rightarrow \begin{pmatrix}0&0&0&0\\0&0&X&0\\0&X&X&0\\0&0&0&0\end{pmatrix}$
Lo repetimos para los unos que esten en el cuadrado central y todo se hace 0.
Asi demostramos que todos los demas arreglos son posibles.