Newsgroup: it.hobby.enigmi
Titolo: Zig Zag

Una formica si trova al centro di un tavolino circolare, di
30 cm di raggio.
Sceglie a caso una direzione e cammina in linea retta per 1
cm, poi cambia direzione, sempre scegliendola a caso, e
percorre un altro cm in linea retta, e cosi' via.
La formica procede cioe' a zig zag, secondo una spezzata
composta da tratti lunghi 1 cm, e con direzioni scelte
sempre in modo casuale.
Ti propongo una scommessa alla pari: vinci se la formica
raggiungera' il bordo del tavolino in meno di 900 *passi*
(percorrendo cioe' meno di 900 cm).
Ti conviene?
ciao
paolo

Non so perche', ma mi viene in mente un marinaio ubriaco... 8-)
Massimo


 wrote:
: Una formica si trova al centro di un tavolino circolare, di
: 30 cm di raggio.
: Sceglie a caso una direzione e cammina in linea retta per 1
: cm, poi cambia direzione, sempre scegliendola a caso, e
: percorre un altro cm in linea retta, e cosi' via.
Con un angolo qualunque tra la prima e la seconda direzione?
.mau.

Con un angolo qualunque tra la prima e la seconda
direzione?
Esatto, un angolo scelto a caso nel range 0-2*Pi, rispetto
ad un qualsiasi riferimento.
Per semplicita' considero di volta in volta come riferimento
(angolo 0) la direzione del segmento immediatamente
precedente.
ciao
paolo


Credo che la probabilità di vittoria sia esattamente del 50%.
Il problema è quello classico della "random walk"  in cui lo spostamento
medio dopo n passi dovrebbe essere uguale a sqrt(n)*ds dove ds è lo
spostamento per ogni passo casuale.
Non sono sicuro che la formula sia esattamente questa (sono passati troppi
anni); mi sembra di ricordare che c'era anche un fattore moltiplicativo,
forse 1/4 o 1/pi.

spostamento per ogni passo casuale.
Anch'io ero partito da questo valore, in base ad alcune
considerazioni:
In primo luogo e' facile vedere che *mediamente* la formica
tende ad allontanarsi dal centro:
poniamo che ad un certo momento la formica si trovi nel
punto P, traccio una circonferenza con centro nel centro del
tavolino, passante per P, e due corde lunghe 1, passanti per
P; se la formica sceglie di muoversi esattamente lungo una
delle corde, la distanza dal centro rimane invariata, se
sceglie la direzione entro l'angolo <180 compreso tra le
corde si avvicina, in caso contrario si allontana; si vede
quindi che la probabilita' di allontanarsi dal centro e'
maggiore, quindi prima o poi dovrebbe raggiungere il bordo
del tavolo.
Per quanto riguarda lo spostamento medio, se O e' il centro
del tavolo, il caso piu' favorevole e' spostarsi secondo il
raggio OP, in verso centrifugo, il caso piu' sfavorevole e'
lo spostamento centripeto nel verso PO; considero che scelga
il caso intermedio e si sposti secondo la direzione
perpendicolare al raggio.
Se fa sempre questa scelta si muovera' secondo una specie di
spirale; dopo il primo passo 01 sara' a distanza 1 dal
centro, il secondo passo 12, perpendicolare a 01, la porta a
distanza sqrt(2), il terzo 23, perpendicolare a 02, a
distanza sqrt(3), e cosi' via; dopo k passi sara'
*mediamente* a distanza sqrt(k) dal centro, e quindi
dovrebbe raggiungere il bordo, distante R dal centro, con
R^2 passi.
Pero', una simulazione mi ha dato risultati diversi; per
alcuni mi pare di intuire una spiegazione, per altri no.
Provero' a illustrarli in un prossimo post.
ciao
paolo

 alcuni mi pare di intuire una spiegazione, per altri no.
Ho provato un metodo assolutamente brutale.
Se all'ennesimo passo la formica e' a distanza r dal centro, al
successivo la nuova distanza media e' data dalla *formuletta*:
integrale( (sqrt(1+2*r*cos(alfa)+r^2)) con alfa da 0 a pigreco)/pigreco.
Peccato sia un integrale un po' scomodo da trattare... comunque per i
primi passi mi da' valori diversi da quelli che ottieni tu.
Ho la forte impressione che sia risolvibile molto piu' facilmente con
metodi statistici... Voglio dire che in ogni caso la formica stara' nei
pressi del centro con uno scarto crescente al crescere dei passi
considerati... rimane il piccolo particolare che io non ne so nulla di
*metodi statistici*, quindi passo in attesa di qualche brillante
deduzione che certamente non manchera'!
Intanto approfitto per un saluto a tutti.
Ciao ciao
Claudio

integrale( (sqrt(1+2*r*cos(alfa)+r^2)) con alfa da 0 a
pigreco)/pigreco.
aaargh! :-((((
Ho usato anch'io un metodo brutale, ossia una simulazione al
computer, facendo marciare la formica a passi successivi con
angoli random.
Su 10000 prove ho ottenuto un numero di passi medio di
917.qualcosa, contro i 900 previsti.
Ho ripetuto la simulazione con tavoli di diversi raggi,
sempre 10000 prove per ciascun raggio, trovando:
raggio      n. medio
            di passi    passi/R^2
2             5.88       1.470
3            11.47       1.274
4            18.97       1.186
6            40.26       1.118
10          107.26       1.073
20          416.08       1.040
30          917.86       1.020
come vedi il numero di passi medio e' sempre *un po'*
maggiore del valore R^2 che avevo previsto, ma lo scarto
percentuale tende a diminuire al crescere del raggio; ho
l'impressione che, al tendere del raggio all'infinito, la
media tenda ad R^2, ma purtroppo i miei modesti strumenti di
programmazione (uso solo il basic) non mi permettono di
verificarlo con tempi di calcolo ragionevoli.
Quanto sopra farebbe pensare che nel caso in esame
(raggio=30cm) la scommessa proposta non sia conveniente, ma
attenzione: non si chiedeva il numero di passi medio, ma...
Al prossimo post daro' gli altri risultati che ho trovato.
ciao
paolo

verificarlo con tempi di calcolo ragionevoli.
Insomma mi pare di capire che avevo ragione io...
I tuoi risultati concordano al limite per R infinito con il mio perché in
tale condizioni lo spostamento medio campionario tende a coincidere con
quello teorico.
Infatti prendere R sempre più grande è equivalente a ridurre la lunghezza
del singolo passo: al limite ogni passo è di misura infinitesima e la
formica compie infiniti passi prima di arrivare al bordo; solo in tal caso
lo spostamento medio delle singole realizzazioni del processo stocastico
coincidono con la media teorica.
Quanto più il tavolo è piccolo tanto più la stima è distorta poiché il
singolo passo viene a pesare sempre di più sulla traiettoria finale (al
limite, se R=1 la formica raggiunge il bordo con probabilità 1 dopo il primo
passo).
Ciao
oOo
  °°

 917.qualcosa, contro i 900 previsti.
Metodo brutale per metodo brutale, il mio fido foglio Excel mi dice
che la scommessa è onestissima, in quanto dopo 900 passi la formica
dovrebbe *mediamente* raggiungere il bordo.
Come hai giustamente accennato in un precedente post, la formica
(sempre *mediamente*) andrà in direzione perpendicolare alla
congiungente il centro con la posizione attuale della formica,
formando un triangolo rettangolo con cateti = distanza attuale dal
centro ed 1 ed ipotenusa = futura distanza dal centro
quindi dopo il 2° passo la distanza sarà  Sqrt(1+1) = 1,414
3° passo = Sqrt(1,414^2+1) = 1,732
4° passo = Sqrt(1,732^2+1) = 2
e dopo 900 passi = Sqrt(29,983^2 + 1) = 30
Ciao
Gianni
P.S. Rileggendo bene il tuo post citato, ho visto che i risultati
trovati da me coincidono con i tuoi. Infatti le radici calcolate da
quella precedente +1 equivalgono alle radici dei passi.

 attenzione: non si chiedeva il numero di passi medio, ma...
Infatti! nella mia simulazione la formica ha raggiunto il bordo entro le
900 mosse, ben 60984 volte [praticamente il 60%].
Ho ottenuto un valore prossimo al 50% limitando i passi a circa 740.
Un fatto ragionevole, visto che fanno media anche i risultati che
superano di molto i 900 passi...
Piu' ci penso sopra e meno mi sento ottimista per trovare una soluzione
generale... ma magari e' solo la mia solita idiosincrasia per le
circonferenze...
Beh, va, ancora un saluto e forza Luna Rossa anche se non c'entra nulla.
Ciao ciao
Claudio

Claudio
ciao
paolo