KombinatorykaŚrednieZadanie nr 32
Drogi pod przekątną
Pionek porusza się po kratownicy z punktu \((0,0)\) do punktu \((5,5)\), wykonując ruchy o \(1\) w prawo lub o \(1\) w górę. Ile jest dróg, na których pionek nigdy nie znajdzie się powyżej prostej \(y=x\)?
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
To klasyczny problem prowadzący do liczb Catalana. Rozważ metodę odbicia.
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Wszystkich dróg z \((0,0)\) do \((5,5)\): \(\binom{10}{5}=252\).
- Drogi „złe” dotykają prostej \(y=x+1\); odbijając ich początek względem tej prostej dostajemy bijekcję z drogami z \((-1,1)\) do \((5,5)\): \(\binom{10}{4}=210\).
- Dobre drogi: \(252-210=42\).
- To piąta liczba Catalana \(C_5=\frac{1}{6}\binom{10}{5}=42\).
Odpowiedź: \(C_5=42\)
Czego warto się nauczyć?
Kombinatoryka to sztuka liczenia bez wypisywania wszystkiego. Najważniejsze jest rozbicie problemu na etapy.
Podobne zadania
- Zagadka logiczna o parzystości: kubki odwracane po dwa — ile wyników liczenia
- Zagadka logiczna „jeśli…, to…”: szachiści, kółko matematyczne i chór
- Zasada szufladkowa: ile koralików wyjąć, by mieć pewność, że są dwa niebieskie
- Zasada szufladkowa: ile piłeczek wyjąć, by mieć pewność trzech w jednym kolorze