2.5. Решение комбинаторных задач

Определения и обозначения

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

Вариант — один конкретный способ составить или выбрать объект. Например, комплект из красной футболки и чёрной юбки — один вариант, а комплект из синей футболки и чёрной юбки — другой. Это понятие нужно, чтобы точно решить, какие случаи считать разными.

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

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

Как это устроено

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

До перебора выясни, чем один вариант отличается от другого и какие ограничения заданы. В задаче о числах могут различаться порядок цифр и запрет на повторение, а при выборе вещей важны сами вещи, но не последовательность, в которой их выбрали. Если не решить это заранее, можно ошибочно считать один случай дважды или включить неподходящий вариант.

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

Таблица или дерево делают перебор наглядным, потому что каждому сочетанию или пути отводится своё место. В таблице можно увидеть, какие элементы соединены, а в дереве — какие решения следуют одно за другим. Если записывать результаты в выбранные ячейки или у конечных ветвей, становится проще заметить одинаковые записи и проверить, все ли случаи рассмотрены.

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

Способы систематического поиска вариантов

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

Разбор задач

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

1. Закрепим красную футболку. С ней можно выбрать чёрную юбку или белую, поэтому получаем два комплекта: красная с чёрной и красная с белой.
2. Теперь возьмём синюю футболку и снова переберём все юбки. Получим синюю с чёрной и синюю с белой.
3. Сосчитаем записи и проверим, что для каждой футболки использованы обе юбки. Всего получилось четыре разных сочетания.

Ответ: 4 комплекта.

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

1. Если первая цифра 1, на втором месте могут быть 2 или 3. Получаются числа 12 и 13.
2. Если первая цифра 2, на втором месте могут быть 1 или 3. Получаются числа 21 и 23.
3. Если первая цифра 3, на втором месте могут быть 1 или 2. Получаются числа 31 и 32.
4. Проверим группы: учтены все три возможные первые цифры, а в каждом числе цифры различны. Всего записано шесть чисел.

Ответ: 6 чисел.

Для поездки нужно выбрать маршрут из пункта А в пункт В через пункт Б. От А до Б ведут три дороги, а от Б до В — две. Нужно учитывать, что маршрут задаётся обеими частями пути, а не только дорогой до Б. Для каждого выбора первой дороги переберём все варианты продолжения.

1. Выберем первую дорогу от А до Б. С неё можно продолжить путь по любой из двух дорог от Б до В, значит, получаются два маршрута.
2. Повторим то же для второй дороги от А до Б: снова есть два продолжения.
3. Для третьей дороги от А до Б тоже рассмотрим обе дороги от Б до В. Получаются ещё два маршрута.
4. Соберём случаи по трём первым дорогам и проверим, что каждая соединена с обоими продолжениями. Всего получилось шесть разных пар дорог.

Ответ: 6 маршрутов.

Типичные ошибки

Можно перечислить только самые очевидные варианты и остановиться, хотя остаются другие. Так происходит, если перебирать случаи без порядка и полагаться на память. Чтобы проверить себя, заранее выбери, например, первую вещь или цифру и по очереди рассмотри все её возможности.

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

В ответ может попасть случай, который нарушает условие: например, двузначное число с повторённой цифрой, если повторять её запрещено. Такой вариант легко включить, если проверять только количество записей. Сверяй каждую запись с ограничениями задачи, а неподходящие случаи сразу исключай.

Порядок выбора и порядок записи иногда смешивают. Если порядок важен, числа 12 и 21 различаются; если выбирают две вещи без учёта порядка, их перестановка не создаёт новый комплект. Перед подсчётом реши, что считается объектом, и проверь, не посчитана ли одна и та же пара как два разных случая.

Связь с другими темами

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

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

Что запомнить

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