Kolorowanie sąsiednich obszarów

Rozwiązanie krok po kroku

Reguła mnożenia: pierwszy obszar $\mathsf{k}$ sposobów, każdy następny $\mathsf{k}-1$

1. Klucz: obszary tworzą DRZEWO (brak cykli), więc każdy poza pierwszym ma dokładnie jednego już pokolorowanego sąsiada. Dlatego wynik $\mathsf{k}\cdot (\mathsf{k}-1{)}^{\mathsf{n}-1}$ NIE zależy od kształtu drzewa (ścieżka, gwiazda czy rozgałęzienie) - liczy się tylko liczba obszarów $\mathsf{n}$.
2. Krok 1. Pierwszy obszar
3. $7$ obszarów, $12$ kolorów, sąsiednie różne
4. $\text{obszar 1:}\boxed{12}\text{ koloroˊw}$
5. pierwszy obszar kolorujemy dowolnie - każdy z $12$ kolorów jest dozwolony
6. Krok 2. Każdy kolejny obszar
7. graniczy z jednym już pokolorowanym
8. $\text{obszary }2,3,\dots ,7:\boxed{11}\text{ koloroˊw}$
9. każdy następny obszar sąsiaduje z dokładnie jednym już pokolorowanym - musi być inny niż jego kolor, więc zostaje $12-1=11$ możliwości
10. $\text{liczba takich obszaroˊw: }7-1=\boxed{6}$
11. Krok 3. Reguła mnożenia
12. $1$ obszar po $12$, $6$ obszarów po $11$
13. $12\cdot \underset{6}{\underbrace{11\cdot 11\cdots 11}}$
14. mnożymy liczby możliwości dla wszystkich obszarów: $12$ dla pierwszego i po $11$ dla każdego z pozostałych $6$
15. $=\boxed{12\cdot 11^6}$

Wynik $12\cdot 11^6=21258732$ jest ten sam dla każdego drzewa o $7$ obszarach - kształt (tu: gwiazda) nie ma znaczenia, bo każdy nowy obszar zawsze styka się z jednym pokolorowanym.

Najczęstsze pomyłki: (1) ${12}^7$ - kolorowanie każdego obszaru niezależnie, ignorując warunek sąsiedztwa; (2) $12\cdot 11^7$ lub $12\cdot 11^5$ - błąd o jeden w wykładniku (powinno być $\mathsf{n}-1$ czynników $\mathsf{k}-1$); (3) użycie permutacji $\frac{12!}{(12-7)!}$ - to zakłada, że WSZYSTKIE obszary mają różne kolory, a graniczyć nie muszą wszystkie.