Newsgroup: it.hobby.enigmi
Titolo: Conta: dove piazzarsi? [lungo]

Capita spesso, sopratutto tra i bambini, di dover effettuare una conta per 
dover scegliere una persona tra N. Un esempio tipico è la scelta del 
portiere in una partita a calcetto.
In generale le N persone si mettono in circolo e si decide la prima persona 
da contare ed un senso di percorrenza. Ogni "partecipante" getta, usando le 
dita di una sola mano, un numero tra 0 e 5, si sommano gli N contributi e si 
calcola la persona interessata.
Con N=2 una conta di questo genere equivale a giocare a pari e dispari e 
nessuno dei due partecipanti è, teoricamente, avvantaggiato.
Gia per N=3, però, non è immediata un'analisi precisa delle probabilità 
della conta. Chi ha più probabilità di capitare? (il primo, il secondo o 
l'utimo?) Chi ha meno probabilità di essere "beccato"?
Dopo l'enumerazione dei casi possibili si può vedere come le tre persone 
abbiano, in effetti, la stessa possibilità di capitare. L'analisi è più 
semplice considerando che, in questo caso, tirare 0 o 3 è identico, allo 
stesso modo sono analoghe le coppie 1-4 e 2-5.
Per N>3 che cosa succede? La conta continua ad essere equa per le N persone 
o subentrano delle asimmetrie?
Naturalmente non è difficile fare delle simulazioni o enumerare, per forza 
bruta, tutte le possibilità (anche se non ho fatto ancora nessuna delle due 
cose) ma ero interessato a sapere se esistono anche soluzioni più "logiche".
Avete qualche considerazione da fare?
Proporrei, per convenzione, che tutte e 6 le combinazioni tirate da ogni 
giocatore siano perfettamente equiprobabili. Questo esclude sia 
considerazioni per cui lo 0 è meno probabile, che complicherebbero solo i 
calcoli, sia considerazioni matematiche per N=4 e 5 che semplificherebbero i 
calcoli ma renderebbero meno "reale" il tutto.
Fatemi sapere,
ciao,
Gabriele 

 "logiche".
Visto che ero al computer mi sono fatto un po' di simulazioni per N compreso 
tra 4 e 10, i risultati sono molto interessanti ma, almeno per ora, non 
vorrei pubblicarli per non indirizzare troppo le vostre ricerche :-)
Ciao,
Gabriele 

 
Così a naso direi che al crescere di N, data l'equiprobabilità, il 
valore più atteso per il risultato della conta sia 2,5*N (per N 
sufficientemente grande, in altre parole). In tal caso si andrebbero a 
fare due giri e mezzo di conta; ergo, al crescere di N, il giocatore che 
ha più probabilità di essere estratto è quello che sta di fronte a 
quello da cui si inizia...
-- 
Fabrizio "Hermooz" Ermini

"Hermooz" ...

Considerazione che credo giustissima (discende direttamente dalla legge dei
grandi numeri), appena ho tempo  faccio una simulazione con N grande e vedo
che succede...ora sarebbe interessante determinare con quale legge al
variare di N si raggiunga il valore asintotico.
Problema interessante, complimenti  a Gabriele
Ciao

 variare di N si raggiunga il valore asintotico.
Per N grande si può applicare il teorema centrale del limite, per cui la
distribuzione della somma tende ad una gaussiana con varianza pari a s/N
(dove s è la varianza della distribuzione di partenza, che dovrebbe essere
10). Questo ci dice che anche la distribuzione dei resti modulo N (che
schematizza la conta) non è uniforme e quindi per N grande c'è sempre un
giocatore svantaggiato. In questo momento vado di fretta e non ho il tempo
di formalizzare esattamente il concetto, lascio a voi le conclusioni...
Ciao

 nessuno dei due partecipanti è, teoricamente, avvantaggiato.
conosco almeno 4 studenti di informatica di perugia che non sarebbero 
d'accordo... hanno passato un pomeriggio intero a discutere per poi 
giungere a una dimostrazione "per induzione" del fatto che è meglio dire 
pari e giocare dispari...
:-P
pazqo
ps: Gabriele, riesci a mandarmi una mail all'indirizzo privato?

 Naturalmente non è difficile fare delle simulazioni ...
Ho fatto delle prove (rigorosamente a mano) ottenendo risultati che
mi hanno meravigliato per la sostanziale uniformità della probabilità
di essere estratti per le N persone.
In particolare per N=2,3 e 6 non ho riscontrato preferenze;
per N=4 è leggermente svantaggiato il primo e avvantaggiato il terzo;
per N=5 è invece un po' avvantaggiato il primo.
I valori che ho ottenuto (ho verificato solo N=2; N=3 e N=4, per N=5 o 6
potrebbero facilmente esserci errori) sono stati ricavati a mano mediante
un triangolo di Tartaglia modificato.
N=2   Casi=6^2=36  Valore medio=18
                             Punteggi      possibili
                        -------------------------------------
                       primo giocatore           secondo gioc.
Punteggio favorevole  0  2  4  6  8  10          1  3  5  7  9
  Casi                1  3  5  5  3  1           2  4  6  4  2
Complessivamente 18 ciascuno
N=3   Casi=6^3=216   Valore medio=72
                             Punteggi      possibili
                  -----------------------------------------------------
                   primo giocatore      secondo gioc.    terzo gioc.
Punteggio favor.  0  3  6  9  12 15    1  4  7  10 13   2  5  8  11 14
  Casi            1 10  25 25 10  1    3 15 27  21  6   6 21  27 15  3
Complessivamente 72 ciascuno
N=4  Casi=6^4=1296   Valore medio=324
Primo gioc.   = 1+35+125+125+35+1 = 322  casi favorevoli
Secondo gioc. = 4+56+140+104+20 = 324           "
Terzo gioc.   = 10+80+146+80+10 = 326           "
Quarto gioc.  = 20+104+140+56+4 = 324           "
N=5  Casi=6^5=7776   Valore medio=1555,2
Primo gioc.   = 1+126+651+651+126+1 = 1556  casi favorevoli
Secondo gioc. = 5+205+735+540+70 = 1555            "
Terzo gioc.   = 15+305+780+420+35 = 1555           "
Quarto gioc.  = 35+420+780+305+15 = 1555           "
Quinto gioc.  = 70+540+735+205+5 = 1555            "
N=6  Casi=6^6=46656   Valore medio=7776
Primo gioc.   = 1+456+3431+3431+456+1 = 7776  casi favorevoli
Secondo gioc. = 6+756+3906+2856+252 = 7776            "
Terzo gioc.   = 21+1161+4221+2247+126 = 7776          "
Quarto gioc.  = 56+1666+4332+1666+56 = 7776           "
Quinto gioc.  = 126+2247+4221+1161+21 = 7776          "
Sesto gioc.   = 252+2856+3906+756+6 = 7776            "
Commenti, approcci diversi o simulazioni?
Ciao, Nino

 "logiche".
Come hanno già fatto notare, la distribuzione della somma della conta tende
alla gaussiana. La distribuzione della somma MODULO N tutto sommato deve 
seguirre lo stesso andamento.
Intanto, è simmetrica, nel senso che il primo giocatore HA SEMPRE LE STESSE
probabilità di vincere dell'ultimo, il secondo del penultimo e così via.
Questo è logico: per ogni combinazione di dita che fa vincere il terzo, la
combinazione complementare ottenuta contando le dita nascoste fa vincere il
terzultimo!
La funzione ricorsiva che conta quante volte la somma (modulo N) di m "mani"
da k è semplice:
          ( 1  se m=0 e k=0
F(k, m) = { 0  se m=0 e k>0
          ( sum(i=0..5){F(k-i, m-1)}
(ovviamente 0<=k,m<=N e la (k-i) è calcolato modulo N)
la spiegazione è semplice.
se non ci sono mani da contare (m=0), la somma si può fare in un modo solo,
e dà zero (vince di sicuro il giocatore che "fa" la conta)
se ci sono m mani da contare, allora k vince tutte le volte che:
la prima mano non mostra nessun dito e le mani successive hanno somma k;
la prima mano mostra un dito e le mani successive danno somma k-1;
..
la prima mano mostra cinque dita e le mani successive danno somma k-5;
Implementate la funzione in un linguaggio qualchesia è semplice, basta una
if è un for, anche se vi sconsiglio di usarla così com'è.
Sarebbe autolesionistico andarsi a calcolare ogni volta somme già calcolate
e si potrebbe usare anche la simmetria evidenziata prima.
Per esempio, si può usare excel, che è ottimo per questo tipo di ricorsione:
per il caso N=10
1) selezioniamo un rettangolo 11X10 (F1:O11) e coloriamo lo sfondo per non
confonderci
2) selezioniamo col mouse le ultime 5 colonne del rettangolo (K1:O11) e
copiamole col Ctrl-C
3) clic col tasto destro su A1, Incolla speciale -> incolla collegamento
(serve per "chiudere" a cilindro la regione colorata)
2) nella cella F2 scriviamo la formula "=SOMMA(A1:F1)" e copiamo la cella in
tutta la regione F2:O11
3) scriviamo "1" nella cella F1 e .. ta-dah!
la riga m-esima rappresenta la distribuzione della conta fatta da 10 persone
di cui solo m "tirano"
-- 
Ciao, Silv:o)

 la spiegazione è semplice.
Ciao, Silvio, bentornato!
Sarà semplice, ma io non ho capito completamente la procedura alla base del
tuo ragionamento; però sono contento che la tua soluzione, applicata a
N=4 , N=5 e N=6 conferma i risultati che, in modo molto più rozzo, avevo
ottenuto e postato precedentemente.
Come hai detto, la distribuzione è simmetrica, ma solo dopo aver tolto il
primo giocatore (quello a cui toccano le somme 0, N, 2N, 3N, 4N e 5N);
cioè, il secondo giocatore ha le stesse probabilità di vincere dell'ultimo,
il terzo del penultimo, ecc..
Effettivamente, all'aumentare di N, le probabilità aumentano gradualmente
(anche se di poco), andando dal primo giocatore (il più svantaggiato) a
quello (quelli se N = dispari) di mezzo.
Ciao, Nino 

 di formalizzare esattamente il concetto, lascio a voi le conclusioni...
Allora...
La convergenza sulla somma dovrebbe essere evidente gia per N=10, ma in
questo modo, dovendo considerare i resti modulo N, la distribuzione
associata alla  conta è ancora abbastanza uniforme. Infatti in questo modo
vengono a sommarsi  code della gaussiana abbastanza "pesanti" che tendono ad
equilibrare le probabilità. Per N=20 invece le cose dovrebbero filare
abbastanza bene, avendo dimezzato la varianza e raddoppiato il numero di
partecipanti.Il favorito (o sfavorito, dipende dai  casi) è proprio quello
che sta al centro.
Più tardi butto giù due linee di Matlab e faccio qualche simulazione,  vi
farò sapere.
Ciao


Per N=20   -----------> 1,82808E+14 +- 10,245%
Giocatori (1....20)  :
    1        2-20       3-19       4-18       5-17       6-16       7-15
 -------    -------    -------    -------    ------     -------    -------
  1,6408    1,64996    1,67656    1,71799    1,7702     1,82807    1,88595
   8-14      9-13       10-12       11
 -------    -------    -------    -------
 1,93816    1,9796     2,0062     2,01537
tutti xE+14
(Il giocatore 1 è quello a cui corrispondono le somme 0-20-40-60-80-100)
Ciao 

 Primo gioc.   = 1+126+651+651+126+1 = 1556  casi favorevoli
Ciao Nino,
esiste una formula che permetta di calcolare direttamente il numero di
combinazioni (tra tutte le k^N) con somma S, oppure è tutto empirico?
Intendo dire, per calcolare il 126 quale numero di combinazioni con somma 5,
oppure 651 con somma 10 e 15, come hai fatto?
Ciao,
Francesco

 primo giocatore (quello a cui toccano le somme 0, N, 2N, 3N, 4N e 5N);
Infatti quello che "fa la conta",  il giocatore 0, è il più
sfortunato. La simmetria degli altri deriva dalla considerazione che ho
fatto, ovvero che ogni giocata ha la sua complementare. Con 10
giocatori la giocata di somma 43 fa vincere il giocatore 3, la giocata
complementare 67 fa vincere il giocatore 7 complementare di 3. Lo 0 non
ha complementari: se vince il giocatore 0 e tutti invertono le dita
rivince di nuovo 0.
-- 
Ciao, Silv:o)

Silvio Sergio wrote....
Ehiiii ! Grande Silvio.
Ben tornato.

 rivince di nuovo 0.
Però, la sua somma favorevole è data da addendi simmetrici:
1 + X + Y + Y + X + 1
Simmetria che (a parte gli estremi, che non valgono 1) si verifica anche
per il giocatore centrale (quello più avvantaggiato), nel caso che
il numero di partecipanti N sia pari.
Ciao, Nino


Come ho detto a Silvio (che ha indicato un procedimento molto più elegante
per trovare direttamente le somme di tutti i casi favorevoli ai vari
giocatori), io ho determinato singolarmente gli addendi da sommare in modo
semi-empirico, valutandoli dal triangolo di Tartaglia, opportunamente
modificato per eliminare i casi impossibili (quelli che comportano 
l'utilizzo
di un numero di "dita" superiore a 5)
  N=2  1
N=3  1   1
   1   2   1
 1   3   3   1
       6   4   1
         10  5   1
           15 _6_  1
             _21 5   1
                25 4   1
In pratica, occorre esaminare le cifre in un canale obliquo;
controllare la simmetria (per N=2 le somme sono 5*2+1 e dopo il 6 si
riprende a scendere con il 5, ecc. ecc..);
inoltre, dopo le prime sei cifre, è necessario apportare una correzione,
sottraendo le cifre (partendo dalla prima) del canale precedente, con N
immediatamente inferiore; cioè, se si esamina il canale N=3, dopo il 21
non viene 21+5=26 , ma 21+5-1 dove l'1 è la prima cifra del canale N=2;
analogamente, la cifra successiva sarà 25+4-2 , ecc. ecc..
Capisco che è un metodo rozzo e macchinoso, ma se N è piccolo (minore
di 10) non è eccessivamente laborioso.
Ciao, Nino
 

 (Il giocatore 1 è quello a cui corrispondono le somme 0-20-40-60-80-100)
solo una curiosità, Nino.
nel contare gli oggetti è naturale etichettarli con la sequenza 1,2,.., ma 
in casi come questo perché non etichettare il giocatore "a cui corrispondono 
le somme 0-20-40-60-80-100" con 0, che è il rappresentante della classe 
resto di pertinenza, invece che con 1?
-- 
Ciao, Silv:o)

"Silvio Sergio" ha scritto nel messaggio

Hai perfettamente ragione.
Non sono abituato ad utilizzare lo zero.
(Mi sembra, quasi, di offendere uno, se gli dico:"Tu sei zero" ;-))
Ciao, Nino 

 equilibrare le probabilità.
Ed in effetti le probabilità fino N=10 sono abbastanza uniformi, anche 
tramite una simulazione non si riescono a notare apprezzabili differenze tra 
i vari "partecipanti al gioco".
Una simulazione con 100000 prove mi genera le seguenti probabilità:
 0.1011  0.0992    0.1000    0.1001    0.1004    0.0999    0.1005    0.1002 
0.0989   0.0998


 che sta al centro.
Ed in effetti una simulazione per N=20 da risultati apprezzabili ed in linea 
con le probabilità calcolate tramite il metodo di Silvio (bentornato!!):
0.0449    0.0455    0.0470    0.0465    0.0477    0.0494    0.0514    0.0541 
0.0549    0.0540    0.0551    0.0561    0.0540    0.0532    0.0521    0.0490 
0.0479    0.0464    0.0457    0.0452
Le assimetrie tra giocatore 0 ed il giocatore posto in posizione centrale si 
manifestano nettamente per N=100. Il primo ha una probabilità di capitare 
dello 0.6% mentre i giocatori posti verso il centro hanno una probabilità 
del 2.35% (probabilità calcolate tramite simulazione di 1000000 conte).
Non sarebbe interessante scoprire che, per N->oo, le probabilità del 
giocatore centrale si assestano sul  e% (2.71%)?? Probabilmente non sarà 
cosi ma qualche calcolo per N maggiori mi interesserebbe...
Complimenti a Silvio, Nino e Pronti Lee per le interessantissimi analisi 
postate.
Ciao a tutti,
Gabriele 

 giocatore centrale si assestano sul  e% (2.71%)??
Ok, penso proprio di aver detto una bella cavolata. Per N->oo le probabilità 
dei singoli giocatori dovrebbero tendere a 0. Giusto?
Gabriele 

"Gabriele "GaS" Carelli"...

Si. La varianza della distribuzione è 10/N che al limite N->oo tende a 0 (la
distribuizone tende ad essere un impulso centrato in 2,5*N). Quindi, per
N->oo , il igocatore centrale è "praticamente certo" di essere sorteggiato
(logicamente in termini probabilistici).
Ciao