Архив задач олимпиады по математике и криптографии

Цикловая структура, 8-11 класс.

Устройство принимает на вход и выдает на выход наборы из n битов (причем n ≥ 4). Поданный на вход набор x = (x1, …, xn) преобразуется в выходной набор h(x) = (x1x(n-1),x2xn, x2x3, x3x4, … , x(n-2)x(n-1), x1xn), где ⊕ - стандартная операция сложения битов: 
0 ⊕ 0 = 1 ⊕ 1 = 0, 0 ⊕ 1 = 1 ⊕ 0 = 1. 
 Подав теперь этот набор h(x) на вход, получим на выходе набор h(h(x)) = h(2)(x), который вновь подадим на вход и получим h(3)(x) и т.д. Докажите, что если все наборы x, h(x), h(2)(x), … , h(k)(x) оказались различными, то k ≤ 2(n-1)-1.