Архив задач олимпиады по математике и криптографии
Цикловая структура, 8-11 класс.
Устройство принимает на вход и выдает на выход наборы из n битов (причем n ≥ 4). Поданный на вход набор x = (x1, …, xn) преобразуется в выходной набор h(x) = (x1 ⊕ x(n-1),x2 ⊕ xn, x2 ⊕ x3, x3 ⊕ x4, … , x(n-2) ⊕ x(n-1), x1 ⊕ xn), где ⊕ - стандартная операция сложения битов:
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.
Заметим, что для всех x вектор h(x) содержит четное число единиц, так как (x1 ⊕ x(n-1)) ⊕ (x2 ⊕ xn) ⊕ (x2 ⊕ x3) ⊕ (x3 ⊕ x4) ⊕ … ⊕ (x(n-2) ⊕ x(n-1)) ⊕ (x1 ⊕ xn) = 0. Значит в рассматриваемой последовательности x, h(x), h(2)(x), … , h(k)(x) все векторы, начиная со второго, имеют четное количество единиц. Количество всех векторов, имеющих четное количество единиц, равно 2(n-1). Поэтому претендентом на самое большое количество различных векторов является последовательность x, h(x), h(2)(x), … , h(k)(x), начинающаяся с вектора, содержащего нечетное количество единиц и продолжающаяся всеми векторами с четным количеством единиц. Количество векторов в такой последовательности будет 1 + 2(n-1) Таким образом k ≤ 2(n-1). Для получения оценки k ≤ 2(n-1) - 1 рассмотрим отдельно случай, когда среди векторов последовательности нет нулевого вектора (0, 0, …, 0) и когда он есть. Если в последовательности нет вектора (0, 0, …, 0), то она содержит не более 1 + (2(n-1) - 1) = 2(n-1) векторов и k ≤ 2(n-1) - 1. Пусть теперь последовательность одержит вектор (0,0,…,0).
Рассмотрим два случая:
1)Если n - нечетное число, то h(0,0,…,0) = h(1,1,…,1) = (0,0,…,0) и других векторов, переходящих в нулевой нет. При этом не существует векторов zтаких, что h(z)=(1,1,…,1) Таким образом в этом случае последовательность содержит максимум два вектора и k ≤ 2(n-1) - 1.
2) Если n - четное число, то h(0,0,…,0) = h(1,1,…,1) = (0,0,…,0) и найдутся два вектора:
a = (0, 0, 1, 0, 1, … , 0, 1, 1) и b = (1, 1, 0, 1, 0, 1, … , 0, 1, 0, 0),
содержащие четное число единиц такие, что h(a) = h(b) = (1,1,…,1). Последовательность x, h(x), h(2)(x), … , h(k)(x) не может содержать одновременно векторы a и b, поэтому в этом случае она содержит не более 1 + (2(n-1) - 1) = 2(n-1) векторов и k ≤ 2(n-1) - 1.