El problema de las tres casas y los tres suministros y la banda de Möbius
Seguro que muchos de vosotros conocéis el problema de las tres casas y los tres suministros. Sí, ése en el que hay que intentar conectar tres casas con tres centrales de suministro de agua, luz y gas con la condición de que ninguno de los caminos usados para estas conexiones se corten.
Este problema no tiene solución, como ya hemos visto por aquí, y la teoría de grafos nos dice por qué. La cuestión es que este problema se puede modelizar mediante grafos. El grafo que queremos construir se denomina (la K es en honor a Kazimierz Kuratowski), por lo que el problema ahora sería el siguiente: ¿podemos construir el grafo
en un plano de forma que no haya dos aristas que se corten (en un punto que no sea un vértice)? Pues la respuesta es no, no se puede. El propio Kuratowski demostró que
no es plano (no se puede dibujar en un plano sin que haya cortes entre aristas en puntos que no son vértices), por lo que el “problema de los suministros” no tiene solución en un plano.
Cambiemos de “ciudad matemática”, pasemos de un plano a una banda de Möbius. ¿Tendrá solución ahora este problema? ¿Podremos suministrar las tres casas con los tres servicios sin que se corten los caminos utilizados para ello? Pues en este caso la respuesta es un rotundo sí, las curiosas propiedades de la banda de Möbius hacen que ahora sí se pueda realizar esta conexión entre casas y centrales de suministro. En concreto, la clave está en el hecho de que la banda de Möbius tiene una sola cara. Pero para entenderlo qué mejor que una imagen ilustrativa de este hecho, ¿verdad? Vamos a ello.
En la imagen siguiente podemos ver tres puntos azules cerrados, que harán el papel de “casas”, y tres puntos negros abiertos, que simbolizarán los “suministros”. Como podéis ver, al conectar casas con suministros “de la forma habitual” quedan dos conexiones sin hacer. Para hacerlas utilizamos que las líneas no están dibujadas “en uno de los dos lados de la banda” sino “en el único lado de la banda” (recordemos, tiene una sola cara). Es decir, tanto los puntos como las líneas están algo así como “incrustados” en la propia banda. Por tanto, podemos dibujar las líneas que aparecen hacia la derecha, que saldrán de manera inversa por el otro lado de la banda, consiguiendo así que no se crucen. Aquí lo vemos con la banda “desplegada”
y aquí con la banda ya “plegada”
Sencillo a la par que curioso, ¿verdad?
Más de uno estaré ahora pensando en otro grafo de Kuratowski que tampoco es plano. Sí, me refiero a , el grafo completo de cinco vértices. Es un grafo con cinco vértices en el que cada uno de los vértices está conectado mediante una arista con los otros cuatro:
Como hemos dicho antes, se sabe que este grafo no puede representarse en un plano sin que haya cortes entre las aristas en puntos que no sean vértices (invito a quien no lo crea a que lo intente). ¿Podrá representarse en una banda de Möbius? Pues, como antes, la respuesta vuelve a ser un rotundo sí. Utilizando de nuevo que la banda de Möbius tiene una única cara podemos representar en ella. Aquí la podéis ver “sin montar”:
y aquí “montada”, en la que se ve que los vértices A y C están unidos con una arista de color azul y los vértices B y D con una de color negro que no se cortan:
Y para finalizar es interesante comentar que ni mucho menos la banda de Möbius es la única superficie donde se pueden representar y
sin que haya cortes entre aristas en puntos que no sean vértices. Por ejemplo, también puede hacerse esto en un toro, y aquí tenéis cómo hacerlo con
.
Fuentes y enlaces relacionados:
- Mapas del metro y redes neuronales, de Claudi Alsina.
- Graph Minor Theory, Part 2 en The Everything Seminar.
- Puedes leer también Puntos, rectas, y un problema sin resolver que cualquier niño puede entender de Cifras y Teclas.
29/01/2013
Excelente aporte, muy interesante!!
29/01/2013
Voy a decir algo muy rebuscado… Ahora entiendo por qué Caixanova eligió una banda de Moebius para su logo… Así el dinero podía fluir desde el suministro (ahorradores), hasta las casas de los banqueros sin cruzarse con nadie por el camino… Uuhhmm interesante… Lo que me recuerda también la peli Moebius (http://es.wikipedia.org/wiki/Moebius_%28pel%C3%ADcula%29) en la que un tren pasaba por las estaciones sin ser visto 🙂
29/01/2013
Excelente artículo, es para recomendar su lectura
29/01/2013
En un plano no es posible, al igual que no es posible en una superficie esférica.
Sin embargo, es posible hacerlo en una superficie tórica (naturalmente un toro y un plano no son topologicamente semejantes, ya que el toro tiene un agujero).
Pero una superficie tórica sigue siendo una superficie, no? 🙂
Es una trampa similar a la banda de Moebius, no? 🙂
03/10/2017
Yo lo resolvi en un plano en la secundaria, a lapiz y papel.
29/01/2013
Me ha gustado mucho, si no te importa me la “subo” al especial de Möbius que poco a poco voy alimentando en el blog…
30/01/2013
Muy bien explicado! Podrías incluir también un juego que hay en supuzle, como hizo una alumno mío aquí http://wp.me/p7JMS-LT
30/01/2013
en mi comentario anterior quería decir un alumno (se llama Antonio Oliva)
30/01/2013
Tocamates, claro que no me importa, faltaría más. Gracias a ti por considerar que merece ser añadido al “especial” :).
Mago Moebius, si haces click en el primer enlace que aparece en el post (al principio del mismo) verás otra entrada mía sobre el tema que comienza con el juego de SuPuzzle 🙂
30/01/2013
Ah! Perfecto!
30/01/2013
Me ha gustado mucho este Gaussi!
Acertaste en el twitter cuando dijiste que le gustaría a los amantes de la topología.
30/01/2013
Juanmi, es que a mí la Topología me llama mucho la atención (desde que comencé a entenderla, que al principio me costó) y sabía que esto os iba a gustar 🙂
30/01/2013
En el dibujo que aparece en el enlace que facilita Mago Moebius las 3 casas están en fila y los 3 suministros en una fila debajo, como se presenta tradicionalmente, y se ve la solución tanto en una banda de Möbius como en un toro, queda muy bonito, vale la pena echarle un vistazo:
http://topologia.wordpress.com/2010/09/21/el-problema-del-agua-la-luz-y-el%C2%A0gas/
Por otro lado si no me falla la memoria, creo recordar haber leído en el libro “Miscelánea Matemática” de Martin Gardner que en la Banda de Möbius no solo son planos los grafos K5 y K3-3 como se muestra en eta entrada, sino incluso el grafo completo K6, (6 puntos en el plano enlazados cada uno con los 5 restantes)
30/01/2013
Loa alumnos no pertenecen a nadie, en todo caso al centro educativo…
31/01/2013
hace tiempo que descubri un proyecto que se llamaba universcale y es curioso pero todo el estaba hecho como si fuera una cinta de lo mas pequeño conocido a lo mas lejano que ha llegado nuestra vista, no seria hermoso que se uniera la cinta por ambos extremos del universo como una cinta moebius? y al hilo del post …. solucionaria esto algun tipo de problema irresoluble hasta el momento?
31/01/2013
Lo que no entendí es porque pusiste el punto E del pentágono en el medio de un cuadrado.
31/01/2013
Romeo, el dibujo es topológicamente equivalente al pentágono. Curva el segmento AB para que forme un arco por encima del cuadrado formado por los otros 4 puntos A,B,C,D. A continuación ves “estirando” del punto central E hacia arriba hasta que lo sitúes por encima de los puntos A y B. Ya tienes el pentágono.
02/02/2013
Un post muy curioso e ingenioso
02/02/2013
Ajá, gracias por la explicación.
02/02/2013
Hola. Me gusta mucho vuestro blog y lo sigo en lo (poco) que puedo entender. Este tema de este problema en la banda de Mobius me resulta muy interesante. Y por eso me puse manos a la obra. Y… no soy capaz de que me salga. Entiendo la solución en el toro, pero no en Mobius. Hago la disposición de puntos que teneis en la primera foto. Pliego el papel haciendo la cinta de mobius (salvo las dos líneas que llevarían a la derecha). Prolongo las de la izquierda hasta dar toda la vuelta a la cinta y… necesitan cruzarse para la última unión. No sé si hay algo que hago mal o no acabo de entender. ¿Alguna otra fuente sobre la resolución de este problema en Mobius (¿video quizás?)? La de http://topologia.wordpress.com/2010/09/21/el-problema-del-agua-la-luz-y-el%C2%A0gas/ no me satisface (aunque sí la solución en el toro), en la foto me parece que está incompleta (no hay líneas en la unión la de banda).
Saludos,
raul
02/02/2013
raultecnologia, es que no tienes que “dar toda la vuelta”. Si has leído el post verás que la cosa es que el punto no está “encima de la banda”, sino “incrustado en la banda” (recuerda que tiene solamente una cara). Por tanto, lo que tendrías que hacer es lo que para ti sería “dar media vuelta” en vez de una vuelta completa. ¿Entendido? 🙂
21/03/2017
La banda tiene una cara, pero es un error pensar que esta incrustado. Una cinta de papel de 20 cm de largo por 3 de ancho tiene un área de 60cm² y dos lados. Al plegarla en una cita de Moebius se transforma en una única cara de 120 cm². La solución aquí propuesta esta “perforando” o incrustándose en la cara.
Al hacer una cinta de Moebius y tratar de resolver el problema de los tres servicios alguna linea se cortará, de la misma manera que ocurre en un papel (plano 2-D).
Saludos.
02/02/2013
@ gaussianos: lo voy procesando y creo haberlo entendido, tenía el esquema mental de sobre y bajo (que reflejaría suponer dos caras) y no el concepto de que las líneas están embebidas en el propio plano. Así ya lo veo. Muchas gracias por la aclaración.
Saludos,
raúl
02/02/2013
dos caras en la cinta de Moebius?
donde está la otra? 🙂 jajaja
por cierto, que anda que estuve yo fino con mi comentario diciendo que en el toro se puede hacer también, si ya lo decía el propio artículo!!!! y yo no lo vi!! eso me pasa por listo, 😉
03/02/2013
Cierto Cartesiano Caótico, se comenta al final del artículo y se da un enlace donde aparece hecho 🙂
01/09/2018
Muestra la parte de atrás. Porque lo intente y parece que tampoco tiene solución en la banda