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

Глеб Зайцев

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

Перед началом

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

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

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

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

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

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

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

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

Маршрут по задачам

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

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

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

4. Выбор пары дежурных: посчитать варианты

5. Три книги на полке: посчитать варианты

6. Маршрут через два выбора: посчитать варианты

7. Капитан и заместитель: посчитать варианты

8. Две открытки из набора: посчитать варианты

9. Три цвета в порядке: посчитать варианты

10. Пицца и напиток: посчитать варианты

11. Логин из символов: посчитать варианты

12. Первое и второе место: посчитать варианты

13. Две задачи на выбор: посчитать варианты

14. Три участника в очереди: посчитать варианты

15. Обложка и шрифт: посчитать варианты

16. Ведущий и секретарь: посчитать варианты

17. Две карточки без порядка: посчитать варианты

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 кандидатов на две разные роли. Сколько назначений?

Решение самостоятельной задачи

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

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