№ 23550. По каналу связи передаются сообщения, содержащие только восемь букв: А, В, Е, Л, Н, О, С, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: В — 10, Л — 01, С — 0001, Я — 111. Для четырёх оставшихся букв А, Е, Н и О кодовые слова неизвестны. Какое наименьшее количество двоичных знаков требуется для кодирования слова ВСЕЛЕННАЯ?

Из известных кодов следуют три свободных коротких пути в кодовом дереве: 0000 (длина 4), 001 (длина 3) и 110 (длина 3). Для кодирования четырёх неизвестных букв нужно разделить один из этих путей на два дочерних слова. Минимальную суммарную длину даёт разделение 0000 на 00000 и 00001: четыре кода для неизвестных букв имеют длины 3, 3, 5 и 5.

В слове ВСЕЛЕННАЯ буквы Е и Н встречаются по 2 раза, а В, С, Л и Я — по 1 разу; буква А встречается 1 раз, О в слове не встречается. Назначим Е и Н свободным словам длины 3, А — слову длины 5, О — другому слову длины 5. Тогда неизвестные буквы требуют 2 · 3 + 2 · 3 + 1 · 5 = 17 знаков.

Известные буквы требуют: В — 2, С — 4, Л — 2, Я — 3 знака, всего 11. Итого 17 + 11 = 28.

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