Olimpiadi della Matematica Torino - OliMaTO - Forum

Determinare quante sono le soluzioni di
[tex]x_0 + x_1 + x_2 + x_3 = 100[/tex] con [tex]x_0 \neq x_1[/tex] e [tex]x_i \in \mathbb N[/tex]

Hint:

Grazie per l'Hint, ma senza il vincolo non avevo problemi (vedi Callegari!).
Il mio problema è proprio il vincolo...

Ok, allora ti scrivo velocemente la soluzione:

Chiaramente senza vincolo il numero di soluzioni è $\displaystyle {103 \choose 3}$ . Troviamo ora il numero di soluzioni quando accade l'opposto, ovvero $x_0=x_1$ , basterà poi sottrarre tale numero da quello iniziale. Bisogna però precisare che, ovviamente, $0 \leq x_0,x_1,x_2,x_3 \leq 100 $ . Voglio quindi il numero di soluzioni di $2x_1+x_2+x_3=100$ .

$\bullet x_0=x_1=0 \rightarrow x_2+x_3=100 \rightarrow \displaystyle {101 \choose 1}$

$\bullet x_0=x_1=1 \rightarrow x_2+x_3=98 \rightarrow \displaystyle {99 \choose 1}$

$...$

$\bullet x_0=x_1=50 \rightarrow x_2+x_3=0 \rightarrow \displaystyle {1 \choose 1}$

Allora ovviamente il numero cercato è:

$\displaystyle \sum ^{50}_{i=0} {\displaystyle {2i+1 \choose 1}}=(51)^2$ e quindi il numero di soluzioni è:

$\displaystyle {103 \choose 3}-(51)^2$

P.S. Questo problema era facile per il numero basso di variabili, quando esse aumentano sinceramente non saprei come trovare una formula chiusa della somma dei binomiali, però le funzioni generatrici dovrebbero poter essere comode come sostitute.

Il fatto è che il problema originario era

Determinare quante sono le soluzioni di
[tex]x_0 + x_1 + x_2 + x_3 + x_4 = 9996[/tex] con [tex]x_0 \neq x_1[/tex] e [tex]x_i \in \mathbb N[/tex]

ed io, sbagliando, lo avevo semplificato per vedere se qualcuno mi aiutava a capire come calcolare in modo semplice la sommatoria dei binomiali.

Infatti, nel problema originario, la sommatoria diventa

[tex]\sum_{i=1}^{4999} \binom{2i}{2}[/tex]

che da calcolare è un po' ..... meno semplice.

In realtà in questo caso si riesce a calcolare abbastanza facilmente perché abbiamo

${2i \choose 2}=\frac{(2i)!}{(2i-2)!\cdot 2!}=2i^2-i$
quindi
$$\sum_{i=1}^{n}{2i \choose 2}=2\sum_{i=1}^{n}i^2-\sum_{i=1}^{n}i=2\cdot\frac{n\cdot(n+1)\cdot(2\cdot n+1)}{6}-\frac{n\cdot(n+1)}{2}=\frac23 n^3+\frac12 n^2-\frac16 n$$

Il calcolo sarebbe molto .... molto più complicato se l'esercizio avesse anche solo un'altra variabile in più!

Ieri ,abbastanza per caso, mi sono ricordato di questo problema. In realtà, oltre a ripetere che con le generatrici viene di sicuro, indipendentemente dal numero di variabili, basta soltanto fare i conti e sapere la somma delle prime potenze $h-$ esime. Cioè: ti sporchi le mani a trovare la somma dei binomiali, dopo di che, dato che hai sempre $k$ fissato, come vedo hai fatto nell'ultimo post, trovi un binomiale generico, ed infine lo scomponi usando le somme delle potenze. Ti faccio l'esempio con una variabile in più:

$x_0 + x_1 + x_2 + x_3 + x_4+x_5 = 100$ con $x_0 \not = x_1$ .

$\bullet x_0=x_1=0 \rightarrow x_2+x_3+x_4+x_5=100 \rightarrow \displaystyle {103 \choose 3}$

$\bullet x_0=x_1=1 \rightarrow x_2+x_3+x_4+x_5=98 \rightarrow \displaystyle {101 \choose 3}$

Ecc..

Quindi:

$\displaystyle \sum ^{51}_{i=1} {\displaystyle {2i+1 \choose 3}}$ .

Ora si vede che: $\displaystyle{2i+1 \choose 3}=\frac{(2i+1)!}{(2i+1-3)!\cdot 3!}= \dfrac {4i^3-i}{3}$

Quindi: $\displaystyle \sum ^{n}_{i=1} {\displaystyle {2i+1 \choose 3}}= \dfrac {1}{3} \cdot (4 \sum_{i=1}^{n}i^3-\sum_{i=1}^{n}i)= \dfrac {1}{6} \cdot n(n+1)(2n^2+2n-1)$

E fine, quindi facendo i conti, e sapendo le varie somme, trovi sempre la somma dei binomiali.