сайты - меню - вход - но­во­сти


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

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