Билет 1 — демоверсия ЕГЭ-2026; остальные билеты — задания в формате экзамена (открытый сборник или тренировочные по образцу). Это тренировочные материалы, а не официальные КИМ. Ответы пересчитаны и сверены.
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 0, Б — 100, В — 101, Г — 1100.
Вопрос. Укажите минимальную суммарную длину кодовых слов для оставшихся трёх букв (Д, Е, Ж), при которой условие Фано будет выполняться. В ответе запишите целое число.
Не знаешь, как решать?
Потренируйся на дереве кода: расставляй коды по свободным местам и строй дерево по кодам.
Дано. Выпишем все буквы и известные коды (неизвестные оставим пустыми):
буква
А
Б
В
Г
Д
Е
Ж
код
0
100
101
1100
Коды нужны для букв Д, Е, Ж.
2Шаг 2
Подход. Задача на условие Фано: ни один код не должен быть началом другого. Отмечаем занятые коды листьями двоичного дерева (влево «0», вправо «1») и размещаем оставшиеся буквы только в свободных местах; затем суммируем длины новых кодов.
3Шаг 3
Занятые коды: А=0, Б=100, В=101, Г=1100. Рисуем двоичное дерево: занятые коды — листья, свободные места (узел 1101 и поддерево 111) показаны пунктиром.
Заданные коды А=0, Б=100, В=101, Г=1100. Свободны узел 1101 и поддерево 111 (пунктир).
заданный кодсвободная ветка
4Шаг 4
Ветка «0» занята целиком — там буква А. Ветка «10» ведёт только к листьям 100 и 101 (буквы Б и В), места под ними нет. В ветке «11» занят код 1100 (Г), а свободны короткий узел 111 и лист 1101.
Свободных мест всего два: узел 111 (3 бита) и лист 1101 (4 бита).
заданный кодсвободная ветка
5Шаг 5
На первый взгляд выгодно занять самый короткий узел 111 (3 бита). Но как только 111 становится листом, его продолжения 1110 и 1111 закрываются, и две оставшиеся буквы помещаются только под 1101 — это коды 11010 и 11011 по 5 бит. Сумма: 3+5+5=13, а не минимум.
Если занять короткий 111 как лист, две буквы уходят на 5-й уровень: 3+5+5=13.
заданный кодболее длинный вариант
6Шаг 6
Выгоднее не гнаться за коротким 111, а занять три свободных листа 4-го уровня: 1110 (Д), 1111 (Е) и 1101 (Ж). Условие Фано выполняется, все коды — листья.
Оптимально: Д=1110, Е=1111, Ж=1101 (добавленные коды — фиолетовые).
заданный коддобавленный код
7Шаг 7
Суммарная длина: 3⋅4=12.
Итог: 4+4+4=12.
заданный коддобавленный код
8Шаг 8
Почему это минимум. Использовать короткий узел 111 как лист нельзя без потерь: он закрывает 1110 и 1111, и тогда две буквы уходят на 5-й уровень — выходит 13. Значит, все три буквы должны стоять на 4-м уровне, а свободных листьев там ровно три: 1101, 1110, 1111. Это единственное размещение с суммой 12; любые коды глубже дают больше. Ловушка. Иногда отвечают 11=3+4+4, беря коды 111, 1110 и 1111. Так нельзя: 111 является началом кодов 1110 и 1111, условие Фано нарушено — встретив строку «111», приёмник не поймёт, это отдельная буква или начало более длинного кода.
Так нельзя: код 111 не лист, поэтому 1110 и 1111 под ним запрещены — сумма 11 недопустима.
заданный коддобавленный коднельзя: код должен быть листом
9Шаг 9
Почему нельзя дорастить заданный код. Новые буквы нельзя вешать и под уже известные коды А = 0, Б = 100, В = 101, Г = 1100. Если продлить такой код, он перестанет быть листом: встретив «100» (или «1100»), приёмник не поймёт, это буква Б (или Г) или начало более длинного кода. Поэтому новые буквы ставятся только в свободные места — узел 111 и лист 1101.
Правильный ответ этого билета: 12
Проверка: свободны узел 1101 и поддерево 111; минимум дают коды 1101, 1110, 1111 по 4 бита → 3⋅4=12. Исчерпывающий перебор подтверждает, что меньшей суммы нет.
Теория и другие билеты
Разбор с нуля, типовые ошибки, частые вопросы и все билеты задания 4 — на странице задания.