О разведчиках и кодах Хемминга

- Скажите, какая разница между разведчиком и шпионом?
 - Если это "свой", то разведчик, а если "чужой" - то шпион!

"Командир разведывательного взвода и восемь его разведчиков десантировались на вражеский остров. Им нужно обнаружить на этом острове секретный вражеский объект. Ровно через два часа они должны вновь собраться на месте высадки и ждать самолета. Командиру точно известно, что объект находится в часе ходьбы по одной из четырех дорог, которые сходятся в точке приземления разведчиков. Но по какой именно дороге? Командир принимает решение: разделить разведчиков на четыре группы по два человека и отправить по всем дорогам, дав каждой группе час на путь "туда" и час на возвращение. Но тут вмешиваются вражеские шпионы..."

Неплохой сценарий для шпионского фильма? А на самом деле это одна из красивейших задач теории информации. Какое отношение имеет теория информации к вражеским шпионам? Не торопитесь, дослушайте до конца.

"...Командир знает, что двое человек из его разведгруппы - вражеские шпионы (вот только не знает, кто). Они, конечно, не посмеют ослушаться приказа, но почти наверняка попытаются не выдать секретный объект. Проще говоря - будут врать. А значит, посылать людей по двое совершенно бессмысленно: если случайно окажется, что в одну пару попали оба шпиона, то возможен вариант, когда все группы вернутся с совершенно одинаковым донесением "объект не обнаружен". Кто при этом соврал - не известно. Задание провалено, а Центр за это по головке не погладит. И даже если шпионы окажутся в разных группах, беды все равно не избежать: в обеих группах один разведчик будет утверждать, что видел объект, а другой - что ничего не видел. И все четверо будут обвинять своих напарников в шпионаже. Поди разберись!..."

Командир задумался (впрочем, тут я завираюсь - все размышления остались позади, а правильное решение было найдено им еще по пути на остров). Итак...

"...По одной дороге командир отправился сам. По двум другим направил группы из трех разведчиков. По последней дороге разведчики пошли вдвоем.

Прошло два часа. Все вернулись обратно, быстро погрузились в прилетевший самолет и улетели. Уже в самолете командир опросил всех. К его удивлению, никакого вранья не было: одна группа разведчиков дружно сообщила, что объект найден, а остальные так же дружно подтвердили, что ничего не видели. Подумав, командир догадался, что его шпионы тоже не лыком шиты: как только они сообразили, что командир все равно сможет узнать правду, тут же решили не "засвечиваться".

Как же командир собирался обнаружить обман? И, самое главное, как можно в случае обмана определить настоящее местонахождение объекта?

Рассуждать можно примерно так (ограничимся только теми случаями, когда сам командир объекта не увидит. Сообщения группы разведчиков, естественно, делятся на противоречивые и непротиворечивые):

1. Если в группе из трех человек все сообщения непротиворечивы, то им можно верить (поскольку из троих хотя бы один - не шпион, то есть говорит правду);
   
2. Если в группе из двух человек сообщения не противоречат одно другому, то ложью это может быть в единственном случае: когда оба человека в этой группе  - шпионы. Но тогда в двух других группах все честны, а значит, донесения этих двоих опровергаются всеми остальными;
   
3. Кроме второго случая, всем непротиворечивым сообщениям от групп можно верить. Если противоречивые сообщения поступили только от одной группы - все нормально: истина легко устанавливается по информации, полученной от остальных;
   
4. Если же противоречия имеются в донесениях двух групп, то в каждой из них - ровно один шпион. Поскольку хотя бы в одной из них три человека, то двое из них говорят правду, а третий врет. Чтобы узнать правду, достаточно "прислушаться к большинству". А поскольку всегда есть еще третья - непротиворечивая - группа, то для двух дорог истина уже известна, и для третьей дороги она определяется методом исключения.

Какое же отношение имеет эта красивая логическая задача к теории информации? Оказывается, самое прямое. Именно теория информации занимается исследованием вопросов об исправлении ошибок при передаче сигналов. Будем считать, что каждое сообщение о наличии объекта на дороге закодировано единичным битом, а каждое сообщение о его отсутствии - нулевым. Таким образом, командир получает от разведчиков восемь бит информации. Если бы вранья не было вовсе, то командир бы получил один из трех вариантов:

• 111 000 00 (объект на второй дороге);
• 000 111 00 (объект на третьей дороге);
• 000 000 11 (объект на четвертой дороге).

А так как возможны "искажения передачи информации вследствие диффамации" (то есть вранья), то ему вполне могут сообщить что-нибудь типа:

• 101 100 00,

и нужно разобраться, какой из трех вариантов имеет место на самом деле.

Это и есть типичная задача теории информации: передается любое сообщение из некоторого набора "кодовых слов", но при этом в словах возможны искажения (обычно, как и в данном случае, искажения возникают из-за помех в работе канала связи). Каждое искажение означает изменение одного двоичного разряда.
Расстоянием Хемминга между двумя словами называется количество несовпадающих в них разрядов. Очевидно, что изменив произвольным образом два разряда, мы окажемся от исходного кодового слова на расстоянии 2. А поскольку наши три кодовых слова находятся друг от друга на расстоянии не меньше пяти (точнее, 5 или 6), то "расшифровка" искаженного сообщения чрезвычайно проста: нужно определить ближайшее к нему кодовое слово. Таким образом, решение укладывается в одну короткую инструкцию: сравнить полученное сообщение со всеми тремя правильными и выбрать ближайшее (в смысле расстояния Хемминга).

Это же рассуждение лежит в основе доказательства одной из самых общих теорем теории информации:

"Если расстояние между любыми двумя кодовыми словами равно 2n+1, то такой код позволяет исправить любые n ошибок".

В заключение предложу еще две вариации на ту же тему:

1. Как быть командиру, если разведчиков (вместе с ним) - шестнадцать, дорог - пять, а шпионов - трое?
2. В языке племени Мумбо-Юмбо всего две буквы: М и Ю. Все слова этого языка состоят из семи букв, причем каждые два слова отличаются по крайней мере в трех местах. Докажите, что в словаре мумбо-юмбского языка не более шестнадцати слов.