KombinatorykaŚrednieZadanie nr 1801

Najkrótsze drogi z (0, 0) do (6, 6) omijające punkty (2, 2) i (4, 4)

Drogi na kracie Matura rozszerzonaPrzygotowanie do Diamentu AGH

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)\)?

+10 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

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
  1. 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\).
  2. Przez \((2,2)\) przechodzi \(\binom42\cdot\binom84=6\cdot70=420\) dróg, przez \((4,4)\) — \(\binom84\cdot\binom42=420\) dróg.
  3. Przez oba punkty przechodzi \(\binom42\cdot\binom42\cdot\binom42=216\) dróg.
  4. 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.

Więcej zadań z kombinatoryki →

Podobne zadania