Newsgroup: it.hobby.enigmi
Titolo: Pilota auto...matico

Alcuni ricercatori hanno messo a punto
un prototipo di automobile che si muove da sola
come con un vero guidatore senza un autista umano a bordo .
Per sperimentare la buona riuscita del progetto la
portano su un'isola che ha la particolarità
che ogni  incrocio è un trivio ;)
Al termine di una strada si puo' scegliere quindi di svoltare
o a destra o a sinistra.
Programmano così il computer di bordo in modo che
lasciata la strada privata svolti subito a sinistra
e poi alternativamente a destra e a sinistra ogni volta
a un nuovo incrocio.
Che possibilità hanno i ricercatori di rivedere finalmente
la loro auto svoltare verso la strada privata e tornare alla base?
NB L'accesso della strada privata dei ricercatori alla strada pubblica
è vista dall'auto come un incrocio a tre vie


Siamo in un caso realistico, con curve e incroci di strade non
perpendicolari, su un'area finita, oppure in un caso ideale, con
strade perpendicolari ed estensione infinita?
In questo secondo caso, direi che l'auto parta verso l'infinito.
Poniamo che la strada privata vada verso nord.
L'auto svolta a ovest.
Poi a nord
Poi a ovest
Poi a nord
Poi a ovest
eccetera.
Inidichiamo con



Ho preso a  pretesto l'isola  per dire
che il numero di incroci è finito.
Schematizzando hai un grafo finito con vertici
da cui si diramano sempre 3 archi.
Fa eccezione il nodo di partenza



[SPOILER}
.
.
.
.
.
Se il grafo è finito, diciamo formato da R rami, la probabilità che
l'auto ritorni alla base è 100%.
Considero il cammino dell'auto formato da *mosse* successive, ciascuna
mossa consiste nel percorrere un ramo da nodo a nodo.
Si possono ipotizzare due casi:
_A) L'auto rientra alla base dopo un numero finito di mosse.
_B) L'auto compie un numero infinito di mosse senza rientrare alla
base.
Provo a dimostrare l'impossibilità del caso B.
Sono possibili 4*R diverse mosse (R rami - Per ciascun ramo2 versi di
percorrenza - Per ciascun verso di percorrenza 2 possibili origini,
cioè l'auto è entrata nel ramo girando a destra o a sinistra).
Chiamo mosse *vergini* quelle che non sono mai state eseguite in
precedenza, e mosse *ripetute* quelle identiche ad almeno una delle
precedenti.
Ovviamente la prima mossa su strada pubblica deve essere vergine.
Essendo il numero di possibili mosse finito, non potranno esistere
infinite mosse vergini, ma dovranno esserci necessariamente delle
mosse ripetute.
Sia N una mossa ripetuta, cioè identica ad una precedente mossa K
(stesso ramo, stesso verso e stessa origine).
Ma se N è identica a K, allora N-1 sarà identica a K-1 (se l'origine
di N e K è una svolta a destra, quella di N-1 e K-1 è una svolta a
sinistra, e viceversa).
Quindi se N è ripetuta, allora è ripetuta anche N-1. E se N-1 è
ripetuta, allora è ripetuta anche N-2. E così via fino alla mossa 1,
che dovrebbe essere una mossa ripetuta, in contraddizione con quanto
affermato sopra.
Ciao
Paolo

 Paolo
Un fuoriclasse...

Dimostrazione molto elegante. Complimenti.

Scusate, temo di non avere capito ne' il testo, ne' la dimostrazione:
1) non mi torna il NB: "L'accesso della strada privata dei ricercatori 
alla strada pubblica è vista dall'auto come un incrocio a tre vie": 
quale delle opzioni è giusta:
a) la frase va corretta in "Entrambi gli accessi alla strada privata..."
b) la frase è giusta [cioè esiste una strada chiusa] e va corretta la 
frase "Al termine di una strada si puo' scegliere quindi di svoltare o a 
destra o a sinistra", visto che entrando nella via privata mi ritrovo a 
non avere possibilità di svolte.
2) La dimostrazione inizia con "se il grafo è finito": ma se non lo è 
(cosa possibilissima, anche se l'isola non è infinita)?
3)La dimostrazione si conclude con la frase " E così via fino alla mossa 
1, che dovrebbe essere una mossa ripetuta"; in realtà, si può procedere 
a ritroso solo fino a N(1), cioè alla prima mossa "non vergine", che 
corrisponde alla mossa 1; ciò prova che la mossa 1 viene successivamente 
ripetuta, e non che la mossa 1 è non vergine; tutto ciò nell'ipotesi che 
esista almeno una mossa non vergine. Ciò (se la strada privata è chiusa) 
sembra comunque portare ad un assurdo, ma ciò che si dimostra essere 
assurdo è l'esistenza di una strada non vergine, non la non verginità 
della strada 1 (invece, se la strada privata è non chiusa, il 
ragionamento mostra che la macchina torna al punto di partenza 
percorrendo la strada di partenza nel verso della prima mossa, e non 
mostra che i ricercatori vedono "tornare indietro" la macchina; si può 
anche costruire un controesempio in cui la macchina percorre la strada 1 
sempre nello stesso verso)

 sempre nello stesso verso)
Per l'appunto. Viene dimostrato che l'unico modo per ottenere strade
non vergini e' ripassare dal punto iniziale, con lo stesso verso di
percorrenza e la stessa direzione di uscita.
Ma se la strada e' chiusa, questa condizione non potra' verificarsi, e
quindi l'auto finira' per esaurire le possibili combinazioni strade-
verso di percorrenza-direzione di uscita, sinche' non interverra'
qualcosa a fermarla. Questo qualcosa e' il suo ritorno nella strada
iniziale in senso inverso.

 problema, chiarita  nel terzo messaggio del thread.
Scusa il bragozzi,
mi sfugge qualcosa evidentemente
date tutte queste 'puntualizzazioni'
sulla mia formulazione del problema.
Mi dici come si ottiene
un grafo infinito come modello
associato a quello delle vie,
su un'isola con una superficie finita
e con strade di superficie non infinitesima?


Infatti non e' possibile.
Ma che si tratti di un caso realistico, con superficie finita e strade
di superficie non infinitesima si chiarisce dal terzo messaggio in
poi.



Ok, va bene