Ešte k počtu riešení cez PIE

[Martin Sleziak]

Ešte sa vrátim k úlohe z prvej skúšky:

Nájdite počet celočíselných riešení rovnice
$$x_1+x_2+x_3=13$$
takých, že $0\le x_1 \le 4$, $0\le x_2\le 6$, $0\le x_3\le 7$.

Vlastne úlohu takéhoto typu máte vyriešenú v poznámkach na stránke.
Na fórum je píšem preto, že v tomto konkrétnom prípade sa dal využiť celkom pekný trik, ktorý riešenie zjednoduší. (Dúfam, že si niekedy nájdem čas dopísať niečo takéto aj do poznámok.)
Ale hneď na úvod napíšem aj to, že takéto niečo funguje iba niekedy, t.j. nie pri každej úlohe tohoto typu to môže pomôcť.

Najprv sa ale pozrieme na štandardné riešenia.

[Martin Sleziak]

Riešenie aké ste videli na prednáške - a máte aj v texte - je použitie princípu zapojenia a vypojenia.

Všetkých riešení je $\binom{13+2}2=\binom{15}2$.

Označme $A_1$ riešenia také, že $x_1\ge 5$; $A_2$ riešenia také, že $x_2\ge 7$ a $A_3$ riešenia také, že $x_3\ge 8$. Vieme vypočítať počty prvkov v týchto množinách a ich prienikoch, štandardným spôsobom. Napríklad pre $A_1$ sa pozeráme na $(x_1-5)+x_2+x_3=7$, pre $A_1\cap A_2$ sa pozeráme na $(x_1-5)+(x_2-7)+x_3=1$, atď. Dostaneme:
\begin{align*}\newcommand{\abs}[1]{|#1|}
\abs{A_1}&=\binom{10}2\\
\abs{A_2}&=\binom82\\
\abs{A_3}&=\binom72\\
\abs{A_1\cap A_2}&=\binom32\\
\abs{A_1\cap A_3}&=\binom22\\
\abs{A_2\cap A_3}&=\abs{A_1\cap A_2\cap A_3}=0
\end{align*}
Potom môžeme počet riešení dostať cez PIE ako
\begin{align*}
P
&=\abs{X}-\abs{A_1}+\abs{A_2}+\abs{A_3}+\abs{A_1\cap A_2}+\abs{A_1\cap A_3}+\abs{A_2\cap A_3}-\abs{A_1\cap A_2\cap A_3}\\
&=\binom{15}2-\binom{10}2-\binom82-\binom72+\binom32+\binom22\\
&=15\cdot7-5\cdot9-4\cdot7-3\cdot7+3+1\\
&=8\cdot7-5\cdot9+3+1\\
&=56-45+4\\
&=15
\end{align*}

[Martin Sleziak]

Zadané čísla boli dosť malé na to, aby sa dali vypísať všetky možnosti (čo ste na písomke viacerí aj urobili), takže sa to dá skontrolovať aj tak:

• Pre $x_1=0$ máme jedinú možnosť $0+6+7=13$.
• Pre $x_1=1$ máme $2$ možnosti $1+6+6=1+5+7=13$.
• Pre $x_1=2$ máme $3$ možnosti $2+6+5=2+5+6=2+4+7=13$.
• Pre $x_1=3$ máme $4$ možnosti $3+6+4=3+5+5=3+4+6=3+3+7=13$.
• Pre $x_1=4$ máme $5$ možností $4+6+3=4+5+4=4+4+5=4+3+6=4+2+7=13$.

Spolu dostaneme
$$1+2+3+4+5=15$$
možností.

[Martin Sleziak]

A teraz už sľúbené "trikové" riešenie. (Trikom som to nazval najmä preto, že ak človek takéto niečo predtým nevidel, tak mu to pravdepodobne nenapadne. "An idea which can be used only once is a trick. If one can use it more than once it becomes a method." - George Pólya, Gábor Szegö, Problems and Theorems in Analysis I, s .8.)

Všimnime si, že z $x_1+x_2+x_3=13$ dostaneme $$(4-x_1)+(6-x_2)+(7-x_3)=4.$$
Ak si teda označíme $y_1=4-x_1$, $y_2=6-x_2$, $y_3=7-x_3$, tak riešime rovnicu
$$y_1+y_2+y_3=4$$
s obmedzeniami $0\le y_1\le 4$, $0\le y_2\le 6$, $0\le y_3\le 7$.
Pretože súčet je $4$, tak tieto obmedzenia spĺňa úplne každé riešenie, takže vlastne stačí nájsť počet všetkých riešení $y_1+y_2+y_3=4$ v nezáporných celých číslach, čo je presne
$$\binom{4+2}2=\binom62=15.$$

Znovu upozorním, že to bola viacmenej šťastná náhoda, že po vhodnej substitúcii sme dostali, že vlastne stačí spočítať všetky riešenia. Ale možno sa oplatí zapamätať si takúto vec - v podobných situáciách skúsiť, či nám vhodná substitúcia nemôže náhodou zjednodušiť situáciu.