KombinatorykaWyzwanieZadanie nr 3854

Niemalejące ciągi długości 10 o wyrazach z {1, …, 12}, w których aᵢ ≠ i dla każdego i

Ścieżki kratowe i liczby Catalana Zadania konkursoweZadania olimpijskiePrzygotowanie do Olimpiady Matematycznej

Ile jest ciągów niemalejących \((a_1,a_2,\ldots,a_{10})\) liczb całkowitych ze zbioru \(\{1,2,\ldots,12\}\), w których \(a_i\ne i\) dla każdego \(i=1,2,\ldots,10\)?

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

Najpierw udowodnij, że aᵢ > i dla każdego i. Potem przekształć ciąg w ścieżkę kratową i zastosuj zasadę odbicia.

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Z \(a_1\ge1\) i \(a_1\ne1\) mamy \(a_1\ge2\). Jeśli \(a_i\ge i+1\), to \(a_{i+1}\ge a_i\ge i+1\) i \(a_{i+1}\ne i+1\), więc \(a_{i+1}\ge i+2\). Zatem warunek jest równoważny nierównościom \(i+1\le a_i\le12\).
  2. Połóżmy \(c_i=13-a_{11-i}\) dla \(i=1,\ldots,10\). Jest to bijekcja na ciągi niemalejące z \(1\le c_i\le i+1\). Dopisując na początku \(1\), dostajemy ciągi niemalejące \(1\le d_1\le\ldots\le d_{11}\) z \(d_j\le j\) (i \(d_1=1\) automatycznie).
  3. Ciągowi \((d_j)\) przypisujemy ścieżkę kratową z \((0,0)\) do \((11,11)\) o krokach \(E=(1,0)\), \(N=(0,1)\), w której \(j\)-ty krok \(E\) wykonujemy na wysokości \(d_j-1\). Warunek \(d_j\le j\) oznacza, że ścieżka nigdy nie wchodzi nad przekątną \(y=x\); jest to bijekcja.
  4. Ścieżek wszystkich jest \(\binom{22}{11}\). Ścieżka zła dotyka prostej \(y=x+1\); odbijając jej początek do pierwszego takiego punktu względem tej prostej, dostajemy bijekcję ze ścieżkami z \((-1,1)\) do \((11,11)\), których jest \(\binom{22}{10}\).
  5. Wynik: \(\binom{22}{11}-\binom{22}{10}=\frac{1}{12}\binom{22}{11}=\frac{705432}{12}=58786\) (liczba Catalana \(C_{11}\)). Odpowiedź: \(58786\).

Odpowiedź: \(58786\)

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