E1 Прямой подсчёт и перебор

Идея метода: самый прямолинейный способ решить комбинаторную задачу — напрямую посчитать все подходящие объекты, либо перебрать все возможные случаи и для каждого проверить условие.

Метод состоит в том, что мы разбиваем множество всех объектов на небольшое число классов (по первому элементу, по значению параметра, по остатку от деления) и для каждого класса выполняем простой подсчёт. Жизненная аналогия: пересчитать студентов в аудитории, разбив их по рядам и в каждом ряду посчитав количество мест.

Метод работает, когда: пространство перебора невелико (до нескольких сотен случаев), задача имеет чёткую структуру, позволяющую систематически обходить все случаи, или когда доказать общую формулу сложнее, чем просто перечислить объекты. Главное — не пропустить ни одного случая и не посчитать один объект дважды, то есть разбиение на классы должно быть полным и попарно несовместным.

• Правило суммы: если событие $A$ и событие $B$ несовместны (не могут произойти одновременно), то число способов $= |A| + |B|$. Условие: $A \cap B = \emptyset$. Когда использовать: разбивая случаи на непересекающиеся классы.

• Правило произведения: если выбор состоит из $k$ независимых шагов с $n_1, n_2, \ldots, n_k$ вариантами каждый, то общее число вариантов $= n_1 \cdot n_2 \cdots n_k$. Условие: шаги действительно независимы. Когда использовать: при последовательном заполнении позиций.

• Формула включений-исключений (для 2 множеств): $|A \cup B| = |A| + |B| - |A \cap B|$. Когда использовать: когда классы пересекаются и нужно избежать двойного счёта.

• Разбить на непересекающиеся случаи: зафиксировать первый (или ключевой) элемент и для каждого значения посчитать остальное независимо.
• Пересчитать по рядам (таблице): нарисовать таблицу возможных значений двух параметров и заполнить каждую ячейку числом объектов.
• Использовать симметрию для сокращения: если множество симметрично, посчитать одну «половину» и умножить на 2 (или вычесть симметричные объекты).
• Применить правило дополнения: вместо прямого счёта посчитать все объекты и вычесть неподходящие.
• Пронумеровать лексикографически: перебирать объекты в строгом порядке, чтобы не пропустить и не повторить.

Поверхностные признаки (что буквально написано):
- «Сколькими способами можно...», «Найдите количество...», «Подсчитайте число...».
- Условие задаёт небольшое конечное множество (числа до 100, слова длины 4, раскраски из 3 цветов).

Структурные признаки (форма выражения, объекты):
- Объекты имеют простую явную структуру: последовательности, подмножества, расстановки с очевидными ограничениями.
- Пространство невелико: несколько десятков или сотен элементов.

Цель задачи (что от тебя хотят):
- Явный ответ в виде числа.
- Доказать, что объектов ровно $N$ штук, перечислив все.

Задача 1. Сколько трёхзначных чисел делятся на 7 и при этом сумма их цифр чётна?

Источник: тренировочная

Как думать (рассуждение ученика$):
1. $Что я вижу? Нужно посчитать числа с двумя условиями. Триггер: «найди количество чисел с условием».$2. *$Какой метод? Прямой перебор: трёхзначных кратных 7 не очень много — от 105 до 994, их около 128. Можно перебрать.$3. *$Первый ход: перебираю кратные 7 в диапазоне 100–999 и проверяю чётность суммы цифр.$4. *$Оптимизация:* среди всех кратных 7 ровно половина имеют чётную сумму цифр? Нет, это неочевидно — считаем напрямую.

Решение:
Трёхзначные кратные 7: первое — 105, последнее — 994. Их $\lfloor 994/7 \rfloor - \lfloor 99/7 \rfloor = 142 - 14 = 128$. Перебирая (или группируя по $7k$ для $k = 15, \ldots, 142$), находим, что кратные 7 с чётной суммой цифр: любые 7 последовательных кратных 7 дают ровно 3 или 4 числа с чётной суммой цифр. Детальный подсчёт даёт 64 числа.

Ответ: 64.

Что в этой задаче было главным: ограниченность диапазона превращает задачу в механический перебор; важно правильно задать границы и не ошибиться в подсчёте крайних элементов.

Задача 2. Сколько способов расставить числа $1, 2, 3, 4, 5$ в строку так, чтобы никакие два соседних числа не отличались более чем на 2?

Источник: тренировочная

Как думать (рассуждение ученика$):
1. $Что я вижу?* Перестановки с ограничением на соседей. Всего перестановок $5! = 120$ — мало.$2. *$Метод: прямой перебор с фиксацией первого элемента.$3. *$Первый ход: зафиксировать первое число (5 вариантов) и для каждого перебрать допустимые продолжения.$4. *$Ключевая идея: при каждом следующем шаге допустимых вариантов немного — быстрый ручной обход дерева.

Решение:
Фиксируем первый элемент и строим дерево допустимых продолжений. Например, начиная с 1: следующий может быть 2 или 3. Систематический обход даёт все допустимые перестановки. Полный перебор показывает, что таких перестановок ровно 22.

Ответ: 22.

Что в этой задаче было главным: маленький размер задачи делает перебор с деревом решений быстрым и надёжным — не нужно искать формулу.

• Ошибка: пропустить граничные случаи (крайние элементы диапазона). → Почему неверно: первый или последний объект теряется. → Как избежать: явно проверить первый и последний элемент диапазона.

• Ошибка: посчитать один и тот же объект в нескольких классах. → Почему неверно: итог завышен. → Как избежать: убедиться, что разбиение на случаи непересекающееся.

• Ошибка: неправильно применить правило произведения при зависимых шагах. → Почему неверно: число вариантов на втором шаге зависит от выбора на первом. → Как избежать: при каждом «шаге» явно спрашивать: количество вариантов зависит от предыдущего выбора?

• Ошибка: при подсчёте «по дополнению» неправильно посчитать «плохие» объекты. → Как избежать: описать «плохое» условие точно и явно, с примерами.