Počet celočíselných riešení

[Martin Sleziak]

Na písomke sa vyskytli príklady takéhoto typu:

Skupina A

Aký je počet celočíselných riešení rovnice
$$x_1+x_2+x_3+x_4=14$$
takých, že $x_1\ge2$, $x_2\ge3$, $x_{3,4}\ge0$? (Inak povedané, máte nájsť počet prvkov tejto množiny usporiadaných štvoríc: $\{(x_1,x_2,x_3,x_4)\in\mathbb Z^4; x_1+x_2+x_3+x_4=14, x_1\ge2, x_2\ge3, x_3\ge0, x_4\ge0\}$.)

Skupina B

Aký je počet celočíselných riešení rovnice
$$x_1+x_2+x_3+x_4=16$$
takých, že $x_1\ge2$, $x_2\ge5$, $x_{3,4}\ge0$? (Inak povedané, máte nájsť počet prvkov tejto množiny usporiadaných štvoríc: $\{(x_1,x_2,x_3,x_4)\in\mathbb Z^4; x_1+x_2+x_3+x_4=16, x_1\ge2, x_2\ge5, x_3\ge0, x_4\ge0\}$.)

Čo sa týka ostatných príkladov z písomky, tak k väčšine identít už na fóre bolo niečo napísané. (Keďže sa na tieto sumy niektorí pred písomkou pýtali.) Výnimkou je jedna suma. K nej niečo napíšem. Takisto aj k poslednému príkladu (slovná úloha - počítanie možností). Samozrejme, ak by ste mali nejaké ďalšie otázky k veciam, čo sú napísané na fóre, alebo ak k niečomu treba napísať detailnejšie riešenie, tak sa pýtajte.

Písomku som bodoval podobným spôsobom ako prvú -- t.j. 15 bodov som bral ako plný počet. (Ospravedlňujem sa, že mi obodovanie trvalo tak dlho.)
Ak si budete chcieť pozrieť svoju písomku, tak sa k nej dostanete napríklad na niektorom skúškovom termíne.

[Martin Sleziak]

Riešenia

Ako štandardný postup som očakával to, že prevediete úlohu na počet celočíselných riešení
$$y_1+\dots+y_n=k, \qquad y_i\ge0,$$
o ktorom z prednášky viete, že to je
$$\binom{n+k-1}k.$$

(Samozrejme, mohli ste to previesť na tvar s podmienkou $\ge1$ namiesto $\ge0$, ak si pamätáte tento vzorece.)

Skupina A

Zadanú rovnicu
$$x_1+x_2+x_3+x_4=14$$
môžeme ekvivalentne prepísať ako
$$(x_1-2)+(x_2-3)+x_3+x_4=9.$$
Teda vlastne hľadáme počet riešení
$$y_1+y_2+y_3+y_4=9$$
takých, že $y_i\ge 0$. Ten je $$\binom{9+3}3=\binom{12}3=220.$$

Skupina B

Zadanú rovnicu
$$x_1+x_2+x_3+x_4=16$$
môžeme prepísať ako
$$(x_1-2)+(x_2-5)+x_3+x_4=9.$$
Teda vlastne hľadáme počet riešení
$$y_1+y_2+y_3+y_4=9$$
takých, že $y_i\ge 0$. Ten je $$\binom{9+3}3=\binom{12}3.$$

Prevod na výber podmnožín

Keďže ste sa to niektorí pokúšali riešiť takto, tak napíšem aj takéto riešenie.

Chceme nájsť počet možností pre $x_1+x_2+x_3+x_4=14$, kde $x_1\ge2$, $x_2\ge3$, $x_3,x_4\ge0$.

Ak poznáme súčty
\begin{align*}
s_1&=x_1\\
s_2&=x_1+x_2\\
s_3&=x_1+x_2+x_3
\end{align*}
tak nimi sú už $x_1$, $x_2$, $x_3$, $x_4$ jednoznačne určené.

Tieto čísla musia očividne spĺňať podmienky $0\le s_1\le s_2\le s_3\le 14$.
Navyše máme $x_1\ge2$, čo je to isté ako $s_1\ge 2$.
Ešte chceme aby $x_2\ge 3$, čo nám hovorí, že $s_2\ge s_1+3$.
Teda podmienky na $s_1$, $s_2$, $s_3$ môžeme zapísať ako tieto nerovnosti:
$$2\le s_1 \le s_2-3 \le s_3-3 \le 11.$$
Ešte ich trochu pozmeňme tak, aby sme mali ostré nerovnosti:
$$2\le s_1 < s_2-2 < s_3-1 \le 13.$$
Teda počet hľadaných možností je rovnaký ako počet možností na výber trojprvkovej podmnožiny $\{s_1,s_2-2,s_3-1\}$ z 12-prvkovej podmnožiny $\{2,3,\dots,12,13\}$, teda ako výsledok dostaneme $\binom{12}3$.

[Martin Sleziak]

Vypisovanie možností

Niektorí ste úlohu skúšali riešiť vypisovaním všetkých možností. Keďže som ako štandardné riešenie bral použitie známeho vzorca, tak som sa nijako nesnažil pri príprave zadaní dať pozor na to, aby bol výsledok dosť malý na to, aby ste stále mohli všetky riešenia vypísať.

Očividne sa to viacerým z vás podarilo vyriešiť takto. (Alebo dostať aspoň k číslu, ktoré nebolo veľmi ďaleko od správneho výsledku.) Takže aj takáto cesta bola schodná.

Chcel by som však poznamenať, že keď si to človek začne vypisovať, tak sa možno dá zbadať nejaká zákonitosť a potom už prísť k nejakému výsledku aj bez toho, aby skutočne vypísal všetky riešenia.

Pozrime sa na skupinu A, t.j. riešime
$$x_1+x_2+x_3+x_4=14$$
za podmienok $x_1\ge2$, $x_2\ge3$, $x_{3,4}\ge0$.

Začnime s najmenšími možnými hodnotami $x_1$ a $x_2$, t.j. ak $x_1=2$, $x_2=3$. Všetky možnosti sú
$$
\begin{array}{|c|c|c|c|}
\hline
x_1 & x_2 & x_3 & x_4 \\\hline
2 & 3 & 0 & 9 \\\hline
2 & 3 & 1 & 8 \\\hline
2 & 3 & 2 & 7 \\\hline
2 & 3 & 3 & 6 \\\hline
2 & 3 & 4 & 5 \\\hline
2 & 3 & 5 & 4 \\\hline
2 & 3 & 6 & 3 \\\hline
2 & 3 & 7 & 2 \\\hline
2 & 3 & 8 & 1 \\\hline
2 & 3 & 9 & 0 \\\hline
\end{array}
$$
Dostali sme $10$ možností.

Ak sa stále pozeráme na $x_1=2$, najbližšia väčšia možnosť pre $x_2$ je $x_2=4$. Všetky možnosti sú
$$\begin{array}{|c|c|c|c|}
\hline
x_1 & x_2 & x_3 & x_4 \\\hline
2 & 4 & 0 & 8 \\\hline
2 & 4 & 1 & 7 \\\hline
2 & 4 & 2 & 6 \\\hline
2 & 4 & 3 & 5 \\\hline
2 & 4 & 4 & 4 \\\hline
2 & 4 & 5 & 3 \\\hline
2 & 4 & 6 & 2 \\\hline
2 & 4 & 7 & 1 \\\hline
2 & 4 & 8 & 0 \\\hline
\end{array}$$
Dostali sme $9$ možností.

V prvom prípade sme potrebovali nájsť všetky možnosti také, kde $x_3+x_4=9$; tých bolo $10$ (od dvojice $(0,9)$ až po dvojicu $(9,0)$).
Podobne v druhom prípade sme našli $9$ možností pre $x_3+x_4=8$.

Snáď už teraz vidno, že pre $x_1=2$ máme niečo takéto
$$\begin{array}{|c|c|c|c|}
\hline
x_1 & x_2 & \text{počet} \\\hline
2 & 3 & 10\text{ možností} \\\hline
2 & 4 & 9\text{ možností} \\\hline
2 & 5 & 8\text{ možností} \\\hline
2 & 6 & 7\text{ možností} \\\hline
2 & 7 & 6\text{ možností} \\\hline
2 & 8 & 5\text{ možností} \\\hline
2 & 9 & 4\text{ možností} \\\hline
2 &10 & 3\text{ možností} \\\hline
2 &11 & 2\text{ možností} \\\hline
2 &12 & 1\text{ možností} \\\hline
\end{array}$$

Spolu pre $x_1=2$ máme
$$10+9+8+\dots+2+1=\frac{10\cdot11}2=\binom{11}2$$
možností.

Podobne by sme sa vedeli pozrieť na prípady $x_1=3$, $x_1=4$ atď. (Posledný bude $x_1=11$.) Zistíme, že spolu dostávame
$$\binom{11}2+\binom{10}2+\dots+\binom32+\binom22=\binom{12}3.$$
Binomický koeficient na pravej strane sme mohli napísať vďaka tomu, že poznáme hokejkovú identitu. Zrátateľné by to bolo aj bez nej. (Spočítať dokopy 10 binomických koeficientov nie je až taká veľká námaha.)
A myslím si, že podobnými úvahami (rátaním počtu riešení sústav) by sme asi boli schopní hokejkovú identitu aj odvodiť.

[Martin Sleziak]

Poznámky k vašim riešeniam

Niektorí ste to posúvali tak, aby ste dostali novú rovnicu, kde riešenia mali vyhovovať podmienkam $x_i\ge1$. (Čo je úplne ok - závisí od toho, ktorý vzorec si pamätáte, resp. ktorý viete ľahšie odvodiť.) Pre počet riešeníe $x_1+\dots+x_n=k$ s obmedzením $x_i\ge1$ by ste mali dostať
$$\binom{k-1}{n-1}.$$
(Je to vyriešené aj v poznámkach, v súčasnom číslovaní je to príklad 5.2.10.)

Niektorí ste chceli urobiť niečo také, že by ste zrátali všetky riešenia zadanej rovnice a potom odpočítali "zlé" riešenia. Také niečo sme robili, keď tam boli nerovnosti opačným smerom, t.j. mali sme horné ohraničenie na niektoré premenné. (Máte niečo takéto vypočítané v poznámkach a aj sme to robili na prednáške.)

Riešenie, kde sa také niečo vyskytlo, bolo vypočítať počet riešení takých, kde $x_1=0$, $x_1=1$ a potom sa pozrieť na riešenia kde $x_2=0, x_2=1,\dots,x_2=5$. To je v princípe niečo, čo by viedlo k riešeniu, ale museli by sme tam riešiť veľa rôznych kombinácií pre $x_1$ a $x_2$.