Zbiór zadań, (zadania różne)
Zadanie 308
Ile rozwiązań w liczbach naturalnych ma nierówność $n_1 + n_2 + n_3 + \ldots + n_{13} \le 13$?
Rozwiązanie
Rozpatrzmy problem ogólny: ile rozwiązań w liczbach naturalnych ma nierówność $a_1 + a_2 + \ldots + a_k \le n$.
Interesuje nas liczba ciągów $(a_1, \ldots, a_k)$ takich, że $a_1 + \ldots + a_k \le n$
Niech $A_i = a_1 + \ldots + a_i + i$ dla $i = 1, \ldots, k$
Ciąg $(A_1, \ldots, A_k)$ jest rosnący i ma wyrazy w zbiorze $\{1, 2, \ldots, n+k\}$.
Dla dowolnego ciągu rosnącego $(B_1, \ldots, B_k) \subset \{1, 2, \ldots, n+k\}$ podstawiając za $a_1 = B_1-1$ oraz $a_i = B_i - B_{i-1}-1$ dla $i = 2, \ldots, k$, otrzymujemy ciąg $(a_1, \ldots, a_k) \subset \{0, 1, \ldots, n\}$ taki, że $a_1 + a_2 + \ldots + a_k \le n$.
Stąd rozwiązań nierówności jest tyle, co $k$-wyrazowych ciągów rosnących o wyrazach w zbiorze $\{1, 2, \ldots, n+k\}$, czyli ${n+k \choose k}$.
Dla $k = n = 13$ liczba rozwiązań równa jest $10400600$.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>