Найдём наи­бо­лее ко­рот­кие пред­став­ле­ния для всех букв. Ко­до­вые слова 01 и 00 ис­поль­зо­вать нель­зя, по­сколь­ку тогда на­ру­ша­ет­ся усло­вие Фано. Ис­поль­зу­ем, на­при­мер, для буквы Л ко­до­вое слово 11. Тогда для четвёртой буквы нель­зя по­до­брать ко­до­вое слово, не на­ру­шая усло­вие Фано. Сле­до­ва­тель­но, для остав­ших­ся двух букв нужно ис­поль­зо­вать трёхзнач­ные ко­до­вые слова. За­ко­ди­ру­ем буквы Л и М ко­до­вы­ми сло­ва­ми 110 и 111. Тогда сум­мар­ная длина всех четырёх ко­до­вых слов равна 1 + 2 + 3 + 3 = 9.

Ответ: 9.

Буква С не может ко­ди­ро­вать­ся стро­кой, ко­то­рая на­чи­на­ет­ся с 0, по­сколь­ку О имеет код 0.

Буква С не может ко­ди­ро­вать­ся как 1, так как ко­ди­ро­ва­ние буквы Т на­чи­на­ет­ся с 1.

Буква С не может ко­ди­ро­вать­ся как 10, так как ко­ди­ро­ва­ние буквы П на­чи­на­ет­ся с 10.

Буква С не может ко­ди­ро­вать­ся как 11, так как ко­ди­ро­ва­ние буквы Т на­чи­на­ет­ся с 11.

Буква С может ко­ди­ро­вать­ся как 101  — это наи­мень­шее воз­мож­ное зна­че­ние.

Ответ: 101.

Пе­ре­чис­лим воз­мож­ные коды в по­ряд­ке воз­рас­та­ния длины. Стоит сразу ска­зать, что любой код, на­чи­на­ю­щий­ся с 0, не под­хо­дит, так как код А  — 0, по­это­му смот­рим толь­ко на те, что на­чи­на­ют­ся с 1.

1  — нель­зя, Б, В на­чи­на­ют­ся с 1.

10  — нель­зя из-⁠за Б.

11  — нель­зя из-⁠за В.

111  — можно ис­поль­зо­вать, пусть это будет код Д.

100  — также можно ис­поль­зо­вать, но если мы его возьмём, то не будет боль­ше кодов, ко­то­рые можно будет взять, так как все коды, на­чи­на­ю­щи­е­ся с 0, уже нель­зя брать, а все коды, на­чи­на­ю­щи­е­ся с 1 и име­ю­щие длину боль­ше трёх, на­чи­на­ют­ся с одной из этих строк: 100, 101, 110, 111.

Рас­смот­ре­ли все коды с дли­на­ми от 1 до 3, по­это­му те­перь до­ста­точ­но взять любые два под­хо­дя­щие кода длины 4. На­при­мер, 1000 и 1001.

В сумме длина кодов 1 + 3 + 3 + 3 + 4 + 4  =  18.

Ответ: 18.

За­ме­тим, что для ал­фа­ви­та из трёх букв, код с наи­мень­шей сум­мар­ной дли­ной ко­до­вых слов, удо­вле­тво­ря­ю­щий усло­вию Фано имел бы длину 1 + 2 + 2  =  5. Для ал­фа­ви­та из четырёх букв: 1 + 2 + 3 + 3  =  9. Ана­ло­гич­но можно по­лу­чить ми­ни­маль­ную длину сум­мар­ную длину ко­до­вых слов для ал­фа­ви­та, со­дер­жа­ще­го про­из­воль­ное число сим­во­лов.

Удо­сто­ве­рим­ся, что, ис­поль­зуя ко­до­вые слова, при­ведённые в усло­вии, можно по­стро­ить код, удо­вле­тво­ря­ю­щий усло­вию Фано и име­ю­щий наи­мень­шую сум­мар­ную длину. Будем ис­поль­зо­вать для буквы D ко­до­вое слово 1000, для буквы E  — ко­до­вое слово 10010, для буквы F  — 10011.

Сум­мар­ная длина та­ко­го кода 1 + 2 + 3 + 4 + 5 + 5  =  20.

Ответ: 20.

Для на­хож­де­ния ко­до­вых слов будем ис­поль­зо­вать дво­ич­ное де­ре­во, в ко­то­ром от каж­до­го узла от­хо­дит две ветви, со­от­вет­ству­ю­щие вы­бо­ру сле­ду­ю­щей цифры кода. Буквы будем раз­ме­щать на ко­неч­ных узлах де­ре­ва  — ли­стьях. Усло­вие Фано вы­пол­ня­ет­ся, по­сколь­ку при про­хо­де от корня де­ре­ва к букве в се­ре­ди­не пути не встре­ча­ет­ся дру­гих букв.

При­мер де­ре­ва, обес­пе­чи­ва­ю­ще­го ми­ни­маль­ную сумму длин всех шести кодов, изоб­ра­жен на ри­сун­ке.

Сум­мар­ная длина та­ко­го кода 1 + 2 + 4 + 4 + 4 + 4  =  19.

Ответ: 19.