El problema de les tres cases amb problemes

L'altre dia, via "la wonder", vaig trobar-me amb què algú havia fet en flash un problema que feia anys que no veia. El problema és el següent: tenim 3 cases que volem connectar als subministradors de gas, de llum i d'aigua però sense que les connexions es creuïn. A alguns els sonarà de quan eren petits.

AVIS: a continuació s'explica la solució, així que si el vostre honor klingon us ho dicta, ressoleu-lo abans.

A primera vista, sembla un simple exercici de lògica, però després d'uns minuts provant-ho es pot veure que no es tant senzill. Després d'intentar enroscar tant com es pot les línies d'unió, la majoria de la gent desisteix. De fet, els que no desisteixen acaben morint de cansament, perquè el problema no té de solució.

A primer de carrera vaig estudiar que un núvol de punts amb arestes que els uneixen s'anomena graf. Quan graf es representable en un paper sense que cap aresta es creuï amb cap altre se'n diu que és un graf planar. El graf del problema s'anomena K3,3 perquè 3 vèrtex s'uneixen amb els altres 3 de totes les maneres possibles (cadascuna de les cases amb cadascun dels subministradors).


Segons el teorema de Kuratowski, qualsevol graf que contingui un subgraf k5 o k3,3 no pot ser planar (a grans trets). Així, si som capaços de refiar-nos d'algú que tingui un nom tant estrany, podríem dir que el problema no tindria solució a planilàndia però que, per sort, si que en te en un món tridimensional.

O sigui que ja sabeu, si de petits us varen proposar aquest problema, no ho dubteu, ho van fer perquè no molestéssiu.