rompicapo forse irrisolvibile

Giochini matematici elementari ma non olimpici.
Rispondi
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

rompicapo forse irrisolvibile

Messaggio da piever » 20 feb 2006, 14:45

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?
"Sei la Barbara della situazione!" (Tap)

eNIgmIsta
Messaggi: 4
Iscritto il: 01 gen 1970, 01:00
Località: Tricase (Le)
Contatta:

Messaggio da eNIgmIsta » 20 feb 2006, 18:00

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

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

Avatar utente
mitchan88
Messaggi: 469
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da mitchan88 » 20 feb 2006, 22:12

C'è nelle schede olimpiche del Gobbino :D

E' una delle due configurazione impossibili, assieme a quella della stella a cinque punte! :mrgreen:
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]

Membro del fan club di Ippo_

MindFlyer

Messaggio da MindFlyer » 20 feb 2006, 23:44

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.

Avatar utente
desko
Messaggi: 267
Iscritto il: 17 ott 2005, 07:59
Località: Modena 44°37'19,40" N 10°56'09,44" E

Re: rompicapo forse irrisolvibile

Messaggio da desko » 21 feb 2006, 10:03

piever ha scritto:È 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?
"Caso è lo pseudonimo usato da Dio quando non vuole firmare col proprio nome"

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 21 feb 2006, 12:09

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."

Avatar utente
desko
Messaggi: 267
Iscritto il: 17 ott 2005, 07:59
Località: Modena 44°37'19,40" N 10°56'09,44" E

Messaggio da desko » 21 feb 2006, 14:58

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.
"Caso è lo pseudonimo usato da Dio quando non vuole firmare col proprio nome"

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 21 feb 2006, 17:03

desko ha scritto: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...]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
desko
Messaggi: 267
Iscritto il: 17 ott 2005, 07:59
Località: Modena 44°37'19,40" N 10°56'09,44" E

Messaggio da desko » 22 feb 2006, 09:36

Marco ha scritto:
desko ha scritto: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
"Caso è lo pseudonimo usato da Dio quando non vuole firmare col proprio nome"

DoctorGhost
Messaggi: 3
Iscritto il: 22 mag 2006, 18:12

Messaggio da DoctorGhost » 22 mag 2006, 18:15

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


Grazie.

Rispondi