Considera un tablero cuadriculado de $m$ x $n$. Dos cuadros unitarios se llaman adyacentes si tienen algun lado en comun y un "camino" es una secuencia de cuadros unitarios donde cualesquiera dos cuadros consecutivos del camino son adyacentes. Se dice que dos caminos no se intersectan si estos no tienen ningun cuadro en comun. Cada cuadro del tablero se colorea de blanco o negro.
Sea $N$ el numero de coloraciones del tablero tal que existe al menos un camino de puros cuadros
negros que empieza en algun cuadro de la primer columna y termina en alguno de la ultima. Sea $M$ el numero de coloraciones del tablero tal que existen al menos dos caminos que no se intersectan y ambos consisten de puros cuadros negros ( ambos caminos tambien empiezan en la primer columna y terminan en la ultima).
Prueba que $M*2^{mn} \le N^2$.
2 comentarios:
Sea $A$ el conjunto de todas las coloraciones del tablero, $B$ el conjunto de todas las coloraciones con al menos un camino negro, y $C$ el conjunto de todas las coloraciones con al menos dos caminos negros que no se intersectan. Entonces $\vert A \vert = 2^{mn}$, $\vert B \vert = N$ y $\vert C \vert = M$.
Ahora, para cada tablero $T$, diremos que un camino negro $\alpha$ en $T$ es mayor que otro camino $\beta$ si para cada columna de $T$, existe un cuadrito de $\alpha$ que está igual o más arriba que todos los cuadritos de $\beta$. Entonces, claramente existe un (único) camino en $T$ que es menor que cualquier otro camino, llamamos a este camino mínimo.
Ahora, definimos una función de $A \times C$ a $B^2$ de la siguiente manera: dada una pareja de tableros $(a, c) \in A \times C$, tomemos el camino mínimo de $C$, junto con todos los cuadritos que están debajo de él, e intercambiamos estos por los cuadritos correspondientes de $a$. La pareja de tableros resultante claramente pertenece a $B^2$, y además es fácil ver que esta función es inyectiva, pues podemos obtener la pareja original tomando el camino mínimo del segundo tablero y todos los cuadritos debajo de el, e intercambiandolos con los cuadritos correspondientes del primer tablero.
Entonces existe una inyección de $A \times C$ a $B^2$ y por lo tanto
$$M \cdot 2^{mn} = \vert A \vert \vert C \vert \leq \vert B \vert^2 = N^2$$
muy bien ari:), es el C3 de 2005
Publicar un comentario