Il gioco dei pacchi 🎁

In una nuova trasmissione televisiva viene fatto questo gioco: vi sono 20 concorrenti, ognuno con un pacco contenente un assegno con una cifra in euro. Viene estratto un concorrente: questi farà aprire un pacco a sua scelta e poi dovrà prendere una decisione: scegliere il pacco appena aperto oppure andare avanti e farne aprire un altro, e così via. Un pacco scartato non potrà più essere scelto. Se nessuno dei pacchi degli altri concorrenti verrà scelto, il concorrente sceglierà forzatamente il proprio pacco (dal valore inizialmente sconosciuto come tutti gli altri). Il concorrente si porterà a casa l’ammontare corrispondente al pacco scelto. Qual è la strategia che massimizza la probabilità di scegliere il pacco dal maggior valore? È da sottolineare che non si ha alcuna informazione sui valori degli assegni, l’unica cosa che si può fare è confrontare i contenuti dei pacchi fra loro.

La situazione è equivalente ad avere 20 pacchi disposti uno dopo l’altro ed aprirli sequenzialmente fino al pacco scelto.

Se scegliamo un pacco che non è il maggiore fra quelli comparsi fino a quel momento, sicuramente non scegliamo il pacco dal valore maggiore. La strategia migliore è aprire un certo numero $k$ di pacchi e poi scegliere il primo con valore superiore al massimo dei valori dei primi $k$ pacchi aperti. Ad ogni $k$ corrisponde una determinata probabilità di successo, e dobbiamo trovare il valore di $k$ che massimizza tale probabilità.

Prima di risolvere il caso generale e scrivere delle belle formulone, facciamo un esempio concreto, per meglio chiarire le idee (sono abituato a fare così, sia con me stesso che con i miei studenti, e ho riscontrato che è una modalità molto efficace). Supponiamo di prendere $k=5$, cioè facciamo aprire $5$ pacchi e poi apriremo i pacchi fino a quando non troveremo un valore superiore a quello dei primi $5$ pacchi o, eventualmente, apriremo e sceglieremo forzatamente l’ultimo pacco. Indico con $\texttt{#}1$ il pacco di maggior valore. La probabilità che il pacco $\texttt{#}1$ sia in una determinata posizione è $\dfrac1{20}$.

Se il pacco $\texttt{#}1$ è tra i primi $k=5$ aperti non sarà scelto. Se il pacco $\texttt{#}1$ è il sesto, sarà sicuramente scelto, quindi la probabilità che il pacco $\texttt{#}1$ sia sesto e venga scelto è $\dfrac1{20}$. Se il pacco $\texttt{#}1$ è il settimo, la probabilità che sia scelto va moltiplicata per $1-\dfrac16$, dove $\dfrac16$ è la probabilità che, fra i sei pacchi precedenti, quello di valore maggiore sia in sesta posizione (nel qual caso sarebbe stato scelto). La probabilità che il pacco $\texttt{#}1$ sia settimo e venga scelto è dunque $\dfrac1{20}\cdot\dfrac56$. Analogamente, se il pacco $\texttt{#}1$ è l’ottavo, la probabilità che venga scelto va moltiplicata per $\left(1-\dfrac16\right)\left(1-\dfrac17\right)=\dfrac57$, ovvero la probabilità che il maggiore fra i primi sei pacchi non sia in sesta posizione e che il maggiore fra i primi sette pacchi non sia in settima posizione. La probabilità che il pacco $\texttt{#}1$ sia ottavo e venga scelto è dunque $\dfrac1{20}\cdot\dfrac57$. Andando avanti, le probabilità sono $\dfrac1{20}\cdot\dfrac58,\dfrac1{20} \cdot\dfrac59, \ldots,\dfrac1{20} \cdot\dfrac5{19}$. La probabilità complessiva di scegliere il pacco $\texttt{#}1$ dopo aver scartato $5$ pacchi e scelto il primo dal valore maggiore di quelli dei primi $k=5$ è dunque, raccogliendo: $p=\dfrac5{20}\left(\dfrac15+\dfrac16+\ldots+\dfrac1{19}\right)$.

Generalizzando, se ho $n$ pacchi e attuo la strategia di aprirne $k$ e poi scegliere il primo che presenti un valore superiore a quelli già visti, la probabilità di scegliere il pacco $\texttt{#}1$ e quindi vincere la maggiore posta in gioco sarà: $$p(n,k)= \dfrac1n+ \dfrac{k}n \left(\dfrac1{k+1} +\dfrac1{k+2} +\ldots+ \dfrac1{n-1} \right)\ .\tag{1}$$

Fissato $n$, la probabilità $p(n,k)$ parte da $p(n,0)=\dfrac1n$ e, a parte i casi $n=1$ (dove si ha $p(1,0)=1$) e $n=2$ (dove si ha $p(2,0)=p(2,1)=\frac12$), cresce per raggiungere un valore massimo e poi decrescere fino a $p(n,n-1)=\dfrac1n$, come si vede in figura $1$. Il valore di $k$ che massimizza la probabilità, valore che indicheremo con $k_M$, sarà il più piccolo fra quelli per cui $p(n,k)>p(n,k+1)$. Il $k$ che cerchiamo deve essere il minimo fra quelli che soddisfano la disuguaglianza

$$\dfrac1n+\dfrac{k}n\left(\dfrac1{k+1}+\ldots+\dfrac1{n-1} \right)>\dfrac1n+\dfrac{k+1}n\left(\dfrac1{k+2}+\ldots+\dfrac1{n-1} \right)$$che possiamo riscrivere come$$k\left(\dfrac1{k+1}+\ldots+\dfrac1{n-1} \right)>(k+1)\left(\dfrac1{k+1}+\dfrac1{k+2}+\ldots+\dfrac1{n-1}-\dfrac1{k+1} \right)$$che diventa $$\dfrac1{k+1}+\dfrac1{k+2}+\ldots+\dfrac1{n-1}<1\ ,$$e poiché cerchiamo il minimo valore di $k$ che soddisfi questa disuguaglianza, il valore cercato è quello per cui$$\dfrac1{k+1}+\ldots+\dfrac1{n-1}<1<\dfrac1{k}+\ldots+\dfrac1{n-1}\ .\tag{2}$$È da notare che, nelle disuguaglianze sopra riportate, non varrà mai l’uguaglianza (a parte il caso banale in cui la sommatoria sia solo del termine $\frac11$) in quanto, come è stato dimostrato da József Kürschák (1864-1933) nel 1918, la sommatoria di reciproci di numeri interi consecutivi non dà mai come risultato un numero intero.

Il valore $k_M$ gode anche di questa proprietà che si può verificare facilmente utilizzando l’uguaglianza $(1)$ e le disuguaglianze in $(2)$: è il massimo valore assunto da $k$ per cui la probabilità che il pacco $\texttt{#}1$ sia già stato visto è inferiore a quella che il pacco $\texttt{#}1$ sia in uno dei pacchi successivi e venga scelto.

Per trovare il valore preciso di $k_M$ dovremmo calcolare le sommatorie e vedere in corrispondenza di quale $k$ superano $1$. In realtà, anche senza calcolare le sommatorie possiamo comunque porre un limite superiore ed inferiore a $k$ tramite le seguenti disuguaglianze che legano le somme dei reciproci di numeri naturali positivi consecutivi all’integrale della funzione $f(x)=\dfrac1x$:$$\int_a^{b+1}\dfrac{dx}x+\dfrac12\left(\dfrac1a-\dfrac1{b+1}\right)<\dfrac1a+\dfrac1{a+1}+\ldots+\dfrac1b<\int_{a-\frac12}^{b+\frac12}\dfrac{dx}x\ .$$Otteniamo allora$$\int_{k+1}^n \dfrac{dx}x+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)<1<\int_{k-\frac12}^{n-\frac12}\dfrac{dx}x$$da cui$$\ln\left(\dfrac{n}{k+1}\right)+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)<1<\ln\left(\dfrac{n-1/2}{k-1/2}\right)\ .\tag{3}$$Dalla seconda disuguaglianza si ricava facilmente $k<\dfrac{n-1/2}{e}+\dfrac12$ mentre l’elaborazione della prima disuguaglianza è un po’ più complessa:$$\ln\left(\dfrac{n}{k+1}\right)+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)<1 \iff \ln\left(\dfrac{k+1}{n}\right)>-1+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)\iff$$ $$\iff \dfrac{k+1}n>\dfrac1e\cdot \exp\left[\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)\right]>\dfrac1e\left[1+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)\right]>$$ $$>\dfrac1e\left[1+\dfrac12\left(\dfrac1{\frac{n-1/2}e+\frac32}-\dfrac1n\right)\right]=\dfrac1e\left(1-\dfrac1{2n}\right)+\dfrac1{2n+3e-1}\ ,$$dove abbiamo utilizzato la disuguaglianza $\exp x>1+x$ se $x\neq0$ e la disuguaglianza precedentemente ottenuta per $k$. Si ha dunque$$k>\dfrac{n-1/2}e+\dfrac{n}{2n+3e-1}-1=\dfrac{n-1/2}e+\dfrac{\left(n+\frac{3e}2-\frac12\right)-\left(\frac{3e}2-\frac12\right)}{2n+3e-1}-1$$e infine$$k> \dfrac{n-1/2}e-\dfrac12- \dfrac{3e-1}{2(2n+3e-1)}\ ,\tag{4}$$e si deve quindi complessivamente avere$$\dfrac{n-1/2}e-\dfrac12-\dfrac{3e-1}{2(2n+3e-1)}=k_{inf}(n)<k_M<k_{sup}(n)=\dfrac{n-1/2}{e}+\dfrac12\ .\tag{5}$$L’intervallo in cui deve stare $k_M$ è di ampiezza $$I(n)=k_{sup}(n) - k_{inf}(n)  =1+\dfrac{3e-1}{4n}+O\left(  \dfrac1{n^2}\right)\simeq 1+\dfrac{1{,}79}{n}-\dfrac{6{,}40}{n^2},$$di poco superiore a $1$ per valori grandi di $n$ e quindi, nella maggior parte dei casi, c’è un solo intero che stia dentro a quell’intervallo. Per $n$ che va da $1$ a $10.000$ nell’intervallo $(k_{inf},k_{sup})$ vi sono due interi solo per $n=2$ (dove però entrambi gli interi, $k=0$ e $k=1$ massimizzano la probabilità di vincita), e per $n=5$, $13$, $21$, $40$, $59$, $78$, $97$, $184$, $290$, $483$, $676$, $1.554$, $2.818$ e $5.539$. A parte il caso $n=97$, $k_M$ è sempre il maggiore dei due interi. Indagando da $n=1$ a $n=100.000.000$, si ha in effetti $k_M=\left\lfloor k_{sup}(n)\right\rfloor$ tranne che per $n=2$, $n=97$, $n=24.586$ e $n=14.122.865$ dove $k_M=\left\lceil k_{inf}(n)\right\rceil = \left\lfloor k_{sup}(n)\right\rfloor-1$.

Prendiamo il caso $n=97$: il limite superiore per $k_M$, ovvero $(n-1/2)/e+1/2$, deve essere di pochissimo superiore all’intero più vicino, visto che il limite inferiore è separato da poco più di $1$ dal limite superiore ed è inferiore all’intero più vicino $k_M$: si ha in effetti $(97-1/2)/e+1/2=36{,}00036607\ldots$ e questo suggerisce che la frazione $\dfrac{36-1/2}{97-1/2}=\dfrac{71}{193}$ sia un’ottima approssimazione di $1/e$ e in effetti $\dfrac{71}{193}$ corrisponde alla frazione continua di $1/e$ troncata al $9$° termine: infatti $1/e=[0;2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,\ldots]$ mentre $\dfrac{71}{193}=[0;2,1,2,1,1,4,1,1]$. Proviamo a fare lo stesso ragionamento con $n=24.586$: si ha $(24586-1/2)/e+1/2=9045{,}0000009204\ldots$ e questo suggerisce che anche la frazione $\dfrac{9045-1/2}{24586-1/2}=\dfrac{18089}{49171}$ sia un’ottima approssimazione di $1/e$, ed in effetti $\dfrac{18089}{49171}=[0; 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1,1]$ corrisponde alla frazione continua di $1/e$ troncata al $15$° termine. Ma vuoi vedere che…? Passiamo a $n=14.122.865$: $(14122865­-1/2)/e+1/2=5195512{,}000000001177\ldots$ e la frazione approssimante di $1/e$ è stavolta $\dfrac{5195512-1/2}{14122865-1/2}=\dfrac{10391023}{28245729}$ che corrisponde a $[0; 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1,1]$, ovvero la frazione continua di $1/e$ troncata al $21$° termine.

Andando a ritroso, la frazione continua di $1/e$ troncata al $3$° termine, cioè $\dfrac{1}{3}$, può essere scritta come $\dfrac{1-1/2}{2-1/2}$ ed in effetti per $n=2$ vi sono due interi compresi fra il limite inferiore e superiore e $k=0$ massimizza la probabilità ma non coincide con $\left\lfloor(2-1/2)/e+1/2\right\rfloor$ (è comunque un caso particolare perché anche $k=1$ massimizza le probabilità).

Tutto questo suggerisce di andare a guardare alla frazione continua di $1/e$ troncata al $27$° termine, che è $\dfrac{10622799089}{28875761731}$ che possiamo scrivere come $\dfrac{5311399545-1/2}{14437880866-1/2}$. Che succede dunque per $n=14.437.880.866$ ? effettivamente anche in questo caso $k_M=\left\lfloor k_{sup}(n)\right\rfloor-1\ $. Questo suggerisce che $k_M=\left\lfloor k_{sup}(n)\right\rfloor$ tranne che per $n=(d_{6k+3}+1)/2$, $k \in \mathbb N$ dove $d_{6k+3}$ è il denominatore della frazione continua di $1/e$ troncata al termine $6k+3$. Non sono in grado di provare questa congettura ma la ritengo molto probabile. O forse farei meglio a dire che ho trovato una dimostrazione ma lo spazio di questo post non è sufficiente a contenerla 😉.

Riprendendo in considerazione la prima disuguaglianza della $(3)$ si ha: $$\ln\left(\dfrac{n}{k+1}\right)+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)<1 \iff \ln n-\dfrac1{2n}-1<\ln(k+1)-\dfrac1{2(k+1)}\iff$$ $$\iff \dfrac n{e^{1+\frac1{2n}}}<(k+1)e^{-\frac1{2(k+1)}}\iff \dfrac{e^{1+\frac 1{2n}}}{2n}>\dfrac 1{2(k+1)}e^{\frac 1{2(k+1)}}\ .\tag{5}$$Facciamo ora uso della funzione $W$ di Lambert, definita in $\mathbb R$ nell’intervallo $[-1/e,+\infty)$ da $x=W(x) e^{W(x)} \land W(x)\geq-1$: se nell’ultima disequazione della $(6)$ ci fosse il segno di uguaglianza si avrebbe $\dfrac 1{2(k+1)} = W \left(\dfrac{e^{1+\frac 1{2n}}}{2n}\right)$ ma poiché la funzione $W$ di Lambert è strettamente crescente, il verso della disuguaglianza rimane lo stesso e si ha $$\dfrac 1{2(k+1)}<W\left(\dfrac{e^{1+\frac 1{2n}}}{2n}\right) \iff k  > k\,'_{inf}(n)=f_W(n) = \left[ 2W \left( \dfrac{e^{1 +\frac 1{2n}}}{2n}\right)\right]^{-1}-1$$e questo pone un limite più stringente di quello della disequazione $(4)$ come si può vedere dalla figura $2$, anche se la differenza fra $k_{sup}(n)$ e $k\,'_{inf}(n)$ rimane comunque sempre superiore a $1$. Si ha infatti $$I'(n)=k_{sup}(n) - k\,'_{inf}(n) = 1+\dfrac{e^2-1}{8\,e\,n}+O\left( \dfrac1{n^2}\right) \simeq 1+\dfrac{0{,}29}{n}-\dfrac{0{,}44}{n^2},$$ e sono quindi ancora possibili, e in effetti ci sono, casi in cui la restrizione $k\,'_{inf}(n)<k_M<k_{sup}(n)$ non determini univocamente $k_M$.

Indagando da $n=1$ a $n=100.000.000$ si ha $k_M=\left\lceil f_W(n) \right\rceil$ tranne che per $n=73.757$, cosa che, con ragionamenti simili a quelli visti prima, riconduce alla frazione già vista $\dfrac{18089}{49171}$, e per $n=42.368.594$, che riconduce alla frazione, anch’essa già vista, $\dfrac{10391023}{28245729}$. In entrambi i casi $k_M=\left\lceil k\,'_{inf}(n)\right\rceil+1$. Facendo i conti, siamo portati a pensare che l’uguaglianza $k_M=\left\lceil f_W(n) \right\rceil$ valga per ogni $n$ tranne che per $n=(3\cdot d_{6k+3}+1)/2$, $k \in \mathbb N, k\geq2$, dove $k_M=\left\lceil f_W(n) \right\rceil+1$. Il valore $n$ successivo da controllare sarebbe $43.313.642.597$ e in effetti si ha lo stesso comportamento.

Sempre indagando fra $n=1$ e $n=100.000.000$, il minimo valore assunto da $k_M-k\,'_{inf}$ è circa $1{,}96\times10^{-8}$ per $n=14.122.865$ mentre il minimo valore assunto da $k_{sup}-k_M$ è circa $3{,}53\times10^{-9}$ per $n=42.368.594$. Altri valori collegati alle frazioni continue troncate di $1/e$ sono riportati in figura $4$.

Sviluppando intorno a $\infty$ la funzione $f_W(n)$ si ottiene $f_W(n)=\dfrac{n-1/2}e-\dfrac12-\dfrac{e^2-1}{8\,e\,n}+O\left(\dfrac1{n^2}\right)$ e lo sviluppo troncato togliendo gli infinitesimi di ordine superiore al primo dà gli stessi risultati nel valutare $\left\lceil f_W(n)\right\rceil$, questo almeno l’ho verificato per $n$ da $1$ a $100.000.000$ e nei valori critici collegati alle frazioni continue troncate di $1/e$ dove $f_W(n)$ più si avvicina inferiormente ad un valore intero (vedi figura $4$).

Ritornando alle frazioni continue troncate di $1/e$, tali frazioni, ovvero $\dfrac01$, $\dfrac{1}{2}$, $\dfrac{1}{3}$, $\dfrac{3}{8}$, $\dfrac{4}{11}$, $\dfrac{7}{19}$, $\dfrac{32}{87}$, $\dfrac{39}{106}$, $\dfrac{71}{193}$, $\dfrac{465}{1264},\ldots$, godono della proprietà di avere il numeratore che corrisponde al $k_M$ relativo al denominatore.

Il comportamento di $k_M$ è rappresentato nelle figure $5$, $6$, $7$ e $8$.

Veniamo ora alla probabilità di vincita usando il metodo ottimale. L’andamento è raffigurato nelle figure $9$, $10$, $11$ e $12$. Cerco uno sviluppo asintotico. Si ha $$H_n=\sum_{m=1}^n\frac1m=\ln n+\gamma+\frac1{2n}-\frac1{12n^2}+O\left(\frac1{n^4}\right)\ $$dove $\gamma$ è la costante di Eulero-Mascheroni. Applicando lo sviluppo alla $(1)$, ponendo $k=(n-1/2)/e\ $ e sviluppando in serie si ottiene$$p(n,k_M)=\dfrac1e+\dfrac{1-1/e}{2n}+O\left(\dfrac1{n^2}\right)\ .$$Si ha dunque $\displaystyle{\lim_{n\to\infty}p(n,k_M)=1/e}$. Come si vede delle figure $13$ e $14$, il termine $O\left(\dfrac1{n^2}\right)$ è oscillante fra $-\dfrac{0{,}1}{n^2}$ e $\dfrac{0{,}25}{n^2}$ per $n>6$. Indagando fra $n=7$ e $n=100.000.000$ i valori estremi di $n^2\left[p(n,k_M)-\left(\dfrac1e+\dfrac{1-1/e}{2n}\right)\right]$ sono $-0{,}0979334322999872\ldots$  per  $n=42.368.594$ (ve lo ricordate?) e $0{,}24681514\ldots$ per $n=14$. Si trovano minimi relativi (rispetto ai numeri precedenti) in corrispondenza dei valori “critici” di $n$: per $n=97$ si ha il valore $-0{,}0975406968057175\ldots$, per $n=24.586$ si ha $-0{,}0979312612917916\ldots$, per $n=73.757$ si ha $-0{,}0979321480954257\ldots$, per $n=14.122.865$ si ha $-0{,}0979334284463647\ldots$, inoltre per $n=14.437.880.866$ (un altro numero “critico”) si ha un nuovo minimo pari a $-0{,}0979334327990594\ldots$. Parrebbe che ad ogni numero “critico” si raggiunga un nuovo minimo relativo e che questi minimi convergano verso un limite… che corrisponda ad un numero particolare?

Quali sono le probabilità, usando la strategia ottimale, di scegliere il pacco di rango $m$, che indicherò $\texttt{#}m$? 

Consideriamo intanto il caso $n-k_M+1\leq m \leq n$, ovvero il caso in cui il pacco $\texttt{#}m$ è, come rango, tra gli ultimi $k_M$. In questo caso l’unica possibilità che il pacco venga scelto è che sia l’ultimo e venga scelto “forzatamente”. Infatti, se il pacco non è l’ultimo, fra i primi $k_M$ pacchi che vengono scartati ve ne è sicuramente almeno uno di rango maggiore e quindi il pacco $\texttt{#}m$ non potrà essere scelto in posizione diversa dalla ultima in quanto di rango minore del massimo dei ranghi tra i primi $k_M$ pacchi scartati. Affinché venga scelto come ultimo, il pacco $\texttt{#}1$ deve essere fra i primi $k_M$ pacchi scartati (probabilità $\frac{k_M}n$) e il pacco $\texttt{#}m$ in ultima posizione (probabilità $\frac 1{n-1})$, quindi possiamo dire che

$$n-k_M+1\leq m \leq n\ \Rightarrow\ p(n,k_M,\texttt{#}m)=\dfrac{k_M}{n(n-1)}$$

quindi complessivamente c’è una probabilità $\dfrac{k_M^2}{n(n-1)}$ di scegliere uno degli ultimi (come rango) $k_M$ pacchi, probabilità che tende a $1/e^2$ per $n$ che tende a infinito.

Per $n>1$ e $k>0$ la $(1)$ può essere riscritta come $$p(n,k,\texttt{#}1)=\sum_{j=k+1}^{n}\dfrac k{n(j-1)}\ .\tag{6}$$Se poniamo $x=k/n$ e $t=j/n$, si ha$$\lim_{n\to\infty} p(n,x\,n,\texttt{#}1)=\lim_{n\to\infty}\dfrac k n \sum_{j=k+1}^{n}\dfrac {1/n}{j/n-1/n}=x \int_{\frac1x}^1 \dfrac{dt}t=-x\ln x\ .\tag{7}$$

La funzione $-x\ln x$ ha un massimo in $x=1/e$ dove assume valore $1/e$ come ci aspettiamo, visto che per $n$ che tende a infinito $k_M/n$ tende a $1/e$ e $p(n,k_M,\texttt{#}1)$ tende a $1/e$.

Ognuno dei termini della sommatoria nella $(6)$ rappresenta la probabilità di trovare e scegliere il pacco $\texttt{#}1$ nella posizione $j$. Se invece vogliamo considerare la probabilità di trovare il pacco $\texttt{#}2$, dobbiamo moltiplicare ognuno di quei termini per la probabilità che il pacco $\texttt{#}1$ si trovi dopo il pacco $\texttt{#}2$, probabilità che vale $\dfrac{n-j}{n-1}$. L’ultimo termine della sommatoria verrà moltiplicato in realtà per $0$, ma dobbiamo aggiungere la probabilità che il pacco $\texttt{#}2$ venga scelto “forzatamente” in posizione $n$, che è pari alla probabilità che il pacco $\texttt{#}1$ sia fra i primi $k$ pacchi e che il pacco $\texttt{#}2$ sia l’ultimo. Questa probabilità è $\dfrac k{n}\cdot\dfrac1{n-1}$. Otteniamo dunque $$\displaystyle{p(n,k,\texttt{#}2)=\sum_{j=k+1}^{n} \dfrac{k(n-j)}{n(j-1)(n-1)}+\dfrac k{n(n-1)}}\ .\tag{8}$$Ora poniamo $k=k_M$ e facciamo tendere $n$ ad infinito, similmente a quanto fatto nella $(7)$ e si ha $$\lim_{n\to\infty} p(n,k_M,\texttt{#}2)=\lim_{n\to\infty} \dfrac {k_M} n \sum_{j=k_M+1}^{n}\dfrac {(1/n)(1-j/n)}{(j/n-1/n)(1-1/n)}=\dfrac1 e \int_{\frac1e}^1 \dfrac{1-t}{t}dt\ .\tag{9}$$Non mi sono cimentato nel calcolare la formula generale per $p(n,k_M,\texttt{#}m)$ per $n$ finito, ma è facile convincersi, ripetendo i ragionamenti che hanno portato alla $(8)$ e passando al limite, che, se consideriamo il caso $n$ che tende a infinito, la $(9)$ è un caso particolare della seguente identità: $$p_\infty(\texttt{#}m)=\lim_{n\to\infty}p(n,k_M,\texttt{#}m)=\dfrac1e \int_{\frac1e}^1 \dfrac{(1-t)^{m-1}}{t}dt \ .$$I valori $p_\infty(\texttt{#}m)$ sono rapidamente decrescenti: $p_\infty(\texttt{#}1)=\dfrac1e\simeq0{,}368$, $p_\infty(\texttt{#}2)=\dfrac1{e^2}\simeq0{,}135$, $p_\infty(\texttt{#}3)=\dfrac{-e^2+4e-1}{2e^3}\simeq0{,}0618$, $p_\infty(\texttt{#}4)\simeq0{,}0309$, $p_\infty(\texttt{#}5)\simeq0{,}0162\ $, $p_\infty(\texttt{#}6)\simeq0{,}00876$… Si ha inoltre $$\sum_{m=1}^\infty p_\infty(\texttt{#}m)=\sum_{m=1}^\infty \int_{\frac1e}^1 \dfrac{(1-t)^{m-1}}{e\,t}dt=\int_{\frac 1e}^1 \frac1{e\,t} \sum_{m=0}^\infty (1-t)^m dt=\int_{\frac1e}^1 \frac{dt}{e\,t^2}=1-\dfrac1e\ .$$Non sorprenda che sia $\displaystyle{\sum_{m=1}^\infty p_\infty(\texttt{#}m)\neq 1}$, in quanto in questo caso non ci sono le condizioni affinché si abbia $$\sum_{m=1}^\infty \lim_{n\to\infty} p(n,k_M,\texttt{#}m)= \lim_{n\to\infty}\sum_{m=1}^n p(n,k_M,\texttt{#}m)\ .$$In figura $15$ è riportato l’andamento di $p(n,k_M,\texttt{#}m)$ per alcuni valori di $n$ e per $n\to\infty$.

Ritornando al problema iniziale, per $n=20$ si ha $k_M=7$ e con la strategia indicata si ha il $38{,}4\%$ di probabilità di portare a casa il primo premio, ed il $16{,}3\%$ di probabilità di portare a casa il secondo premio. In totale più del $50\%$ di probabilità di portarsi a casa o il primo premio o il “premio di consolazione”: non è male per un gioco “al buio”, purché però si usi la migliore strategia.

Questo problema matematico, menzionato in genere come “problema della segretaria” o “problema del matrimonio” comparve per la prima volta in forma scritta nel febbraio 1960 nella mitica rubrica di Martin Gardner (1914-2010) su Scientific American, presentato come il “gioco del googol” (googol è il nome del numero $10^{100}$). È anche noto come “problema della dote del sultano” dove si immagina che a un pretendente venga chiesto di scegliere, fra le figlie di un sultano, quella con la dote maggiore. Un problema simile era già stato proposto dal matematico Arthur Cayley (1821-1895) dove però l’ammontare dei diversi premi è noto al giocatore. Pare che Johannes Kepler (1571-1630) abbia affrontato nella vita reale un “gioco” simile a questo dopo la morte della prima moglie nel 1611, cercando di scegliere la “migliore” sposa possibile fra 11 candidate. La cosa gli richiese due anni di “investigazioni” e, dopo avere esaminato le 11 possibili spose, alla fine scelse la 5ª. Se avesse conosciuto questo gioco e la sua soluzione, che prevede $k_M=4$ per $n=11$, forse avrebbe risparmiato molto tempo e fatica.
Maggiori dettagli sulla storia di questo problema nell’articolo di Ferguson citato in bibliografia.

__________________________

Bibliografia

John P. Gilbert and Frederick Mosteller, Recognizing the Maximum of a Sequence, Journal of the American Statistical Association Vol. 61, No. 313 (Mar., 1966), pp. 35-73 https://bit.ly/GilbMostMaxSeq

Thomas S. Ferguson, Who Solved the Secretary Problem?, Statistical Science. 4 (3): 282-289 https://bit.ly/FergusonSecretary

Wikipedia – Secretary problem https://bit.ly/WikiSecretaryProb

Figura 1. Andamento di $p(n,k)$ per diversi valori di $n$. Per $n\to\infty$ il grafico tende a quello della curva di equazione $y=-x\ln x$.

Figura 2. I punti corrispondono alle coppie $(n,k_M)$. Le coppie corrispondenti a denominatore e numeratore dello sviluppo troncato della frazione continua di $1/e$ sono rappresentate da punti cerchiati.

Figura 3. Come la precedente ma in un intervallo più ampio per $n$.

Figura 4. Andamento di $k\,'_{inf}$ e $k_{sup}$ per alcuni valori “critici” di $n$ legati allo sviluppo di $1/e$ in frazione continua. I numeri evidenziati in blu corrispondono a $k_M$.

Figura 5. Andamento del rapporto $\dfrac{k_M}{n-1/2}$ per $n$ fra $1$ e $200$.

Figura 6. Andamento del rapporto $\dfrac{k_M}{n-1/2}$ per $n$ fra $1$ e $200$, zoom attorno a $y=1/e$.

Figura 7. Andamento di $k_M-\dfrac{n-1/2}e$ per $n$ fra $1$ e $200$.
Si noti il picco negativo per $n=97$.

Figura 8. Andamento di $k_M-\dfrac{n-1/2}e$ per $n$ fra $24.500$ e $24.700$.
Si noti il picco negativo per $n=24.586$.

Figura 9. Andamento di $p(n,k_M)$ per $n$ da $1$ a $100$.

Figura 10. Andamento di $p(n,k_M)$ per $n$ da $1$ a $200$.

Figura 11. Andamento di $p(n,k_M)$ per $n$ da $1$ a $1000$.

Figura 12. Andamento di $p(n,k_M)$ per $n$ da $1$ a $20$ confrontato con quello dello sviluppo asintotico troncato.

Figura 13. Andamento della quantità $n^2\left[p(n,k_M)-\left(\dfrac1e+\dfrac{1-1/e}{2n}\right)\right]$
per $n$ fra $1$ e $200$. Si noti il picco negativo per $n=97$.

Figura 14. Andamento della quantità $n^2\left[p(n,k_M)-\left(\dfrac1e+\dfrac{1-1/e}{2n}\right)\right]$
per $n$ fra $24.500$ e $24.700$. Si noti il picco negativo per $n=24.586$.

Figura 15. Andamento di $p(n,k_M,\texttt{#}m)$ per alcuni valori di $n$ e per $n\to\infty$.

_____________________________________

Un particolare ringraziamento all’amico L. B. per la preziosa consulenza

su un argomento di cui è uno dei massimi esperti.