Matematické Fórum

Akcope · 07. 11. 2013 15:33

Zdravím, mohl by mi prosím někdo poradit jak na následující úlohu:

Kolik je slov délky n v abecedě $\{a,b,c,d\}$ tak, aby a,b nikdy nesousedily?

Předem díky za rady.

Rumburak · 07. 11. 2013 16:00

Ahoj.

Napřed bych spočítal, kolik je slov délky n celkově (bez zřetele k té dodatečné podmínce)
a od tohoto mezivýsledku bych odečetl počet těch slov délky n, která onu dodatečnou
podmínku nesplňují.

Akcope · 07. 11. 2013 18:20 — Editoval Akcope (07. 11. 2013 20:51)

↑ Rumburak:

Tak slov délky n celkově je určitě $4^{n}$ .

Jak ale zjistit počet slov které tuto podmínku nesplňují?

Já na to koukal tímhle způsobem (možná je to skoro správně, prosím o kontrolu mé úvahy)

Do prvního chlívku lze určitě umístit 4 písmena. Pokud je první písmeno A nebo B, lze umístit do druhého chlívku jen 3 písmena. Pokud je C nebo D, lze tam umístit opět 4. A tak to pokračuje dále.

Takže jsem toto zprůměroval a řekl si, že výsledek by mohl být $4*3.5^{n-1}$ . Zkoušel jsem to pro n = 2,3 a fungoval. Pro n = 1 tento vzorec nefunguje a pro n = 3 hodí desetinné číslo, takže je asi třeba něco doladit. Nevíte jestli je tohle správně, a pokud ano, jak tohle zobecnit?

Rumburak

↑ Akcope:

Do prvního chlívku lze určitě umístit 4 písmena. Pokud je první písmeno A nebo B, lze umístit do druhého chlívku jen 3 písmena. Pokud je C nebo D, lze tam umístit opět 4. A tak to pokračuje dále.

To je, myslím, správná úvaha. Dejme jí nějakou formálnější podobu.

Nechť $P_n(x)$ je počet přípustných slov délky $n$ , jejichž posledním znakem je $x \in \{ a, b, c, d \}$ .
Ptejme se, jak na tomto čísle závisí $P_{n+1}(y)$ , kde rovněž $y \in \{ a, b, c, d \}$ . Musíme rozlišit několik případů:

I. $x = a$ ... přípustné jsou $y \in \{a, c, d \}$ , tedy 3 možnosti,

II. $x = b$ ... přípustné jsou $y \in \{b, c, d \}$ , tedy 3 možnosti,

III. $x = c$ ... přípustné jsou $y \in \{a, b, c, d \}$ , tedy 4 možnosti,

IV. $x = d$ ... přípustné jsou $y \in \{a, b, c, d \}$ , tedy 4 možnosti.

Odtud je také zřejmé, že

(1) $P_{n+1}(a) = P_{n}(a) + P_{n}(c) + P_{n}(d)$ ,

protože možnost $y = a$ se vyskytuje v případech I , III, IV , obdobně

(2) $P_{n+1}(b) = P_{n}(b) + P_{n}(c) + P_{n}(d)$ ,
(3) $P_{n+1}(c) = P_{n}(a) + P_{n}(b) + P_{n}(c) + P_{n}(d)$ ,
(4) $P_{n+1}(d) = P_{n}(a) + P_{n}(b) + P_{n}(c) + P_{n}(d)$ .

Dále platí

(5) $P_n(a) = P_n(b)$ , $P_n(c) = P_n(d)$ ,

protože prvek $a$ má v úloze obdobné postavení jako prvek $b$ a $c$ má obdobné postavení jako $d$ ,

Je-li $P_n$ počet všech přípustných slov délky $n$ , potom

$P_n = P_n(a) + P_n(b) + P_n(c) + P_n(d) = 2P_n(a) + 2P_n(c)$ .

Čísla $x_n := P_n(a), y_n :=P_n(c)$ získáme řešením soustavy diferenčních rovnic

$x_{n+1} = x_{n} + 2y_{n}$ ,
$y_{n+1} = 2x_{n} + 2y_{n}$

odvozené ze vztahů (1) , ... , (5). Počátečními podmínkami jsou zřejmě $x_1 = y_1 = 1$ .

Tak doufám, že tam nemám chybu.