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 K_{3,3} (la K es en honor a Kazimierz Kuratowski), por lo que el problema ahora sería el siguiente: ¿podemos construir el grafo K_{3,3} 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 K_{3,3} 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.

(Una representación de K_{3,3} con varios cortes en puntos que no son vértices.)

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 K_5, 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:

(Una representación de K_5 con varios cortes en puntos que no son vértices.)

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 K_5 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 K_{3,3} y K_5 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 K_{3,3}.


Fuentes y enlaces relacionados:

Share

28 comentarios

  1. Trackback | 29 ene, 2013

    El problema de las tres casas y los tres suministros y la banda de Möbius

  2. Daniel | 29 de enero de 2013 | 16:35

    Vótalo Thumb up 0

    Excelente aporte, muy interesante!!

  3. Víctor | 29 de enero de 2013 | 16:55

    Vótalo Thumb up 0

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

  4. Nora | 29 de enero de 2013 | 18:51

    Vótalo Thumb up 0

    Excelente artículo, es para recomendar su lectura

  5. Trackback | 29 ene, 2013

    Bitacoras.com

  6. Cartesiano Caotico | 29 de enero de 2013 | 20:22

    Vótalo Thumb up 0

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

  7. Tocamates | 29 de enero de 2013 | 23:59

    Vótalo Thumb up 0

    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…

  8. Mago Moebius | 30 de enero de 2013 | 01:27

    Vótalo Thumb up 0

    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

  9. Mago Moebius | 30 de enero de 2013 | 01:36

    Vótalo Thumb up 0

    en mi comentario anterior quería decir un alumno (se llama Antonio Oliva)

  10. gaussianos | 30 de enero de 2013 | 03:17

    Vótalo Thumb up 0

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

  11. Mago Moebius | 30 de enero de 2013 | 07:23

    Vótalo Thumb up 0

    Ah! Perfecto!

  12. Juanmi | 30 de enero de 2013 | 13:08

    Vótalo Thumb up 0

    Me ha gustado mucho este Gaussi!
    Acertaste en el twitter cuando dijiste que le gustaría a los amantes de la topología.

  13. gaussianos | 30 de enero de 2013 | 14:46

    Vótalo Thumb up 0

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

  14. Albert | 30 de enero de 2013 | 17:28

    Vótalo Thumb up 0

    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)

  15. daniel | 30 de enero de 2013 | 19:39

    Vótalo Thumb up 0

    Loa alumnos no pertenecen a nadie, en todo caso al centro educativo…

  16. Trackback | 30 ene, 2013

    El problema de las tres casas y los tres suministros y la banda de Möbius

  17. anon42 | 31 de enero de 2013 | 01:56

    Vótalo Thumb up 0

    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?

  18. Romeo | 31 de enero de 2013 | 15:04

    Vótalo Thumb up 0

    Lo que no entendí es porque pusiste el punto E del pentágono en el medio de un cuadrado.

  19. Albert | 31 de enero de 2013 | 16:51

    Vótalo Thumb up 0

    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.

  20. sadig | 2 de febrero de 2013 | 00:25

    Vótalo Thumb up 0

    Un post muy curioso e ingenioso

  21. Romeo | 2 de febrero de 2013 | 16:11

    Vótalo Thumb up 0

    Ajá, gracias por la explicación.

  22. raultecnologia | 2 de febrero de 2013 | 20:41

    Vótalo Thumb up 0

    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

  23. gaussianos | 2 de febrero de 2013 | 22:30

    Vótalo Thumb up 0

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

  24. rualtecnologia | 2 de febrero de 2013 | 23:44

    Vótalo Thumb up 0

    @ 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

  25. Cartesiano Caotico | 2 de febrero de 2013 | 23:53

    Vótalo Thumb up 0

    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, ;)

  26. gaussianos | 3 de febrero de 2013 | 05:58

    Vótalo Thumb up 0

    Cierto Cartesiano Caótico, se comenta al final del artículo y se da un enlace donde aparece hecho :)

  27. Trackback | 10 ene, 2014

    (Lo que yo considero) Lo mejor de 2013 en Gaussianos | Matemáticas Secundaria

  28. Trackback | 26 feb, 2014

    El problema matemático que nació en un campo de trabajo de la Segunda Guerra Mundial | Cifras y Teclas

Escribe un comentario

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia. Utiliza la Vista Previa antes de publicar tu comentario para asegurarte de que las fórmulas están correctamente escritas.