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.

  (Una representación de 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 , 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 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 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 .

Fuente:

Gaussianos

El problema de las distancias enteras en el plano

Que levanten la mano los que crean que “en matemáticas está todo inventado”. Venga, sin miedo que aquí estamos para aprender.

Pues no, las matemáticas son una ciencia muy viva con una gran actividad investigadora (y, por el momento, España está entre los primeros puestos en investigación matemática). Sin embargo, aún quedan muchos problemas para los que no se conoce solución, o para los que se busca una solución mejor.


Hoy contaremos un ejemplo de problema muy fácil de entender, pero aún sin resolver, el problema de las distancias enteras en el plano. Empecemos por la siguiente pregunta:

¿Cuántos puntos se pueden colocar en el plano de manera que la distancia entre cualquier par de puntos sea un número entero?

Así sin más, la respuesta es muy fácil. Piénsalo un poco... ¿La tienes? Bastaría con poner puntos alineados, por ejemplo a lo largo de una recta horizontal, cada uno a distancia 1 del siguiente. Así podríamos colocar infinitos puntos con distancias enteras entre todos ellos.

Y entonces podemos preguntarnos

¿Hay alguna otra manera, que no sea sobre una recta, de colocar infinitos puntos en el plano con distancias enteras entre todos ellos?

En 1945 Erdős (un matemático muy particular) y Anning demostraron que no, que sólo puede haber infinitos puntos con distancias enteras si éstos están alineados. Además, también demostraron que para cualquier número (finito) n, se pueden colocar n puntos en el plano con distancias enteras entre ellos.

Eso sí, para ello tenían que colocar todos los puntos sobre una circunferencia. Así que después de publicar este resultado en 1945, Erdős modificó la pregunta inicial. Lo verdaderamente interesante era:

¿Cuántos puntos se pueden colocar en el plano, sin que haya tres en una misma recta ni cuatro en una misma circunferencia, de manera que la distancia entre cualquier par de puntos sea un número entero?

Vamos a intentar responder a esta pregunta. Con 2 puntos todo el mundo sabe hacerlo...

Ahora inténtalo con 3 puntos. ¿Ya lo tienes? Sirve cualquier triángulo rectángulo cuyas longitudes de los lados formen una terna pitagórica. Por ejemplo:

Con 4 puntos es un poco más difícil, pero no mucho. Después de un rato pensando, se nos puede ocurrir usar cuatro triángulos como el anterior para obtener:

Con 5 puntos la cosa ya se complica más y no pretendemos que lo resuelvas, pero si quieres puedes comprobar que los puntos de la siguiente figura cumplen la propiedad:

Para 6 puntos también se puede hacer, si quieres comprobarlo puedes mirar este enlace.

Para 7 puntos, Kreisel y Kurz encontraron la manera de hacerlo, que puedes ver también en este otro enlace. Lo llamativo es que para ello necesitaron varias buenas ideas y unas cuantas horas de cálculo por ordenador... y su resultado es de 2007. Es decir, más de 60 años después de la pregunta original de Erdős.

¿Y para 8 puntos? Pues, aunque no te lo creas:

Nadie sabe si es posible colocar 8 puntos en el plano, sin que haya tres en una misma recta ni cuatro en una misma circunferencia, con distancias enteras entre todos ellos.

Así que aquí tienes un problema de matemáticas que es bien fácil de entender y que sigue sin resolverse, en el que siguen trabajando investigadores de todo el mundo. ¡¡Y eso que son sólo 8 inofensivos puntos!! 

Fuente:

Cifras y teclas