Obbligo di svolta

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Obbligo di svolta

Messaggio da giobimbo »

Nella città di Olde Yorke, di cui sotto vediamo una piantina schematica, con le sue 10 piazze ma però priva delle strade che conducono alle altre città, vige un singolare regolamento stradale.

11…00…00…00…00…00
00…00…00…12…00…13
14…00…15…00…16…00
00…00…00…00…00…17
00…18…00…19…00…00
00…00…00…00…00…20
carta stradale di Olde Yorke. Le strade sono indicate dai numeri 00, le piazze con i numeri da 11 a 20.

I lunghi viali rettilinei invitano alla velocità per cui è vietato attraversare una piazza con un percorso diritto, quindi arrivati lì c’e un segnale di direzione consentita a destra e a sinistra. Inoltre per andare da una piazza all’altra bisogna percorrere due tratti di strada tra loro perpendicolari, rallentando ulteriormente la velocità di percorrenza.
Per esempio, se dotiamo la mappa di un sistema di riferimento cartesiano, non possiamo andare direttamente da 11 a 14, ma bisogna fare (1,6) (2,6) (2,5) (2,4) (2,3) (2,2) (1,2) (1,3) (1,4). Indichiamo tale viaggio con (11-18-14).
Non contento di ciò il sindaco ora vuole far mettere sensi unici e obblighi di svolta in modo che la città sia tutta percorribile senza incroci, eliminando così anche i semafori (+sicurezza -spese =rielezione sicura!).

Problema 1. Trovare un percorso che passi per tutte le vie rispettando le regole

Problema 2. Dimostrare che tale percorso circolare è unico

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Obbligo di svolta

Messaggio da Gianfranco »

Ciao giobimbo,
non sono sicuro di aver capito le regole, perciò posto un esempio di prova.
giobimbo_incroci.png
giobimbo_incroci.png (25.62 KiB) Visto 6356 volte
Per esempio, se vogliamo fare un percorso che passi per tutte le piazze (non tutte le vie), quello rosso segue le regole?
Pace e bene a tutti.
Gianfranco

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Obbligo di svolta

Messaggio da giobimbo »

Ricapitolo:
Regola 1. Non si può attraversare una piazza con un percorso diritto.
Regola 2. Per andare da una piazza all’altra bisogna percorrere 2 (due) tratti di strada tra loro perpendicolari.

Quindi, usando il tuo esempio, per il percorso 11-14 hai usato 4 tratti invece di 2: la Regola 2 lo proibisce, bisogna usare solo due tratti.
Lo stesso per 14-18 (3 tratti); 12-13 (4 tratti); 17-20 (4 tratti); 18-19 (4 tratti); 19-20 (3 tratti).
Giusto invece 12-15, 13-16, 16-17.
Per andare da 18 a 19 bisogna passare per 15, o per 17, o per 20.

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Obbligo di svolta

Messaggio da Gianfranco »

Grazie giobimbo, ho capito un po' di più ma ho ancora dei dubbi.
Problema 1. Trovare un percorso che passi per tutte le vie rispettando le regole
Significa che il percorso deve passare per tutte le vie della città o soltanto per quelle necessarie a fare il giro delle piazze?
il sindaco ora vuole far mettere sensi unici e obblighi di svolta in modo che la città sia tutta percorribile senza incroci, eliminando così anche i semafori
Non ho capito bene.
Significa che ad ogni incrocio bisogna svoltare o si possono percorrere due o più tratti in linea retta?
Pace e bene a tutti.
Gianfranco

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Obbligo di svolta

Messaggio da Gianfranco »

Questa soluzione segue le regole?
giobimbo_incroci2.png
giobimbo_incroci2.png (16.21 KiB) Visto 6315 volte
Pace e bene a tutti.
Gianfranco

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Obbligo di svolta

Messaggio da giobimbo »

Questa è la soluzione del Problema 1, giusto. Adesso manca solo la risposta al Problema 2, che è quella che più mi interessa, altrimenti avrei messo un numero maggiore di piazze :D

Sono anni che faccio dei cruciverba per un settimanale di annunci gratuiti, all’inizio usando carta e matita, poi, facendosi l’impegno sempre più gravoso ho comperato un programma che mi aiutasse. Tempo dopo ricevo una email dai programmatori del cruciverba in cui, oltre ai ringraziamenti per l’acquisto, mi davano un link per scaricare un programma con tanti rompicapo alfanumerici, tra cui questo. Pensavo di farlo pubblicare sul giornale con il titolo “La curva di Peano”, ma volevo saperne di più prima, non affidarmi ciecamente ad un software. Ho trovato una dimostrazione, ovvio, ma penso e spero ce ne sia un’altra più semplice.

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Obbligo di svolta

Messaggio da Gianfranco »

Non sono in grado di dimostrare con sicurezza che la soluzione è unica, ma posso spiegare come l'ho trovata, dopo aver capito le regole.

1. Osserviamo che il punto 3 si può colegare soltanto con 1 e 6. La scelta è obbligata.
giobimbo_incroci_d1.png
giobimbo_incroci_d1.png (13.06 KiB) Visto 6011 volte
2. Fatto questo, osserviamo che 1 si può collegare solo con 2. La scelta è obbligata.
giobimbo_incroci_d2.png
giobimbo_incroci_d2.png (13.41 KiB) Visto 6011 volte
3. Fatto questo, osserviamo che 2 si può collegare solo con 5. E 6 solo con 7.
Infatti escludiamo comunque di collegare 6 con 10 e con 9 perché si taglierebbe fuori il 7 (e comunque non sarebbe ammesso in base alle regole)
Dobbiamo escludere anche 2-7 perché si taglierebbe fuori il 6.
giobimbo_incroci_d3.png
giobimbo_incroci_d3.png (13.96 KiB) Visto 6011 volte
4. Fatto questo, osserviamo che il 4 si può collegare solo con l'8 però ci sono due possibilità.
A questo punto, basta un po' di backtracking dominabile con carta e matita, per arrivare alla soluzione.
Il backtracking permette di trovare una soluzione, se c'è, ma non dimostra che è l'unica.
Pace e bene a tutti.
Gianfranco

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Obbligo di svolta

Messaggio da giobimbo »

Gianfranco ha scritto:
ven feb 01, 2019 11:43 pm
Il backtracking permette di trovare una soluzione, se c'è, ma non dimostra che è l'unica.
Esattamente. Quindi la soluzione del Problema 2 è ancora incompleta. Una dimostrazione matematica non si affida solo al provare tutte le possibili strade tornando indietro e ricominciando se si vede che qualcosa non va, è logico. Come le combinazioni al gioco degli scacchi la dimostrazione parte da A per arrivare a B, con eventuali bivi, ma inesorabilmente arriva al traguardo. Spero che tu o qualche altro frequentatore ci arriviate.
Pensavo che applicando l’algoritmo ungherese, usato in Ricerca Operativa, si potessero trovare tutti i percorsi corretti, ma non ha funzionato, (o perlomeno, io) non sono riuscito a farlo funzionare…

Rispondi