Funzione sui sottoinsiemi

[what]

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} $.

[xxalenicxx]

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

[enomis_costa88]

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} $

[enomis_costa88]

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.