KombinatorykaŚrednieZadanie nr 32

Drogi pod przekątną

Liczby Catalana Zadania konkursoweZadania olimpijskie

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

+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ę

To klasyczny problem prowadzący do liczb Catalana. Rozważ metodę odbicia.

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Wszystkich dróg z \((0,0)\) do \((5,5)\): \(\binom{10}{5}=252\).
  2. 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\).
  3. Dobre drogi: \(252-210=42\).
  4. 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.

Więcej zadań z kombinatoryki →

Podobne zadania