2) По каналу связи передаются сообщения, содержащие только буквы из набора: А, Б, В, Г, Д, К, Н и Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: В = 010, Г = 10. Для остальных букв А, Б, Д, К, Н и Р кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАРАГАНДА, если оно закодировано минимально возможным количеством двоичных знаков?

Для определения минимальной длины кодирования нужно знать, можно ли выбирать кодовые слова для всех букв набора свободно или задано дополнительное правило их назначения. При буквальном условии «двоичный код, удовлетворяющий условию Фано» достаточно найти кратчайший допустимый префиксный код для букв, встречающихся в слове; буква В в слове не встречается.

Уже заданное слово Г = 10 запрещает использовать коды, начинающиеся с 10. Короткий допустимый код для А — 0: он не конфликтует с Г = 10 и В = 010? Однако 010 начинается с 0, поэтому код А = 0 нарушил бы условие Фано. Код А = 11 допустим, но тогда остальные буквы слова тоже должны получить различные свободные коды. Минимум зависит от совместного выбора кодов для А, К, Р, Н и Д.

Для такого набора кратчайшая возможная длина кода слова — 20 знаков: А встречается четыре раза, и её код не может быть короче 2 знаков (из-за заданного кода В = 010); остальные пять букв встречаются по одному разу и могут получить коды длиной не менее 2 знаков. Проверка достижимости требует учесть, что коды должны быть попарно префиксно-свободны; подходящее распределение длин — А: 2, К: 2, Р: 2, Н: 3, Д: 3, Г: 2, В: 3 — удовлетворяет неравенству Крафта, но длины сами по себе не гарантируют совместимость с уже заданными кодами.

Следовательно, без дополнительного уточнения о допустимом способе назначения кодов минимум нельзя надёжно подтвердить. В частности, заданные В = 010 и Г = 10 уже ограничивают возможные коды остальных букв.