6) По каналу связи передаются сообщения, содержащие только семь букв: С, В, Е, Т, И, Л и О. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: С — 11, В — 01, Е — 101, Т — 1000, И — 00. Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите сумму длин кодовых слов для букв Л, О.

Код по условию Фано должен быть префиксным: ни одно кодовое слово не может быть началом другого.

Слова 00, 01, 11 и 10 уже заняты на длине 2. Поэтому кодовое слово для каждой из оставшихся букв должно начинаться с 10: ветвь 00 и 01 уже занята, а 11 тоже занята.

Продолжим ветвь 10. Слово 1000 уже принадлежит букве Т, поэтому минимальные доступные слова в этой ветви — 1001 и 101. Однако 101 уже занято буквой Е; значит, для двух букв Л и О подходят, например, 1001 и 10000. Они удовлетворяют условию Фано, а сумма длин равна 4 + 5 = 9.

Меньшей суммы быть не может: оба слова должны продолжать ветвь 10; длина 2 невозможна, а единственное свободное слово длины 3 — 101 — занято. Следовательно, каждое из двух новых слов имеет длину не менее 4, но для двух слов длины 4 потребовались бы оба потомка 1000 и 1001; 1000 уже занято. Минимальный набор длин — 4 и 5.

Ответ: 9.