№ 255. По каналу связи передаются сообщения, содержащие только пять букв: В, Р, Е, М, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: В — 101, М — 01. Какова минимальная общая длина кодовых слов для всех пяти букв?

Код 01 занят буквой М, а код 101 — буквой В. Можно назначить трём оставшимся буквам коды 00, 11 и 100. Ни один из этих кодов не является началом другого, и они не конфликтуют с заданными кодами.

Суммарная длина равна \(2+3+2+2+3=12\): длины заданных кодов — 3 и 2, а новых — 2, 2 и 3.

Меньше получить нельзя: в ветви 1 код 101 оставляет свободными только два непересекающихся места для кодов, а вне этой ветви доступно лишь одно кодовое слово длины 2 — 00. Поэтому для пяти букв при указанных кодах суммарная длина не может быть меньше 12.

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