Штирлиц хочет послать в Центр шифровку, представляющую собой код из 100 символов «точка» или «тире». Полученная им накануне из Центра Инструкция о конспирации гласит:
— при передаче шифровки по радио ровно 49 символов следует заменить на противоположные;
— расположение «неверных» символов возлагается на передающую сторону и с Центром не обсуждается.
Докажите, что Штирлиц может послать свою шифровку 10 раз, подбирая при каждой передаче 49 символов так, чтобы Центр, получив эти 10 шифровок, имел возможность однозначно восстановить исходный код.
Пусть шифровки представляют собой последовательности из нулей и единиц. Ясно, что можно считать, что Штирлиц шифрует строку, состоящую из одних нулей.
Штирлиц разобьёт двоичную строку на два блока по 49 бит в каждом и оставшиеся два бита. В шифровке C1 единицы будут стоять в первом блоке, в строка C2 — во втором блоке. Центр, увидев эти шифровки, обнаружит, что они различаются в 98 битах, а, значит, последние два бита верное в обеих шифровках. Если на шаге Центр уже вычислил а бит в первом блоке и b бит во втором блоке, то всего ему уже известно
бита. Пусть для определенности
(если
то первый и второй блоки меняются местами). Тогда Штирлиц передаст шифровку Ck, 6 которой единицы будут стоять на этих
позициях, а такое каких-то
позициях первого блока. Центр сравнит C2 и Ck и обнаружит, что в них есть одинаковые неверные b бит, а также различающиеся
позиций (47 – b в первом блоке и 49 – b во втором). Но такое возможно только, если на оставшихся позициях переданы верные биты. Следовательно, Центр теперь в дополнении к известным ранее а битам знает еще b + 2 бита из первого блока и всего ему известно
бита из первого блока. Выпишем далее пары чисел a u, которые будут возникать после получения Центром очередной шифровки. После второй шифровки
после третей
и
после четвертой
и
после пятой
и
после шестой
и
после седьмой
и
наконец, после восьмой шифровки
и
Следовательно, в этот момент Центр уже знает 66 бит из послания Штирлица. Тогда в девятой шифровке Штирлиц передаст 49 единиц в каких-то 49 позициях из уже известных Центру и тогда центр поймет, что остальные позиции правильные и узнает оставшуюся часть сообщения. Десятая шифровка Штирлицу даже и не пригодилась.

