OliForum Matematico

IMO 81, problema 2.
Sia $ 1\leq r\leq n $, e consideriamo tutti i sottoinsiemi di r elementi di {1,2,...,n}. Ogni sottoinsieme ha un elemento minimo. Sia $ F_{n,r} $ la media aritmetica di questi elementi minimi.
Dimostrare che $ F_{n,r}=\frac{n+1}{r+1} $.

Il numero di tutti i possibili sottoinsiemi di r elementi sono C(n,r) dove con C(n,r) indico le combinazioni di n elementi su k posizioni (il coefficiente binomiale). Adesso enumeriamo tutti i possibili minimi. Ad esempio se volessimo che il minimo dei sottoinsiemi sia 1, allora tutti gli insiemi che hanno uno come elemento minimo sono C(n-1,r-1), se volessimo che il minimo sia 2, tutti gli insiemi che hanno 2 come elemento minimo sono C(n-2, r-1) (n-2 perchè non deve esserci l'1 altrimenti sarebbe lui il minimo), e così via, quindi possiamo dire che:

$ F_{n,r} =\frac{ \sum_{k=1}^{n+1-r}{k \cdot C(n-k,r-1)}}{C(n,r)} $

Concentriamoci sulla sommatria:

$ \sum_{k=1}^{n+1-r}{k \cdot C(n-k,r-1)} = \sum_{k=r-1}^{n-1}{(n-k) \cdot C(k,r-1)} $ = $ C(n+1,r+1) $

In effetti non ho trovato un modo diretto ed elegante per dimostrare questa uguaglianza, però la si può dimostrare per induzione :

Caso base: n = r
1*C(r-1,r-1) = C(r+1,r+1) = 1

Passo induttivo:

$ \sum_{k=r-1}^{n}{(n+1-k) \cdot C(k,r-1)} $ =$ \sum_{k=r-1}^{n}{(n-k) \cdot C(k,r-1)}+ \sum_{k=r-1}^{n}{C(k,r-1)} $ =
= $ C(n+2,r+1) $

$ \sum_{k=r-1}^{n}{C(k,r-1)} = C(n+1,r) $ quindi
$ C(n+1,r+1) + C(n+1,r) = C(n+2, r+1) $

In fine quindi: $ F_{n,k} = \frac{C(n+1,r+1)}{C(n,r)} = \frac{n+1}{r+1} $

Spero di esser stato chiaro. Vorrei chiedervi invece se qualcuno mi fa vedere come si dimostra l'uguaglianza senza passare per induzione. Grazie

Ecco una soluzione alternativa che non usa l'induzione..

Step 1: $ \displaystyle \sum_{i=r}^{n}{i\choose r} = {n+1 \choose r+1} $

Sia considerato l'insieme {1,..,n,n+1}; il numero di sottoinsiemi di r+1 elementi di questo insieme è $ {n+1 \choose r+1} $.
Il numero di sottinsiemi di r+1 elementi il cui max sia i+1 è $ {i\choose r} $ poiché ho già scelto il massimo e devo scegliere altri r elementi tra gli i elementi minori di quello scelto.
Il minimo numero massimo sceglibile è r+1 poiché altrimenti non potrei trovare r elementi minori.
Il numero di sottinsiemi di r+1 elementi è quindi anche $ \sum_{i=r}^{n}{i\choose r} $

Step 2: $ \displaystyle \sum_{i=1}^{n-r+1}{n-i\choose r-1}i = {n+1 \choose r+1} $

Considero i sottinsiemi di {1,..,n,n+1} con r+1 elementi.
Siano $ A_1\ge A_2 \ge .. \ge A_{r+1} $ gli elementi di questi sottinsiemi. So per ipotesi che r>0 quindi esiste $ A_r $.
Il numero di sottinsiemi di r+1 elementi nei quali $ A_r = i+1 $ è dato dal numero di modi per scegliere $ A_{r+1} $ tra i numeri minori di i+1 e dal numero di modi di scegliere i rimanenti r-1 elementi tra i numeri maggiori di i+1 ovvero:
$ {i+1-1\choose 1}{n+1-(i+1)\choose r-1}={n-i\choose r-1}i $
Quindi il numero di sottinsiemi di r+1 elementi è anche $ \sum_{i=1}^{n-r+1}{n-i\choose r-1}i $

Step 3: $ \displaystyle \sum_{A\subseteq \{1,..,n\};|A|=r} max A $ = $ \displaystyle r\sum_{A\subseteq \{1,..,n\};|A|=r} min A $

Il numero di sottinsiemi di r elementi il cui max sia i è $ {i-1\choose r-1} $ poiché ho già scelto il massimo e devo scegliere altri r-1 elementi tra gli i-1 elementi minori di quello scelto. Ovvero:
$ \displaystyle \sum_{A\subseteq \{1,..,n\};|A|=r} max A $ = $ \displaystyle \sum_{i=r}^{n}{i-1\choose r-1}i $ = $ \displaystyle \sum_{i=r}^{n}{i\choose r}r $

Inoltre:
Il numero di sottinsiemi di r elementi il cui minimo sia i è $ {n-i \choose r-1} $poiché ho già scelto il minimo e devo scegliere altri r-1 elementi tra gli n-i elementi maggiori di quello scelto. Ovvero:
$ \displaystyle \sum_{A\subseteq \{1,..,n\};|A|=r} min A $= $ \displaystyle \sum_{i=1}^{n-(r-1)}{n-i\choose r-1}i $

Devo quindi dimostrare che
$ \displaystyle r\sum_{i=1}^{n-(r-1)}{n-i\choose r-1}i $ = $ \displaystyle \sum_{i=r}^{n}{i\choose r}r $
ovvero:
$ \displaystyle \sum_{i=1}^{n-(r-1)}{n-i\choose r-1}i $= $ \displaystyle \sum_{i=r}^{n}{i\choose r} $
e per lo step 1: $ \displaystyle \sum_{i=r}^{n}{i\choose r} = {n+1 \choose r+1} $
e per lo step 2: $ \displaystyle \sum_{i=1}^{n-r+1}{n-i\choose r-1}i = {n+1 \choose r+1} $
quindi: $ \displaystyle \sum_{i=1}^{n-(r-1)}{n-i\choose r-1}i $= $ \displaystyle \sum_{i=r}^{n}{i\choose r}= {n+1 \choose r+1} $

Step 4: $ \displaystyle \sum_{A\subseteq \{1,..,n\};|A|=r} min A + max A $= $ \displaystyle (n+1){n \choose r} $

Noto che:
$ \displaystyle \sum_{i=1}^{n-r+1}{n-i \choose r-1}( n+1-i) $= $ \displaystyle \sum_{i=r}^{n}{i-1\choose r-1}i $
$ \displaystyle \sum_{i=1}^{n-r+1}{n-i \choose r-1} $= $ \displaystyle \sum_{i=r-1}^{n-1}{i\choose r-1} $
Per quanto detto:
$ \displaystyle \sum_{A\subseteq \{1,..,n\};|A|=r} min A + max A $
$ \displaystyle =(\sum_{i=1}^{n-r+1}{n-i \choose r-1}i +\sum_{i=1}^{n-r+1}{n-i \choose r-1}( n+1-i) $
$ \displaystyle = ((n+1) \sum_{i=1}^{n-r+1}{n-i \choose r-1}) $
$ \displaystyle =(n+1)\sum_{i=1}^{n-r+1}{n-i \choose r-1} $ = $ \displaystyle (n+1)\sum_{i=r-1}^{n-1}{i\choose r-1} $ = $ \displaystyle (n+1){n \choose r} $

Step 5: conclusione.

Per gli step 3 e 4:
$ \displaystyle (n+1){n \choose r} $= $ \displaystyle \sum_{A\subseteq \{1,..,n\};|A|=r} min A + max A $ $ \displaystyle =\sum_{A\subseteq \{1,..,n\};|A|=r} min A + r (min A) $
$ \displaystyle =(r+1) \sum_{A\subseteq \{1,..,n\};|A|=r} min A $
ovvero:
$ \displaystyle \sum_{A\subseteq \{1,..,n\};|A|=r} min A $ = $ \displaystyle \frac{n+1}{r+1}{n \choose r} $
Quindi:
$ \displaystyle F_{n,r}=\frac{\sum_{A\subseteq \{1,..,n\};|A|=r} min A }{{n \choose r}} $= $ \displaystyle \frac{n+1}{r+1} $

Scusa "xxalenicxx" non avevo letto la tua soluzione prima di postare..
ora che l'ho letta mi rendo conto che sarebbe bastato il mio step 2 per concludere senza andare troppo per le lunge (però non avrei dimostrato un po' di cose interessanti)

Bè la dimostrazione combinatorica di quell'uguaglianza dovrebbe essere quella dello step 2 (al solito a meno di granchi).

Buona serata, Simone.