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