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


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

Штир­лиц хочет по­слать в Центр шиф­ров­ку, пред­став­ля­ю­щую собой код из 100 сим­во­лов «точка» или «тире». По­лу­чен­ная им на­ка­ну­не из Цен­тра Ин­струк­ция о кон­спи­ра­ции гла­сит:

— при пе­ре­да­че шиф­ров­ки по радио ровно 49 сим­во­лов сле­ду­ет за­ме­нить на про­ти­во­по­лож­ные;

— рас­по­ло­же­ние «не­вер­ных» сим­во­лов воз­ла­га­ет­ся на пе­ре­да­ю­щую сто­ро­ну и с Цен­тром не об­суж­да­ет­ся.

До­ка­жи­те, что Штир­лиц может по­слать свою шиф­ров­ку 10 раз, под­би­рая при каж­дой пе­ре­да­че 49 сим­во­лов так, чтобы Центр, по­лу­чив эти 10 шиф­ро­вок, имел воз­мож­ность од­но­знач­но вос­ста­но­вить ис­ход­ный код.

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

Ре­ше­ние.

Пусть шиф­ров­ки пред­став­ля­ют собой по­сле­до­ва­тель­но­сти из нулей и еди­ниц. Ясно, что можно счи­тать, что Штир­лиц шиф­ру­ет стро­ку, со­сто­я­щую из одних нулей.

Штир­лиц разобьёт дво­ич­ную стро­ку на два блока по 49 бит в каж­дом и остав­ши­е­ся два бита. В шиф­ров­ке C1 еди­ни­цы будут сто­ять в пер­вом блоке, в стро­ка C2  — во вто­ром блоке. Центр, уви­дев эти шиф­ров­ки, об­на­ру­жит, что они раз­ли­ча­ют­ся в 98 битах, а, зна­чит, по­след­ние два бита вер­ное в обеих шиф­ров­ках. Если на k минус 1 шаге Центр уже вы­чис­лил а бит в пер­вом блоке и b бит во вто­ром блоке, то всего ему уже из­вест­но a плюс b плюс 2 бита. Пусть для опре­де­лен­но­сти a мень­ше или равно b (если a боль­ше b, то пер­вый и вто­рой блоки ме­ня­ют­ся ме­ста­ми). Тогда Штир­лиц пе­ре­даст шиф­ров­ку Ck, 6 ко­то­рой еди­ни­цы будут сто­ять на этих a плюс b плюс 2 по­зи­ци­ях, а такое каких-то 47 минус a минус b по­зи­ци­ях пер­во­го блока. Центр срав­нит C2 и Ck и об­на­ру­жит, что в них есть оди­на­ко­вые не­вер­ные b бит, а также раз­ли­ча­ю­щи­е­ся 98 минус 2 b по­зи­ций (47 – b в пер­вом блоке и 49 – b во вто­ром). Но такое воз­мож­но толь­ко, если на остав­ших­ся по­зи­ци­ях пе­ре­да­ны вер­ные биты. Сле­до­ва­тель­но, Центр те­перь в до­пол­не­нии к из­вест­ным ранее а битам знает еще b + 2 бита из пер­во­го блока и всего ему из­вест­но a плюс b плюс 2 бита из пер­во­го блока. Вы­пи­шем далее пары чисел a u, ко­то­рые будут воз­ни­кать после по­лу­че­ния Цен­тром оче­ред­ной шиф­ров­ки. После вто­рой шиф­ров­ки a=b=0, после тре­тей a=2 и  b=0, после чет­вер­той a=2 и b=4, после пятой a=8 и b=4, после ше­стой a=8 и b=14, после седь­мой a=24 и b=14, на­ко­нец, после вось­мой шиф­ров­ки a=24 и b=40. Сле­до­ва­тель­но, в этот мо­мент Центр уже знает 66 бит из по­сла­ния Штир­ли­ца. Тогда в де­вя­той шиф­ров­ке Штир­лиц пе­ре­даст 49 еди­ниц в каких-то 49 по­зи­ци­ях из уже из­вест­ных Цен­тру и тогда центр пой­мет, что осталь­ные по­зи­ции пра­виль­ные и узна­ет остав­шу­ю­ся часть со­об­ще­ния. Де­ся­тая шиф­ров­ка Штир­ли­цу даже и не при­го­ди­лась.