Newsgroup: it.hobby.enigmi
Titolo: [MAT] Ancora formiche su una stecca - revival

Nell'ormai lontano 2009 il grande Silvio Sergio pose un bel problema:
 
"Abbiamo una stecca lunga un metro disposta da Sud a Nord e 100 formiche che 
ci camminano sopra a velocita' costante di 1 cm/sec., in direzione S o N. 
Quando due formiche si scontrano immediatamente invertono la marcia e 
proseguono verso l'altro estremo. Se arrivano ad una delle due etremita' N o 
S cadono e buonanotte.
Sapresti piazzare le 100 formiche, in termini di posizione e orientamento 
iniziale, in modo da massimizzare il tempo di permanenza dell'ultima formica 
sulla stecca?"
 
vd. 
https://groups.google.com/forum/#!searchin/it.hobby.enigmi/formica/it.hobby.enigmi/OB5hPlfnaEk/hc1sIPZ5FwQJ
 
 
 
Vorrei adesso rilanciare con un bel problema correlato che ho trovato:
 
Immaginiamo di mettere sulla stessa stecca un numero dispari di formiche, diciamo 25, ognuna in maniera completamente casuale sia come posizione che come orientamento S o N.
Chiamiamo Alice la formica "centrale": qual'è la probabilità che Alice cada dal lato della stecca verso cui è orientata all'inizio?
 
Che dite?
Un saluto,
Gabriele

 Gabriele
 
Ciao Gabriele! :)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 
Allora, qualche premessa: le formiche che in un dato momento vanno nella 
stessa direzione di Alice non avranno alcuna influenza. Le uniche che 
contano sono quelle che vanno in direzione opposta (sempre rispetto alla 
direzione attuale di Alice). Anche in questo caso consideriamo che le 
formiche invece di rimbalzare si attraversano (tranne che nel caso di 
scontro con Alice).
 
Supponiamo che inizialmente Alice sia orientata verso N. Se da quel lato non 
ci sono formiche che vanno in senso contrario, Alice esce a N senza 
problemi. Se c'è una formica orientata in senso contrario, Alice si 
scontrerà e cambierà verso e anche la formica contro cui si è scontrata 
cambierà verso diventando quindi ininfluente per il futuro. A questo punto 
Alice uscirà a S se non incontrerà almeno una formica che va in direzione 
opposta. Se succede, il discorso si ripete con le eventuali rimanenti 
formiche in senso opposto ad Alice.
 
Questo dovrebbe convincerci che Alice uscirà a N se inizialmente il numero 
di formiche che vanno in senso contrario sul lato N (che vanno cioè da N a 
S) è minore o uguale a quelle che vanno in senso contrario nel lato S (che 
vanno cioè da S a N).
 
Il tutto quindi si riduce a calcolare la probabilità che, presi due numeri a 
caso tra un insieme di n numeri, il primo sia minore o uguale al secondo. 
Questi due numeri corrispondono al numero di formiche che inizialmente 
viaggiano in direzione contraria ad Alice rispettivamente sul lato N e sul 
lato S.
 
Per comodità definisco n come il numero dei possibili valori che possono 
assumere queste formiche "contrarie" su ciascun lato. Se t è il totale delle 
formiche (Gabriele propone 25), avremo 12 formiche per parte e i possibili 
valori di formiche in senso contrario andranno da 0 a 12, quindi 13 in 
tutto, per cui n = 13. In generale n = (t + 1) / 2.
 
Provo a vedere cosa succede per n = 3.
 
Se le formiche contrarie a N sono 0, Alice esce a N se le formiche contrarie 
a S sono 0, 1 o 2.
Se le formiche contrarie a N sono 1, Alice esce a N se le formiche contrarie 
a S sono 1 o 2.
Se le formiche contrarie a N sono 2, Alice esce a N se le formiche contrarie 
a S sono 2.
 
Si vede che il numero di casi favorevole è un classico numero triangolare 
(per n = 3 sono 6, per n = 4 sono 10 e così via; la formula è n * (n + 1) / 
2). Il numero di casi possibili è n * n;
 
Quindi la probabilità diventa n * (n + 1)  /  2  /  (n * n)
 
Nel caso di n = 1, cioè 0 formiche per parte, la probabilità è 1.
Nel caso di n = 2, cioè 1 formica per parte, la probabilità è 3/4.
Nel caso di n = 3, cioè 2 formiche per parte, la probabilità è 2/3.
.
Nel caso di n = 13, cioè 12 formiche per parte, la probabilità è 91/169.
 
Per n che tende a infinito, la probabilità diventa 1/2.
 
Grazie Gabriele, mi hai fatto ritornare ai vecchi tempi! :)
 
Ciao!
 
Giorgio
 
 
 

 Giorgio
 
Grazie a te, fa piacere sapere che si continua a monitorare il gruppo anche se è praticamente inattivo...
 
Un saluto,
Gabriele

 Ti torna?
 
Accidenti, è vero!
 
La mia soluzione andrebbe bene se il problema fosse posto in altri termini, 
ad esempio: si dispongono inizialmente tutte le formiche nella stessa 
direzione e poi se ne girano un numero a piacere sia a N che a S di Alice.
 
Diciamo che nel voler semplificare il discorso trascurando le formiche 
orientate "giuste" ho implicitamente concluso che le probabilità di averne 
in direzione contraria 0, 1, fino a n-1 fosse la stessa, cosa che 
giustamente mi hai fatto notare che non è, dati i termini iniziali del 
problema.
 
Quindi nel caso di n = 2:
1 volta su 4 Alice avrà 0 formiche in direzione contraria e quindi uscirà a 
N senz'altro
1 volta su 2 Alice avrà 1 formica in direzione contraria e quindi uscirà a N 
se a S c'è almeno una formica in direzione contraria (3 volte su 4)
1 volta su 4 Alice avrà 2 formiche in direzione contraria e quindi uscirà a 
N se a S ci sono due formiche in direzione contraria (1 volta su 4)
 
1 / 4 * 1 + 1 / 2 * 3 / 4 + 1 / 4 * 1 / 4 dà proprio 11/16
 
Adesso bisognerebbe trovare una formula generale che contempli tutto questo. 
Ci penso su.
 
Ciao!
 
Giorgio
 
 

 questo. Ci penso su.
 
Con Excel i risultati si trovano. Queste le probabilità di successo per un 
numero di formiche per parte da 0 a 12:
 
0    1
1    3/4
2    11/16
3    21/32
4    163/256
5    319/512
6    0,612792969
7    0,604736328
8    0,598190308
9    0,592735291
10    0,588098526
11    0,584094048
12    0,580590129
 
Da qui però ad arrivare a una formula semplice per me è dura, perché ci sono 
di mezzo combinazioni e sommatorie. Mi sa che mi fermo (sempre che fino a 
qui sia tutto giusto :) ).
 
Ciao.
 
Giorgio
 
 
 

 qui sia tutto giusto :) ).
 
A me torna, non capisco come hai fatto a tirare fuori i risultati senza formula ma mi tornano :-)
 
Secondo me questo ti può aiutare a semplificare il ragionamento: se Alice deve cadere a N, quante formiche devono esserci all'inizio, come minimo, che puntano verso N?
Siamo sicuri che ci interessa se sono sopra o sotto Alice?
 
:-))))

 Siamo sicuri che ci interessa se sono sopra o sotto Alice?
 
A mia parziale discolpa devo dire che non mi sono mai messo a ragionare su 
carta ma solo immaginando il tutto, mentre uno schemino (come il tuo) 
avrebbe aiutato parecchio, soprattutto nel convincersi che ogni S di sopra 
viene compensato da un N di sotto. Quindi alla fine si tratta solo di 
contare i casi in cui il numero di N è complessivamente maggiore o uguale al 
numero di S, ovvero il numero di N è maggiore o uguale a n / 2, dove n è il 
numero di formiche esclusa Alice.
 
Bello!
 
Ciao.
 
Giorgio
 
 
 


100 % !!!

Giorgio e Gabriele, che piacere ritrovarvi. 
Scrivo dal cellulare quindi non mi dilungo troppo in abbracci virtuali :)
Ma davvero non vi è venuto in mente di mettere sul motore di ricerca delle sequenze intere quei denominatori 1,3,11,42,163... Trovati da Giorgio?
 
Miiiiii, come siete invecchiati male :)
 
Come al solito, escono fuori dei parenti stretti dei numeri Catalani. 
Se stasera ho un po' di tempo cerco di trovare una delle mie giustificazioni a posteriori.
Intanto, un caloroso saluto,
Silv:o)

 Se stasera ho un po' di tempo cerco di trovare una delle mie giustificazioni a posteriori.
 
Provato qualcosa di ricorsivo, niente di interessante per ora.
 
Comunque quei numeri contano anche interessanti classi di poliomini convessi e fanno capolino anche negli alberi binari.
Ma c'era da aspettarselo vista la versatilità dei numeri DI CATALAN che spuntano fuori ovunque ci sia un problema che si risolve con un backtrack binario.
 
Ciao, Silv:o)

 Provato qualcosa di ricorsivo, niente di interessante per ora.
 
Grande Silvio.
 
In effetti avevo un po' lasciato morire il problema senza dare una soluzione "generale", dopo lo spoiler per chi fosse interessato...
.
.
.
.
.
.
.
S
.
.
.
.
.
.
.
P
.
.
.
.
.
.
.
O
.
.
.
.
.
.
.
I
.
.
.
.
.
.
.
L
.
.
.
.
.
.
.
E
.
.
.
.
.
.
.
R
.
.
.
.
.
.
.
 
Come detto da Giorgio:
 
"Quindi alla fine si tratta solo di 
contare i casi in cui il numero di N è complessivamente maggiore o uguale al 
numero di S, ovvero il numero di N è maggiore o uguale a n / 2, dove n è il 
numero di formiche esclusa Alice.
 
Quanto vale questo numero?
Possiamo scomporre il problema in due contributi:
 - quello per cui il numero di N è uguale a n/2, sia A
 - quello per cui il numero di N è maggiore di n/2, sia B
 
 
A non è difficile e vale: A=(n  n/2)
dove la parentesi dovrebbe essere "verticale" rappresentando una combinazione (si chiama "coefficiente binomiale"??)
 
B è poco poco più difficile ma basta pensare che, per simmetria, è uguale ad 1/2*(le combinazioni che rimangono da 2^n dopo averne tolte A), quindi:
B=1/2*(2^n-A)
 
In totale la probabilità vale quindi:
 
P=(A+B)/2^n=(A+1/2*(2^n-A))/2^n=(2^(n-1)+A/2)/2^n
 
dove, come abbiamo visto, A è dato dal coefficienti binomiale "n su n/2"
 
Spero di essermi spiegato, ovviamente la formula da esattamente i risultati dati da Giorgio qualche post più su
 
un saluto,
Gabriele

 Spero di essermi spiegato, ovviamente la formula da esattamente i risultati dati da Giorgio qualche post più su
 
Possiamo usare le righe pari del triangolo di Tartaglia.
 
Ogni termine rappresenta il numero di sequenze con 0, 1, 2, .. , n/2, .., n-1, n simboli N
 
B è il termine centrale, A è la somma fino al centrale escluso.
A+B è semplicemente la somma fino al centrale incluso.
 
per esempio:
 
1 6 15 20 15 6 1 
 
A=1+6+15, B=20
 
come dice Gabriele A si ottiene anche per differenza (64-20)/2
 
Ciao, Silv:o)