KombinatorykaTrudneZadanie nr 3905

Ciągi długości 10 z wyrazami 1–4 i najwyżej dwiema wartościami w każdej czwórce

Zliczanie ciągów z warunkiem lokalnym Zadania konkursoweZadania olimpijskiePrzygotowanie do Olimpiady Matematycznej

Ile jest ciągów \((c_1,c_2,\ldots,c_{10})\) o wyrazach ze zbioru \(\{1,2,3,4\}\), w których każde cztery kolejne wyrazy \(c_i,c_{i+1},c_{i+2},c_{i+3}\) (\(i=1,\ldots,7\)) przyjmują co najwyżej dwie różne wartości?

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

Klasyfikuj ciągi według wzorca trzech ostatnich wyrazów: \(xxx\), \(xxy\), \(xyx\), \(xyy\) (\(x\neq y\)). Ustal, w jaki wzorzec przechodzi każdy z nich po dopisaniu dozwolonego wyrazu, i ułóż układ rekurencji.

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Dla \(n\ge3\) niech \(A_n,P_n,Q_n,R_n\) oznaczają liczby dobrych ciągów długości \(n\), których trzy ostatnie wyrazy mają odpowiednio wzorzec \(xxx\), \(xxy\), \(xyx\), \(xyy\) (\(x\neq y\)). Dopisanie wyrazu sprawdza tylko nowe okno czterech wyrazów, więc liczy się tylko wzorzec końcówki.
  2. Przejścia: z \(xxx\) dopisanie \(x\) daje \(xxx\), a dopisanie jednej z trzech innych wartości daje wzorzec \(xxy\). Z \(xxy\): \(x\to xyx\), \(y\to xyy\). Z \(xyx\): \(x\to\) końcówka \(yxx\) (wzorzec \(xyy\)), \(y\to yxy\) (wzorzec \(xyx\)). Z \(xyy\): \(x\to yyx\) (wzorzec \(xxy\)), \(y\to yyy\). Innych wartości dopisać nie można.
  3. Stąd \(A_{n+1}=A_n+R_n\), \(P_{n+1}=3A_n+R_n\), \(Q_{n+1}=P_n+Q_n\), \(R_{n+1}=P_n+Q_n\), a dla \(n=3\): \(A_3=4\), \(P_3=Q_3=R_3=12\) (wszystkie \(64\) ciągi).
  4. Kolejne wartości \((A,P,Q,R)\): \(n=4\): \((16,24,24,24)\) — razem \(88\); \(n=5\): \((40,72,48,48)\); \(n=6\): \((88,168,120,120)\); \(n=7\): \((208,384,288,288)\); \(n=8\): \((496,912,672,672)\); \(n=9\): \((1168,2160,1584,1584)\); \(n=10\): \((2752,5088,3744,3744)\).
  5. Liczba ciągów długości \(10\): \(2752+5088+3744+3744=15328\). (Kontrola dla \(n=4\): \(4+\binom42(2^4-2)=88\).)

Odpowiedź: \(15328\)

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