РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 7669 Добавить в вариант

Устройство принимает на вход и выдает на выход наборы из n битов (причем $n больше или равно 5 правая круглая скобка .$ Поданный на вход набор $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 правая круглая скобка .$

Спрятать решение

Решение.

Заметим, что для всех 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) (1) все векторы, начиная со второго, имеют четное количество единиц. Количество всех векторов, имеющих четное количество единиц, равно $2 в степени левая круглая скобка n минус 1 правая круглая скобка .$ Поэтому претендентом на самое большое количество различных векторов является последовательность (1), начинающаяся с вектора, содержащего нечетное количество единиц и продолжающаяся всеми векторами с четным количеством единиц. Количество векторов в такой последовательности будет $1 плюс 2 в степени левая круглая скобка n минус 1 правая круглая скобка$ Таким образом, $k меньше или равно 2 в степени левая круглая скобка n минус 1 правая круглая скобка .$

Межрегиональная олимпиада школьников им. И. Я. Верченко, 9 класс, 2 тур (заключительный), 2021 год

Классификатор: Разное. Логические уравнения

Спрятать решение · Помощь