Newsgroup: it.hobby.enigmi
Titolo: altre tre buste

Non ricordo se questa versione sia stata già trattata, da una ricerca su 
google sembra di no.
Avete tre buste chiuse; ciascuna contiene una somma; non avete nessuna 
informazione su come le somme siano state scelte, non conoscete nemmeno 
il range in cui le somme possono essere comprese.
Potete aprire le buste una alla volta. Dopo aperta una busta potete 
scegliere se incassare la somma, e il gioco finisce lì, oppura scartarla 
e passare alla busta successiva.
Qual è la migliore strategia per massimizzare il guadagno?
E se invece avete un numero N di buste? (con N>2)
(notare che per N=2 il problema somiglia ad uno piuttosto dibattuto)
Un'altra variante: sapete che le somme sono state scelte a caso in un 
range noto, 
p.es
. da 0 a 1.000.000 di Euro.
(Nota: per il momento ho solo una soluzione per il primo caso, quindi ci 
provo anch'io)
ciao
paolo 


Ciao Paolo!
Partiamo da questo primo caso, gli altri che proponi andranno studiati a 
parte...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Senza formalizzare troppo direi che la soluzione seguente non è male:
Apro la prima busta e la scarto, poi apro la seconda busta: se la somma è 
maggiore della prima la tengo, altrimenti apro la terza busta.
Analizzo i casi uno per uno. Chiamo le tre somme a (alta), b (bassa) e m 
(media). In maiuscolo quelle che incasso:
b M a
b A m
m b A
m A b
a b M
a m B
3 volte vinco la somma alta, 2 volte la media e 1 volta la bassa. Sempre 
meglio che andare a caso! :-)
Coincide con la tua soluzione?
Ciao
Giorgio

 Coincide con la tua soluzione?
esattamente
ciao
paolo 

E' parente del gioco della dote della figlia del sultano?
Dario

 E se invece avete un numero N di buste? (con N>2)
Estendendo la strategia indicata da Giorgio per N buste (scelgo la busta
la prima volta che la somma è maggiore a quella della busta precedente,
continuando eventualmente fino all'ultima busta), i casi favorevoli alla
scelta del premio massimo sono:
  N  buste      Scelta casuale      Metodo
  --------      --------------    ----------
     2                  1                 1
     3                  2                 3
     4                  6                10
     5                 24                41
    ...                ..                ..
     10           362.880           623.530
    ...                ..                ..
Si passa cioè da una prob. casuale (N-1)!   casi a
sommatoria per  k  da 1 a N-1  di  (N-1)!/k!
(mentre la somma più bassa verrà sempre scelta solo in 1 caso)
Ciao, Nino

 continuando eventualmente fino all'ultima busta),
Il tuo metodo sicuramente è migliore della scelta causale, resterebbe da 
verificare se è la strategia ottimale.
Tra l'altro non so se si possa definire rigorosamente cosa si intende 
per ottimale.
Per esempio, pensi che potrebbe esistere una strategia che per un certo 
N (abbastanza grande) dia una probabilità un po' minore della tua di 
trovare la somma massima, ma una probabilità molto maggiore di trovare 
una delle due buste migliori?
E in quel caso quale sarebbe la strategia migliore?
Avevo pensato ad un approcio diverso, di tipo statistico. Non sono 
granché esperto di statistica, quindi potrei dire qualche cavolata :-)
Per N molto grande, apro preventivamnte K buste che costituiscano un 
*campione rappresentativo* delle N.
Per le restanti N-K potrei prevedere (forse) la probabile distribuzione 
dei valori, rappresentabile con un istogramma. Dovrei stabilire per ogni 
valore X la probabilità p(X) che esista almeno una busta >X.
Stabilisco un valore di p che ritengo accettabile (quanto? 50% ? 90%? o 
che?) e vado avanti con l'apertura delle buste finché rtrovo un valore 
maggiore o uguale alla X corrispondente alla probabilità scelta.
Pensi che la cosa abbia senso e possa funzionare?
ciao
paolo 


Newsgroups: it.hobby.enigmi
Sent: Wednesday, February 16, 2005 11:39 AM
Subject: Re: altre tre buste
Sono totalmente a digiuno di teoria dei giochi, ma dissento dalla tua
soluzione. Questo perchè è ignoto il range dei premi. Supponi che nella
prima busta ci siano 10^7 euro :-), tu veramente la scarti in base al tuo
ragionamento? Secondo me prima di aprire la prima busta bisognerebbe crearsi
una (individuale) tabella di aspettative. Per me sono tanti 100mila euro
(esempio), mentre posso rinunciare a cuor leggero a 1000 euro. A questo
punto se nella prima busta c'è una cifra attorno ai mille applico la tua
strategia, ma se c'è una cifra che già mi soddisfa mi fermo subito!
Marco

 maggiore della prima la tengo, altrimenti apro la terza busta.
solo maggiore o anche uguale?

 prima busta ci siano 10^7 euro :-), tu veramente la scarti ...
Secondo me e' proprio il fatto che e' ignoto il range dei premi che rende 
(almeno apparentemente) insolubile il problema, nel senso che non vedo come 
si possa massimizzare una probabilita'.
Mi spiego meglio: il range, per quel che ne sappiamo puo' comunque essere 
scelto, in qualsivoglia modo, tra 0 ed infinito. Prendendo come esempio la 
tua ipotesi, mi sembra che vi siano 10^7-1 valori inferiori che renderebbero 
conveniente tenere il premio, contro un campo infinito di valori superiori, 
o ancor piu' esattamente: il valore 10^7 puo' essere il limite superiore di 
un range di premi, comunque limitato inferiormente, mentre puo' benissimo 
essere il limite inferiore di infiniti range. Ma questo accade qualunque 
quantita' finita di euro si consideri. Come ne usciamo?
ciao
fulvio 

 quantita' finita di euro si consideri. Come ne usciamo?
Io, come ho già detto, ne esco fissandomi su una aspettativa di
soddisfazione. Guadagnare 10^7  2*10^7 euro mi cambia veramente qualcosa?
Ingenuamente dico no, e mi fermo, perchè non mi interessa tentare di
aumentare il guadagno. Diverso il discorso se ho mille euro. Anche a fronte
del rischio di guadagnarne solo uno, vado avanti. Ma è tutto terribilmente
soggettivo.
Marco

 soddisfazione.
Beh... questo e' chiaro a livello pratico (parli con uno che se dovesse 
vincere una lotteria preferirebbe un paio di milioni di euro piuttosto che 
50 milioni che secondo me portano piu' pensieri che altro), io indendevo 
solo approfondire l' aspetto piu' puramente probabilistico...
ciao
fulvio 


Marco,
Questi problemi vengono solitamente proposti in una forma volutamente 
astratta e ipotetica e come tali solitamente vengono affrontati. 
Sinceramente non ho proprio considerato l'eventualità di una situazione 
reale. Però penso che nel caso da te prospettato mi comporterei proprio come 
te! :-)
Ciao
Giorgio 

"Ludico.Net"

Premesso che non credo che nelle intenzioni del problema ci fosse anche 
quella di considerare somme di ugual valore, il risultato finale comunque 
non cambia.
Nel caso di strettamente maggiore, il metodo ti fa comunque vincere la somma 
maggiore 2 volte su 3.
Nel caso del maggiore o uguale, vinci 1 volta su 3 se le somme uguali 
costituiscono il valore minore,
mentre vinci 3 volte su 3 se le somme uguali costituiscono il valore 
maggiore.
Se poi le somme sono tutte e tre uguali, direi che un metodo vale l'altro! 
:-)
Ciao
Giorgio


Penso di sì,  si potrebbe calcolare la dev. standard, e scegliere ad es.
per N>1000 quando il valore è > media + 3 sigma.
Ma potrei dire anch'io fesserie, lascio la parola a qualcuno meno
arrugginito di me.
Ciao, Nino 

 conveniente tenere il premio, contro un campo infinito di valori
superiori,
quindi converrebbe andare avanti perchè le
probabilità sono superiori da un punto di vista logico?

 continuando eventualmente fino all'ultima busta),
Di seguito riporto le prob. che si hanno con questo metodo
in funzione del numero di buste disponibili:
             prob. di scegliere la somma  1 = più bassa .... 10 = più alta
  N. buste    1     2     3     4     5     6     7     8     9     10
  --------  ----- ----- ----- ----- ----- ----- ----- ----- ----- -------
     3      0,167 0,333 0,500
     4      0,042 0,208 0,333 0,417
     5      0,008 0,133 0,225 0,292 0,342
     6      0,001 0,090 0,158 0,211 0,253 0,286
     7      2E-04 0,065 0,116 0,159 0,193 0,222 0,245
     8      2E-05 0,049 0,089 0,123 0,152 0,176 0,197 0,215
     9      3E-06 0,038 0,070 0,098 0,122 0,143 0,161 0,177 0,191
    10      3E-07 0,030 0,057 0,080 0,100 0,118 0,134 0,148 0,161 0,172
Supponendo la linearità della distribuzione delle somme contenute nelle 
buste,
è evidente che il metodo migliora la scelta del premio medio atteso dal 50%
casuale a circa i 2/3 del massimo.
A prescindere dal fatto che la distribuzione dei premi è ignota, e quindi 
non
si può stabilire una strategia ottimale valida sempre (può essere utile
l'approccio empirico), al crescere di N buste penso però si possa fare 
meglio
rispetto al metodo proposto sopra.
Un esito più vantaggioso si ha variando la busta da scegliere secondo la
sequenza di "valore contenuto in aumento" rilevabile da:
arrotonda.per.eccesso[ln(N)]
Ad es., con N=5 buste occorrerà scegliere la seconda busta in crescita,
        con N=100 la quinta e con N=10.000 il decimo aumento di seguito.
E' probabilmente ancora preferibile tener conto dei valori reali più alti
dopo il primo, indipendentemente dalla sequenza secondo cui si verificano
(anche se il valore elevato è isolato); cioè, al primo valore della prima
busta si assegna il numero 1, a quello tra le buste successive che lo supera
il numero 2, a quello che supera il secondo il n.3, ecc.
La scelta della busta definitiva dovrebbe essere:
per 100 buste il settimo aumento
per 10.000 buste il quattordicesimo aumento
per 1.000.000 buste il ventesimo aumento
(sperando di non andare fino in fondo, ad accontentarsi dell'ultima 
busta...)
Ovviamente, questo discorso necessiterebbe di conferma sperimentale.
Ciao, Nino
 

    10      3E-07 0,030 
0,057 0,080 0,100 0,118 0,134 0,148 0,161 0,172
Ho dei valori 
diversi
Il problema l'ho trovato, con un esposto completamente diverso, ma 
credo sostanzialmente equivalente a questo, nel testo "Matematica - Corso di 
sopravvivenza" di Ricardo Bersani e Ennio Peres.
Nel testo si parlava di una 
ragazza che deve scegiere tra diversi spasimanti, li esamina uno alla volta 
assegnando a ciascuno un *voto* secondo certi parametri, e dopo ogni esame 
decide se prendere o lasciare.
La strategia (riportata al nostro 
problema) sarebbe quella di aprire preventivamente un certo numero K di buste e 
scartarle. Poi procedere con le altre N-K e scegliere (mi è sembrato di capire) 
la prima che sia maggiore di tutte le K scartate.
Secondo gli autori, per i 
vari valori di N, il numero ottimale di scarti K e le probabilità P di beccare 
la busta migliore, 
sarebbero:
N          
K       
P%
4          
1       45.83
5          
2       
43.33
6          
2       
42.78
7          
2       
41.42
8          
3       
40.98
9          
3       
40.60
10         
3       
39.87
20         
7       
38.42
30        
11       
37.87
40        
15       
37.57
50        
19       
37.39
100       
37       
37.10
500      
184       36.85
1000     
368       36.81


 


Non spiegano come siano stati ottenuti 
questi valori.


Sei in grado di verificare ed eventualmente 
trovare la formula usata?


 


ciao


paolo


 


 



per 1.000.000 buste il ventesimo aumento
abbia minore prob. di beccare la busta migliore.
Ciao, Nino

>(anche se il valore elevato č isolato); cioč, al primo valore della prima


Non spiegano come siano stati ottenuti questi 
valori.


 


Ho controllato qualcuno dei valori di prob. 
di beccare


la busta migliore con il metodo che hai 
postato (a 
proposito,


per N ----> infinito  questa prob. 
-----> 1/e -----> 0,36788)


 


A mano, i calcoli sono lunghi e 
laboriosi.


Siano i valori nelle buste 1 - 2 - 3 - 4 - 
5 - ....


 


A) N=4      
 K=1


   Se V_k = 
1     p(4) = 2/6


   Se V_k = 
2     p(4) = 3/6


   Se V_k = 
3     p(4) = 6/6


   Se V_k = 
4     p(4) = 0


 P(tot 4) = (2/6 + 3/6 + 6/6) / 4 = 
0,4583


 


B) N=5       
K=2


   Se V_k = 1-5 ; 2-5 ; 3-5 ; 
4-5    p(5) = 0


   Se V_k = 1-4 ; 2-4 ; 
3-4          p(5) = 1


   Se V_k = 
1-2                      
p(5) = 2/6


   Se V_k = 1-3 ; 
2-3                
p(5) = 3/6


 P(tot 5) = (1 + 1 + 1 + 2/6 + 3/6 + 
3/6) / 10 = 0,4333


 


Ciao, Nino