РЕШУ ОЛИМП — математика

Задания

Устройство принимает на вход и выдает на выход наборы из n битов (причем $n больше или равно 4 правая круглая скобка .$ Поданный на вход набор $x= левая круглая скобка x_1, \ldots, x_n правая круглая скобка$ преобразуется в выходной набор

$h левая круглая скобка x правая круглая скобка = левая круглая скобка x_1 \oplus x_n минус 1, x_2 \oplus x_n, x_2 \oplus x_3, x_3 \oplus x_4, \ldots, x_n минус 2 \oplus x_n минус 1, x_1 \oplus x_n правая круглая скобка ,$

где ⊕ — стандартная операция сложения битов:

$0 \oplus 0=1 \oplus 1=0,$ $0 \oplus 1=1 \oplus 0=1.$

Подав теперь этот набор h(x) на вход, получим на выходе набор $h левая круглая скобка h левая круглая скобка x правая круглая скобка правая круглая скобка =h в степени левая круглая скобка левая круглая скобка 2 правая круглая скобка правая круглая скобка левая круглая скобка x правая круглая скобка ,$ который вновь подадим на вход и получим $h в степени левая круглая скобка левая круглая скобка 3 правая круглая скобка правая круглая скобка левая круглая скобка x правая круглая скобка$ и т. д. Докажите, что если все наборы x, h(x), h⁽²⁾(x), ..., h^(k)(x) оказались различными, то $k меньше или равно 2 в степени левая круглая скобка n минус 1 правая круглая скобка минус 1.$

Решение. Заметим, что для всех x вектор h(x) содержит четное число единиц, так как

$левая круглая скобка x_1 \oplus x_n минус 1 правая круглая скобка \oplus левая круглая скобка x_2 \oplus x_n правая круглая скобка \oplus левая круглая скобка x_2 \oplus x_3 правая круглая скобка \oplus левая круглая скобка x_3 \oplus x_4 правая круглая скобка \oplus \ldots, \oplus левая круглая скобка x_n минус 2 \oplus x_n минус 1 правая круглая скобка \oplus левая круглая скобка x_1 \oplus x_n правая круглая скобка =0 .$

Значит, в рассматриваемой последовательности x, h(x), h⁽²⁾(x), ..., h^(k)(x) все векторы, начиная со второго, имеют четное количество единиц. Количество всех векторов, имеющих четное количество единиц, равно $2 в степени левая круглая скобка n минус 1 правая круглая скобка .$ Поэтому претендентом на самое большое количество различных векторов является последовательность (1), начинающаяся с вектора, содержащего нечетное количество единиц и продолжающаяся всеми векторами с четным количеством единиц. Количество векторов в такой последовательности будет $1 плюс 2 в степени левая круглая скобка n минус 1 правая круглая скобка$ Таким образом, $k меньше или равно 2 в степени левая круглая скобка n минус 1 правая круглая скобка .$ Для получения оценки $k \leqslant$ $2 в степени левая круглая скобка n минус 1 правая круглая скобка минус 1$ рассмотрим отдельно случай когда среди векторов последовательности (1) нет нулевого вектора (0, 0, ..., 0) и когда он есть. Если в последовательности (1) нет вектора (0, 0, ..., 0), то она содержит не более

$1 плюс левая круглая скобка 2 в степени левая круглая скобка n минус 1 правая круглая скобка минус 1 правая круглая скобка =2 в степени левая круглая скобка n минус 1 правая круглая скобка$

векторов и $k меньше или равно 2 в степени левая круглая скобка n минус 1 правая круглая скобка минус 1.$ Пусть теперь последовательность (1) содержит вектор (0, 0, ..., 0). Рассмотрим два случая.

1)  Если n – нечетное число, то

$h левая круглая скобка 0, 0, \ldots, 0 правая круглая скобка =h левая круглая скобка 1, 1, \ldots, 1 правая круглая скобка = левая круглая скобка 0, 0, \ldots, 0 правая круглая скобка$

и других векторов, переходящих в нулевой нет. При этом не существует векторов z таких, что $h левая круглая скобка z правая круглая скобка = левая круглая скобка 1, 1, \ldots, 1 правая круглая скобка$ Таким образом, в этом случае последовательность (1) содержит максимум два вектора и $k меньше или равно 2 в степени левая круглая скобка n минус 1 правая круглая скобка минус 1.$

2)  Если n  — четное число, то

и найдутся два вектора

$a= левая круглая скобка 0, 0, 1, 0, 1, \ldots, 0, 1, 1 правая круглая скобка$ и $b= левая круглая скобка 1, 1, 0, 1, 0, 1, \ldots, 0, 1, 0, 0 правая круглая скобка$

содержащие четное число единиц такие, что $h левая круглая скобка a правая круглая скобка =h левая круглая скобка b правая круглая скобка = левая круглая скобка 1, 1, \ldots, 1 правая круглая скобка .$ Последовательность (1) не может содержать одновременно векторы a и b, поэтому в этом случае она содержит не более

векторов и $k меньше или равно 2 в степени левая круглая скобка n минус 1 правая круглая скобка минус 1.$

Ключ