Cuando saber plantear un problema es casi la solución

En uno de los maravillosos libros del genial divulgador Martin Gardner, ¡Ajá! Inspiración, pude leer, hace ya mucho tiempo, un curioso problema que quiero compartir ahora con los lectores del blog. Tenemos 2 caballos blancos y 2 caballos negros de ajedrez en un tablero 3×3, tal y como muestra la imagen. ¿Cuál es el número mínimo de movimientos necesarios para intercambiar las posiciones de los caballos blancos y negros?

Posición inicial

El problema en sí es sólo un pasatiempo, pero lo presento aquí porque me parece un buen ejemplo de cómo la solución a un problema pasa, en muchas ocasiones, por transformarlo en otro equivalente mucho más fácil de resolver. En este caso encontrar una solución llevará un rato pero se acaba logrando. Sin embargo, si no se cambia de enfoque, es difícil imaginar cómo se demuestra que una solución es mínima.

En la entrada de este blog, “Para comenzar, hablemos un poco de Euler”, se describe cómo Euler fue capaz de resolver el problema de los puentes de Königsberg transformando las diferentes partes de la ciudad y sus puentes en un grafo (un matemático diría que encontró un problema isomorfo). En el problema propuesto, la clave para resolverlo (el “momento ¡ajá!” que diría Martin Gardner) pasa por generar el grafo asociado a los movimientos de los caballos.

¿Y cómo se hace eso? Uniendo con una línea los pares de celdas involucradas en un salto de caballo. Por ejemplo, si numeramos las celdas del 1 al 9, un caballo en 1 puede ir a 6 y a 8, luego dibujamos una línea de 1 a 6 y otra de 1 a 8. Repitiendo el proceso para el resto de celdas obtenemos el siguiente grafo:

Todos los posibles saltos de caballo

Pero ese grafo, que parece un barullo de líneas e inútil para resolver el problema planteado, es en realidad el sencillo grafo de la imagen (¡compruébalo tú mismo!):

Grafo simplificado de los saltos de los caballos

Las celdas del tablero son llamadas nodos en teoría de grafos y las líneas entre pares de celdas, enlaces. Cuando unimos un par de celdas con un enlace, indicamos que ese par de celdas están comunicadas mediante un salto de caballo. La celda 5 queda aislada debido a que no existe salto de caballo que nos lleve a ella, pero las restantes quedan ordenadas en forma de un anillo. Y con esta sencilla, aunque ciertamente inspirada, transformación el problema se resuelve fácilmente: el número mínimo de saltos necesarios para intercambiar los 4 caballos es 16 (¿ves cómo?).

Un planteamiento adecuado hace que un problema, que de otra forma sería difícil, se resuelva cómodamente. Ese es el convencimiento que tenemos quienes nos dedicamos a las Redes Complejas. Hoy día existe una gran cantidad de publicaciones en los que, de forma reiterada, se comprueba que con este enfoque se entienden mejor las intrincadas relaciones entre los constituyentes de sistemas muy diversos. Una extensa lista de referencias se puede encontrar en Physics Report 424, Issue 4-5, February 2006, Pages 175-308.

Compartir:

Un comentario

Deja un comentario