Newsgroup: it.hobby.enigmi
Titolo: [NON SE] Un problema di probabilita'

 
 
Visto l'assoluto rifiuto della mandria dei solutori di marcare [SE] le
richieste relative alla medesima, prova ad implementare la soluzione
complementare...... 
 
 
Comunque, ho incontrato altrove questo quesito e' mi e' sembrato interessante.
 
==========
Ci sono dieci scatole numerate da 1 a 10 e dieci palline numerate da 1 a 10.
 
Le palline vengono distribuite a caso nelle dieci scatole, una per scatola.
 
Al concorrente viene assegnato un numero da 1 a 10 e puo' aprire 5 scatole per
trovare la pallina con quel numero, se la trova vince altrimente perde.
 
Fin qui nessun problema, la probabilita' di vincere e' 5/10 quindi 1/2, come
giocare a testa o croce...
 
 
Ma il gioco non e' questo, al gioco partecipano squadre di 10 concorrenti
numerati anche essi da 1 a 10, e, a turno ognuno entra nella stanza con le 10
scatole ne apre 5, rimette tutto a posto come era quando e' entrato ed esce
senza poter poi comunicare  con chi non ha ancora partecipato.  A turno tutti
eseguono e la squadra vince solo se tutti e 10 i concorrenti vincono (cioe'
trovano il proprio numero aprendo 5 scatole). 
 
Sembrerebbe che la probabilta' di vincere della squadra sia la stessa di fare
10 volte testa lanciando una moneta, cioe 1/1024, e giocando a caso e'
certamente cosi'.
 
Ma esiste una strategia che migliora questa probabilta'?
 
Beh. la risposta e' ovviamente si, ma quale e' questa strategia e quale la
probabilita' 
 
Ciao,
      Gorgo

 probabilita'
 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 
Direi che i componenti di una squadra possono mettersi d'accordo per aprire 
tutti le stesse scatole (ad esempio le scatole da 1 a 5). In questo modo la 
probabilità torna a essere 1/2 a prescindere dal numero di componenti di una 
squadra.
 
Ciao!
 
Giorgio
 

 
 
 
No, sarebbe cosi' se tutti dovessereo trovare lo stesso numero, ma ognuno deve
trovare il numero a lui assegnato (il primo il numero 1 fino al decimo il
numero 10)
 
Ciao,
      Gorgo
 

 numero 10)
 
Opss, mi sembrava un po' troppo facile... ;-)
 
Allora le cose sono un po' più complicate. Non ho una soluzione ma posso 
fare qualche considerazione.
 
Partiamo dal fatto che se i partecipanti fossero solo in due, 
massimizzerebbero la probabilità decidendo di aprire ognuno 5 scatole 
diverse. E' intuitivo che se il primo apre le prime 5 scatole e trova il suo 
numero (e solo in questo caso ha senso continuare a ragionare), il secondo 
massimizza la probabilità di successo se sceglie le altre 5 scatole; evita 
in tal modo di correre il rischio di aprire la scatola con il numero del 
primo che sicuramente non è vincente per il secondo. La cosa è intuitiva: se 
il secondo aprisse le stesse scatole del primo avrebbe 4 possibilità su 10 
di trovare la sua (sempre nell'ipotesi che il primo abbia avuto successo), 
mentre se aprisse le altre 5 scatole avrebbe 5 possibilità su 10. 
Naturalmente ci sono tutti gli altri casi intermedi (es. 4 scatole nuove e 1 
di quelle aperte dal primo, e così via).
 
Continuando con questa analisi di buon senso si può concludere che le 
probabilità sono massime se si decide di distribuire il meglio possibile le 
aperture in modo da minimizzare le "sovrapposizioni", cioè far sì di aprire 
il minor numero di volte possibile le scatole già aperte dagli altri.
 
Dal momento che i partecipanti sono 10 e ognuno apre 5 scatole, in totale 
verranno aperte 50 scatole. Distribuendo bene le cose, ogni scatola verrà 
aperta in totale 5 volte. Si può rappresentare la cosa con una specie di 
scacchiera. Ogni riga rappresenta le scatole aperte da ciascun partecipante, 
una riga per ogni partecipante.
 
Una possibile soluzione potrebbe essere questa:
 
OOOOO.....
.....OOOOO
OOO..OO...
..OOO...OO
OO...OOO..
...OO..OOO
.OO.OO..O.
O..O..OO.O
O.O.O.O.O.
.O.O.O.O.O
 
Tra tutte le matrici con queste caratteristiche (5 O per riga e 5 O per 
colonna), dobbiamo stabilire quante sono quelle che vincono. Per comodità 
possiamo pensare che le scatole contengano ognuna la pallina che ha proprio 
il numero corrispondente alla scatola stessa (naturalmente i partecipanti 
non lo devono sapere ;-) ). Se facciamo così, la scacchiera vincente è 
quella che ha le O nelle 10 caselle della diagonale alto sinistra, basso 
destra.
 
Ora le cose sono *facili*. Basta calcolare quante sono le scacchiere con la 
caratteristica della distribuzione equa. Quante sono tra queste quelle con 
le O sulla diagonale e fare il rapporto (inverso). Questo sarà il valore 
della probabilità di successo.
 
Per ora arrivo fin qui. Dimmi se la strada è buona.
 
Ciao!
 
Giorgio
 


Hmmmm. Di sicuro non e' la strada che conosco.
 
E ad essere sincero non credo neanche che possa aumentare le probabilita'. 
La tecnica da cui parti va bene solo se il numero di partecipanti e' minore
del numero delle scatole ma se i numeri sono uguali si ricade in un
equivalente di scegliere a caso.
 
Forse si vede meglio usando il procedimento inverso: distribuisci a caso i
numeri sulla scacchiera (uno per colonna) la probabilita' che ogni numero cada
in una colonna cha ha lo 0 al posto giusto e' 1/2  e quindi...
 
Quello che ti posso dire e' che la strategia che conosco:
 
1) non modifica la probabilita' del singolo concorrente di trovare il proprio
numero, e' sempre 1/2.
 
2) aumenta la probabilita' di vittoria della squadra da un po' peggio di
1/1000 a un po' meglio di 1/3 !
 
 
Ciao,
      Gorgo
 

 1/1000 a un po' meglio di 1/3 !
 
Nel semplice caso di 2 partecipanti e 2 scatole il mio metodo le cose le 
migliora. Giocando a caso, la probabilità finale è 1/4 mentre se ci si 
accorda di aprire scatole diverse sale a 1/2: o le palline sono messe 1 - 2 
o 2 - 1 e una volta su due si vince. Non ti so dire cosa succeda con 10 
scatole ma credo che il solo fatto di eliminare in modo deterministico (e 
non probabilistico) le soluzioni sicuramente perdenti (ad esempio, una o più 
scatole non vengono mai aperte da nessuno) dovrebbe migliorare la 
probabilità.
 
Certo, non credo si arrivi a superare 1/3 ! Sono molto curioso. Così, di 
primo acchito la cosa mi sembra un po' impossibile. Se assumiamo che il 
primo abbia 1/2 di indovinare (e qui non credo si possa applicare alcuna 
strategia migliorativa), mi viene solo in mente che il secondo possa 
scegliere le altre 5. In questo modo la sua probabilità (se il primo ha 
indovinato) è di 5 su 9 (eliminando dal conteggio quella indovinata dal 
primo). 1/2 * 5/9 fa 0.2(7) che è già meno di 1/3. Non credo che, 
proseguendo con gli altri, le cose possano migliorare...
 
Spero non ci siano trucchi, eh... ;-)
 
Ciao.
 
Giorgio
 


No, niente trucchi.
 
 
La strategia, molto semplice, e' questa:
 
 
spoiler se ancora non vuoi vederla
 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 
 
Ogni concorrente sceglie per prima la scatola col proprio numero, se contiene
il numero giusto vince, se no apre la scatola col numero che trova e cosi'
via.
 
Tutto qui, ma l'effetto e devastante. 
 
Quello che succede e' che si "raggruppano"  vincenti e perdenti andando a
cercare le "catene", nel senso che la scatola 1 contiene 5, la 5 il 3, la 3 il
2 ....... fino che si trova la scatola con l'1 , questa e' una catena. Se la
configurazione contiene come catena piu' lunga una di 5 il concorrente vince
ma vincono anche tutti gli altri, se la catena piu' lunga e' 6 o piu si perde
ma perdono almeno altri 5. 
 
Se partecipano 100 squadre (ognuna con una configurazione di numeri diversa a
caso) e quindi 1000 concorrenti ci saranno sempre 500 che vincono e 500 che
perdono ma i perdenti si raggruppano e cosi' i vincenti ed il numero di
squadre con 10 vincenti aumenta fino a circa il 35%.
 
Quello che ho trovato sorprendente e' proprio l'effetto di una soluzione cosi'
semplice....
 
G
 
 
Ciao,
      Gorgo
 

 via.
 
Molto interessante!
 
Ciao
 
Giorgio
 


Confermo il molto interessante: ho fatto delle simulazioni che
confermano il fenomeno perň non riesco a darmene una spiegazione
matematica. Qualcuno ne sa di piů?
 
M.
 
-- 
Per rispondermi via e-mail togli l'ovvio.

 sa di piů?
 
 
Pensavo che la spiegazione data insieme alla soluzione fosse abbastanza, cosa
c'e' che non torna o che non e' chiaro? 
 
Posso aggiungere che dalla simulazione che ho fatto anche io, delle 3628800
possibili configurazione di numeri nelle scatole ce ne sono:
 
362880  con una catena di 10
403200  con una catena di 9
453600  con una catena di 8
518400  con una catena di 7
604800 con una catena di 6
 
e finalmente 
1285920 con una catena di 5 o meno che sono le vincenti (il 35.4%)
 
Ciao,
      Gorgo
 

 c'e' che non torna o che non e' chiaro?
 
Ciao.
 
Non credo che Maurizio intendesse questo (Maurizio è uno di quelli MOLTO 
bravi, qui), ma forse invocava una qualche giustificazione matematica a tale 
comportamento.
 
Naturalmente io non ce l'ho, ma oltre ad avere fatto anch'io la mia brava 
simulazione al computer (che conferma ovviamente tutto), ho anche buttato 
giù una tabellina in Excel tanto per ragionare su qualcosa. Ho usato 4 sole 
scatole, quindi 4 giocatori e 2 tentativi. Ecco cosa succede:
 
    1    2    3    4    Totale    Media tentativi    <= 2
1234    1    1    1    1    4    1    OK
1243    1    1    2    2    6    1,5    OK
1324    1    2    2    1    6    1,5    OK
1432    1    2    1    2    6    1,5    OK
2134    2    2    1    1    6    1,5    OK
3214    2    1    2    1    6    1,5    OK
4231    2    1    1    2    6    1,5    OK
2143    2    2    2    2    8    2    OK
3412    2    2    2    2    8    2    OK
4321    2    2    2    2    8    2    OK
1342    1    3    3    3    10    2,5
1423    1    3    3    3    10    2,5
2314    3    3    3    1    10    2,5
2431    3    3    1    3    10    2,5
3124    3    3    3    1    10    2,5
3241    3    1    3    3    10    2,5
4132    3    3    1    3    10    2,5
4213    3    1    3    3    10    2,5
2341    4    4    4    4    16    4
2413    4    4    4    4    16    4
3142    4    4    4    4    16    4
3421    4    4    4    4    16    4
4123    4    4    4    4    16    4
4312    4    4    4    4    16    4
                    Media    2,5
 
L'ho ordinata per tentativi totali della squadra in ordine crescente. 
Innanzitutto viene confermato che la media delle scatole che verranno aperte 
globalmente sarà 2.5 (la semplice media tra 1 e 4), poi si vede che, 
applicando il metodo, si vince con una buona probabilità, 10 volte su 24 = 
41.(6)%, ben più del casuale 1/16. La cosa interessante è vedere in che modo 
si relazionano i tentativi dei vari partecipanti in merito ad ogni possibile 
disposizione delle palline nelle scatole.
 
Guardando le ultime 6 righe si vede che se uno impiega 4 tentativi, allora 
tutti impiegano 4 tentativi. Questo è abbastanza intuitivo (a posteriori 
;-) ), se i numeri sono tutti "sbagliati" per uno, allora lo sono per tutti. 
E' un po' quello che dicevi tu, Gorgo. E questo fa sì che un gran numero di 
tentativi si concentri in pochi casi. Poi, se è vero che ogni volta che una 
catena è lunga 4, allora per quella combinazione sono tutte lunghe 4, si può 
capire che se uno trova il proprio numero al primo tentativo, e un altro lo 
trova in 3 tentativi, per lo stesso motivo del caso precedente anche tutti i 
rimanenti partecipanti dovranno fare 3 tentativi.
 
Naturalmente il discorso andrebbe formalizzato in ben altro modo e 
generalizzato per N, ma già così credo si intuisca il perché del 
comportamento generale.
 
E' simpatico vedere che in questo caso particolare, con 4 scatole, se il 
primo che entra trova la sua pallina in esattamente 2 tentativi, può uscire 
avendo già la certezza di avere vinto!
 
Questo è il mio piccolo contributo.
 
Ciao!
 
Giorgio
 

 
 
e nel caso N=10 se trova il numero in 5, poiche' questo esclude la
possibilita' di catene di 6 o piu' facendone una configurazione vincente.
 
Se invece intendeva la spiegazione dei numeri di configurazioni vincenti e
perdenti si puo' vedere che le configurazioni con catene di:
 
(partiamo sempre da 1)
10   sono 9!          (il numero 1 deve essere nell'ultima)
9    sono 8!*10       (una pallina qualsiasi resta fuori dalla catena)
8    sono 7!*10*9      .....
7    sono 6!*10*9*8
6    sono 5!*10*9*8*7
 
e questo e' facilmente generalizzabile.
 
Ciao,
      Gorgo
 

 e questo e' facilmente generalizzabile.
 
Grazie a te e a Giorgio: ora tutto mi è più chiaro, anche se a livello
intuitivo la cosa continua a sembrare sorprendente. Bel problema.


"Maurizio Frigeni"  wrote in message 
news:1kgphbj.hjna1h1no6maqN%frigeni_ovvio@tiscali_ovvio.it...

E' la stessa mia sensazione. Credo che la chiave di tutto stia nel 
convincersi (ma non è intuitivo, per lo meno all'inizio) che una catena 
lunga K è lunga K per tutti i K punti di inizio di tale catena e quindi che 
non ci possono essere contemporaneamente, ad esempio, catene di 7, catene di 
4 ecc. con N=10 perché non esiste il concetto di "sottocatena", né il caso 
di catene che si intersechino tra loro. Una volta "digerito" questo, tutto 
il resto è banale! :-)
 
Ancora grazie a Gorgo per aver proposto un problema nuovo e interessante (ce 
n'era bisogno in questo NG... :-( )
 
Ciao!
 
Giorgio