Intorno la media aritmetica dei minimi

[salva90]

Sia $ 1\le r\le n $ e si considerino tutti i sottoinsiemi di r elementi dell'insieme $ \{1, ~2,\dots,~n\} $. Ognuno di questi sottoinsiemi ha un elemento minimo. Sia $ F(n,~r) $ la media aritmetica di questi minimi; provare che

$ \displaystyle F(n,~r)=\frac{n+1}{r+1} $

Dovrebbe essere un IMO 1981... io l'ho preso dall'Engel. La mia soluzione è a dir poco orrida mentre quella del testo è carina... su provateci

[Alex89]

Fatto 1.Nei sottoinsiemi di r elementi, il minimo di ogni sottoinsieme è compreso tra 1 e n-r+1.

Fatto 2.Dato un numero $ 1 \le k \le n+1-r $ i sottoinsiemi che hanno k come minimo sono $ \displaystyle\binom{n-k}{r-1} $.


Fatto 3.$ \displaystyle\sum_{k=1}^{n+1-r}\binom{n-k}{r-1}=\binom{n}{r} $

Poichè somma di una diagonale del triangolo di tartaglia.

Ora,iniziamo

Sia S(n) la somma di tutti i minimi.

$ S(n)=\displaystyle\sum_{k=1}^{n+1-r}\binom{n-k}{r-1}k $
Su questo credo siamo tutti d'accordo.
Ora:

$ S(n)=\displaystyle\sum_{k=1}^{n+1-r}\binom{n-k}{r-1}k $
da cui
$ S(n)=\binom{n-1}{r-1}1+\binom{n-2}{r-1}2+...+(n+1-r)\binom{r-1}{r-1} $

Questa cosa io la posso riarrangiare come:

$ S(n)=[\binom{n-1}{r-1}+...+\binom{r-1}{r-1}]+[\binom{n-2}{r-1}+...+\binom{r-1}{r-1}]+...+[\binom{r-1}{r-1}] $

Per il fatto 3 io ho che

$ S(n)=\binom{n}{r}+\binom{n-1}{r}+...+\binom{r}{r} $

Usando ancora il fatto 3 ho che S(n) è somma di una diagonale del triangolo di tartaglia e quindi

$ S(n)=\binom{n+1}{r+1} $

Ora per la definizione di media aritmetica io ho che:
$ F(n,r)=\frac{S(n)}{\binom{n}{r}}=\frac{\binom{n+1}{r+1}}{\binom{n}{r}}=\frac{n+1}{r+1} $

[Marco]

Soluzione per induzione.

Complichiamo un po' il problema, e indichiamo con $ G(n,r,k) $ la media del $ k $-esimo elemento delle $ r $-uple ordinate con elementi da $ 1 $ a $ n $. ($ k $ varia da 1 a $ r $).

Ad esempio, la media dei minimi sara' $ F(n,r) = G(n,r,1) $, mentre la media dei massimi sara' $ G(n,r,r) $.

Dico che
$ $ G(n,r,k) = k \frac{n+1}{r+1} $.

Do la seguente interpretazione combinatoria: supponiamo di avere un'urna con $ n $ bussolotti; $ r $ di essi sono rossi e i restanti bianchi.

Vuoto l'urna estraendo un bussolotto per volta e segno il numero d'ordine delle palle rosse. In questo modo estraggo con probabilita' uniforme una $ r $-upla ordinata.

$ G(n,r,k) $ e' il numero atteso di estrazioni per trovare $ k $ bussolotti rossi.

Vediamo ora l'induzione: se $ n = 1 $, allora $ G(1,1,1) = 1 $.

Supponiamo allora vera l'induzione e di conoscere il valore di $ G(n-1, \cdot, \cdot) $.

Ci chiediamo quanto vale $ G(n,r,k) $. Estraiamo il primo bussolotto dalla nostra urna. Con probabilita' $ \frac{r}{n} $ sara' rosso, altrimenti con probabilita' $ \frac{n-r}{n} $ sara' bianco.

Primo caso: il primo bussolotto estatto e' rosso.

Resto con un urna con $ n-1 $ bussolotti, di cui $ r-1 $ rossi. Ne ho gia' estratto uno rosso, quindi me ne restano altri $ k-1 $ per averne $ k $ rossi. Ne segue che il numero atteso di estrazioni ulteriori e' $ G(n-1, r-1, k-1) $. Sommando a questo la prima estrazione, significa che il numero atteso di estrazioni e'

$ G(n-1, r-1, k-1) +1 $ (*)

Secondo caso: il primo bussolotto estatto e' bianco.

Resto con un urna con $ n-1 $ bussolotti, di cui $ r $ rossi, e ne devo ancora estrarre $ k $. Ragionando come prima, il numero atteso di estrazioni e'

$ G(n-1, r, k) + 1 $.

Notate che non puo' succedere che $ n-1 $ diventi minore di $ r $, in quanto allora la probabilita' del secondo caso sarebbe zero.

Facendo la media tra i due eventi, si trova che il numero medio di estrazioni e'

$ $ G(n,r,k) = \frac{r}{n} G(n-1, r-1, k-1) + \frac{n-r}{r} G(n-1, r, k) + 1 $.

Applicate l'ipotesi induttiva, fate il conto e torna. []


(*) Qui ho commesso un piccolo abuso di notazione, e ho posto $ \scriptstyle G(\cdot, \cdot, 0) = 0 $ (i.e., mi bastano zero estrazioni per trovare zero bussolotti rossi)