Newsgroup: it.hobby.enigmi
Titolo: Chiavi Scrigni Principesse racchie e Sultani

La settimana scorsa ho salvato la vita della figlia di un ricco sultano
arabo. Quale omaggio alle eroiche gesta ha voluto ricompensarmi a modo suo:
Ha fatto mettere in un'urna 100 chiavi numerate da  1 a 100 che aprono
rispettivamente 100 scrigni (anch'essi numerati da 1 a 100). Poi estratte in
maniera casuale le ha messa una alla volta negli scrigni.
Chiarisco meglio questo punto. La chiave che viene estratta per prima viene
posta nel primo scrigno, la seconda estratta nel secondo, e cosě via... in
maniera tale che uno scrigno contenga la chiave che lo apre solo con
probabilitŕ 1/100.
In ciascuno scrigno ha fatto inserire anche un diamante. Poi ha ordinato che
gli scrigni venissero chiusi con altre chiavi (delle copie). Mi ha porto la
copia della chiave numero 1 ovvero quella che apre lo scrigno numero 1 e mi
augurato buona fortuna...
Ho aperto il primo scrigno ho preso il diamante e la chiave. Ho letto il
numero della chiave e mi sono avviato verso lo scrigno che veniva aperto da
quella chiave. E cosě via finché ho potuto.
Alla  fine di diamanti ne ho racimolati solo 5.
Sfortunato?
Quanti diamanti sarebbe stato in grado di accalappiarsi il mio  amico
MedioMan? MedioMan č tutto il contrario di un tipo particolare. Tutto quello
che fa lo fa nella media. E' alto 1.75, ha il cuore che gli batte a 72
battiti al minuto e se tira due dadi potete star certi che la loro somma č
7. Sinceramente mi sta un po' sulle palle...ma non glielo dite.
Luigi

7. Sinceramente mi sta un po' sulle palle...ma non glielo dite.
Da me non sapra' nulla :-)

 ricco sultano arabo...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Una risposta spannometrica a caldo.
La catena si arresta solo quando viene scovata la chiave
numero uno. MedioMan raccogliera' quindi una cinquantina
di diamanti, forse poco di piů visto che il primo e' garantito.
Ciao!!!  ((^__^))'
Livio

del problema in maniera adeguata: come e perche' la catena si blocca?
Faccio un esempio per chiarire il tutto. Scuserai la mia pigrizia se uso
soli 10 scrigni invece che 100...
supponiamo che negli scrigni dall'1 al 10 si trovano le seguenti chiavi
5 6 8 3 2 1 4 7  9 10
apro il lo scrigno numero 1 prendo il diamante e la chiave numero 5
apro il lo scrigno numero 5 prendo il diamante e la chiave numero 2
apro il lo scrigno numero 2 prendo il diamante e la chiave numero 6
apro il lo scrigno numero 6 prendo il diamante e la chiave numero 1
Ma qui mi fermo perché lo scrigno numero 1 è già stato aperto e trafugato
Come vedi anche se gli scrigni che contengono le chiavi che li aprono sono
solamente due (9 e 10) non si riesce ad ottenere 8 (10-2) diamanti. Bensì 4
Luigi

La catena si arresta quando si trova la chiave n. 1, ma non tutti gli
scrigni fanno parte del conto possibile; bisogna considerare la
possibilita` di catene *chiuse* del tipo:
scrigno      chiave
10            12      
12            14
14            10 
gli scrigni che fanno parte di catene chiuse non saranno mai aperti
(n-n e` in realta` una cat.chiusa di lunghezza 1).
Come si calcola la probabilita` del numero di scrigni contenuti in
tutte le possibili catene chiuse?
Altrimenti detto, bisogna trovare la lunghezza media della catena
chiusa in cui e` contenuta la chiave 1, la quale corrispondera` al
numero di scrigni che si aprono. Ma di come si fa questo calcolo, non
ne ho idea...
domanov

 di diamanti, forse poco di piů visto che il primo e' garantito.
OK, allora faccio una simulazione.
Il risultato mi conferma l'intuizione:
100.000 cicli sperimentali danno 50.3 diamanti per MediaMan.
Allego programma nel caso qualcuno voglia verificarlo.
Ciao!!!  ((^__^))'
Livio
----------------------------------------------------------------------------
---------
Dim Chiave(100) As Boolean          'le chiavi (false=gia' usata)
Dim Scrigno(100)                    'scrigno(chiave)
NumProve = 100000                    'numero dei cicli di prova
For Prova = 1 To NumProve           'loop per NumProve cicli
    For j = 1 To 100                'tutte le chiavi fuori
        Chiave(j) = True            'dagli scrigni = true
    Next j
    For j = 1 To 100                'per tutte le chiavi
        Do                          'estraggo a sorte una chiave
            NumChiave = Int(Rnd * 100 + 1)
        Loop Until Chiave(NumChiave)
        Chiave(NumChiave) = False   'chiave gia' usata
        Scrigno(j) = NumChiave      'metto la chiave nello scrigno
    Next j
    ProxScrigno = 1                 'chiave falsa per scrigno 1
    NumDiamanti = 0                 'numero diamanti ogni ciclo
    Do                              'sequenza apertura scrigni
        ProxScrigno = Scrigno(ProxScrigno)
        NumDiamanti = NumDiamanti + 1
    Loop Until ProxScrigno = 1
    Media = Media + NumDiamanti     'accumulo diamanti in Media
Next Prova
Print Media / NumProve       'calcolo e stampa media

 dice

Per quanto possa sembrare controintuitivo, la presenza di queste eventuali
"catene" non ha alcuna influenza sul numero medio di diamanti che potrai
trovare.
Il problema proposto da Luigi è abilmente arzigogolato ma potrebbe essere
riformulato così: Ci sono 100 scrigni e in ognuno c'è un diamante (e
nient'altro), apri il primo scrigno e prendi il diamante che c'è dentro;
appena recuperato il diamante (e solo allora) estrai da un'urna una chiave
numerata (senza
reintrodurla nell'urna stessa); se estrai la chiave numero 1 hai
terminato, altrimenti vai allo scrigno corrispondente, prendi il diamante e
procedi per la successiva estrazione della chiave e così via.
Dovrebbe essere evidente che le due formulazioni sono del tutto equivalenti:
il fatto di anticipare l'estrazione di tutte le chiavi prima dell'inizio del
gioco non comporta alcuna differenza, dal punto di vista del caso, rispetto
ad estrarre ogni chiave nel momento in cui serve. Invece di avere la chiave
già predisposta in ogni scrigno, ne prendi a caso una al momento: è
esattamente la stessa cosa.
Però in quest'ultimo modo non ci si distrae più con il pensiero delle
"catene", perché semplicemente non ci riguardano. La chiave numero 1
apparirà sempre PRIMA di un'eventuale catena, quindi, dal punto di vista del
gioco, tale catena non esiste.
A questo punto il problema si può riformulare in maniera ancora più
semplice: ci sono 100 scrigni con un diamante in ognuno, in uno a caso di
questi c'è anche una chiave contrassegnata dal numero 1. Comincia dal primo
scrigno e recupera il diamante al suo interno poi procedi in ordine con lo
scrigno successivo. Interrompi il gioco quando trovi la chiave. Anche in
questo caso la scelta avviene esattamente a caso come prima.
E' evidente che la probabilità di trovare la chiave nel primo scrigno è
uguale a quella di trovarla nell'ultimo o in uno qualunque degli altri. Se
la trovo subito vinco un diamante, se la trovo alla fine ne vinco 100,
mediamente ne vincerò (1+100)/2 = 50.5 .
... però sono sicuro che anche per MedioMan sarà un'impresa impossibile
riuscire a recuperare esattamente 50 diamanti e MEZZO!!! :-)
Ciao :-)
Giorgio

 Giorgio
Perdono, umilmente! ma non sono d'accordo.
Infatti ti ho dimostrato che le due formulazioni NON sono equivalenti,
e nella fattispecie dall'urna (nella seconda form.) NON dovresti poter
estrarre chiavi appartenenti ad una qualunque cat.chiusa, cosa che e`
impossibile nella prima formulazione.
Dunque non sono 100 le possibilita`, ma 100-(numero medio di chiavi
appartenenti a una qualsiasi catena chiusa).
Ti faccio questa domanda: su 100 chiavi e 100 scrigni numerati, date
due distribuzioni indipendenti, qual'e` la probabilita` che si abbiano
due numeri uguali? Il numero e` piccolo ma c'e` (e` un problema simile
a quello di due persone con lo stesso compleanno in una classe di
trenta persone, probablita` altissima). Prosegui poi per n=2,...,99 e
la somma di queste probabilita` e` il numero medio di chiavi che non
potrai mai estrarre dall'urna. Queste chiavi, nella tua urna, non ci
sono.
Resta il fatto che nella mia ignoranza abissale non so fare questi
calcoli...
Ciao
domanov

 due numeri uguali?
Non c'č dubbio che distribuendo a caso 100 numeri in 100 posizioni, troverai
dei numeri in corrispondenza delle loro posizioni e delle catene chiuse.
Perň questo fatto non ha nulla a che fare con il problema esposto da Luigi.
Ti propongo una situazione concreta, con solo 4 scrigni.
Questi sono i 24 (4!) possibili modi di disporre le chiavi numerate
all'interno dei 4 scrigni:
1234 1
1243 1
1324 1
1342 1
1423 1
1432 1
2134 2
2143 2
2314 3
2341 4
2413 4
2431 3
3124 3
3142 4
3214 2
3241 3
3412 2
3421 4
4123 4
4132 3
4213 3
4231 2
4312 4
4321 2
Di fianco alla disposizione c'č il numero che indica quanti diamanti
riuscirai a prendere partendo dallo scrigno in prima posizione. Come vedi ci
sono sei 1, sei 2, sei 3 e sei 4. Se fai la media di tutti questi valori
trovi esattamente 2.5, cioč (1+4)/2. Se provi a cercare le "catene" ne
troverai tantissime e di vari ordini (molte piů, percentualmente, di quante
ne troveresti con 100 scrigni); nonostante ciň la cosa funziona anche con
soli 4 scrigni, ma anche con 3, con 2, con 1 e con ogni n.
Ciao :-)
Giorgio