№ 27759. По каналу связи передаются сообщения, содержащие только буквы из набора: А, И, К, Р, Н, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Р — 1, Н — 01. Для оставшихся букв А, И, К и С кодовые слова неизвестны. Какое количество двоичных знаков требуется для кодирования слова КАРАСИК, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Код Р = 1 занимает ветвь 1, а Н = 01 — часть ветви 0. Четыре неизвестные буквы можно закодировать словами 000, 001, 10 и 11: все они имеют длину 3 и ни одно не является началом другого. Короче кодировать их нельзя: при таком расположении фиксированных кодов для четырёх букв нет четырёх свободных слов меньшей длины.

В слове КАРАСИК буквы К и А встречаются по 2 раза, И и С — по 1 разу. Неизвестные буквы дают (2 + 2 + 1 + 1) · 3 = 18 знаков. Буква Р встречается 1 раз, её код имеет длину 1, значит, для неё требуется ещё 1 знак.

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