lista-0.md

lang	title	author
pl	Lista 0	Jerry Sky

---

• Zadanie 1.
• Zadanie 2.
• Zadanie 3.

---

Zadanie 1.

Udowodnić, że najdłuższa ścieżka od korzenia do liścia w dowolnym drzewie binarnym o $n$ wierzchołkach ma co najmniej $\lfloor\log_2n\rfloor$ krawędzi.

Musimy sprawdzić jak sytuacja wygląda dla drzew zbalansowanych, jako że to drzewa zbalansowane mają najkrótsze «drogi najdłuższe». Innymi słowy — chodzi o drzewa o jak najmniejszej wysokości.

Bez straty ogólności niech $$ n = 2^k + l\ \text{gdzie } l \in [0; 2^k) \cap \mathbb{N} $$

Warto zauważyć, że w przypadku drzewa zbalansowanego dodajemy kolejne węzły na tym samym „poziomie” i nie zaczynamy dodawać węzłów na następnych „poziomach” jeśli jest jeszcze miejsce na aktualnym.

$$ 2^0 + 2^1 + 2^2 + \dotsb + 2^k = 2^{k+1} - 1 $$

(korzystamy z zadania 3.2. przy tamtejszym $k=2$)

Dalej, widzimy, że wysokość naszego drzewa jest taka sama dla liczby węzłów w przedziale $[2^k; 2^{k+1} - 1]$ i wynosi ona dokładnie $k$ co zgadza się z tym czego oczekiwaliśmy:
wynik logarytmu „spłaszczamy”, bierzemy część całkowitą: $$ \lfloor \log_2(2^k + l) \rfloor = log_2(2^k) = k $$

$k$ — liczba o 1 mniejsza niż liczba węzłów na najdłuższej drodze czyli liczba krawędzi.

---

Zadanie 2.

Uogólnij zadanie 1. na drzewo, w którym każdy wierzchołek ma co najwyżej $\cancel{k}$ $p$ synów.

Dokonujemy zmian w powyższych rozważaniach:

• zamieniamy $2$ na żądaną zmienną
• zamieniamy sumę $\sum_{i=0}^{k+1}2^i = 2^{k+1} - 1$ na sumę $\sum_{i=0}^{k+1}p^i = \frac{p^{k+1} - 1}{p - 1}$
• zmieniamy przedział: $l \in \left[0; p^{k}\cdot(p-1)\right)\cap \mathbb{N}$

---

Zadanie 3.

Mamy alfabet złożony z $k$ symboli. Policz ile jest:

1. wszystkich różnych słów długości $n$ nad tym alfabetem

   $$ 1 \cdot \underbrace{k \cdot k \cdot \dotsb k}_{n \text{ razy}} = k^n $$

   ponieważ za każdym razem mamy $k$ możliwości do wyboru litery a potrzebujemy dobrać $n$ liter.

   1. $n=0$: $1 = k^0$ — mamy jedno słowo puste — zgadza się
   2. $n\implies n+1$:
      mamy $\underbrace{k \cdot k \cdot \dotsb k}{n \text{ razy}} = k^n$
      doklejamy nową literę: dla każdej litery (mamy ich $k$) mamy osobno nowych $k^n$ słów; zatem:
      $\underbrace{k^n + k^n + \dotsb + k^n}{k\text{ razy}} = k \cdot k^n = k^{n+1}$

---

2. wszystkich różnych słów długości co najwyżej $n$

   Dowód tradycyjny:
   Niech $$ \sum_{i=0}^{n}k^i = S_n $$

   Wówczas:

   $$ S_n = \sum_{i=0}^{n}k^i\ //\cdot k \ S_n \cdot k = \sum_{i=1}^{n+1}k^i \ S_n \cdot k = S_n - 1 + k^{n+1}\ //-S_n \ S_n \cdot (k - 1) = k^{n+1} - 1 \ \blacksquare $$

   Dowód indukcyjny: $$ \sum_{i=0}^{n}k^i

   \frac{k^{n+1} - 1}{k-1} $$

   1. $n=0$: $1 = k^0 = \frac{k^{1} - 1}{k-1} = 1$ — zgadza się
   2. $n \implies n+1$: $$ \sum_{i=0}^{n}k^i = \frac{k^{n+1} - 1}{k-1}\ // + k^{n+1} \ \sum_{i=0}^{n+1}k^i = \frac{k^{n+1} - 1}{k-1} + \frac{k^{n+1} \cdot (k-1)}{k-1} \ \sum_{i=0}^{n+1}k^i = \frac{k^{n+1} - 1 + k^{n+2} - k^{n+1}}{k-1} \ \sum_{i=0}^{n+1}k^i = \frac{k^{n+2} - 1}{k-1} $$ zgadza się

---

3. wszystkich palindromów długości $n$

   rozważamy dwa przypadki:

   1. $n$ jest parzyste
      dobieramy $\frac{n}{2}$ liter z alfabetu $k$-elementowego na jedną połówkę słowa: $$ k^{\frac{n}{2}} $$
   2. $n$ jest nieparzyste
      dobieramy $\left\lfloor \frac{n}{2} \right\rfloor$ liter z alfabetu $k$-elementowego na jedną połówkę słowa: $$ k^{\left\lfloor \frac{n}{2} \right\rfloor} $$ dodatkowo dobieramy jedną literę środkową słowa spośród $k$ liter

   dowód taki sam jak dla «3.1.»

---

4. wszystkich palindromów długości co najwyżej $n$

   tak samo jak dla «3.2.» + «3.3.»