Непериодическая последовательность.

[ODM]

Существует ли последовательность $\begin{Bmatrix}{a}_{n}\end{Bmatrix}$, такая что любая последовательность $\begin{Bmatrix}{b}_{n}\end{Bmatrix}$, удовлетворяющая условию ${a}_{i} \neq {b}_{i}$ для всех натуральных $i$ и не является периодической? Все ${a}_{i}, {b}_{i}$ - эллементы какого-то конечного множества.

[Хорхе]

Понятное дело, существует. И даже для счетного множества.

Намного интереснее найти последовательность, которая пересекается с любой eventually (как это по русски?) периодической последовательностью, то есть с любой последовательностью, которая "зацикливается".

UPD: Впрочем, это тоже просто.

Назовем $N$-цацей конечную последовательность $b_1,\dots,b_M$ натуральных чисел, такую, что для любых натуральных $k,l,r\le N$ найдется $n\le [M/k]-1$, что $b_{nk+r}=b_{(n+1)k+r} = l$.

После этого возьмем такую последовательность: $1$-цаца, $2$-цаца, ..., $N$-цаца, ...

[ODM]

Хорхе в сообщении #511161 писал(а):

Назовем $N$-цацей конечную последовательность $b_1,\dots,b_M$ натуральных чисел, такую, что для любых натуральных $k,l,r\le N$ найдется $n\le [M/k]-1$, что $b_{nk+r}=b_{(n+1)k+r} = l$.

После этого возьмем такую последовательность: $1$-цаца, $2$-цаца, ..., $N$-цаца, ...

Не понятно одно, почему она должна существовать? А если не найдется такой конечной?

[Dave]

Да, существует. Пусть $C = \lbrace c_1,c_2,\ldots,c_p\rbrace$ - указанное в формулировке конечное множество из $p$ элементов. Тогда указанному свойству будет удовлетворять последовательность $\lbrace a_n \rbrace$, задаваемая формулой

$$a_n = c_{[\sqrt n]\mod p + 1} .$$

Действительно, если $\lbrace b_n \rbrace$ - некоторая периодическая последовательность с периодом $k$ и $b_1=c_r$, то, рассматривая члены последовательностей $\lbrace a_n \rbrace$ и $\lbrace b_n \rbrace$ при значениях индекса $n$, равных

$$m^2,m^2+1,\ldots,(m+1)^2-1,$$

где $m$ - любое целое число, дающее при делении на $p$ остаток $r-1$ и большее, чем $k$, мы увидим, что:
1) Все члены последовательности $\lbrace a_n \rbrace$ с указанными индексами равны $c_r=b_1$;
2) Поскольку $(m+1)^2-m^2=2m+1>k$, а последовательность $\lbrace b_n \rbrace$ - периодическая с периодом $k$, то среди $\lbrace b_n \rbrace$ с указанными индексами обязательно найдётся элемент, равный $b_1$.
Это говорит о том, что условие $a_i \neq b_i$ не может выполняться для всех индексов $i$, какой бы ни была периодическая последовательность $\lbrace b_n \rbrace$.

[ODM]

Dave в сообщении #511170 писал(а):

Да, существует. Пусть $C = \lbrace c_1,c_2,\ldots,c_p\rbrace$ - указанное в формулировке конечное множество из $p$ элементов. Тогда указанному свойству будет удовлетворять последовательность $\lbrace a_n \rbrace$, задаваемая формулой

$$a_n = c_{[\sqrt n]\mod p + 1} .$$

[Хорхе]

ODM в сообщении #511168 писал(а):

Хорхе в сообщении #511161 писал(а):

Назовем $N$-цацей конечную последовательность $b_1,\dots,b_M$ натуральных чисел, такую, что для любых натуральных $k,l,r\le N$ найдется $n\le [M/k]-1$, что $b_{nk+r}=b_{(n+1)k+r} = l$.

После этого возьмем такую последовательность: $1$-цаца, $2$-цаца, ..., $N$-цаца, ...

Не понятно одно, почему она должна существовать? А если не найдется такой конечной?

Да понятно, что найдется. (Например, безыдейно возьмем $2N$ единиц, $2N$ двоек, ..., $2N$ чисел $N$.) Если длина $M$ достаточно большая, то почти все (в вероятностном смысле) последовательности длины $M$ такие.

[ODM]

Убедил. Ну и чести ради, мое решение.

Всего периодических последовательностей счетно. Тогда пронумеруем их все.
$1) x_{11},x_{12}, ... ,x_{1n},...$
$2) x_{21},x_{22}, ... ,x_{2n},...$
$...$
$n) x_{n1},x_{n2}, ... ,x_{nn},...$
$...$

А значит искомая последовательность $\{a_i\}$: a_i=x_{ii}

Вот только мне казалось, что если множество не конечно, по периодических последовательностей континуум. Ошибся.