За­ме­тим, что для ал­фа­ви­та из трёх букв, код с наи­мень­шей сум­мар­ной дли­ной ко­до­вых слов, удо­вле­тво­ря­ю­щий усло­вию Фано имел бы длину 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 + 3 + 4 + 5 + 5  =  20.

Ответ: 20.