Республиканская олимпиада по математике, 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}$