KombinatorykaŚrednieZadanie nr 1801
Najkrótsze drogi z (0, 0) do (6, 6) omijające punkty (2, 2) i (4, 4)
Pionek porusza się po punktach kratowych płaszczyzny: w każdym ruchu przechodzi z punktu \((x,y)\) do \((x+1,y)\) albo do \((x,y+1)\). Ile jest dróg pionka z punktu \((0,0)\) do punktu \((6,6)\), które nie przechodzą ani przez punkt \((2,2)\), ani przez punkt \((4,4)\)?
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Liczba dróg z \((0,0)\) do \((a,b)\) wynosi \(\binom{a+b}{a}\). Odejmij drogi przechodzące przez zakazane punkty, stosując zasadę włączeń i wyłączeń.
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Każda droga do \((6,6)\) składa się z \(6\) ruchów w prawo i \(6\) w górę; wszystkich dróg jest \(\binom{12}{6}=924\).
- Przez \((2,2)\) przechodzi \(\binom42\cdot\binom84=6\cdot70=420\) dróg, przez \((4,4)\) — \(\binom84\cdot\binom42=420\) dróg.
- Przez oba punkty przechodzi \(\binom42\cdot\binom42\cdot\binom42=216\) dróg.
- Dróg omijających oba punkty jest \(924-420-420+216=300\).
Odpowiedź: \(300\)
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