"Алгебра", Дорофеев Г.В., Суворова С.Б., Бунимович Е.А. и др.
Комбинаторные задачи помогают подсчитать, сколько существует способов сделать выбор или составить набор. Если действие состоит из нескольких последовательных выборов, число возможных результатов находят правилом умножения: перемножают количество вариантов на каждом этапе. Сначала нужно правильно выделить этапы и выяснить, сколько способов доступно на каждом из них. Если выборы идут без повторения, число вариантов может меняться.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Комбинаторная задача — задача, в которой нужно подсчитать число возможных вариантов или способов. Например, можно считать, сколькими способами составить обед из нескольких блюд или выбрать цифры для числа. Это определение помогает отличить задачи на перебор вариантов от тех, где требуется найти одно конкретное значение.
Правило умножения — способ подсчёта, по которому число вариантов последовательного выполнения нескольких выборов равно произведению числа вариантов на каждом шаге. Если первый выбор можно сделать m способами, а второй — n способами, то всего получится m · n сочетаний. Правило позволяет считать варианты, не выписывая их по одному.
Этап выбора — один из последовательных шагов, на каждом из которых выбирают один вариант из доступных. Например, при составлении комплекта одежды отдельными этапами могут быть выбор футболки и выбор брюк. Если точно определить этапы, проще понять, какие числа нужно перемножить и не пропустить часть условия.
Представим два последовательных выбора: сначала выбирают одну из m вещей, затем одну из n других. С каждым вариантом первого выбора можно соединить все n вариантов второго, поэтому для каждого из m вариантов получается по n пар. Если собрать такие группы вместе, всего выйдет m · n пар, а не m + n: в каждом результате присутствуют оба выбора.
Рассуждение продолжается и для большего числа этапов. После выбора на первом этапе к нему присоединяют каждый вариант второго, затем к каждой полученной паре — каждый вариант третьего. Поэтому при трёх этапах с m, n и k возможностями получается m · n · k результатов, а при нескольких этапах перемножаются все числа вариантов.
Чтобы применить правило, прочитай условие и представь один готовый результат задачи. Затем спроси себя, какие решения нужно принять, чтобы его получить: это и будут этапы выбора. Для каждого этапа запиши число доступных вариантов, например: выбрать напиток — 3 способа, булочку — 4 способа. После этого можно перемножить числа.
Число вариантов на следующем этапе не всегда одинаково после каждого предыдущего выбора. Правило работает и в этом случае, если для каждого предыдущего результата известно, сколько продолжений ему соответствует; одинаковое число продолжений можно умножить на число предыдущих вариантов. Если же количество продолжений различается, нужно считать их для каждого случая отдельно и складывать результаты. Поэтому прежде чем перемножать числа, проверь условие задачи.
Варианты можно изобразить деревом: от начальной точки проводят ветви для первого выбора, а от каждой ветви — ветви для следующих. Каждая ветка на очередном уровне показывает один доступный вариант, а полный путь от начала до конца соответствует одному итоговому результату. Число конечных путей совпадает с подсчётом по правилу умножения, если число продолжений на каждом уровне одинаково. Дерево особенно удобно для проверки небольших задач.
| Число этапов | Число вариантов на этапах | Общее число вариантов |
|---|---|---|
| Два этапа | m вариантов и n вариантов | m · n |
| Три этапа | m вариантов, n вариантов и k вариантов | m · n · k |
| Несколько этапов | a₁, a₂, …, aₙ вариантов | a₁ · a₂ · … · aₙ |
В таблице буквы обозначают количества доступных вариантов на соответствующих этапах. Найди в условии задачи число этапов и подставь их количества в подходящую строку. Если варианты меняются из-за предыдущего выбора, учитывай это отдельно, а не подставляй одно и то же число автоматически.
Задача 1. В кафе предлагают 3 вида напитка и 4 вида булочек. Сколько разных наборов из одного напитка и одной булочки можно составить? Нужно получить набор, в котором обязательно есть оба продукта, поэтому выбор состоит из двух этапов.
Ответ: можно составить 12 разных наборов. Например, каждому из трёх напитков соответствуют четыре набора с разными булочками. Такой подсчёт учитывает каждый возможный набор один раз.
Задача 2. Для школьного спектакля выбирают одну из 3 ролей, один из 2 костюмов и один из 4 вариантов оформления сцены. Сколько возможных комплектов получится? Комплект считается готовым, когда сделаны все три выбора, поэтому выделяем три этапа.
Ответ: получится 24 комплекта. Каждый комплект содержит выбранные роль, костюм и оформление сцены. Здесь нет запрета на сочетание какого-либо костюма с какой-либо ролью, поэтому все варианты можно соединять.
Задача 3. Сколько двузначных чисел можно составить из цифр 1, 2, 3, 4, если цифры не повторяются? Число состоит из цифры десятков и цифры единиц. Запрет на повторение означает, что после первого выбора использованную цифру нельзя взять снова.
Ответ: можно составить 12 двузначных чисел. Например, если для десятков выбрана цифра 1, единицами могут быть 2, 3 или 4. Для каждого другого выбора десятков остаются также три цифры.
Ошибка — складывать числа вариантов вместо умножения. Её допускают, когда видят несколько чисел в условии, но не различают последовательные и альтернативные действия. Проверь себя: если итоговый результат должен включать выбор на каждом этапе, варианты каждого этапа сочетаются, значит, нужно умножать.
Ошибка — посчитать этапы, но не проверить, меняется ли число вариантов на следующем. Так бывает, если предполагают, что после любого выбора доступен прежний набор возможностей. Проверь условие на ограничения: например, нельзя ли использовать уже выбранный предмет или цифру повторно.
Ошибка — снова учитывать предмет или цифру, хотя повторение запрещено. Это завышает число вариантов, потому что в подсчёт попадают недопустимые результаты. Проверь себя на конкретном случае: после первого выбора вычеркни использованный вариант и пересчитай, сколько осталось.
Ошибка — пропустить этап или учесть один выбор дважды. В первом случае часть результатов потеряется, а во втором некоторые будут посчитаны повторно. Составь описание одного полного результата и сверяй с ним этапы; дерево вариантов поможет увидеть пропуски и повторы.
Для решения задач по правилу умножения нужны навыки умножения натуральных чисел. Ещё важно внимательно читать условие, чтобы не пропустить число вариантов, запрет на повторение или обязательный этап. Эти умения помогают превратить словесную задачу в понятный план подсчёта.
Правило умножения пригодится при изучении вероятности и при подсчёте способов составления кодов. Оно также служит основой для более сложных комбинаторных задач, где нужно учитывать дополнительные ограничения. В таких случаях сначала разбирают отдельные этапы и условия, а затем выбирают подходящий способ подсчёта.
Когда в задаче нужно умножать, а когда складывать?
Умножают, когда результат получается последовательным выполнением нескольких выборов: например, выбирают и напиток, и булочку. Складывают, когда нужно выбрать один из разных альтернативных способов.
Как понять, сколько этапов выбора в задаче?
Найдите, какие решения нужно принять, чтобы получить один полный результат. Каждый отдельный выбор — этап: например, выбор цифры десятков и затем цифры единиц.
Можно ли применять правило умножения, если число вариантов меняется?
Можно, если известно число вариантов на каждом этапе после сделанных ранее выборов. Например, при выборе двух разных цифр из четырёх сначала есть 4 варианта, а затем — 3.
Как учитывать запрет на повторение предметов или цифр?
После каждого выбора исключите уже использованный предмет или цифру из доступных вариантов. Поэтому число вариантов на следующих этапах обычно уменьшается.
Зачем изображать дерево вариантов, если можно сразу перемножить числа?
Дерево наглядно показывает, какие выборы можно сочетать и какие результаты получаются. Оно помогает проверить, что ни один вариант не пропущен и не посчитан дважды.
Решение комбинаторных задач. Правило умножения
