По условию Фано новое кодовое слово не может совпадать с известным (0111, 0110), быть его началом или начинаться с него.
Заняты сами известные слова и их начала (0, 01, 011), поэтому новые слова можно начинать только со свободных ветвей кодового дерева: 00, 010, 1.
Кодовые слова нужны ещё 4 буквам (А, В, М, Р), а свободных ветвей 3 — одну ветвь придётся разделить: ветвь x делится на x0 и x1, и её слова становятся на знак длиннее.
В слове САМОВАР: буква А — 2 раза, буквы В, М, Р — по одному разу. Короткие слова выгодно отдавать частым буквам.
Наборы слов, которые могут дать наименьшую длину (любой другой набор по каждой длине не короче одного из них):
- 1, 000, 001, 010 (длины 1, 3, 3, 3): А — 1, В — 000, М — 001, Р — 010; длина кода 2 · 1 + 3 + 3 + 3 = 11;
- 00, 10, 11, 010 (длины 2, 2, 2, 3): А — 00, В — 10, М — 11, Р — 010; длина кода 2 · 2 + 2 + 2 + 3 = 11;
- 1, 00, 0100, 0101 (длины 1, 2, 4, 4): А — 1, В — 00, М — 0100, Р — 0101; длина кода 2 · 1 + 2 + 4 + 4 = 12.
Наименьшая длина кода букв А, В, М, Р — 11.
Буквы с известным кодом: О (0111, 4 знака) встречается 1 раз — 4; С (0110, 4 знака) встречается 1 раз — 4.
Итого: 11 + 8 = 19.