20. По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Известны кодовые слова для некоторых букв: А — 010, Б — 011, Г — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?

Коды 010, 011 и 100 уже заняты. Можно назначить М, И, Я кодовые слова длины 3, а Р — свободное слово 11 длины 2. Например: М — 000, И — 001, Я — 101, Р — 11. Ни одно слово не является началом другого.

В слове МАГИЯ пять букв; длины кодов М, А, Г, И, Я в таком варианте равны 3, 3, 3, 3, 3.

Меньше 15 знаков получить нельзя: для четырёх ещё не закодированных букв нужно назначить четыре слова. Если одно из слов длины 2 отдать букве М, И или Я, оставшимся трём буквам и букве Р понадобятся как минимум три слова длины 3. Тогда суммарная длина кодов букв слова всё равно не меньше 3 + 3 + 2 + 3 + 3 = 14. Такая оценка достижима: М — 11, И — 000, Я — 001, Р — 101. Остальные известные коды сохраняются; код удовлетворяет условию Фано.

Ответ: 14 двоичных знаков.