Kolorowanie sąsiednich obszarów
Na rysunku przedstawiono 7 ponumerowanych obszarów połączonych liniami. Każdy obszar kolorujemy jednym z 12 kolorów tak, aby żadne dwa sąsiednie obszary nie miały tego samego koloru. Liczba sposobów takiego kolorowania jest równa
Rozwiąż to zadanie online z natychmiastowym sprawdzeniem wyniku i pełnym rozwiązaniem krok po kroku.
Rozwiązanie krok po kroku
Reguła mnożenia: pierwszy obszar k sposobów, każdy następny k-1
- Klucz: obszary tworzą DRZEWO (brak cykli), więc każdy poza pierwszym ma dokładnie jednego już pokolorowanego sąsiada. Dlatego wynik k·(k-1)^ n-1 NIE zależy od kształtu drzewa (ścieżka, gwiazda czy rozgałęzienie) - liczy się tylko liczba obszarów n.
- Krok 1. Pierwszy obszar
- 7 obszarów, 12 kolorów, sąsiednie różne
- obszar 1: 12 kolorów
- pierwszy obszar kolorujemy dowolnie - każdy z 12 kolorów jest dozwolony
- Krok 2. Każdy kolejny obszar
- graniczy z jednym już pokolorowanym
- obszary 2, 3,, 7: 11 kolorów
- 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
- liczba takich obszarów: 7 - 1 = 6
- Krok 3. Reguła mnożenia
- 1 obszar po 12, 6 obszarów po 11
- 12 · 11 · 11 ·s 11 _ 6
- mnożymy liczby możliwości dla wszystkich obszarów: 12 dla pierwszego i po 11 dla każdego z pozostałych 6
- = 12 · 11^ 6
Wynik 12 · 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 · 11^ 7 lub 12 · 11^ 5 - błąd o jeden w wykładniku (powinno być n-1 czynników k-1); (3) użycie permutacji 12! / (12-7)! - to zakłada, że WSZYSTKIE obszary mają różne kolory, a graniczyć nie muszą wszystkie.