Задание 8 ЕГЭ по информатике: перебор слов и системы счисления

Что проверяет задание

Задание 8 проверяет умение считать количество слов (последовательностей символов) фиксированной длины над заданным алфавитом — часто это цифры системы счисления с основанием $b$. Проверяются три навыка: подсчёт количества последовательностей без ограничений или с ограничением на число повторений символа; подсчёт слов с дополнительными условиями (сравнения цифр, суммы, положения); подсчёт «слов по порядку» — чисел, цифры которых идут в строго возрастающем или убывающем порядке. Все три навыка опираются на комбинаторику: правило умножения, правило сложения, сочетания и размещения.

Как выглядит формулировка и сколько баллов

Типичная формулировка: задан алфавит (обычно цифры системы счисления с основанием $b$, то есть $0,1,\dots,b-1$) и длина слова $n$. Дополнительно накладывается условие — например, конкретная цифра встречается ровно $k$ раз, или сумма одних цифр больше/меньше других, или цифры идут строго по возрастанию/убыванию. Нужно найти количество слов (чисел), удовлетворяющих условию. Задание оценивается в 1 балл, относится к базовому или повышенному уровню сложности, на решение стоит закладывать 3–5 минут.

Что нужно знать

• Правило умножения: если выбор на каждой из $n$ независимых позиций можно сделать $k_1, k_2, \dots, k_n$ способами, то общее число вариантов равно $k_1 \cdot k_2 \cdot \dots \cdot k_n$.
• Правило сложения: если варианты разбиваются на непересекающиеся группы, общее число равно сумме количеств в каждой группе.
• Число сочетаний: $C_n^k = \dfrac{n!}{k!(n-k)!}$ — количество способов выбрать $k$ элементов из $n$ без учёта порядка.
• Число размещений: $A_n^k = \dfrac{n!}{(n-k)!}$ — количество способов выбрать и упорядочить $k$ элементов из $n$.
• В системе счисления с основанием $b$ используются цифры $0, 1, \dots, b-1$, всего $b$ различных цифр.
• Если речь о $n$-значном числе (а не о произвольной последовательности символов), первая цифра не может быть равна $0$.
• Строго возрастающая или строго убывающая последовательность из $k$ различных цифр однозначно определяется набором этих цифр — порядок в ней фиксирован, поэтому количество таких последовательностей равно $C_b^k$.
• Если условие «символ $x$ встречается ровно $m$ раз», решение строится в два шага: выбор позиций для $x$ — $C_n^m$, и заполнение оставшихся $n-m$ позиций символами из алфавита без $x$.

Методы решения

1. Прямой перебор. Применяется при очень малом числе вариантов, когда проще перечислить все случаи, чем выводить формулу. Мини-пример: сколько двухсимвольных слов из алфавита $\{A,B\}$ существует? Перебором получаем AA, AB, BA, BB — то есть 4 варианта.

2. Правило умножения для независимых позиций. Если на каждую позицию слова можно поставить символ независимо от других (с учётом запрета нуля на первой позиции для чисел), число вариантов на каждой позиции перемножается. Мини-пример: сколько трёхзначных чисел в троичной системе счисления (цифры $0,1,2$), если первая цифра не может быть $0$? Первая позиция — 2 варианта ($1$ или $2$), вторая и третья — по 3 варианта. Итого $2 \cdot 3 \cdot 3 = 18$.

3. Выбор позиций + заполнение оставшихся (для условия «встречается ровно $k$ раз»). Сначала выбираем, на каких позициях стоит фиксированный символ ($C_n^k$ способов), затем оставшиеся позиции заполняем оставшимся алфавитом (без этого символа), чтобы не получить лишних повторений. Мини-пример: в пятибуквенном слове из алфавита $\{А, Б, В\}$ буква А встречается ровно 3 раза, остальные позиции — буквы Б или В в любом количестве. Число позиций для А: $C_5^3 = 10$; оставшиеся 2 позиции заполняются двумя буквами: $2^2 = 4$. Итого $10 \cdot 4 = 40$.

4. Сочетания для строго монотонных последовательностей. Если цифры должны идти строго по возрастанию или убыванию, достаточно выбрать набор цифр — порядок расставится однозначно. Мини-пример: сколько трёхзначных чисел в десятичной системе счисления имеют строго возрастающие цифры? Нуль не может входить в набор (иначе он окажется на первой позиции при возрастающем порядке), поэтому цифры выбираются из $1$–$9$: $C_9^3 = 84$.

5. Группировка по промежуточной величине для сравнительных условий. Если условие связывает цифры неравенством (например, сумма одних больше другой), удобно перебрать возможные значения этой суммы (или разности) и для каждого значения посчитать, сколько вариантов даёт нужное неравенство, а затем сложить результаты. Этот метод подробно разобран в примере 2 ниже.

Алгоритм решения по шагам

1. Определить алфавит: если это система счисления с основанием $b$, зафиксировать множество цифр $0,\dots,b-1$.
2. Установить длину слова (числа) $n$.
3. Проверить, идёт ли речь о числе — если да, первая цифра не может быть $0$.
4. Внимательно прочитать условие: есть ли требование «ровно $k$ раз», есть ли требование строгого порядка цифр, есть ли сравнение (сумма, разность) между цифрами на конкретных позициях.
5. Выбрать подходящий метод из раздела выше (произведение, сочетания, выбор позиций, группировка).
6. Разбить задачу на независимые этапы, посчитать количество вариантов на каждом этапе.
7. Перемножить или сложить результаты этапов в зависимости от того, независимы они (умножение) или взаимоисключающие случаи (сложение).
8. Проверить, не пересчитаны ли одинаковые варианты несколько раз, и сверить порядок полученного числа со здравым смыслом.

Разбор примеров

Пример 1. Шифр кодового замка — последовательность из пяти символов, каждый из которых цифра от 1 до 4. Цифра 1 встречается ровно два раза, остальные допустимые цифры (2, 3, 4) могут встречаться любое количество раз или не встречаться совсем. Сколько различных шифров можно задать?

Шаг 1. Длина последовательности $n=5$, алфавит — цифры $\{1,2,3,4\}$.

Шаг 2. Условие «ровно два раза» относится к цифре 1 — применяем метод «выбор позиций + заполнение оставшихся».

Шаг 3. Выбираем 2 позиции из 5 для цифры 1: $C_5^2 = \dfrac{5!}{2!3!} = 10$.

Шаг 4. Оставшиеся 3 позиции нужно заполнить так, чтобы цифра 1 там не встречалась (иначе она встретится больше двух раз), значит используем только цифры $\{2,3,4\}$ — три варианта на каждую из трёх позиций: $3^3 = 27$.

Шаг 5. Так как выбор позиций и заполнение оставшихся позиций — независимые этапы, применяем правило умножения: $10 \cdot 27 = 270$.

Ответ: 270.

Пример 2. Сколько существует различных трёхзначных чисел, записанных в четверичной системе счисления, в записи которых сумма первой и последней цифры строго больше цифры, стоящей посередине?

Шаг 1. В четверичной системе цифры — $0,1,2,3$. Обозначим цифры числа $a$ (первая), $b$ (средняя), $c$ (последняя). Так как число трёхзначное, $a \in \{1,2,3\}$, а $b, c \in \{0,1,2,3\}$.

Шаг 2. Условие: $a + c > b$. Применяем метод группировки по промежуточной величине $s = a+c$.

Шаг 3. Переберём возможные значения $s$ и посчитаем, сколько пар $(a,c)$ дают каждое значение суммы:

• $s=1$: $(1,0)$ — 1 пара;
• $s=2$: $(1,1),(2,0)$ — 2 пары;
• $s=3$: $(1,2),(2,1),(3,0)$ — 3 пары;
• $s=4$: $(1,3),(2,2),(3,1)$ — 3 пары;
• $s=5$: $(2,3),(3,2)$ — 2 пары;
• $s=6$: $(3,3)$ — 1 пара.

Шаг 4. Для каждого значения $s$ считаем, сколько значений $b \in \{0,1,2,3\}$ удовлетворяют $b < s$: количество равно $\min(s,4)$ при $s \ge 1$.

• $s=1 \Rightarrow 1$ значение;
• $s=2 \Rightarrow 2$;
• $s=3 \Rightarrow 3$;
• $s=4 \Rightarrow 4$;
• $s=5 \Rightarrow 4$;
• $s=6 \Rightarrow 4$.

Шаг 5. Для каждого $s$ умножаем число пар $(a,c)$ на число допустимых $b$ и складываем: $$1\cdot1 + 2\cdot2 + 3\cdot3 + 3\cdot4 + 2\cdot4 + 1\cdot4 = 1+4+9+12+8+4 = 38.$$

Ответ: 38.

Пример 3. Сколько существует различных четырёхзначных чисел, записанных в семеричной системе счисления, в записи которых цифры следуют слева направо в строго убывающем порядке?

Шаг 1. В семеричной системе цифры — $0,1,2,3,4,5,6$, всего 7 различных цифр.

Шаг 2. Число должно быть четырёхзначным, а цифры строго убывают слева направо. Значит нужно выбрать 4 различные цифры из 7 доступных — порядок их расположения определяется автоматически (по убыванию), других вариантов расстановки нет.

Шаг 3. Первая цифра автоматически не равна $0$, так как $0$ — наименьшая цифра и при строгом убывании окажется последней, а не первой. Значит дополнительно проверять условие «первая цифра не ноль» не нужно — оно выполняется само по себе.

Шаг 4. Считаем количество способов выбрать 4 цифры из 7 без учёта порядка: $C_7^4 = \dfrac{7!}{4!3!} = 35$.

Ответ: 35.

Типичные ошибки и ловушки

• Забывают, что первая цифра числа не может быть $0$, и переоценивают количество вариантов на первой позиции.
• Путают сочетания и размещения: для строго монотонных последовательностей порядок цифр фиксирован набором, поэтому используются именно сочетания, а не размещения — иначе результат окажется завышенным в $k!$ раз.
• При условии «символ встречается ровно $k$ раз» забывают исключить этот символ из оставшихся позиций — это приводит к завышению ответа, так как символ может встретиться больше $k$ раз.
• При сравнительных условиях (сумма, разность цифр) пытаются перебирать все комбинации напрямую без группировки, что резко увеличивает время решения и повышает риск ошибки; группировка по промежуточной переменной ускоряет и упорядочивает подсчёт.
• Ошибаются в количестве цифр системы счисления: например, в семеричной системе цифры — это $0$–$6$ (7 цифр), а не $1$–$7$.
• Не проверяют, требуется ли строгое неравенство или нестрогое ($>$ или $\ge$) — это меняет границы суммирования и итоговый ответ.
• Забывают, что при подсчёте убывающих или возрастающих последовательностей ноль может входить в набор цифр только на определённой позиции (например, только как последняя цифра при убывании), и это нужно учитывать отдельно, если задача не гарантирует это автоматически.

Как готовиться

• Решить подряд несколько задач каждой подтемы отдельно: сначала на подсчёт последовательностей без ограничений, затем с ограничением на количество повторений, затем на строгий порядок цифр, затем на сравнительные условия.
• Составить и держать под рукой таблицу формул: правило умножения, правило сложения, $C_n^k$, $A_n^k$, а также таблицу «основание системы счисления — количество цифр».
• Тренироваться быстро определять допустимый диапазон первой цифры числа и полный набор цифр системы счисления по её основанию.
• При решении новой задачи письменно разбивать её на этапы (выбор позиций, заполнение, группировка) — это снижает риск случайных ошибок.
• Проверять полученный ответ на маленьких аналогичных примерах прямым перебором, чтобы убедиться в верности выбранного метода.
• После каждой решённой задачи сверяться с чек-листом типичных ошибок из предыдущего раздела.