Problema de los tres servicios

Se conoce como el problema de los tres servicios a un problema matemático clásico que consiste en proporcionar tres servicios: agua, electricidad y gas, a tres casas. Para ello hay que conectar cada uno de los servicios a cada casa con una línea que representa la cañería o los cables. Debemos dar todos los servicios a todas las casas sin que las líneas de conexión se crucen.

Problema de los tres servicios.

Historia

En un análisis sobre la historia del problema, realizado por Kullman, declara que la mayoría de las referencias al problema lo caracterizan de "muy antiguo".^[1] La publicación más temprana encontrada por Kullman es de Dudeney, y el problema es denominado "agua, gas, y electricidad". Aun así, Dudeney declara que el problema es "tan viejo como las montañas..., mucho más viejo que la luz eléctrica o incluso el servicio de gas".^[2] Dudeney También publicó el mismo rompecabezas anteriormente, en "The Strand Magazine" en 1913.^[3]

Solución

Solución al problema de los tres servicios, utilizando la superficie de un toroide.

El problema es imposible de resolver cuando es presentado en un plano; es decir, no hay ninguna manera de hacer las nueve conexiones sin que alguna de las líneas crucen otra.

Existen soluciones alternativas, realizadas en la superficie de un toroide (ver figura).

El problema puede ser formalizado matemáticamente analizando si el grafo bipartito completo K3,3 es un grafo plano. Kazimierz Kuratowski declaró en 1930 que K3,3 es no planar, por lo que se sigue que el problema no tiene solución.^[4]

Se puede probar la imposibilidad de encontrar una solución plana de K3,3 es con el Teorema de la curva de Jordan. Este problema también puede demostrarse como imposible de resolver utilizando la Característica de Euler.

Alternativas del juego con solución

Solución al problema de los tres servicios, si se permite usar el reverso de una hoja perforada.

Se puede plantear el mismo problema con algunas variantes para que tenga solución:

• Permitiendo un único cruce de líneas.
• Permitiendo pasar un servicio por dentro de una casa.
• Permitiendo usar el reverso de una hoja perforada. (ver gráfico)

Referencias

1. Kullman, David (1979), «The Utilities Problem», Mathematics Magazine 52 (5): 299-302..
2. Dudeney, Henry (1917), «Problem 251 – Water, Gas, and Electricity», Amusements in mathematics, Thomas Nelson.
3. Dudeney, Henry (1913), «Perplexities, with some easy puzzles for beginners», The Strand Magazine 46: 110..
4. Kuratowski, Kazimierz (1930), «Sur le problème des courbes gauches en topologie», Fund. Math. (en francés) 15: 271-283.

• Datos: Q32918
• Multimedia: Three utilities problem / Q32918