Устройство принимает на вход и выдает на выход наборы из n битов (причем Поданный на вход набор преобразуется в выходной набор
где ⊕ — стандартная операция сложения битов:
Подав теперь этот набор h(x) на вход, получим на выходе набор который вновь подадим на вход и получим и т. д. Докажите, что если все наборы x, h(x),
Заметим, что для всех x вектор h(x) содержит четное число единиц, так как
Значит, в рассматриваемой последовательности x, h(x), h(2)(x), ..., h(k)(x) (1) все векторы, начиная со второго, имеют четное количество единиц. Количество всех векторов, имеющих четное количество единиц, равно Поэтому претендентом на самое большое количество различных векторов является последовательность (1), начинающаяся с вектора, содержащего нечетное количество единиц и продолжающаяся всеми векторами с четным количеством единиц. Количество векторов в такой последовательности будет Таким образом,