Entradas etiquetadas como ‘ajedrez’

Hoy toca pensar (y mañana también) — Las soluciones

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?

Fuente
 

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:

cubo de rubik

 

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):

cubo-de-rubik-300x300

 

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:

hamilton

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:

hamilton-300x225Ahora 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.

Hoy toca pensar (y mañana también)

Parte del valor de las Matemáticas (de la disciplina, no de las afortunadas que nos dedicamos a la misma),  al margen de su utilidad y aplicación a otras disciplinas, radica en la capacidad que tienen para hacernos pensar. Pero hacernos pensar bien, en el sentido de que hemos de ordenar nuestro pensamiento y determinar las pautas adecuadas que nos permitan resolver el problema con el que nos enfrentamos. Me gustaría poner tres ejemplos de problemas muy conocidos que comparten un espíritu común. Del primero daré la solución, aunque propondré variantes de las que no adelantaré la suya, pero de los otros dos solo daré alguna pista. Una aclaración: son problemas para todas las edades, podemos decir que de 9 a 99 años.

¿Estamos listos? Puesto que decimos que tenemos que ser ordenados, empezaremos por el primero:

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?

La respuesta no es excesivamente complicada si encontramos la clave para resolver el problema: cada ficha de dominó ocupa dos casillas de ajedrez, y como dichas casillas son contiguas han de ser forzosamente de distinto color: una casilla negra y otra blanca, por tanto con las fichas de dominó cubriremos siempre el mismo número de casillas blancas que negras; pero dos casillas diagonalmente opuestas siempre tienen el mismo color, por lo tanto en nuestro tablero «mutilado» tendremos más casillas de un color que de otro y será imposible de cubrir con fichas de dominó.

Ahora supongamos que eliminamos dos casillas de distinto color: ¿se puede siempre cubrir el tablero con fichas de dominó? ¿existen casos en los que sí y otros en los que no? Espero vuestras soluciones en los comentarios.

Para los otros dos problemas no voy a dar la solución, aunque daré alguna pista al final:

Supongamos que tenemos un cubo dividido en 27 cubitos como en la figura:

cubo de rubik

 

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?

El último puede que sea el más difícil, pero si habéis resuelto los anteriores tenemos un buen entrenamiento que nos permitirá atacarlo con la actitud adecuada:

El esquema que exponemos a continuación representa a 13 ciudades y a las carreteras que las unen:

hamilton

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).

Espero que os gusten los problemas propuestos y que dejéis vuestras soluciones en los comentarios, pero…, un momento: se me olvidaba que había prometido alguna pista. No quiero ser muy explícita, pero digamos que para solucionar el problema de cubrir con fichas de dominó el tablero de ajedrez sin dos esquinas opuestas ha venido muy bien que las casillas del tablero sean blancas y negras y con una disposición muy específica.

Venga, va, deja de pensar en la estupidez que haya dicho alguno de nuestros ministros este fin de semana y trata de resolver estos retos.

Espero que mis alumnos de Matemática Discreta sepan resolverlos todos sin ningún esfuerzo… 😉