Zliczanie możliwości polega na policzeniu każdego dopuszczalnego wyniku dokładnie raz. Pomaga w tym uporządkowana lista, tabela, drzewko, podział na przypadki lub odjęcie wyników niedozwolonych od wszystkich.
Pojęcia, od których zaczynamy
Zacznij od zapisania, co jest jednym wynikiem. Dla stroju jest to konkretna para ubrań, dla kodu uporządkowany ciąg znaków, a dla komisji skład grupy. Następnie ustal, kiedy dwa opisy oznaczają to samo: para osób Anna–Bartek i Bartek–Anna daje tę samą komisję, ale inne obsadzenie dwóch różnych funkcji.
Przypadki mają być rozłączne i łącznie obejmować wszystkie poprawne wyniki. Można np. podzielić liczby według ostatniej cyfry. Podział na „podzielne przez dwa” i „podzielne przez pięć” nie jest rozłączny, ponieważ wielokrotności dziesięciu spełniają oba warunki.
Zasady i wzory
Zliczanie możliwości polega na dobraniu reprezentacji: podziale na przypadki, regule mnożenia, dopełnieniu albo zasadzie włączeń i wyłączeń. Najważniejsze jest uniknięcie pominięć i podwójnego liczenia.
- Przypadki powinny wyczerpywać wszystkie możliwości.
- Rozłączne przypadki można bezpiecznie dodawać.
- Czasem łatwiej policzyć wszystkie wyniki i odjąć niedozwolone.
Odjęcie części wspólnej koryguje podwójne zliczenie.
Jak czytać rysunek?
Dwa koła oznaczają liczby podzielne przez dwa i przez pięć wśród liczb całkowitych od \(1\) do \(100\). Poza częścią wspólną jest odpowiednio \(40\) i \(10\) liczb, a wspólnych jest \(10\). Łącznie daje to \(40+10+10=60\). Można też dodać pełne liczebności grup i odjąć jedno wystąpienie części wspólnej.
Przykład krok po kroku
Ile liczb od 1 do 100 jest podzielnych przez 2 lub przez 5?
Dlaczego odejmujemy wielokrotności dziesięciu? Liczba podzielna przez \(10\) jest jednocześnie podzielna przez \(2\) i \(5\), więc została policzona w obu grupach. Odejmujemy ją raz, aby nadal liczyć ją jako jeden poprawny wynik. Zapis \(\lfloor x\rfloor\) oznacza największą liczbę całkowitą nieprzekraczającą \(x\).
- Policz wielokrotności 2 i 5.\(\lfloor\frac{100}{2}\rfloor=50,\quad\lfloor\frac{100}{5}\rfloor=20\)
- Policz część wspólną: wielokrotności 10.\(\lfloor\frac{100}{10}\rfloor=10\)
- Zastosuj włączenia i wyłączenia.\(50+20-10=60\)
Typowy błąd
Elementów należących do obu warunków nie liczymy dwukrotnie.
Dodatkowy przykład i kontrola
Czasem łatwiej liczyć przez dopełnienie. Trzyznakowych kodów z cyfr \(0,1,2,3\), z powtórzeniami i zerem na początku, jest \(4^3=64\). Kodów bez zera jest \(3^3=27\). Co najmniej jedno zero ma więc \(64-27=37\) kodów. Ten rachunek uwzględnia także dwa lub trzy zera.
Na końcu sprawdź granice: liczba wyników z ograniczeniem nie może przewyższać liczby wszystkich wyników. Przy małych danych wypisz wyniki. Z cyfr \(1,2,3\) powstaje sześć liczb dwucyfrowych bez powtórzeń: \(12,13,21,23,31,32\). Taka lista pozwala zauważyć, dlaczego kolejność tworzy osobne wyniki.