rompicapo forse irrisolvibile

[piever]

Un po' di tempo fa mi hanno fatto questo indovinello che ancora non ho risolto, né riesco a capire se sia risolvibile o no.

x x x

o o o

Lo scopo è unire ciascuna delle tre x con ciascuna delle tre o senza incrociare i fili.
E' possibile dimostrare l'irrisolvibilità di questo rompicapo?

[eNIgmIsta]

È dimostrato che in due dimensioni non è possibile questo problema... ma non mi chiedere come si fa...

edit: dovrebbe centrare Gauss e i ponti di koninsberg ma non ne sono sicuro...

[mitchan88]

C'è nelle schede olimpiche del Gobbino

E' una delle due configurazione impossibili, assieme a quella della stella a cinque punte!

[MindFlyer]

Gauss e i ponti di Konigsberg non c'entrano una cippa.
Di questo problema si è parlato moltissime volte nel forum, si dimostra semplicemente che il grafo richiesto non esiste nel piano, ma che ad esempio esiste sulla superficie di un toro.
Inoltre si dimostra che ogni grafo non planare contiene un sottografo isomorfo a quello richiesto, oppure al grafo completo di 5 nodi.

[desko]

È possibile dimostrare l'irrisolvibilità di questo rompicapo?

In parole povere (visto che le parole ricche sono già state usate) si può dire questo:
unisci due delle O ciscuna con le tre X senza incroci, non dovresti incontrare difficoltà; ora, qualunque configurazione tu abbia ottenuto se guardi bene vedrai che 4 dei 6 fili formano una linea chiusa che separa la terza X da una delle O (cioè, la O è dentro e la X è fuori o viceversa), rendendo quindi impossibile la connessione.
Se non sono stato chiaro dimmelo che cerco di postare un disegno.

Gauss e i ponti di Königsberg secondo me c'entrano nel senso che sono alle origini della teoria dei grafi.
Per il toro faccio veramente tanta fatica a capire come ci si possa riuscire, si riesce a darne un'idea?

[Marco]

Questo del toro è più facile di quanto non sembri: disegna un quadrato e considera che le linee che escono da un lato rientrano del lato opposto, nel punto corrispondente al punto d'uscita (nessuno di voi da piccolo ha giocato ad Asteroids o a Pac-Man, o sono l'unico ad essere abbastanza vecchio?). La superficie che ottieni è di fatto un toro. Metti a piacere case e pozzi e divertiti a disegnare i sentieri...

[desko]

Sì, sì, ho presente come giocare su un toro, ma continuo a non riuscire a sfruttarlo, rispetto al piano euclideo.
Diciamo che ho messo le tre case (A, B, c) allineate in orizzontale, poi ho messo il pozzo 1 sopra B ed il pozzo 2 sotto B, in modo da formare una sorta di croce greca.
Ora connettere ciascuna casa ai due pozzi è banale.
Ma ora dove posso mettere il pozzo 3 in modo che sia raggiungibile dalle tre case?
Il piano (così come il toro) risulta partizionato in tre regioni distinte (due quadrilateri e tutto il resto nel caso del piano o tre quadrilateri nel caso del toro) che hanno per vertici rispettivamente A1B2, B1C2, C1A2.
Ora, se metto il pozzo C all'interno di uno di essi (e devo farlo, visto che esauriscono il piano), risulta inaccessibile alla casa che non è vertice del quadrilatero.
Dove sbaglio? Sicuramente mi sfugge qualcosa di grosso relativamente al toro, ma anche "uscendo" dal foglio per "rientrare" dall'altra parte non vedo come posa aiutarmi.

[Marco]

Ora connettere ciascuna casa ai due pozzi è banale.

Se lo fai nel modo banale, effettivamente, non ce la fai. Ma se lo fai in modo da sfruttare il toro...

Soluzione in piccolo, se vuoi ancora provarci da solo:
Congiungi tutto nel modo banale, ma lascia aperto il cammino 1-C. Parti da 1. Esci dal mondo ad est e rientra girando a sud di 2. Ora sei di nuovo alla situazione tutte le case unite ai pozzi 1 e 2. Ora, basta che tu non metta il pozzo 3 nel quadrilatero 1A2B e il gioco viene.
La soluzione precedente divide il toro in due quadrilateri e un decagono. Una più simmetrica, che lo divide in tre esagoni è:
Case e pozzi allineati. Ogni casa ha a sud un pozzo. Congiungo ogni casa con il pozzo a sud con un segmento. Congiungo ogni casa con il pozzo a sud ovest di essa con un segmento (la casa ad ovest è congiunta con il pozzo a est attraversando il confine del mondo). Congiungo ogni casa con il pozzo di sud est di essa con un cammino che va verso nordest, esce al confine nord e colpisce il pozzo voluto (il cammino uscente dalla casa ad est deve uscire a nord, uscire ad est e raggiungere il pozzo ovest).

Per la cronaca, è possibile dimostrare che non ci sono altre scomposizioni possibili, oltre a 3 esagoni e 2 quadrilateri + decagono. [EDIT: Forse no.... 4 + 6 + 8... mmmh pensarci mentre vado a casa...]

[desko]

Ora connettere ciascuna casa ai due pozzi è banale.

Se lo fai nel modo banale, effettivamente, non ce la fai. Ma se lo fai in modo da sfruttare il toro...

Ecco dove sbagliavo: io andavo avanti il più possibile senza sfruttare il toro ed arrivavo ad incastrarmi.
Grazie

[DoctorGhost]

scusate la mia ignoranza ma nn ho proprio capito come è possibile risolvere questo enigma.... me lo potete spiegare meglio.... per piacere.


Grazie.