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

  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 .
  2. Krok 1. Pierwszy obszar
  3. 7 obszarów, 12 kolorów, sąsiednie różne
  4. obszar 1: 12 koloró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. obszary 2, 3, , 7: 11 koloró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. liczba takich obszarów: 7 - 1 = 6
  11. Krok 3. Reguła mnożenia
  12. 1 obszar po 12 , 6 obszarów po 11
  13. 12 11 11 11 _ 6
  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. = 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.