[Ciągi] niezmiennik ciągu

[m-2]

W ciągu \(\displaystyle{ 1, 0, 1, 0, 1, 0, 3, ...}\) każdy wyraz począwszy od siódmego jest równy ostatniej cyfrze liczby, będącej sumą sześciu poprzednich wyrazów. Udowodnij, że w tym ciągu nie może wystąpić następujący blok liczb: \(\displaystyle{ 0, 1, 0, 1, 0, 1.}\)

[XMaS11]

Wyrazy tego ciagu to reszty z dzielenia przez 10, zatem warto poszukac niezmiennika wlasnie mod 10. Charakter rekurencji danej na ten ciag moze sugerowac, ze bedzie to jakis niezmiennik liniowo uzalezniony od szesciu kolejnych wyrazow, bedzie wiec musial wygladac tak:
\(\displaystyle{ x_1a+x_2b+x_3c+x_4d+x_5e+x_6f}\), gdzie \(\displaystyle{ x_i}\) to reszty z dzielenia przez 10. a : a,b,c,d,e,f to kolejne wyrazy ciagu. Skoro to ma byc niezmiennik, to oznacza, ze:
\(\displaystyle{ x_1a+x_2b+x_3c+x_4d+x_5e+x_6f=x_1b+x_2c+x_3d+x_4e+x_5f+x_6(a+b+c+d+e+f)}\)
czyli:
\(\displaystyle{ a(x_6-x_1)+b(x_6+x_1-x_2)+c(x_6+x_2-x_3)+d(x_6+x_3-x_4)+e(x_6+x_4-x_5)+fx_5=0}\)
dla kazdych a,b,c,d,e,f, a to oznacza, ze wszystkie wspolczynniki musza byc rowne 0. Dostajemy zwykly uklad rownan liniowych, ktorego rozwiazaniem jest zdaje sie:
\(\displaystyle{ x_1=2, x_2=4, x_3=6, x_4=8, x_5=0, x_6=2}\). Oczywiscie niezmiennik ten spelnia swoja role, gdyz jest rozny dla dwoch podanych ciagow dlugosci 6.