Párny a nepárny počet zložiek v slove

[Martin Sleziak]

Uvažuje množinu slov v abecede $A=\{modrá, červená, biela\}$ dĺžky $n$. Koľko slov má párny počet zložiek rovný červená? Ako by to dopadlo pre nepárny počet červených zložiek?

Je to úloha 1 z 07cvicenie_cesty.pdf.
Dostal som otázku, kde bolo napísané, že nie je jasné ako je zadanie myslené.

Konkrétne príklady

Označme si teda farby ako R, G, B (red green blue).

Napríklad slovo RRG má párny počet červených zložiek, slovo RRR nepárny.

Keď si prejdeme malé prípady, tak slová s nepárnym počtom zložiek R sú:
Dĺžky 1: $R$;
Dĺžky 2: $RB$, $RG$, $GR$, $GB$;
Skúste vy, či by ste vedeli prísť na to koľko je takých slov dĺžky 3.

Ak si $E_n$ označíme počet párnych slov (slov s párnym počtom výskytov R) a $O_n$ počet nepárnych slov, tak by ste mali dostať takéto hodnoty:

$$
\begin{array}{c|c|c}
n & E_n & O_n \\\hline
0 & 1 & 0 \\
1 & 2 & 1 \\
2 & 5 & 4 \\
3 & 14 & 13 \\
\end{array}
$$

K riešeniu

Hint k riešeniu:
Vedeli by ste niečo povedať o $O_n+E_n$.
Ak poznáme predošlé hodnoty, vieme nejako vyjadriť $O_{n+1}$ a $E_{n+1}$.

P.S. Keďže vlastne jedna skupina riešenie tejto úlohy videla, tak môžete pomôcť kolegom z druhej skupiny, ak sem riešenie napíšete.

[Martin Sleziak]

Zaoberáme sa teda slovami dĺžky $n$ v abecede $\{R,G,B\}$.
Označili sme teda $O_n$ počet slov, ktoré majú nepárny počet výskytov $R$; symbol $E_n$ označuje tie, ktoré majú párny počet výskytov $R$.

Pretože spolu dostaneme všetky slová, vieme, že $E_n+O_n=3^n$.

Ďalej je rozumné zamyslieť sa nad tým, či vieme vypočítať $O_{n+1}$ a $E_{n+1}$, ak poznáme predošlé hodnoty.

Spoiler:

Pozrime sa na nepárne slová dĺžky $n+1$.
Ak je na poslednom mieste $R$, tak na prvých $n$ miestach musí byť párny počet výskytov $R$. Takýchto slov je teda $E_n$.
Podobne ak je na poslednom mieste $G$ alebo $B$, tak na prvých $n$ miestach bude nepárny počet $R$. Teda mám $2O_n$ takýchto slov.
Zistili sme, že $O_{n+1}=E_n+2O_n$. Veľmi podobnými úvahami vieme dostať vzťah pre $E_{n+1}$.
\begin{align*}
O_{n+1}&=E_n+2O_n\\
E_{n+1}&=2E_n+O_n
\end{align*}

Ak už máme rekurentný predpis ako vypočítať $E_{n+1}$, $O_{n+1}$ z $E_n$ $O_n$, tak sa môžeme skúsiť zamyslieť, či z toho neviem odvodiť nejaký nový vzťah, ktorý nám niečo povie o $E_n$ a $O_n$.

Spoiler:

Máme dve rovnice
\begin{align*}
O_{n+1}&=E_n+2O_n\\
E_{n+1}&=2E_n+O_n
\end{align*}
Stačí si všimnúť, že ich odčítaním dostaneme
$$E_{n+1}-O_{n+1}=E_n-O_n.$$
Z toho vidno, že rozdiel $E_n-O_n$ bude pre každé $n$ rovnaký.
Takže dostávame $E_n-O_n=E_1-O_1=1$.

Teraz už stačí poskladať dokopy veci, ktoré sme doteraz zistili, a vyjadriť z nich $E_n$ a $O_n$.

Spoiler:

Máme dve rovnice
\begin{align*}
E_n+O_n&=3^n\\
E_n-O_n&=1
\end{align*}
Z tejto sústavy ľahko vyjadríme
\begin{align*}
E_n&=\frac{3^n+1}2\\
O_n&=\frac{3^n-1}2
\end{align*}