Invariantes: un frame que permite razonar por el absurdo

Invariantes

(Adaptado  de http://boumbo.toonywood.org/xavier/old/maths/stmalo/base-cours.pdf )

Se tiene un conjunto de configuraciones (por ejemplo, estados o posiciones en un juego). A una configuración inicial se le aplica una transformación (una jugada) sujeta a ciertas reglas (las reglas del juego) y sobre la configuración resultante se aplica otra transformación de acuerdo a las mismas reglas (el juego sigue). Se pide decidir si una cierta configuración puede o no obtenerse mediante transformaciones válidas partiendo de una configuración inicial.

El método de invariantes consiste en asociar a cada configuración un objeto (por ejemplo un número entero o una propiedad) que se va a llamar su invariante (pues no cambia de una transforamación a otra, es decir, de una configuración a su configuración transformada.

Para la configuracón inicial y la que está en cuestión se calcula el valor de la invariante, y si resultan diferentes entonces la configuración en cuestión no puede derivarse de la inicial mediante transformaciones válidas. (Ojo: si son iguales nada se concluye --la falacia de afirmación del consecuente es tentadora pero...)

Ejemplo:

Considere las palabras en el alfabeto a, b, z. Las transformaciones autorizadas son las siguientes: a) ab-->bba y bba-->ab; b)az-->zza y zza-->az; c)bz-->zb y zb-->bz. Demostrar que no es posible pasar, mediante transformaciones autorizadas, de la palabra abza a la palabra zabz.

Invariante de paridad

En un conjunto S de configuraciones se define una función con valores en el conjunto B={0,1}. Es decir, a cada configuración se le asocia un 0 o bien un 1.

Ejemplo

Se tiene un tablero cuadriculado de 8x8 con focos en cada cuadro o casilla. Para cada fila y para cada columna del tablero hay un interruptor con dos estados: on/off. (Imagine el lector que los interruptores encabezan las filas y las columnas.) Al cambiar de estado un interruptor, se cambian de estado cada uno de los focos de la fila o de la columna a la cual pertenece el interruptor (si un foco está prendido se apaga y si está apagado se prende). Al principio todos los focos están apagados. ¿Es posible que, en una serie finita de cambios de estado de los interruptores, se pueda lograr que solamente el foco en el cuadro de la fila 3 y columna 4 esté prendido?

(Sugerencia: considere una fila o una columna y sean a los focos apagados en ella y b los focos prendidos en ella; ahora note que a+b=8 ¿Te dice algo esto sobre la paridad de los focos prendidos en esa fila o columna antes y después de activar su interruptor? ¿Y sobre la paridad de todos los focos prendidos en el tablero?)

Paridad y coloración

Ejemplo

En un tablero de ajedrez (cuadrícula 8x8) se han quitado dos cuadros de esquinas opuestas. ¿Es posible cubrir las 62 casillas restantes con 31 mosaicos de dos cuadrados --como fichas de dominó?

La demostración de que no es posible se basa en considerar los mosaicos coloreados en blanco y negro --un cuadro blanco y el otro negro. Entonces se ve claramente que cada vez que se coloca un mosaico se cubren una casilla negra y una blanca del tablero --sin importar si se coloca verticalmente u horizontalmente. Por lo tanto, colocando 31 mosaicos se cubrieron 31 casillas negras y 31 blancas del tablero. Y se logra una contradicción. Pues las casillas eliminadas del tablero son ambas negras o ambas blancas, es decir, las casillas restantes del tablero son 32 de un color y 30 del otro.

Comentario

Una configuración, en este caso, es una cuadrícula coloreada como en tablero de ajedrez donde se han eliminado ciertas casillas. Sobre estas configuraciones se cuentan las casillas presentes y coloreadas de negro --digamos que sean a--, y las presentes y coloreadas de blanco --digamos que sean b. La función que se define sobre las configuraciones es la diferencia a-b. De esa manera, el número asociado a la configuración en cuestión es 2 (en valor absoluto). La función así definida es invariante sobre las configuraciones cubiertas con mosaicos de dos cuadros uno blanco y uno negro. Para estas configuraciones la diferencia de negras y blancas siempre es 0.

Los saluda

jmd

PD: en esta semana pongo el material de invariantes y los otros temas que faltan...