"Алгебра (углублённый уровень)", Макарычев Ю.Н., Миндюк Н.Г., Нешков К.И. и др./Под ред.Теляковского С.А.
Комбинаторная задача — это задача, в которой нужно подсчитать, сколькими способами можно выбрать, расположить или составить объекты. Такие подсчёты помогают не перебирать все варианты наугад и нужны, например, при изучении вероятности. Главное — определить, выбираем ли мы один из разных случаев или выполняем несколько шагов подряд: в первом случае количества складывают, во втором — перемножают. Дерево вариантов и таблица помогают организовать перебор и проверить результат.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Комбинаторная задача — задача, в которой требуется подсчитать число возможных вариантов выбора, расположения или составления объектов. Например, можно выяснять, сколько пар получится из нескольких видов напитков и десертов. Понимание того, что именно считается одним вариантом, помогает не смешать разные результаты и правильно выбрать способ подсчёта.
Правило сложения говорит: если варианты разделены на взаимоисключающие случаи, общее число вариантов равно сумме их количеств. Взаимоисключающие случаи — такие, к которым один результат не может относиться одновременно. Правило удобно, когда нужно выбрать только один тип действия, например один вид транспорта из нескольких.
Правило умножения применяют, когда действие состоит из нескольких последовательных шагов. Если первый шаг можно выполнить m способами, а для каждого его результата второй шаг — n способами, то всего получается m · n вариантов. Это правило позволяет подсчитать все сочетания шагов, не выписывая каждое по отдельности.
Перебор вариантов — последовательное перечисление всех подходящих результатов. Его можно записать списком, представить в виде дерева, где ветви обозначают выборы, или оформить таблицей. Такая запись нужна, чтобы контролировать полноту подсчёта и замечать повторы, особенно когда условия ограничивают выбор.
Чтобы применить сложение, сначала разделяют задачу на случаи. Случаи должны охватывать все возможные варианты, иначе часть ответов потеряется, и не пересекаться, иначе одни и те же варианты попадут в сумму дважды. Например, если путь выбирают только на автобусе или только на поезде, эти группы не пересекаются. Поэтому достаточно подсчитать число маршрутов в каждой группе и сложить результаты.
При последовательном выборе каждый вариант первого шага можно продолжить допустимыми вариантами следующего. Если после каждого первого выбора доступно одинаковое число продолжений, получается произведение чисел возможностей. Причина в том, что для каждого выбора на первом шаге учитываются все его продолжения, а не только одно из них. Если условия меняют доступные возможности, их считают отдельно для соответствующих ветвей дерева или групп выбора.
Различить сложение и умножение помогает вопрос о том, что представляет собой один итоговый результат. Если результатом служит один из альтернативных вариантов, например поездка автобусом или поездом, считают отдельные случаи и складывают. Если результат включает сразу несколько решений — например, выбранные сок и булочку, — это последовательные шаги, и их количества перемножают. В сложной задаче могут встретиться оба правила: сначала разбивают задачу на случаи, а внутри каждого случая считают последовательные выборы.
Дерево вариантов начинают с первого шага: из начальной точки проводят ветви для всех его возможностей. От конца каждой ветви проводят продолжения для следующего шага, учитывая ограничения условия; каждую конечную ветвь читают как один полный исход. Если ветви ведут к 3 вариантам первого шага и из каждого есть по 2 продолжения, на концах будет 3 · 2 = 6 исходов. Когда число продолжений неодинаково, можно посчитать конечные ветви в каждой группе отдельно и сложить.
Систематический перебор начинают с выбора постоянного порядка: например, сначала фиксируют первую цифру, затем перебирают все допустимые вторые. Так проще заметить, какая часть вариантов уже рассмотрена и какая ещё нет. Для проверки сравните записи с условиями задачи: все ли они допустимы, встречается ли каждый вариант только один раз и есть ли продолжение для каждого выбора. Если список неудобно проверять, те же шаги можно перенести в дерево или таблицу.
| Ситуация | Что происходит | Способ подсчёта | Пример записи |
|---|---|---|---|
| Выбор одного из взаимоисключающих случаев | Выбирают только один случай; варианты случаев не пересекаются | Сложить количества вариантов по случаям | 2 + 3 = 5 |
| Последовательное выполнение нескольких шагов | Результат включает выбор на каждом шаге | Перемножить числа вариантов шагов | 3 · 2 = 6 |
| Небольшое число вариантов, которое удобно перечислить | Можно записать каждый допустимый результат по порядку | Систематический перебор | 12, 13, 14, … |
| Проверка полноты перечисления с помощью дерева или таблицы | Результаты группируют по первому выбору или по шагам | Просмотреть все ветви или ячейки | Число конечных ветвей |
Сначала определите, какой результат считается одним вариантом и какие ограничения заданы. Затем выберите соответствующую строку таблицы: случаи складывают, а последовательные шаги перемножают. Перебор, дерево и таблица помогают проверить вычисления и особенно полезны при небольшом количестве вариантов.
В меню есть 3 вида сока и 2 вида булочки. Нужно составить пару, в которую входят и сок, и булочка. Это не выбор между соком и булочкой: для каждой пары нужно выполнить оба шага выбора.
Сначала выбираем сок: у нас есть 3 возможности. Фиксируем любой один вид сока и выясняем, сколько пар он образует.
К каждому из трёх видов сока можно добавить любой из 2 видов булочки. Значит, у каждого выбора сока есть 2 продолжения, и применяем правило умножения: 3 · 2 = 6.
Ответ: можно составить 6 разных пар. Например, в дереве у каждого из трёх соков будут две ветви — по одной для каждого вида булочки.
До соседнего города можно добраться автобусом по 2 маршрутам или поездом по 3 маршрутам. По условию выбирают один вид транспорта, значит, один способ относится либо к автобусным маршрутам, либо к железнодорожным. Эти случаи взаимоисключающие.
Считаем варианты поездки на автобусе: их 2. Отдельно считаем поездные маршруты: их 3.
Маршрут выбирают только в одном из двух случаев, поэтому сочетать автобусный маршрут с поездным не нужно. Складываем числа вариантов: 2 + 3 = 5.
Ответ: добраться можно 5 способами. Проверка проста: каждый способ — это один конкретный маршрут, и он не может быть одновременно автобусным и железнодорожным.
Из цифр 1, 2, 3, 4 составляют двузначные числа, причём повторять цифру нельзя. Один вариант — это конкретное число с выбранной цифрой десятков и цифрой единиц. Так как цифра, поставленная в десятки, уже использована, число возможностей для единиц уменьшится.
Для разряда десятков доступны все 4 цифры: 1, 2, 3 или 4. Выбираем одну из них первой.
Для разряда единиц остаются 3 цифры, потому что выбранную для десятков повторять нельзя. Каждый из четырёх выборов десятков сочетается с тремя выборами единиц, поэтому 4 · 3 = 12.
Для проверки можно сгруппировать числа по цифре десятков: при 1 это 12, 13, 14; при 2 — 21, 23, 24; при 3 — 31, 32, 34; при 4 — 41, 42, 43. В каждой группе три числа, а групп четыре, пропусков и повторов нет.
Ответ: можно составить 12 чисел. Если бы повторение цифр разрешалось, на втором шаге оставались бы все 4 цифры, но здесь ограничение меняет число вариантов.
Перемножать количества для взаимоисключающих случаев. Так ошибаются, когда видят несколько чисел, но не замечают, что нужно выбрать только один случай. Например, автобусный маршрут или поездной не образуют совместную пару, поэтому числа вариантов складывают. Проверьте, включает ли один результат несколько выборов одновременно: если нет, умножение не подходит.
Складывать количества последовательных шагов. Ошибка возникает, если считать выбор сока и выбор булочки отдельными альтернативами, хотя итоговая пара содержит и то и другое. Каждый сок сочетается с каждым видом булочки, поэтому нужно учитывать все продолжения и перемножать. Проверьте себя, спросив, можно ли составить итоговый вариант без одного из шагов.
Не учитывать запрет на повторение объектов. Если в задаче нельзя использовать объект дважды, подсчёт одинакового числа вариантов на каждом шаге включает недопустимые результаты. Это часто происходит, когда условие о повторении читают невнимательно или забывают после первого выбора. Проследите по шагам, остаётся ли уже выбранный объект доступным; например, для второй цифры без повторения вариантов на один меньше.
Перебирать без порядка. При случайном перечислении легко пропустить вариант или записать его дважды, потому что непонятно, какие группы уже проверены. Задайте порядок, например фиксируйте первую цифру и перебирайте для неё все продолжения, а затем переходите к следующей. После этого сравните список с деревом или таблицей и убедитесь, что каждый допустимый результат встретился ровно один раз.
Для подсчёта вариантов нужны обычные арифметические действия и внимательное чтение условия. Особенно важно замечать, можно ли повторять выбранные объекты, сколько шагов включает выбор и что считается отдельным результатом. Эти ограничения определяют, сколько возможностей остаётся на каждом этапе.
Комбинаторный подсчёт используют при вычислении вероятности: нужно знать число подходящих, то есть благоприятных, исходов и число всех возможных исходов. Поэтому аккуратный подсчёт вариантов помогает правильно составить отношение этих чисел. Если исходы подсчитаны с пропусками или повторами, вероятность тоже получится неверной.
Правила сложения и умножения служат основой для более специальных способов подсчёта. Перестановки описывают упорядочивание объектов, размещения — выбор объектов с учётом порядка, а сочетания — выбор без учёта порядка. Понимание базовых правил помогает разобраться, какие варианты считать разными в каждом таком случае.
Как понять, нужно складывать или умножать число вариантов?
Если выбирают один из взаимоисключающих случаев, количества вариантов складывают. Если действие состоит из нескольких шагов и варианты каждого шага соединяются между собой, количества перемножают. Полезно спросить себя: «Выбираю один случай или выполняю все шаги?»
Когда случаи считаются взаимоисключающими?
Случаи взаимоисключающие, если один и тот же результат не может относиться сразу к двум из них. Например, путь выбирают либо на автобусе, либо на поезде. Тогда каждый подходящий вариант учитывают ровно один раз и складывают количества вариантов в случаях.
Как учесть, что один и тот же объект нельзя выбрать повторно?
После выбора объекта исключите его из вариантов, доступных на следующих шагах. Поэтому число возможностей может уменьшиться: например, для первой цифры доступны четыре цифры, а для второй — только три. Это ограничение нужно учитывать в каждом продолжении выбора.
Зачем строить дерево вариантов, если можно посчитать устно?
Дерево показывает, какие продолжения возможны после каждого шага выбора. Оно особенно полезно, если вариантов несколько или действуют ограничения: так проще заметить пропуск или повтор. Для маленькой задачи дерево также служит наглядной проверкой устного подсчёта.
Как проверить, что при переборе учтены все варианты?
Задайте постоянный порядок выбора и перечисляйте варианты по нему, например сначала по первой цифре, затем по второй. Проверьте, что каждый допустимый вариант встретился ровно один раз. Дерево или таблица помогают увидеть пустые места и повторяющиеся записи.
Примеры комбинаторных задач.
