rompicapo forse irrisolvibile
rompicapo forse irrisolvibile
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?
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?
"Sei la Barbara della situazione!" (Tap)
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.
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.
Re: rompicapo forse irrisolvibile
In parole povere (visto che le parole ricche sono già state usate) si può dire questo:piever ha scritto:È possibile dimostrare l'irrisolvibilità di questo rompicapo?
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?
"Caso è lo pseudonimo usato da Dio quando non vuole firmare col proprio nome"
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...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
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.
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.
"Caso è lo pseudonimo usato da Dio quando non vuole firmare col proprio nome"
Se lo fai nel modo banale, effettivamente, non ce la fai. Ma se lo fai in modo da sfruttare il toro...desko ha scritto:Ora connettere ciascuna casa ai due pozzi è banale.
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...]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Ecco dove sbagliavo: io andavo avanti il più possibile senza sfruttare il toro ed arrivavo ad incastrarmi.Marco ha scritto:Se lo fai nel modo banale, effettivamente, non ce la fai. Ma se lo fai in modo da sfruttare il toro...desko ha scritto:Ora connettere ciascuna casa ai due pozzi è banale.
Grazie
"Caso è lo pseudonimo usato da Dio quando non vuole firmare col proprio nome"
-
- Messaggi: 3
- Iscritto il: 22 mag 2006, 18:12