msleziak.com

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.

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. 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$. Teraz už stačí poskladať dokopy veci, ktoré sme doteraz zistili, a vyjadriť z nich $E_n$ a $O_n$.