KombinatorykaTrudneZadanie nr 3905
Ciągi długości 10 z wyrazami 1–4 i najwyżej dwiema wartościami w każdej czwórce
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?
Świetnie.
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
- 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.
- 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.
- 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).
- 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)\).
- 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.