{"id":160,"date":"2010-12-15T18:51:15","date_gmt":"2010-12-15T17:51:15","guid":{"rendered":"http:\/\/www.madrimasd.org\/blogs\/redes-complejas\/?p=160"},"modified":"2010-12-15T18:51:15","modified_gmt":"2010-12-15T17:51:15","slug":"cuando-saber-plantear-un-problema-es-casi-la-solucion","status":"publish","type":"post","link":"https:\/\/www.madrimasd.org\/blogs\/redes-complejas\/2010\/12\/15\/160\/","title":{"rendered":"Cuando saber plantear un problema es casi la soluci\u00f3n"},"content":{"rendered":"

En uno de los maravillosos libros del genial divulgador\u00a0Martin Gardner<\/a>, \u00a1Aj\u00e1! Inspiraci\u00f3n<\/em><\/a>, 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\u00d73, tal y como muestra la imagen.\u00a0\u00bfCu\u00e1l es el n\u00famero m\u00ednimo de movimientos necesarios para intercambiar las posiciones de los caballos blancos y negros?<\/p>\n

\"Posici\u00f3n<\/p>\n

El problema en s\u00ed es s\u00f3lo un pasatiempo, pero lo presento aqu\u00ed porque me parece un buen ejemplo de c\u00f3mo la soluci\u00f3n a un problema pasa, en muchas ocasiones, por transformarlo en otro equivalente mucho m\u00e1s f\u00e1cil de resolver. En este caso\u00a0encontrar una soluci\u00f3n llevar\u00e1 un rato pero se acaba logrando. Sin embargo,\u00a0si no se cambia de enfoque, es dif\u00edcil imaginar c\u00f3mo se demuestra que una soluci\u00f3n es m\u00ednima.<\/p>\n

En la entrada de este blog,\u00a0\u00abPara comenzar, hablemos un poco de Euler\u00bb<\/a>, se describe c\u00f3mo Euler fue capaz de resolver el problema de los puentes de K\u00f6nigsberg transformando las diferentes partes de la ciudad y sus puentes en un grafo (un matem\u00e1tico dir\u00eda que encontr\u00f3 un problema isomorfo<\/a>). En el problema propuesto, la clave para resolverlo (el \u00abmomento \u00a1aj\u00e1!\u00bb que dir\u00eda Martin Gardner) pasa por generar el grafo<\/a> asociado a los movimientos de los caballos.<\/p>\n

\u00bfY c\u00f3mo se hace eso? Uniendo con una l\u00ednea 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\u00ednea de 1 a 6 y otra de 1 a 8. Repitiendo el proceso para el resto de celdas obtenemos el siguiente grafo:<\/p>\n

\"Todos<\/p>\n

Pero ese grafo, que parece un barullo de l\u00edneas e in\u00fatil para resolver el problema planteado, es en realidad el sencillo grafo de la imagen (\u00a1compru\u00e9balo t\u00fa mismo!):<\/p>\n

\"Grafo<\/p>\n

Las celdas del tablero son llamadas nodos en teor\u00eda de grafos\u00a0y las l\u00edneas entre pares de celdas, enlaces. Cuando unimos un par de celdas con un enlace, indicamos que ese par de celdas est\u00e1n comunicadas mediante un salto de caballo.\u00a0La 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,\u00a0transformaci\u00f3n el problema se resuelve f\u00e1cilmente: el n\u00famero m\u00ednimo de saltos necesarios para intercambiar los 4 caballos es 16 (\u00bfves c\u00f3mo?).<\/p>\n

Un planteamiento adecuado hace que un problema, que de otra forma ser\u00eda dif\u00edcil, se resuelva c\u00f3modamente. Ese es el convencimiento que tenemos quienes nos dedicamos a las Redes Complejas.\u00a0Hoy d\u00eda existe una gran cantidad de publicaciones en los que, de forma reiterada, se comprueba que con este enfoque se entienden mejor\u00a0las intrincadas relaciones entre los constituyentes de sistemas muy diversos. Una extensa lista de referencias se puede encontrar en\u00a0Physics Report 424, Issue 4-5, February 2006, Pages 175-308<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

En uno de los maravillosos libros del genial divulgador\u00a0Martin Gardner, \u00a1Aj\u00e1! Inspiraci\u00f3n, 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\u00d73, tal y como muestra la imagen.\u00a0\u00bfCu\u00e1l es el n\u00famero m\u00ednimo de movimientos necesarios para intercambiar las posiciones de los caballos blancos y negros? El problema en s\u00ed es s\u00f3lo un pasatiempo, pero lo presento aqu\u00ed porque me parece un buen ejemplo de c\u00f3mo la soluci\u00f3n a un problema pasa, en muchas ocasiones, por transformarlo en otro\u2026<\/p>\n","protected":false},"author":166,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0},"categories":[1],"tags":[2254,2562],"blocksy_meta":{"styles_descriptor":{"styles":{"desktop":"","tablet":"","mobile":""},"google_fonts":[],"version":4}},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.madrimasd.org\/blogs\/redes-complejas\/wp-json\/wp\/v2\/posts\/160"}],"collection":[{"href":"https:\/\/www.madrimasd.org\/blogs\/redes-complejas\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madrimasd.org\/blogs\/redes-complejas\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/redes-complejas\/wp-json\/wp\/v2\/users\/166"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/redes-complejas\/wp-json\/wp\/v2\/comments?post=160"}],"version-history":[{"count":28,"href":"https:\/\/www.madrimasd.org\/blogs\/redes-complejas\/wp-json\/wp\/v2\/posts\/160\/revisions"}],"predecessor-version":[{"id":253,"href":"https:\/\/www.madrimasd.org\/blogs\/redes-complejas\/wp-json\/wp\/v2\/posts\/160\/revisions\/253"}],"wp:attachment":[{"href":"https:\/\/www.madrimasd.org\/blogs\/redes-complejas\/wp-json\/wp\/v2\/media?parent=160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/redes-complejas\/wp-json\/wp\/v2\/categories?post=160"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/redes-complejas\/wp-json\/wp\/v2\/tags?post=160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}