Matematyka.pl

Mam problem z rozwiązaniem następującego zadania:

Niech \(\displaystyle{ x_0,x_1,\ldots,x_n,\ldots}\) będzie dowolnym ciągiem nieskończonym samych tylko liczb całkowitych z zakresu \(\displaystyle{ [0,9]}\). Czy prawdą jest, że jeśli istnieje \(\displaystyle{ k \in \mathbb{N} \setminus \left\{ 0\right\}}\) i istnieją \(\displaystyle{ a_0,...,a_{k-1} \in \mathbb{Z} \cap [0,9]}\) oraz istnieje taka funkcja \(\displaystyle{ S:\left\{ 0,1,2,3,4,5,6,7,8,9\right\}^k \rightarrow \left\{ 0,1,2,3,4,5,6,7,8,9\right\}}\), że \(\displaystyle{ \begin{cases}x_0=a_0 \\ x_1=a_1 \\ \vdots \\ x_{k-1}=a_{k-1} \\ x_{n+k}=S(x_n,...,x_{n+k-1}) \end{cases}}\), to ciąg \(\displaystyle{ (x_n)_{n \in \mathbb{N}}}\) jest okresowy? Jeśli nie jest to prawdą - podać kontrprzykład.

O ciągu \(\displaystyle{ (x_n)}\) powiemy, że jest okresowy, jeśli istnieje takie \(\displaystyle{ N \in \NN}\) oraz \(\displaystyle{ \ell \in \NN,}\) że dla każdego \(\displaystyle{ n \ge N}\) jest \(\displaystyle{ a_{n+\ell} = a_n.}\) - Czy ta definicja jest zgodną z twoją?
Jeśli tak, to teza jest prawdziwa: weźmy dowolny ciąg \(\displaystyle{ (x_n),}\) który spełnia założenia. Krotki postaci

\(\displaystyle{ \left( x_i, x_{i+1}, \ldots, x_{i+k-1} \right)}\) dla \(\displaystyle{ i = 0, 1, \ldots, 10^k}\)

są elementami zbioru \(\displaystyle{ \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}^k}\) mocy \(\displaystyle{ 10^k}\) i jest ich \(\displaystyle{ 10^k+1,}\) zatem któraś się powtarza, tzn.

\(\displaystyle{ \left( x_i, x_{i+1}, \ldots, x_{i+k-1} \right) = \left( x_j, x_{j+1}, \ldots, x_{j+k-1} \right)}\) dla pewnych \(\displaystyle{ i, j \in \{ 0, 1, \ldots, 10^k \}}\) - możemy przyjąć, że \(\displaystyle{ i<j.}\)

Teraz wystarczy przyjąć \(\displaystyle{ \ell = j - i}\) i indukcyjnie pokazać, że \(\displaystyle{ x_{n+\ell} = x_n}\) dla wszystkich \(\displaystyle{ n \ge i.}\)

Ja miałem taką definicję ciągu okresowego - \(\displaystyle{ \exists_{N \in \mathbb{N}}(N>0 \wedge \forall_{n \in \mathbb{N}} \ x_{n+N}=x_n)}\) gdzie \(\displaystyle{ \mathbb{N}=\left\{ 0,1,2,...\right\}}\)

W takiej wersji zadanie jest trochę mniej ciekawe i teza jest nieprawdziwa: ciąg

\(\displaystyle{ x_n = \begin{cases} 0 & \text{dla } n = 0 \\ 1 & \text{dla } n \ge 1 \end{cases} \quad = (0, 1, 1, 1, \ldots )}\)

wraz z liczbami \(\displaystyle{ k = 1, a_0 = 0}\) i funkcją \(\displaystyle{ S : \{ 0, \ldots, 9 \} \to \{ 0, \ldots, 9 \}}\) daną wzorem

\(\displaystyle{ S(n) = 1}\)

spełnia założenia, ale nie jest okresowy, bo zero się już więcej nie powtarza.

Wielkie dzięki za pomoc.