Математикадан республикалық олимпиада, 2009-2010 оқу жылы, 11 сынып

$(x_1, x_2, \ldots, x_n)$ тізбегіне іліністіру амалын қолдансақ, $(x_1x_2, x_2x_3, \ldots, x_nx_1)$ тізбегін аламыз. Қандай натурал $n > 1$ сандары үшін $1$ және $-1$ сандарынан тұратын кез келген бастапқы тізбектен іліністіру амалын бірнеше рет қолданып, әрқашан $(1, 1, \ldots, 1)$ тізбегін алуға болады?

Комментарий/решение

Последовательности, из которых никогда не получается $(1,1,...,1)$, назовём неприводимыми. Назовём $n$, для которых существует неприводимая последовательность размера $n$, плохими. Заметим три вещи:

1) после сцепления произведение всех чисел равно $(x_1x_2...x_n)^2=1$, то есть количество $-1$ после сцепления всегда чётное

2) Допустим при некотором $n$ существует неприводимая последовательность $(x_1,x_2,...,x_n)$. Тогда для любого $k\in\mathbb{N}$ последовательность $(y_1,y_2,...,y_{kn})$, где $y_{sn+r}=x_r$, тоже неприводима.

3) Сцеплением $(1,1...,1)$ можно получить только из $(-1,-1,...,-1)$, либо из $(1,1,...,1)$. Следовательно из п.1 все нечётные плохие. Тогда из п.2, следует что хорошими могут являться только степени 2.

Теперь, используя метод мат. индукции, нетрудно убедится, что после применения $2^k$ операций сцепления последовательность $(x_1,x_2,...,x_n)$ превращается в $(y_1,y_2,...,y_n)$, где $y_i=x_ix_{i+2^k}$ для всех $1\le i\le n$(Здесь считаем, что $x_{i+n}=x_i$). Поэтому, если $n=2^k$, то $$y_i=x_ix_{i+2^k}=x_i^2=1$$ Таким образом

Ответ: $n=2^k\forall k\in\mathbb{N}$