Cabanes i pous

Últimament l'Hotel infinit s'està convertint en un blog de petit format: hom podria atribuir-ho a la falta de motivació, a aquell inevitable període de la vida blogaire en què actualitzar resulta una càrrega; ara mateix, però, de ganes i esperit no me'n falten. És més: sempre ressorgeixen a la mateixa època, i sospito que la correlació amb els exàmens és notable. Sigui com sigui: hom hauria d'atribuir-ho a l'escassetat de temps de l'autor, i, ara sí, encertaria. Així doncs, mentre els exàmens segueixin ben visibles a l'horitzó la història seguirà invariable, i el director de l'hotel, en la seva croada personal contra la procrastinació, seguirà optant per les entrades en mode degustació.

Avui us porto un bonic -i clàssic- problema, apte per a tots els públics, que us farà dibuixar i gastar full rere full:

Tenim tres cabanes (simbolitzades per punts de color vermell) i tres pous (simbolitzats per punts de color blau). Els propietaris de les cabanes volen connectar amb camins cadascuna de les seves cabanes amb cadascun dels pous, amb la condició que dos camins diferents no es poden creuar (en total, doncs, hi ha d'haver 9 camins diferents).

És possible aconseguir-ho? En cas que sí, doneu un dibuix de la solució, i en cas que no demostreu-ho.

La solució en un parell o tres de dies. Com a pista inicial: proveu-ho amb llapis i paper i rendiu-vos a l'evidència.

--------

Actualització: solució del problema

La resposta és que és impossible, i la clau es troba en la famosa fórmula d'Euler de grafs planars. Suposem que tenim una figura que compleix les condicions del problema: aleshores s'ha de complir:

\[V+C=A+2\]

On $V$ és el nombre de vèrtexs, $C$ és el nombre de cares i $A$ és el nombre d'arestes. Si la figura que volem construir fos possible, aquesta tindria $V=6$ (tres cabanes i tres pous) i $A=9$ (de cada cabana en surten tres camins). De la fórmula en deduïm que $C$ hauria de ser $5$. Ara bé, notem que les cares que tindríem com a mínim haurien de ser quadrilàters (és a dir, polígons de quatre costats): de dos costats no podria ser, perquè ens trobaríem amb dos camins sortint de la mateixa casa i anant al mateix pou, i de tres tampoc perquè aleshores tindríem alguna casa connectada amb alguna altra casa, o algun pou connectat amb algun altre pou, cosa que no està permesa. Ara, comptant que cada línia formaria part de dos polígons alhora, tenim que hi hauria d'haver $\frac{5.4}{2}=10$ línies (5 cares, per quatre arestes com a mínim per polígon i dividit entre dos perquè cada aresta forma part de dues regions alhora). I això evidentment es contradiu amb el fet que tinguem $9$ arestes.