Cari amici, il seguente problema postato da Dario Uri su Facebook mi ha incuriosito. Forse abbiamo già parlato di qualcosa di simile ma non abbiamo concluso.
----------------
3 dischi numerati da 1 a 8 tengono chiusa una cassaforte.
Per trovare la giusta combinazione occorrerebbe testare 8^3= 512 posizioni, ma la serratura è difettosa ed è sufficiente indovinare 2 numeri su 3 per poterla aprire.
Qual è il minor numero di tentativi (di tre cifre) che occorre mettere in atto per assicurarne l’apertura?
----------------
E' possibile scrivere un programmino che generi automaticamente tutte le terne da provare?
Questo problema è forse simile a quelli che chiedono di generare sistemi ridotti al lotto o al totocalcio?
Un problema di Dario Uri
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
-
Gianfranco
- Supervisore del sito
- Messaggi: 1720
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Un problema di Dario Uri
Pace e bene a tutti.
Gianfranco
Gianfranco
Re: Un problema di Dario Uri
Se la combinazione giusta è ABC, le combinazioni che aprono la serratura difettosa sono xBC, AxC e ABx (con x qualunque) quindi, evitando di contare 3 volte ABC, sono 22 su 512.
Provando con numeri a caso, l'aspettativa sono 23 tentativi... a scrivere il programmino ci vuole più tempo
Provando con numeri a caso, l'aspettativa sono 23 tentativi... a scrivere il programmino ci vuole più tempo
Franco
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Un problema di Dario Uri
... comunque, con 64 tentativi siamo sicuri di trovare la combinazione giusta: si tiene fissa una cifra e si provano le 8x8 combinazioni delle altre due.
Non escludo però che possano esserci tecniche più efficienti.
...
Nel passato remoto avevo un Atari ZX Spectrum (da buon "bastian contrario" non volevo il Commodore 64 come tutti gli altri) con cui scrissi un programmino in basic per "ridurre" i sistemi del totocalcio.
Si partiva da un pronostico base formato da "fisse", "doppie" e "triple" e poi si scartavano le colonne che non rientravano in determinati parametri impostabili di volta in volta (ad esempio quelle con più di 4 "2", o quelle con meno di 2 "1" o quelle con più di 4 "X" consecutivi).
Il problema era però che le colonne andavano ricopiate a mano sulle schedine e non ne avevo ne il tempo ne la voglia, il programma l'avevo scritto solo per giocare col basic.
Comunque, evidentemente, non c'era alcuna garanzia di successo (altrimenti non starei passando l'inverno a Bergamo
): se non si azzecca il pronostico base, non c'è sistema (integrale o ridotto) che tenga!
Tornando al problema di Dario Uri, credo che il programma per generare la sequenza di prove che ci diano la certezza di aprire la cassaforte debba essere completamente diverso.
(non cito il lotto perchè parlare di pronostici in questo caso è abbastanza ridicolo)
Non escludo però che possano esserci tecniche più efficienti.
...
Nel passato remoto avevo un Atari ZX Spectrum (da buon "bastian contrario" non volevo il Commodore 64 come tutti gli altri) con cui scrissi un programmino in basic per "ridurre" i sistemi del totocalcio.
Si partiva da un pronostico base formato da "fisse", "doppie" e "triple" e poi si scartavano le colonne che non rientravano in determinati parametri impostabili di volta in volta (ad esempio quelle con più di 4 "2", o quelle con meno di 2 "1" o quelle con più di 4 "X" consecutivi).
Il problema era però che le colonne andavano ricopiate a mano sulle schedine e non ne avevo ne il tempo ne la voglia, il programma l'avevo scritto solo per giocare col basic.
Comunque, evidentemente, non c'era alcuna garanzia di successo (altrimenti non starei passando l'inverno a Bergamo
): se non si azzecca il pronostico base, non c'è sistema (integrale o ridotto) che tenga!Tornando al problema di Dario Uri, credo che il programma per generare la sequenza di prove che ci diano la certezza di aprire la cassaforte debba essere completamente diverso.
(non cito il lotto perchè parlare di pronostici in questo caso è abbastanza ridicolo
)Franco
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Un problema di Dario Uri
Come indicato da Franco le combinazioni che aprono la cassaforte sono 22 su 512, quindi la probabilità di indovinare al primo tentativo è
$\displaystyle P(1)=\frac{22}{512}=0,04296875$
Consideriamo come prima strategia la tecnica dei tentativi a caso, senza segnare le combinazioni già provate
1. Tecnica casuale senza scarto
Se fallisce il primo tentativo, abbiamo scelto una delle 490 combinazioni non buone, al secondo tentativo la probabilità sarà
$\displaystyle P(2)=P(1)+\frac{22}{512}\frac{490}{512}=0,084091187$
Se anche questo tentativo fallisce dobbiamo moltiplicare di nuovo per 490/512 e così via
$\displaystyle P(n)=\sum_{k=0}^{n}\frac{22}{512}\left(\frac{490}{512}\right)^k$
Potremmo anche continuare a scegliere combinazioni errate per sempre, ma statisticamente vediamo che al 210° tentativo la probabilità di riuscita è superiore al 99,99%
Con questa tecnica il risultato atteso è di 23,2727 tentativi e la probabilità di riuscita supera il 50% con 16 tentativi
Valutiamo ora di scartare le combinazioni già testate
2. Tecnica casuale con scarto
Se fallisce il primo tentativo, abbiamo scelto una delle 490 combinazioni non buone, ma scartandone una, al secondo tentativo la probabilità sarà
$\displaystyle P(2)=P(1)+\frac{22}{511}\frac{490}{512}=0,084171661$
Al terzo
$\displaystyle P(3)=P(2)+\frac{22}{510}\frac{490}{512}\frac{490}{511}=0,084171661$
e così via
$\displaystyle P(n)=\frac{22}{512}+\sum_{j=0}^{n-2}{\frac{22}{511-j}\prod_{k=0}^{j}{\frac{490-k}{512-k}}}$
In questo caso il numero massimo di tentativi è di 490 ma anche qui al 171° tentativo la probabilità è superiore al 99,99%
Con questa tecnica il risultato atteso è di 22,3043 tentativi e la probabilità supera il 50% con 16 tentativi
Quindi, com'era prevedibile, è migliore dell'altra tecnica
Vediamo la strategia suggerita da Franco
3. Tecnica del disco 1 fisso
Fisso il primo disco su un valore casuale e provo tutte le combinazioni degli altri due dischi
Per comodità fisso il secondo disco e ruoto il terzo
Se il primo tentativo fallisce so che il disco 1 e il disco 2 non possono essere tutti e due corretti (probabilità 1/8*1/8=1/64), quindi potrebbe essere giusto il primo oppure il secondo oppure nessun dei due.
Nell'ultima ipotesi il primo giro del terzo disco andrebbe a vuoto, quindi consideriamo gli altri due casi con le relative probabilità
Disco 1 ok e disco 2 non ok (1/8*7/8=7/64)
Disco 1 non ok e disco 2 ok (1/8*7/8=7/64)
Consideriamo quindi 7/32 da dividere per le possibilità del terzo disco: ogni tentativo fornisce un contributo di 7/256 alla nostra probabilità
$\displaystyle P(n_{1-8})=\frac{22}{512}+\frac{7(n-1)}{256}$
Completato il primo giro sappiamo che il primo disco non è corretto, per cui consideriamo solo il secondo disco: ogni tentativo fornisce un contributo di 7/512 alla nostra probabilità
$\displaystyle P(n_{9-64})=\frac{22}{512}+\frac{49}{256}+\frac{7(n-8)}{512}$
Con questa tecnica il numero massimo di tentativi è 64, il risultato atteso è di 28,9453 tentativi e la probabilità supera il 50% con 28 tentativi
Un'ulteriore possibile strategia potrebbe essere quella di variare il disco 1 insieme al disco 2
4. Tecnica del disco 1 variabile
Per il primo giro del disco 3 non ci sono variazioni rispetto alla precedente
Tutti gli altri giri sono analoghi al primo con la differenza che le probabilità dei dischi 1 e 2 passano a 1/7 poi 1/6 ecc...
Il fallimento del primo giro sottrare 15/64 di possibilità, quindi devo partire da una probabilità residua di 49/64
Disco 1 ok e disco 2 ok (49/64*1/7*1/7=1/64)
Disco 1 ok o disco 2 ok (49/64*2*1/7*6/7=12/64)
Il primo tentativo del secondo turno aggiunge un contributo di 1/64+12/64*1/8=10/256
Dal secondo tentativo 12/64*1/8=6/256
Con il terzo giro
Disco 1 ok e disco 2 ok (49/64*36/49*1/6*1/6=1/64)
Disco 1 ok o disco 2 ok (49/64*36/49*2*1/6*5/6=10/64)
Il primo tentativo aggiunge un contributo di 1/64+10/64*1/8=9/256
Dal secondo tentativo 10/64*1/8=5/256
e così via
Con questa tecnica il numero massimo di tentativi è 64, il risultato atteso è di 21,5625 tentativi e la probabilità supera il 50% con 19 tentativi
Al momento sembrerebbe la strategia migliore
SE&O
$\displaystyle P(1)=\frac{22}{512}=0,04296875$
Consideriamo come prima strategia la tecnica dei tentativi a caso, senza segnare le combinazioni già provate
1. Tecnica casuale senza scarto
Se fallisce il primo tentativo, abbiamo scelto una delle 490 combinazioni non buone, al secondo tentativo la probabilità sarà
$\displaystyle P(2)=P(1)+\frac{22}{512}\frac{490}{512}=0,084091187$
Se anche questo tentativo fallisce dobbiamo moltiplicare di nuovo per 490/512 e così via
$\displaystyle P(n)=\sum_{k=0}^{n}\frac{22}{512}\left(\frac{490}{512}\right)^k$
Potremmo anche continuare a scegliere combinazioni errate per sempre, ma statisticamente vediamo che al 210° tentativo la probabilità di riuscita è superiore al 99,99%
Con questa tecnica il risultato atteso è di 23,2727 tentativi e la probabilità di riuscita supera il 50% con 16 tentativi
Valutiamo ora di scartare le combinazioni già testate
2. Tecnica casuale con scarto
Se fallisce il primo tentativo, abbiamo scelto una delle 490 combinazioni non buone, ma scartandone una, al secondo tentativo la probabilità sarà
$\displaystyle P(2)=P(1)+\frac{22}{511}\frac{490}{512}=0,084171661$
Al terzo
$\displaystyle P(3)=P(2)+\frac{22}{510}\frac{490}{512}\frac{490}{511}=0,084171661$
e così via
$\displaystyle P(n)=\frac{22}{512}+\sum_{j=0}^{n-2}{\frac{22}{511-j}\prod_{k=0}^{j}{\frac{490-k}{512-k}}}$
In questo caso il numero massimo di tentativi è di 490 ma anche qui al 171° tentativo la probabilità è superiore al 99,99%
Con questa tecnica il risultato atteso è di 22,3043 tentativi e la probabilità supera il 50% con 16 tentativi
Quindi, com'era prevedibile, è migliore dell'altra tecnica
Vediamo la strategia suggerita da Franco
3. Tecnica del disco 1 fisso
Fisso il primo disco su un valore casuale e provo tutte le combinazioni degli altri due dischi
Per comodità fisso il secondo disco e ruoto il terzo
Se il primo tentativo fallisce so che il disco 1 e il disco 2 non possono essere tutti e due corretti (probabilità 1/8*1/8=1/64), quindi potrebbe essere giusto il primo oppure il secondo oppure nessun dei due.
Nell'ultima ipotesi il primo giro del terzo disco andrebbe a vuoto, quindi consideriamo gli altri due casi con le relative probabilità
Disco 1 ok e disco 2 non ok (1/8*7/8=7/64)
Disco 1 non ok e disco 2 ok (1/8*7/8=7/64)
Consideriamo quindi 7/32 da dividere per le possibilità del terzo disco: ogni tentativo fornisce un contributo di 7/256 alla nostra probabilità
$\displaystyle P(n_{1-8})=\frac{22}{512}+\frac{7(n-1)}{256}$
Completato il primo giro sappiamo che il primo disco non è corretto, per cui consideriamo solo il secondo disco: ogni tentativo fornisce un contributo di 7/512 alla nostra probabilità
$\displaystyle P(n_{9-64})=\frac{22}{512}+\frac{49}{256}+\frac{7(n-8)}{512}$
Con questa tecnica il numero massimo di tentativi è 64, il risultato atteso è di 28,9453 tentativi e la probabilità supera il 50% con 28 tentativi
Un'ulteriore possibile strategia potrebbe essere quella di variare il disco 1 insieme al disco 2
4. Tecnica del disco 1 variabile
Per il primo giro del disco 3 non ci sono variazioni rispetto alla precedente
Tutti gli altri giri sono analoghi al primo con la differenza che le probabilità dei dischi 1 e 2 passano a 1/7 poi 1/6 ecc...
Il fallimento del primo giro sottrare 15/64 di possibilità, quindi devo partire da una probabilità residua di 49/64
Disco 1 ok e disco 2 ok (49/64*1/7*1/7=1/64)
Disco 1 ok o disco 2 ok (49/64*2*1/7*6/7=12/64)
Il primo tentativo del secondo turno aggiunge un contributo di 1/64+12/64*1/8=10/256
Dal secondo tentativo 12/64*1/8=6/256
Con il terzo giro
Disco 1 ok e disco 2 ok (49/64*36/49*1/6*1/6=1/64)
Disco 1 ok o disco 2 ok (49/64*36/49*2*1/6*5/6=10/64)
Il primo tentativo aggiunge un contributo di 1/64+10/64*1/8=9/256
Dal secondo tentativo 10/64*1/8=5/256
e così via
Con questa tecnica il numero massimo di tentativi è 64, il risultato atteso è di 21,5625 tentativi e la probabilità supera il 50% con 19 tentativi
Al momento sembrerebbe la strategia migliore
SE&O
[Sergio] / $17$
Re: Un problema di Dario Uri
Leggiamo il testo.
3 dischi numerati da 1 a 8 tengono chiusa una cassaforte.
Per trovare la giusta combinazione occorrerebbe testare 8^3= 512 posizioni, ma la serratura è difettosa ed è sufficiente indovinare 2 numeri su 3 per poterla aprire.
Qual è il minor numero di tentativi (di tre cifre) che occorre mettere in atto per assicurarne l’apertura?
Questo è un problema deterministico: chiede quante combinazioni bisogna testare per essere sicuri di aprire la cassaforte.
Un po’ di discussione mi sembra necessaria.
In primo luogo, vi sono due possibili modalità di funzionamento di una serratura: il primo, tipo “porta di casa”, prevede di girare la chiave per sbloccare il chiavistello e di dare un’altro mezzo giro o di azionare una maniglia per aprire effettivamente la porta; il secondo, tipo “Alì Babà e i quaranta ladroni”, prevede di sbloccare la porta che si apre da sola.
A mio parere, testare 8^3= 512 posizioni è compatibile con il primo scenario: col secondo scenario, la combinazione di partenza non deve essere testata perché, se fosse valida, la porta sarebbe aperta quindi le combinazioni da testare sono $511$. Inoltre, la necessità di azionare la maniglia per aprire la porta definisce in modo netto anche il concetto di “tentativo”: possiamo muovere i dischi quanto e come vogliamo perché la fine del tentativo è segnata dall’azionamento della maniglia; se la porta si aprisse appena trovata una combinazione utile, saremmo costretti a girare i dischi simultaneamente altrimenti ogni spostamento di un disco potrebbe far aprire la porta: ai fini pratici saremmo costretti a regolare un disco alla volta.
Secondo, per i nostri fini non ci interessa quali sono i numeri effettivi ma solo se aprono o no la porta quindi possiamo indicare i numeri giusti con $1$ e gli altri con $0$ (dobbiamo smettere di guardare i dischi o nascondere i numeri): identificheremo le combinazioni con due terne di numeri, la prima formata di $0$ e $1$ è la combinazione, la seconda indica per ciascun disco la distanza in senso orario dalla posizione raggiunta nel primo tentativo. Per esempio $\framebox{$\genfrac{}{}{0cm}{1}{011}{027}$}$ è una combinazione con due dischi allineati dopo aver spostato in avanti di $2$ il secondo disco e di $7$ il terzo disco.
Ora, se avessimo una cassaforte con due dischi perfettamente funzionante dovremmo testare $64$ combinazioni: se giriamo solo due dischi della nostra cassaforte otteniamo lo stesso risultato (il terzo disco deve essere non allineato per avere il caso peggiore).
Prendiamo in considerazione un paio di processi:
1. scansione sistematica delle $64$ combinazioni;
2. campionamento casuale (senza ripetizioni) su $64$ combinazioni.
Seguiamo il processo $1$: giro il terzo disco e provo ad aprire la porta fino a che il disco ha raggiunto la posizione $7$ (un altro scatto e si tornerebbe a $0$); giro di $1$ il secondo disco e ricomincio.
Questo processo scandisce le $64$ posizioni come mostato in figura (in rosso è indicato lo spostamento di una posizione dei dischi due e tre)
Non c’è bisogno di verificare che il secondo disco non faccia un giro completo perché la combinazione $\framebox{$\genfrac{}{}{0cm}{1}{011}{0ab}$}$ viene sicuramente raggiunta con $a\leq 7$: il processo esce sicuramente con “aperto”.
Nel caso peggiore, abbiamo $\framebox{$\genfrac{}{}{0cm}{1}{011}{077}$}$ .
Seguendo il processo $2$, testiamo le stesse combinazioni ma in un altro ordine (una permutazione delle posizioni) e termineremo non in $\framebox{$\genfrac{}{}{0cm}{1}{011}{077}$}$ ma in un altra posizione che indichiamo con $\framebox{$\genfrac{}{}{0cm}{1}{011} {0ab}$}$ : a questo punto basta spostare indietro di $a$ il secondo disco e di $b$ il terzo disco per trovare la combinazione dalla quale scorrendo la permutazione si è costretti a provarle tutte e $64$.
Il testo dice tentativi (di tre cifre) suggerendo che qualcosa di diverso possa succedere muovendo tre dischi per cui prendiamo in considerazione altri due processi:
3. scansione sistematica delle $512$ combinazioni;
4. campionamento casuale (senza ripetizioni) su $512$ combinazioni.
Nel processo $3$ la parte che scandisce le $64$ combinazioni esce certamente prima che il secondo disco torni in posizione $0$ quindi non arriveremo mai a “giro il disco 1”; viceversa, nel processo $4$ testeremo anche tutte le combinazioni $\framebox{$\genfrac{}{}{0cm}{1}{xyz}{abc}$}$ con $a>0$: poichè delle $512$ combinazioni possibili solo $22$ aprono la porta dovremo (principio dei cassetti) testarne $491$.
Il processo $4$ fallirà settanta volte sette prima di aprire la cassaforte come previsto dalla Legge di Murphy che possiamo riformulare come
$\Pr\left(K=491\middle|\top_4\right)=1$
ovvero, la probabilità di dover fare $491$ tentativi con un campionamento casuale su tre dischi senza ripetizioni è $1$: questo ci insegni a essere sistematici.
E a non usare mai e poi mai un campionamento con ripetizioni che, oltre a toglierci la certezza del successo, nel caso peggiore ci farebbe ricadere nel Problema del Collezionista: l’expectation del numero di tentivi per provare a caso tutte le $64$ combinazioni di due dischi è $64\,H_{64}\approx 303$ mentre, per le $491$ dei tre dischi l’expectation è $491\,H_{491}\approx 3300$ ($H_n$ è l’ennesimo Numero Armonico).
Il fatto che il problema sia deterministico non ci impedisce di considerare, come hanno fatto gli altri, gli aspetti probabilistici. La domanda che sorge spontanea è: c’è un qualche processo che minimizza l’expectation del numero di tentativi necessari per aprire la cassaforte?
Per il processo $1$, in figura è mostato quel che succede girando il terzo disco a seconda della posizione ottenuta nel primo tentativo
Per $\framebox{$\genfrac{}{}{0cm}{1}{111}{000}$}$ , $\framebox{$\genfrac{}{}{0cm}{1}{110}{000}$}$ , $\framebox{$\genfrac{}{}{0cm}{1}{101}{000}$}$ e $\framebox{$\genfrac{}{}{0cm}{1}{011}{000}$}$ il processo termina subito mentre per $\framebox{$\genfrac{}{}{0cm}{1}{100}{000}$}$ e $\framebox{$\genfrac{}{}{0cm}{1}{010}{000}$}$ termina, con eguale probabilità, tra il secondo e l’ottavo tentativo; più complesso è il caso di $\framebox{$\genfrac{}{}{0cm}{1}{001}{000}$}$ e $\framebox{$\genfrac{}{}{0cm}{1}{000}{000}$}$ .
Infatti, girare sette volte di una posizione il terzo disco partendo da $\framebox{$\genfrac{}{}{0cm}{1}{001}{000}$}$ porta certamente a $\framebox{$\genfrac{}{}{0cm}{1}{000}{000}$}$ mentre, partendo da $\framebox{$\genfrac{}{}{0cm}{1}{000}{000}$}$ , otteniamo $\framebox{$\genfrac{}{}{0cm}{1}{000}{000}$}$ sei volte su sette e $\framebox{$\genfrac{}{}{0cm}{1}{001}{000}$}$ una volta su sette: la frequenza iniziale e la frequenza finale delle combinazioni $\framebox{$\genfrac{}{}{0cm}{1}{001}{000}$}$ e $\framebox{$\genfrac{}{}{0cm}{1}{000}{000}$}$ sono uguali. Per terminare il processo bisogna cominciare a girare il secondo disco, come si vede nella figura seguente
Dalla combinazione $\framebox{$\genfrac{}{}{0cm}{1}{001}{0xx}$}$ il processo può terminare in $\framebox{$\genfrac{}{}{0cm}{1}{011}{0yx}$}$ ; dalla combinazione $\framebox{$\genfrac{}{}{0cm}{1}{000}{0xx}$}$ il processo può arrivare in $\framebox{$\genfrac{}{}{0cm}{1}{010}{0yx}$}$ a cui segue la possibilità di terminare con una qualunque delle sette posizioni successive (come succede per $\framebox{$\genfrac{}{}{0cm}{1}{010}{000}$}$ ).
Dovrebbe essere intuitivamente ovvio che la distribuzione di probabilità sui tentativi da $9$ a $64$ è uniforme: per coloro che, come me, si fidano poco dell’intuizione quando si parla di Probabilità, il calcolo che conferma tale distribuzione è presto fatto
$\Pr\left(\framebox{$\genfrac{}{}{0cm}{1}{011}{010}$}\middle|\top_1\right)=\dfrac{343}{512}\cdot\dfrac17\cdot\dfrac17=\dfrac7{512}$
per l’uscita diretta e
$\Pr\left(\framebox{$\genfrac{}{}{0cm}{1}{010}{010}$}\middle|\top_1\right)=\left(\dfrac{343}{512}\cdot\dfrac67+\dfrac{49}{512}\cdot\dfrac77\right)\cdot\dfrac17=\dfrac{49}{512}$
per l’uscita in uno dei sette tentativi successivi, ognuno con uguale probabilità.
Se volessimo, potremmo continuare ma ci è sufficiente osservare che distribuendo uniformemente la probabilità in ingresso, $49/512+343/512=392/512$, sui $56$ tentativi otteniamo precisamente $7/512$.
La distribuzione di probabilità è
$\Pr\left(K=k\middle|\top_1\right)=\left\{
\begin{array}{lllC}
\dfrac{22}{512} & \phantom{x} & k=1 \\
\dfrac{14}{512} & \phantom{x} & 2\leq k\leq 8 \\
\dfrac{7}{512} & \phantom{x} & 9\leq k\leq 66\\
\phantom{x} & \phantom{x} & \phantom{x} \\
0 & \phantom{x} & k > 64
\end{array}\right.$
la probabilità cumulativa è
$\Pr\left(K\leq k\middle|\top_1\right)=\left\{
\begin{array}{lllC}
\dfrac{22}{512} & \phantom{x} & k=1 \\
\dfrac{22+14(k-1)}{512} & \phantom{x} & 2\leq k\leq 8 \\
\dfrac{120+7(k-8)}{512} & \phantom{x} & 9\leq k\leq 66\\
\phantom{x} & \phantom{x} & \phantom{x} \\
1 & \phantom{x} & k > 64
\end{array}\right.$
e l’expectation è
$\left\langle K\middle|\top_1\right\rangle=\dfrac{22+14\cdot\left(\dfrac{8\cdot 9}2-1\right)+7\cdot\left(\dfrac{64\cdot 65}2-\dfrac{8\cdot 9}2\right)}{512}=\dfrac{3705}{128}=28,94\ldots$
Per il processo $2$, abbiamo due casi distinti a seconda se il primo disco è allineato o no dopo il primo tentativo.
Se è $\framebox{$\genfrac{}{}{0cm}{1}{1xx}{000}$}$ abbiamo $15$ combinazioni su $64$ che aprono la cassaforte quindi la distribuzione di probabilità è
$\dfrac{15}{64},\quad\dfrac{49}{64}\cdot\dfrac{15}{63},\quad\dfrac{49}{64}\cdot\dfrac{48}{63}\cdot\dfrac{15}{62},\quad\cdots$
Si può dimostrare che questa distribuzione di probabilità è una distribuzione ipergeometrica modificata
$\Pr\left(K=k\middle|\framebox{$\genfrac{}{}{0cm}{1}{1xx}{000}$}\land\top_2\right)=\dfrac1k\cdot\dfrac{\dbinom{15}{1}\dbinom{49}{k-1}}{\dbinom{64}{k}}$
per $k>0$ (quando $k>50$ il cofficiente binomiale $\tbinom{49}{k-1}$ si annulla).
Se è $\framebox{$\genfrac{}{}{0cm}{1}{0xx}{000}$}$ allora la combinazione che apre la cassaforte è una sola per cui la distribuzione è uniforme
$\Pr\left(K=k\middle|\framebox{$\genfrac{}{}{0cm}{1}{0xx}{000}$}\land\top_2\right)=
\left\{\begin{array}{lllC}
\dfrac1{64}&\phantom{x}&1\leq k\leq 64\\
\phantom{x}&\phantom{x}&\phantom{x}\\
0&\phantom{x}&k>64
\end{array}\right.$
La distribuzione complessiva è
$
\Pr\left(K=k\middle|\top_2\right)=
\Pr\left(\framebox{$\genfrac{}{}{0cm}{1}{1xx}{000}$}\middle|\top_2\right)\,
\Pr\left(K=k\middle|\framebox{$\genfrac{}{}{0cm}{1}{1xx}{000}$}\land\top_2\right)+
\Pr\left(\framebox{$\genfrac{}{}{0cm}{1}{0xx}{000}$}\middle|\top_2\right)\,
\Pr\left(K=k\middle|\framebox{$\genfrac{}{}{0cm}{1}{0xx}{000}$}\land\top_2\right)
$
cioè
$
\Pr\left(K=k\middle|\top_2\right)=
\left\{\begin{array}{lllC}
\dfrac18\cdot\dfrac1k\cdot\dfrac{\dbinom{15}{1}\dbinom{49}{k-1}}{\dbinom{64}{k}}+\dfrac78\cdot\dfrac1{64}&\phantom{x}&1\leq k\leq 64\\
\phantom{x}&\phantom{x}&\phantom{x}\\
0&\phantom{x}&k>64
\end{array}\right.
$
La probabilità cumulativa è
$
\Pr\left(K\leq k\middle|\top_2\right)=
\left\{\begin{array}{lllC}
\dfrac18\cdot\displaystyle\sum_{i=1}^{k}{\dfrac1i\cdot\dfrac{\dbinom{15}{1}\dbinom{49}{i-1}}{\dbinom{64}{i}}}+\dfrac78\cdot\dfrac{k}{64}&\phantom{x}&1\leq k\leq 64\\
\phantom{x}&\phantom{x}&\phantom{x}\\
1&\phantom{x}&k>64
\end{array}\right.
$
e l’expectation
$
\left\langle K\middle|\top_2\right\rangle=
\dfrac18\cdot\displaystyle\sum_{i=1}^{50}{\dfrac{\dbinom{15}{1}\dbinom{49}{i-1}}{\dbinom{64}{i}}}+\dfrac78\cdot\dfrac{64\cdot 65}2=\dfrac18\cdot\dfrac{65}{16}+\dfrac78\cdot\dfrac{65}2=\dfrac{3705}{128}=28,94\ldots
$
Ma guarda un po’, uguale a quella del processo $1$.
Il processo $3$ è indistiguibile dal processo $1$; per il processo $4$ vi sono $22$ combinazioni su $512$ che aprono la cassaforte: usiamo, come abbiamo fatto prima, la distribuzione ipergeometrica modificata
$\Pr\left(K=k\middle|\top_4\right)=\dfrac1k\cdot\dfrac{\dbinom{22}{1}\dbinom{490}{k-1}}{\dbinom{512}{k}}$
per $k>0$; la probabilità cumulativa è
$\Pr\left(K\leq k\middle|\top_4\right)=\displaystyle{\sum_{i=1}^k{\dfrac1i\cdot\dfrac{\dbinom{22}{1}\dbinom{490}{i-1}}{\dbinom{512}{i}}}}$
e l’expectation
$\left\langle K\middle|\top_4\right\rangle=\displaystyle{\sum_{i=1}^{491}{\dfrac{\dbinom{22}{1}\dbinom{490}{i-1}}{\dbinom{512}{i}}}}=\dfrac{513}{23}=20,30\ldots$
Consideriamo adesso i campionamenti con ripetizione su $64$ e $512$ combinazioni rispettivamente.
Il processo $5$ si comporta come il processo $2$ a seconda dell’allineamento del primo disco, con probabilità di successo pari a $15/64$ con il primo disco allineato e $1/64$ con il primo disco non allineato: distribuzione di probabilità
$\Pr\left(K=k\middle|\top_5\right)=\dfrac18\cdot\dfrac{15}{64}\left(\dfrac{49}{64}\right)^{k-1}+\dfrac78\cdot\dfrac{1}{64}\left(\dfrac{63}{64}\right)^{k-1}$
probabilità cumulativa
$\Pr\left(K\leq k\middle|\top_5\right)=\dfrac18\cdot\left[1-\left(\dfrac{49}{64}\right)^k\right]+\dfrac78\cdot\left[1-\left(\dfrac{63}{64}\right)^k\right]=1-\left[\dfrac18\cdot\left(\dfrac{49}{64}\right)^k+\dfrac78\cdot\left(\dfrac{63}{64}\right)^k\right]$
expectation
$\left\langle K\middle|\top_5\right\rangle=\dfrac18\cdot\dfrac{64}{15}+\dfrac78\cdot\dfrac{64}1=\dfrac{848}{15}=56,53\ldots$
Il processo $6$ è dritto: distribuzione di probabilità
$\Pr\left(K=k\middle|\top_6\right)=\dfrac{22}{512}\left(\dfrac{490}{512}\right)^{k-1}$
probabilità cumulativa
$\Pr\left(K\leq k\middle|\top_6\right)=1-\left(\dfrac{490}{512}\right)^k$
expectation
$\left\langle K\middle|\top_6\right\rangle=\dfrac{512}{22}=23,27\ldots$
Riassumendo
$\begin{array}{|c|l|C}
\hline
\text{processo}&\text{expectation}\\
\hline
1 & 28,94\ldots \\
\hline
2 & 28,94\ldots \\
\hline
3 & 28,94\ldots \\
\hline
4 & 20,30\ldots \\
\hline
5 & 56,53\ldots \\
\hline
6 & 23,27\ldots \\
\hline
\end{array}$
...e il processo $4$ vince!
3 dischi numerati da 1 a 8 tengono chiusa una cassaforte.
Per trovare la giusta combinazione occorrerebbe testare 8^3= 512 posizioni, ma la serratura è difettosa ed è sufficiente indovinare 2 numeri su 3 per poterla aprire.
Qual è il minor numero di tentativi (di tre cifre) che occorre mettere in atto per assicurarne l’apertura?
Questo è un problema deterministico: chiede quante combinazioni bisogna testare per essere sicuri di aprire la cassaforte.
Un po’ di discussione mi sembra necessaria.
In primo luogo, vi sono due possibili modalità di funzionamento di una serratura: il primo, tipo “porta di casa”, prevede di girare la chiave per sbloccare il chiavistello e di dare un’altro mezzo giro o di azionare una maniglia per aprire effettivamente la porta; il secondo, tipo “Alì Babà e i quaranta ladroni”, prevede di sbloccare la porta che si apre da sola.
A mio parere, testare 8^3= 512 posizioni è compatibile con il primo scenario: col secondo scenario, la combinazione di partenza non deve essere testata perché, se fosse valida, la porta sarebbe aperta quindi le combinazioni da testare sono $511$. Inoltre, la necessità di azionare la maniglia per aprire la porta definisce in modo netto anche il concetto di “tentativo”: possiamo muovere i dischi quanto e come vogliamo perché la fine del tentativo è segnata dall’azionamento della maniglia; se la porta si aprisse appena trovata una combinazione utile, saremmo costretti a girare i dischi simultaneamente altrimenti ogni spostamento di un disco potrebbe far aprire la porta: ai fini pratici saremmo costretti a regolare un disco alla volta.
Secondo, per i nostri fini non ci interessa quali sono i numeri effettivi ma solo se aprono o no la porta quindi possiamo indicare i numeri giusti con $1$ e gli altri con $0$ (dobbiamo smettere di guardare i dischi o nascondere i numeri): identificheremo le combinazioni con due terne di numeri, la prima formata di $0$ e $1$ è la combinazione, la seconda indica per ciascun disco la distanza in senso orario dalla posizione raggiunta nel primo tentativo. Per esempio $\framebox{$\genfrac{}{}{0cm}{1}{011}{027}$}$ è una combinazione con due dischi allineati dopo aver spostato in avanti di $2$ il secondo disco e di $7$ il terzo disco.
Ora, se avessimo una cassaforte con due dischi perfettamente funzionante dovremmo testare $64$ combinazioni: se giriamo solo due dischi della nostra cassaforte otteniamo lo stesso risultato (il terzo disco deve essere non allineato per avere il caso peggiore).
Prendiamo in considerazione un paio di processi:
1. scansione sistematica delle $64$ combinazioni;
2. campionamento casuale (senza ripetizioni) su $64$ combinazioni.
- UPdDU.fig.01.png (22.04 KiB) Visto 35653 volte
Questo processo scandisce le $64$ posizioni come mostato in figura (in rosso è indicato lo spostamento di una posizione dei dischi due e tre)
- UPdDU.fig.02.png (25.45 KiB) Visto 35653 volte
Nel caso peggiore, abbiamo $\framebox{$\genfrac{}{}{0cm}{1}{011}{077}$}$ .
Seguendo il processo $2$, testiamo le stesse combinazioni ma in un altro ordine (una permutazione delle posizioni) e termineremo non in $\framebox{$\genfrac{}{}{0cm}{1}{011}{077}$}$ ma in un altra posizione che indichiamo con $\framebox{$\genfrac{}{}{0cm}{1}{011} {0ab}$}$ : a questo punto basta spostare indietro di $a$ il secondo disco e di $b$ il terzo disco per trovare la combinazione dalla quale scorrendo la permutazione si è costretti a provarle tutte e $64$.
Il testo dice tentativi (di tre cifre) suggerendo che qualcosa di diverso possa succedere muovendo tre dischi per cui prendiamo in considerazione altri due processi:
3. scansione sistematica delle $512$ combinazioni;
4. campionamento casuale (senza ripetizioni) su $512$ combinazioni.
- UPdDU.fig.03.png (30.29 KiB) Visto 35653 volte
Il processo $4$ fallirà settanta volte sette prima di aprire la cassaforte come previsto dalla Legge di Murphy che possiamo riformulare come
$\Pr\left(K=491\middle|\top_4\right)=1$
ovvero, la probabilità di dover fare $491$ tentativi con un campionamento casuale su tre dischi senza ripetizioni è $1$: questo ci insegni a essere sistematici.
E a non usare mai e poi mai un campionamento con ripetizioni che, oltre a toglierci la certezza del successo, nel caso peggiore ci farebbe ricadere nel Problema del Collezionista: l’expectation del numero di tentivi per provare a caso tutte le $64$ combinazioni di due dischi è $64\,H_{64}\approx 303$ mentre, per le $491$ dei tre dischi l’expectation è $491\,H_{491}\approx 3300$ ($H_n$ è l’ennesimo Numero Armonico).
Il fatto che il problema sia deterministico non ci impedisce di considerare, come hanno fatto gli altri, gli aspetti probabilistici. La domanda che sorge spontanea è: c’è un qualche processo che minimizza l’expectation del numero di tentativi necessari per aprire la cassaforte?
Per il processo $1$, in figura è mostato quel che succede girando il terzo disco a seconda della posizione ottenuta nel primo tentativo
- UPdDU.fig.04.png (86.63 KiB) Visto 35653 volte
Infatti, girare sette volte di una posizione il terzo disco partendo da $\framebox{$\genfrac{}{}{0cm}{1}{001}{000}$}$ porta certamente a $\framebox{$\genfrac{}{}{0cm}{1}{000}{000}$}$ mentre, partendo da $\framebox{$\genfrac{}{}{0cm}{1}{000}{000}$}$ , otteniamo $\framebox{$\genfrac{}{}{0cm}{1}{000}{000}$}$ sei volte su sette e $\framebox{$\genfrac{}{}{0cm}{1}{001}{000}$}$ una volta su sette: la frequenza iniziale e la frequenza finale delle combinazioni $\framebox{$\genfrac{}{}{0cm}{1}{001}{000}$}$ e $\framebox{$\genfrac{}{}{0cm}{1}{000}{000}$}$ sono uguali. Per terminare il processo bisogna cominciare a girare il secondo disco, come si vede nella figura seguente
- UPdDU.fig.05.png (61.99 KiB) Visto 35653 volte
Dovrebbe essere intuitivamente ovvio che la distribuzione di probabilità sui tentativi da $9$ a $64$ è uniforme: per coloro che, come me, si fidano poco dell’intuizione quando si parla di Probabilità, il calcolo che conferma tale distribuzione è presto fatto
$\Pr\left(\framebox{$\genfrac{}{}{0cm}{1}{011}{010}$}\middle|\top_1\right)=\dfrac{343}{512}\cdot\dfrac17\cdot\dfrac17=\dfrac7{512}$
per l’uscita diretta e
$\Pr\left(\framebox{$\genfrac{}{}{0cm}{1}{010}{010}$}\middle|\top_1\right)=\left(\dfrac{343}{512}\cdot\dfrac67+\dfrac{49}{512}\cdot\dfrac77\right)\cdot\dfrac17=\dfrac{49}{512}$
per l’uscita in uno dei sette tentativi successivi, ognuno con uguale probabilità.
Se volessimo, potremmo continuare ma ci è sufficiente osservare che distribuendo uniformemente la probabilità in ingresso, $49/512+343/512=392/512$, sui $56$ tentativi otteniamo precisamente $7/512$.
La distribuzione di probabilità è
$\Pr\left(K=k\middle|\top_1\right)=\left\{
\begin{array}{lllC}
\dfrac{22}{512} & \phantom{x} & k=1 \\
\dfrac{14}{512} & \phantom{x} & 2\leq k\leq 8 \\
\dfrac{7}{512} & \phantom{x} & 9\leq k\leq 66\\
\phantom{x} & \phantom{x} & \phantom{x} \\
0 & \phantom{x} & k > 64
\end{array}\right.$
la probabilità cumulativa è
$\Pr\left(K\leq k\middle|\top_1\right)=\left\{
\begin{array}{lllC}
\dfrac{22}{512} & \phantom{x} & k=1 \\
\dfrac{22+14(k-1)}{512} & \phantom{x} & 2\leq k\leq 8 \\
\dfrac{120+7(k-8)}{512} & \phantom{x} & 9\leq k\leq 66\\
\phantom{x} & \phantom{x} & \phantom{x} \\
1 & \phantom{x} & k > 64
\end{array}\right.$
e l’expectation è
$\left\langle K\middle|\top_1\right\rangle=\dfrac{22+14\cdot\left(\dfrac{8\cdot 9}2-1\right)+7\cdot\left(\dfrac{64\cdot 65}2-\dfrac{8\cdot 9}2\right)}{512}=\dfrac{3705}{128}=28,94\ldots$
Per il processo $2$, abbiamo due casi distinti a seconda se il primo disco è allineato o no dopo il primo tentativo.
Se è $\framebox{$\genfrac{}{}{0cm}{1}{1xx}{000}$}$ abbiamo $15$ combinazioni su $64$ che aprono la cassaforte quindi la distribuzione di probabilità è
$\dfrac{15}{64},\quad\dfrac{49}{64}\cdot\dfrac{15}{63},\quad\dfrac{49}{64}\cdot\dfrac{48}{63}\cdot\dfrac{15}{62},\quad\cdots$
Si può dimostrare che questa distribuzione di probabilità è una distribuzione ipergeometrica modificata
$\Pr\left(K=k\middle|\framebox{$\genfrac{}{}{0cm}{1}{1xx}{000}$}\land\top_2\right)=\dfrac1k\cdot\dfrac{\dbinom{15}{1}\dbinom{49}{k-1}}{\dbinom{64}{k}}$
per $k>0$ (quando $k>50$ il cofficiente binomiale $\tbinom{49}{k-1}$ si annulla).
Se è $\framebox{$\genfrac{}{}{0cm}{1}{0xx}{000}$}$ allora la combinazione che apre la cassaforte è una sola per cui la distribuzione è uniforme
$\Pr\left(K=k\middle|\framebox{$\genfrac{}{}{0cm}{1}{0xx}{000}$}\land\top_2\right)=
\left\{\begin{array}{lllC}
\dfrac1{64}&\phantom{x}&1\leq k\leq 64\\
\phantom{x}&\phantom{x}&\phantom{x}\\
0&\phantom{x}&k>64
\end{array}\right.$
La distribuzione complessiva è
$
\Pr\left(K=k\middle|\top_2\right)=
\Pr\left(\framebox{$\genfrac{}{}{0cm}{1}{1xx}{000}$}\middle|\top_2\right)\,
\Pr\left(K=k\middle|\framebox{$\genfrac{}{}{0cm}{1}{1xx}{000}$}\land\top_2\right)+
\Pr\left(\framebox{$\genfrac{}{}{0cm}{1}{0xx}{000}$}\middle|\top_2\right)\,
\Pr\left(K=k\middle|\framebox{$\genfrac{}{}{0cm}{1}{0xx}{000}$}\land\top_2\right)
$
cioè
$
\Pr\left(K=k\middle|\top_2\right)=
\left\{\begin{array}{lllC}
\dfrac18\cdot\dfrac1k\cdot\dfrac{\dbinom{15}{1}\dbinom{49}{k-1}}{\dbinom{64}{k}}+\dfrac78\cdot\dfrac1{64}&\phantom{x}&1\leq k\leq 64\\
\phantom{x}&\phantom{x}&\phantom{x}\\
0&\phantom{x}&k>64
\end{array}\right.
$
La probabilità cumulativa è
$
\Pr\left(K\leq k\middle|\top_2\right)=
\left\{\begin{array}{lllC}
\dfrac18\cdot\displaystyle\sum_{i=1}^{k}{\dfrac1i\cdot\dfrac{\dbinom{15}{1}\dbinom{49}{i-1}}{\dbinom{64}{i}}}+\dfrac78\cdot\dfrac{k}{64}&\phantom{x}&1\leq k\leq 64\\
\phantom{x}&\phantom{x}&\phantom{x}\\
1&\phantom{x}&k>64
\end{array}\right.
$
e l’expectation
$
\left\langle K\middle|\top_2\right\rangle=
\dfrac18\cdot\displaystyle\sum_{i=1}^{50}{\dfrac{\dbinom{15}{1}\dbinom{49}{i-1}}{\dbinom{64}{i}}}+\dfrac78\cdot\dfrac{64\cdot 65}2=\dfrac18\cdot\dfrac{65}{16}+\dfrac78\cdot\dfrac{65}2=\dfrac{3705}{128}=28,94\ldots
$
Ma guarda un po’, uguale a quella del processo $1$.
Il processo $3$ è indistiguibile dal processo $1$; per il processo $4$ vi sono $22$ combinazioni su $512$ che aprono la cassaforte: usiamo, come abbiamo fatto prima, la distribuzione ipergeometrica modificata
$\Pr\left(K=k\middle|\top_4\right)=\dfrac1k\cdot\dfrac{\dbinom{22}{1}\dbinom{490}{k-1}}{\dbinom{512}{k}}$
per $k>0$; la probabilità cumulativa è
$\Pr\left(K\leq k\middle|\top_4\right)=\displaystyle{\sum_{i=1}^k{\dfrac1i\cdot\dfrac{\dbinom{22}{1}\dbinom{490}{i-1}}{\dbinom{512}{i}}}}$
e l’expectation
$\left\langle K\middle|\top_4\right\rangle=\displaystyle{\sum_{i=1}^{491}{\dfrac{\dbinom{22}{1}\dbinom{490}{i-1}}{\dbinom{512}{i}}}}=\dfrac{513}{23}=20,30\ldots$
Consideriamo adesso i campionamenti con ripetizione su $64$ e $512$ combinazioni rispettivamente.
Il processo $5$ si comporta come il processo $2$ a seconda dell’allineamento del primo disco, con probabilità di successo pari a $15/64$ con il primo disco allineato e $1/64$ con il primo disco non allineato: distribuzione di probabilità
$\Pr\left(K=k\middle|\top_5\right)=\dfrac18\cdot\dfrac{15}{64}\left(\dfrac{49}{64}\right)^{k-1}+\dfrac78\cdot\dfrac{1}{64}\left(\dfrac{63}{64}\right)^{k-1}$
probabilità cumulativa
$\Pr\left(K\leq k\middle|\top_5\right)=\dfrac18\cdot\left[1-\left(\dfrac{49}{64}\right)^k\right]+\dfrac78\cdot\left[1-\left(\dfrac{63}{64}\right)^k\right]=1-\left[\dfrac18\cdot\left(\dfrac{49}{64}\right)^k+\dfrac78\cdot\left(\dfrac{63}{64}\right)^k\right]$
expectation
$\left\langle K\middle|\top_5\right\rangle=\dfrac18\cdot\dfrac{64}{15}+\dfrac78\cdot\dfrac{64}1=\dfrac{848}{15}=56,53\ldots$
Il processo $6$ è dritto: distribuzione di probabilità
$\Pr\left(K=k\middle|\top_6\right)=\dfrac{22}{512}\left(\dfrac{490}{512}\right)^{k-1}$
probabilità cumulativa
$\Pr\left(K\leq k\middle|\top_6\right)=1-\left(\dfrac{490}{512}\right)^k$
expectation
$\left\langle K\middle|\top_6\right\rangle=\dfrac{512}{22}=23,27\ldots$
Riassumendo
$\begin{array}{|c|l|C}
\hline
\text{processo}&\text{expectation}\\
\hline
1 & 28,94\ldots \\
\hline
2 & 28,94\ldots \\
\hline
3 & 28,94\ldots \\
\hline
4 & 20,30\ldots \\
\hline
5 & 56,53\ldots \\
\hline
6 & 23,27\ldots \\
\hline
\end{array}$
...e il processo $4$ vince!
il panurgo
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Re: Un problema di Dario Uri
Se $a$ è il numero di combinazioni che aprono la cassaforte e $b$ è il numero di combinazioni che non la aprono allora la nostra distribuzione sarà
$\begin{array}{lC}\dfrac{a}{a+b} \\
\dfrac{b}{a+b}\cdot\dfrac{a}{a+b-1} \\
\dfrac{b}{a+b}\cdot\dfrac{b-1}{a+b-1}\cdot\dfrac{a}{a+b-2} \\
\mspace{100mu}\vdots\end{array}$
Facciamo uso del fatto che
$\begin{array}{lC}n(n-1)\cdots(n-k+1)=\dfrac{n!}{(n-k)!}\\n=\dfrac{n!}{(n-1)!}=\dfrac{n!}{1!(n-1)!}\\1=\dfrac{n!}{0!n!}\end{array}$
e otteniamo
$\begin{array}{lC}
\dfrac{
\dfrac{b!}{b!}\cdot\dfrac{a!}{(a-1)!}
}{
\dfrac{(a+b)!}{(a+b-1)!}
}\\
\dfrac{
\dfrac{b!}{(b-1)!}\cdot\dfrac{a!}{a!}
}{
\dfrac{(a+b)!}{(a+b-1)!}
}\cdot
\dfrac{
\dfrac{(b-1)!}{(b-1)!}\cdot\dfrac{a!}{(a-1)!}
}{
\dfrac{(a+b-1)!}{(a+b-2)!}
},\\
\dfrac{
\dfrac{b!}{(b-1)!}\cdot\dfrac{a!}{a!}
}{
\dfrac{(a+b)!}{(a+b-1)!}
}\cdot
\dfrac{
\dfrac{(b-1)!}{(b-2)!}\cdot\dfrac{a!}{a!}
}{
\dfrac{(a+b-1)!}{(a+b-2)!}
}\cdot
\dfrac{
\dfrac{(b-2)!}{(b-2)!}\cdot\dfrac{a!}{(a-1)!}
}{
\dfrac{(a+b-2)!}{(a+b-3)!}
}\\
\mspace{190mu}\vdots\end{array}$
cioè
$\begin{array}{lC}
\dfrac{\dbinom{b}{0}\dbinom{a}{1}}{\dbinom{a+b}{1}}\\
\dfrac{\dbinom{b}{1}\dbinom{a}{0}}{\dbinom{a+b}{1}}\cdot
\dfrac{\dbinom{b-1}{0}\dbinom{a}{1}}{\dbinom{a+b-1}{1}}\\
\dfrac{\dbinom{b}{1}\dbinom{a}{0}}{\dbinom{a+b}{1}}\cdot
\dfrac{\dbinom{b-1}{1}\dbinom{a}{0}}{\dbinom{a+b-1}{1}}\cdot
\dfrac{\dbinom{b-2}{0}\dbinom{a}{1}}{\dbinom{a+b-2}{1}}\\
\mspace{145mu}\vdots\end{array}$
Ora giochiamo un po’ con i coefficienti binomiali
$\dbinom{n}{k}\dbinom{n-k}{1}=\dfrac{k+1}{k+1}\cdot\dfrac{n!}{k!(n-k)!}\cdot\dfrac{(n-k)!}{1!(n-k-1)!}=\dfrac{(k+1)\cdot n!}{(k+1)!(n-k-1)!}=(k+1)\cdot\dbinom{n}{k+1}$
Per la nostra distribuzione: per $k=1$
$
\dfrac{\dbinom{b}{0}\dbinom{a}{1}}{\dbinom{a+b}{1}}=
\dfrac{\dbinom{b}{0}\dbinom{a}{1}}{1\cdot\dbinom{a+b}{1}}
$
per $k=2$
$
\dfrac{\dbinom{b}{1}\dbinom{a}{0}}{\dbinom{a+b}{1}}\cdot
\dfrac{\dbinom{b-1}{0}\dbinom{a}{1}}{\dbinom{a+b-1}{1}}=
\dfrac{\dbinom{b}{1}\dbinom{a}{1}}{2\cdot\dbinom{a+b}{2}}
$
per $k=3$
$
\dfrac{\dbinom{b}{1}\dbinom{a}{0}}{\dbinom{a+b}{1}}\cdot
\dfrac{\dbinom{b-1}{1}\dbinom{a}{0}}{\dbinom{a+b-1}{1}}\cdot
\dfrac{\dbinom{b-2}{0}\dbinom{a}{1}}{\dbinom{a+b-2}{1}}=
\dfrac{\not{2}\cdot\dbinom{b}{2}\dbinom{a}{0}}{\not{2}\cdot\dbinom{a+b}{2}}\cdot
\dfrac{\dbinom{b-2}{0}\dbinom{a}{1}}{\dbinom{a+b-2}{1}}=
\dfrac{\dbinom{b}{2}\dbinom{a}{1}}{3\cdot\dbinom{a+b}{3}}
$
La distribuzione di probabilità è
$\Pr\left(K=k\middle|\top\right)=\dfrac{1}{k}\cdot\dfrac{\dbinom{b}{k-1}\dbinom{a}{1}}{\dbinom{a+b}{k}}$
e l’expectation è
$\displaystyle\left\langle K\middle|\top\right)=\sum_{k=1}^\infty{k\cdot\Pr\left(K=k\middle|\top\right)}=\sum_{k=1}^{b+1}{\dfrac{\binom{b}{k-1}\binom{a}{1}}{\binom{a+b}{k}}}=\frac{a+b+1}{a+1}$
La sommatoria è limitata perché $\tbinom{b}{k-1}=0$ per $k>b+1$.
il panurgo
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"