Комбинаторика без перебора. 18 задач с решениями

Зачем здесь задачи, а не пересказ правила

В теме «комбинаторика» ошибка часто появляется не из-за сложной арифметики, а из-за неправильно прочитанного условия. Поэтому каждая глава начинается с маленькой ситуации и вопроса: что именно требуется найти и какие данные действительно участвуют в ответе.

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

Задачи не копируют чужие учебники и не обещают оценку на контрольной. Это самостоятельный практикум: понять условие, записать модель, сделать вычисление, проверить смысл ответа и увидеть типичную ошибку.

Как читать решение

Сначала попробуйте решить задачу самостоятельно. Если ответ не находится, прочитайте только раздел «Метод»: он подсказывает направление, но не заменяет решение.

Затем сравните не только последнюю строку, но и рассуждение. Совпавшее число ещё не доказывает, что способ был правильным: иногда две ошибки случайно дают красивый результат.

После основной задачи выполните самостоятельную. Она похожа по приёму, но не является простой заменой имени или одного числа. Цель — перенести способ на соседнюю ситуацию.

Задача 1. Обед из супа и салата: посчитать варианты

Учебная ситуация: обед из супа и салата. Нужно понять, считаем ли мы пары, роли, порядок или независимые шаги.

Сколько вариантов возможно и почему здесь используется именно это правило счёта?

Сначала решите, важен ли порядок. Если роли или позиции различаются, порядок важен; если выбирается просто набор, порядок не важен.

Затем решите, являются ли выборы независимыми шагами. Для независимых шагов работает произведение, для пары без порядка нужно убрать двойной счёт.

Всего вариантов 12: для каждого из 3 первых выборов есть 4 вторых.

Здесь выполняются два независимых шага. Сначала выбираем один вариант из 3, затем к нему можно присоединить один вариант из 4.

Правило произведения даёт 3 × 4 = 12. Мы не складываем 3 и 4, потому что варианты образуют пары.

Проверка через маленький список: если взять первый вариант первого шага, он даёт 4 пар; таких первых вариантов 3, значит всего 12.

Типичная ошибка — всегда перемножать или всегда делить на 2. Деление появляется только тогда, когда один и тот же набор был посчитан в разных порядках.

Повторите для 4 первых вариантов и 6 вторых. Коротко объясните, важен ли порядок выбора.

Определите, поменяется ли вариант, если поменять элементы местами. Это главный тест на порядок.

После этого примените такое же правило и проверьте результат на маленьком списке из двух-трёх вариантов.

24 вариантов.

Комбинаторика становится проще, когда перед формулой задан вопрос: что считается одним вариантом и когда два варианта считаются одинаковыми.

Задача 2. Пароль из цифры и буквы: посчитать варианты

Учебная ситуация: пароль из цифры и буквы. Нужно понять, считаем ли мы пары, роли, порядок или независимые шаги.

Сколько вариантов возможно и почему здесь используется именно это правило счёта?

Сначала решите, важен ли порядок. Если роли или позиции различаются, порядок важен; если выбирается просто набор, порядок не важен.

Затем решите, являются ли выборы независимыми шагами. Для независимых шагов работает произведение, для пары без порядка нужно убрать двойной счёт.

Всего вариантов 50: для каждого из 10 первых выборов есть 5 вторых.

Здесь выполняются два независимых шага. Сначала выбираем один вариант из 10, затем к нему можно присоединить один вариант из 5.

Правило произведения даёт 10 × 5 = 50. Мы не складываем 10 и 5, потому что варианты образуют пары.

Проверка через маленький список: если взять первый вариант первого шага, он даёт 5 пар; таких первых вариантов 10, значит всего 50.

Типичная ошибка — всегда перемножать или всегда делить на 2. Деление появляется только тогда, когда один и тот же набор был посчитан в разных порядках.

Повторите для 11 первых вариантов и 7 вторых.

Определите, поменяется ли вариант, если поменять элементы местами. Это главный тест на порядок.

После этого примените такое же правило и проверьте результат на маленьком списке из двух-трёх вариантов.

77 вариантов.

Комбинаторика становится проще, когда перед формулой задан вопрос: что считается одним вариантом и когда два варианта считаются одинаковыми.

Задача 3. Рассадка двух ролей: посчитать варианты

Учебная ситуация: рассадка двух ролей. Нужно понять, считаем ли мы пары, роли, порядок или независимые шаги.

Сколько вариантов возможно и почему здесь используется именно это правило счёта?

Сначала решите, важен ли порядок. Если роли или позиции различаются, порядок важен; если выбирается просто набор, порядок не важен.

Затем решите, являются ли выборы независимыми шагами. Для независимых шагов работает произведение, для пары без порядка нужно убрать двойной счёт.

Всего упорядоченных вариантов 30: первый выбор 6, второй 5.

Роли различаются, поэтому порядок важен: выбрать Анну капитаном и Бориса заместителем не то же самое, что наоборот.

На первую роль есть 6 кандидатов. После выбора одного человека на вторую роль остаётся 5. Получаем 6 × 5 = 30.

Проверка: если бы роли не различались, каждую пару посчитали бы дважды. Но здесь роли имеют разные названия, поэтому делить на 2 нельзя.

Типичная ошибка — всегда перемножать или всегда делить на 2. Деление появляется только тогда, когда один и тот же набор был посчитан в разных порядках.

Есть 8 кандидатов на две разные роли. Сколько назначений?

Определите, поменяется ли вариант, если поменять элементы местами. Это главный тест на порядок.

После этого примените такое же правило и проверьте результат на маленьком списке из двух-трёх вариантов.