En el capítulo de Mati del pasado lunes propusimos algunos retos y ya anunciamos que en el capítulo de hoy íbamos a dar las soluciones a dichos retos. Pero antes repasemos dichos retos. Primero, propusimos una al que dimos la solución:
Supongamos que tenemos un tablero de ajedrez y varios juegos de dominó tal que sus piezas cubren dos casillas del tablero; es evidente que con 32 piezas de dominó se puede cubrir todo el tablero, pero una pregunta clásica es la siguiente: si eliminamos dos casillas que ocupan alguna de las esquinas diagonalmente opuestas del tablero: ¿podemos cubrir las casillas restantes con piezas de dominó de tal forma que cada pieza cubra dos casillas y que no se superpongan?
Tal y como decíamos, la solución de este enigma no era excesivamente complicada y para ello basta con contar el número de casillas blancas y el de casillas negras que nos quedan (no es el mismo quitemos los pares de esquinas opuestas que quitemos) y observar que cada ficha de dominó tapa una blanca y una negra. Lo que quisiera destacar es que el uso los dos colores en los escaques es una ayuda fundamental a la hora de resolver el problema. Del ajedrez pasábamos a un cubo:
Supongamos que tenemos un cubo dividido en 27 cubitos como en la figura:
Si una hormiga comienza a horadar un túnel comenzando por una de las caras de uno de los cubitos de alguna esquina y pasando de un cubito a otro a través de una pared común (no a través de un lado, ni de un vértice), ¿podrá nuestra hormiga terminar en el cubito central después de haber pasado por todos los demás cubitos y sin repetir ninguno?
La idea para resolver este problema es usar un truco similar al anterior y colorear los 27 cubitos de blanco y negro alternativamente (de tal forma que dos cubos que compartan una pared común no tengan el mismo color. Así nos quedaría algo como muestra la siguiente figura (el resto de los cubitos que no se ven tienen que seguir el mismo patrón):
La idea es que nuestra hormiga empieza a horadar en alguna de las caras de una de las esquinas, esto es: empieza en un cubito negro en nuestro dibujo y pasa a un cubito con el que comparta cara, por tanto el segundo cubito por el que pasa será blanco. Pero como tenemos 27 cubitos, empezando en negro, pasamos a blanco (como hemos dicho), después negro, blanco, etc., y tendremos que acabar en negro forzosamente ya que como hemos coloreado tenemos 14 cubitos negros y 13 blancos, por lo tanto, nuestra hormiga acabará en un cubo negro. Como nos preguntábamos si podíamos acabar en el cubo central, la pregunta será ¿de qué color es el cubo central? Observando un poco, vemos que el cubito central es blanco y ello nos demuestra que nuestra hormiga no puede acabar su «paseo» en él. No era tan difícil ¿verdad? La clave ha residido en saber dar una estructura adecuada y una propiedad, basándonos en dicha estructura que nos ha permitido solucionar el problema.
¿Pasamos al otro reto?
El esquema que exponemos a continuación representa a 13 ciudades y a las carreteras que las unen:
La pregunta en este caso es: ¿podemos realizar un recorrido empezando y terminando en alguna de las ciudades y pasando por todas las demás ciudades y sin repetir ninguna? (El camino empieza y termina en la misma ciudad).
¿Podremos utilizar el mismo truco (o similar) para resolver este problema? La respuesta, como supongo que ya empezáis a sospechar es que sí. Efectivamente, podemos «colorear» nuestras ciudades de blanco y negro de tal forma que si dos están unidas no compartan el mismo color de la siguiente forma:
Ahora observamos que cualquier recorrido que acabe y termine en la misma ciudad y que no repita ninguna ha de contener forzosamente el mismo número de ciudades blancas que negras, pero en nuestro caso tenemos 6 ciudades negras y 7 blancas, luego no podremos pasar por todas en un recorrido con las condiciones expuestas.
Una vez que se ve la solución parece sencillo, ¿verdad? el problema ha sido resuelto siempre usando el mismo esquema: sea una tablero, un cubo dividido en cubos o un mapa de carreteras, hemos visto que podemos colorear con dos colores de tal forma que dos elementos contiguos no comparten el mismo color, después hemos usado dicho coloreado para tratar de encontrar la solución.
Nos quedaría por resolver el caso de qué ocurre cuando eliminamos dos casillas de distinto color en un tablero de ajedrez ¿podemos recubrir los escaques restantes con fichas de dominó? Tal y como apuntó alguno en los comentarios, este caso es relativamente distinto a los anteriores y se trata de examinar todos los casos posibles. Vamos a tratar de examinar dichos casos (sin dar la solución explícitamente que no será excesivamente difícil de encontrar para el lector):
Primero sugiero que pensemos que una de las casillas que eliminamos sea una esquina (supongamos que la superior izquierda: blanca), como la otra casilla ha de ser negra, el rectángulo que definen entre ambas forzosamente ha de tener o un número impar de columnas y un número par de filas o un número par de columnas e impar de filas. Tratad de solucionar dicho caso. A partir de lo visto en el caso anterior, se puede atacar el caso general: suerte.