2014-06-08
Пусть $A = (a_{1}; \cdots; a_{m})$ - набор из $m = 2^{n} (n \in \mathbf{N})$ чисел $a_{i} \in \{1; - 1 \}, i = 1, 2, \cdots, m$. Операция S определяется формулой
$S(A) = (a_{1}a_{2}; a_{2}a_{3}; \cdots ; a_{m}a_{1})$.
Доказать, что для любого набора $A$ в последовательности $A, S(A), S(S(A)), \cdots$ имеется набор из $m$ единиц.
Решение:
Докажем индукцией по $n \in \mathbf{Z}^{+}$, что в результате последовательного применения $2^{n}$ операций S получится набор из $m = 2^{n}$ единиц. Для $n = 0$ имеем $S(A) = (a_{1}a_{1}) = 1$. Пусть утверждение уже доказано для числа $n = 1$. Докажем его для числа $n$. Заметим, что в наборе
$T(A) = S(S(A)) = S(a_{1}a_{2}; a_{2}a_{3}; \cdots; a_{m}a_{1}) = (a_{1}a_{3}; a_{2}a_{4}; \cdots ; a_{m-1}a_{1}; a_{m}a_{2})$
числа, стоящие на четных местах, совпадают соответственно с числами, которые получаются из набора $(a_{2}; a_{4}; \cdots; a_{m})$ под действием операции S. Аналогично, числа, стоящие в наборе $T(A)$ на нечетных местах, образуют набор
$S(a_{1}; a_{3}; \cdots; a_{m-1})$.
По предположению индукции, после $m/2 = 2^{n-1}$ операций $T$ как на четных, так и на нечетных местах будут стоять одни единицы. Следовательно, после $m$ операций $S$ весь набор будет состоять из единиц.