Hace unas semanas, hablábamos del problema de las casas y los suministros en un toro, a propósito del libro Formas que se deforman, de Vicente Muñoz, que sorteamos para el 20 aniversario de Gaussianos. En ese artículo, Vicente nos daba la solución al problema que planteó para sortear su libro: 3 casas y 4 suministros en un toro. Hoy, ampliamos el problema y vemos hasta dónde se puede llegar.

Por poner en contexto el tema, el problema clásico de las 3 casas y los 3 suministros en un plano no tiene solución, como ya comentamos aquí. Ahora, si nos vamos a un toro, el problema equivalente sí que tiene solución. En el artículo que os enlazo en el primer párrafo, se daba una solución para el problema con un suministro más: 3 casas y 4 suministros en un toro. Os dejo también un post de Instagram que publiqué sobre el tema con dibujos de todos esos casos:

La cuestión que quedaba sin resolver era qué ocurría si seguíamos aumentando el número de suministros. ¿El problema tenía solución siempre o, por el contrario, llegaba un momento en el que dejaba de tenerla?

Para responder a estas cuestiones, contamos con la inestimable ayuda de Samuel Ranz, profesor de CUNEF Universidad y ganador del libro sorteado por Vicente. Samuel fue quien presentó la solución más completa, resolviendo el problema principal y dando respuesta al resto de casos.

Para que todo el mundo tenga clara la notación usada por Samuel, él ha tomado el toro como un cuadrado con los lados paralelos identificados y ha etiquetado las casas con los números 1, 2 y 3 y los suministros con letras. Para hacernos un poco con dicha notación, os dejo la solución de los casos de 3 y 4 suministros:

K33 en un toro
K43 en un toro

Vamos ahora con el caso siguiente, esto es, el que tiene 5 suministros. Aquí, Samuel nos muestra esta manera de unir las tres casas con esos 5 suministros:

K53 en un toro

Ahora, el siguiente caso, en el que se añade un sexto suministro. La solución propuesta por Samuel es la siguiente:

K63 en un toro

Y la cuestión es que ya no hay más imágenes, ya que no hay solución para el problema de las 3 casas y los n suministros en un toro si n es mayor que 6. En este caso, no tenemos imágenes, sino una demostración matemática que Vicente y Samuel nos han preparado. Os la dejo a continuación:

Teorema: En el toro, un grafo bipartito cumple que \( A \leq 2V \), donde \( A \) es el número de aristas y \( V \) es el número de vértices.

Demostración:

Sea un embebimiento de \( G=K_{n,3} \) en el toro \( T^2 \). Entonces:

  1. El embebimiento es celular (cada componente conexa del complementario \( T^2 \setminus G \) es homeomorfa a un disco abierto).

    Al considerar el complementario, nos quedan las caras; si alguna no fuera un disco, esta contendría una curva cerrada simple esencial que cortaría al toro; si tapamos el resultado con discos, tendríamos una esfera que seguiría conteniendo a \( G \), por lo que \( G\) sería plano. No obstante, sabemos que \( K_{n,3} \) no es plano, lo cual hace esto imposible. Por tanto, todas las caras son discos y se tiene que
    \[
    V – A + C = \chi(T^2) = 0.
    \]

  2. Toda cara tiene un ciclo de longitud al menos 4.

    Como \( G \) es conexo por vértices (esto es, \( G \) es conexo y, si eliminamos cualquier vértice, sigue siendo conexo), en un embebimiento celular cada cara tiene como borde un ciclo. Como el grafo es bipartito, no puede haber ciclos impares. Como es simple, no hay ciclos de longitud 2. Por tanto, cada ciclo tiene longitud al menos 4. Contando las incidencias entre aristas y caras, cada arista aparece dos veces, luego
    \[
    2A = \sum_a \deg(a) \geq 4A.
    \]

  3. Combinamos 1 y 2.

    De lo anterior, se deduce que \( 0 \leq V – \dfrac{A}{2} \), luego \( A\leq 2V \), como se quería probar.

Corolario: Si \( K_{n,3} \) admite un embebimiento en el toro, entonces \( n\leq 6 \).

Demostración:
Los vértices de un grafo bipartito \( K_{n,m} \) son \( n+m \), y las aristas, \( n\cdot m \). En el problema de Planito, se tiene \( m=3 \), por lo que los vértices son \( n+3 \) y las aristas son \( 3n \).

Por el Teorema de Planito, se tiene que \( A\leq 2V \), luego
\[
3n \leq 2(n+3),
\]

de donde se obtiene que \( n\leq 6 \).

Se deja como ejercicio para el lector darle a Planito la terrible noticia de que, cuando aparezca una séptima vivienda en su mundo, no se podrá conectar a los servicios sin cruces.

Podéis hacer cualquier consulta sobre la misma, y sobre cualquier otra cuestión relacionada con este problema, en los comentarios. Tanto Vicente como Samuel estarán encantados de ayudaros.

Por cierto, he dejado en Instagram una nueva publicación con todo lo que hemos hablado hoy. Aquí la tenéis:

Print Friendly, PDF & Email

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉


0 0 votes
Article Rating
Comparte: