Problema dels tres servicis

Archiu:3 utilities problem blank.svg

Problema dels tres servicis

Archiu:Problema tres servicios.png

Problema dels tres servicis.

Es coneix com el problema dels tres servicis a un problema matemàtic clàssic que consistix en proporcionar tres servicis: aigua, electricitat i gas, a tres cases. Per a això cal conectar cada u dels servicis a cada casa en una llínea que representa la encanyat o els cables. Devem donar tots els servicis a totes les cases sense que les llínees de conexió es creuen.

Història

En un anàlisis sobre l'història del problema, realisat per Kullman, declara que la majoria de les referències al problema ho caracterisen de "molt antic". La publicació més primerenca trobada per Kullman és de Dudeney, i el problema és denominat "aigua, gas, i electricitat". Aixina i tot, Dudeney declara que el problema és "tan vell com les montanyes..., molt més vell que la llum elèctrica o inclús el servici de gas". Dudeney També va publicar el mateix rompecabezas anteriorment, en "The Strand Magazine" en 1913.

Solució

Archiu:3 utilities problem torus.svg

Solució al problema dels tres servicis, utilisant la superfície d'un toroide.

El problema és impossible de resoldre quan és presentat en un pla; és dir, no hi ha cap manera de fer les nou conexions sense que alguna de les llínees creuen atra.

Existixen solucions alternatives, realisades en la superfície d'un toroide (vore figura).

El problema pot ser formalisat matemàticament analisant si el grafo bipartito complet K3,3 és un grafo pla. Kazimierz Kuratowski va declarar en 1930 que K3,3 és no planar, per lo que se seguix que el problema no té solució.

Es pot provar l'impossibilitat de trobar una solució plana de K3,3 és en el Teorema de la curva de Jordan. Este problema també pot demostrar-se com a impossible de resoldre utilisant la Característica de Euler.