"Математика", Бунимович Е.А., Дорофеев Г.В., Суворова С.Б. и др.
Комбинаторная задача помогает найти или подсчитать все способы выбора и составления объектов. Такие задачи встречаются, когда нужно выбрать одежду, составить число или придумать расписание. Главное — сначала понять, что считается отдельным вариантом и какие условия ограничивают выбор. Затем варианты перечисляют по плану: используют последовательный перебор, дерево или таблицу. Систематическая запись помогает не пропустить случаи и не посчитать один и тот же вариант дважды.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Комбинаторная задача — задача, в которой требуется найти или подсчитать все возможные варианты выбора, составления или расположения объектов. Например, можно выяснять, сколько разных наборов получится из нескольких предметов. Это определение помогает сразу увидеть цель задачи: не просто назвать один подходящий случай, а разобраться со всем набором возможностей.
Перебор вариантов — способ решения, при котором возможные случаи рассматривают по очереди и следят, чтобы не пропустить и не повторить ни одного. Можно, например, сначала записать все случаи с одним предметом, а затем перейти к следующему. Такой способ нужен, когда вариантов немного и их можно аккуратно перечислить.
Дерево вариантов — схема, в которой каждый следующий выбор изображают ветвями, показывая все возможные последовательности решений. От начальной точки идут ветви первого выбора, а от каждой из них — ветви следующего. Схема нужна, чтобы видеть, как один выбор продолжается другими, и не забывать возможные продолжения.
Таблица вариантов — способ записать сочетания двух выборов в строках и столбцах, чтобы проверить полноту перебора. Один выбор обозначают строками, второй — столбцами, а в клетках записывают получившиеся пары. Таблица помогает быстро заметить пустую клетку или случайно пропущенное сочетание.
Сначала нужно определить, что именно считается отдельным вариантом и какие условия ограничивают выбор. Если не договориться об этом заранее, можно случайно считать разные записи одним случаем или, наоборот, принять их за разные. Например, в задаче о двузначных числах порядок цифр важен, а в наборе из двух игрушек перестановка игрушек обычно ничего не меняет. Условие о запрете повторений тоже меняет список допустимых вариантов, поэтому его нужно учитывать с самого начала.
Чтобы перебор был полным, составь план и разбей варианты на группы. Например, в каждой группе можно зафиксировать первый выбранный предмет, а потом рассмотреть все допустимые продолжения. Группы должны покрывать все случаи, иначе часть вариантов потеряется; при этом они не должны пересекаться, иначе один случай будет записан дважды. После перебора проверь каждую группу отдельно: все ли продолжения в ней перечислены и не попало ли туда то, что запрещено условием.
Дерево вариантов особенно полезно, когда решение состоит из нескольких шагов. На первом шаге выбирают один объект, а затем от каждой ветви проводят новые ветви для следующего выбора. Так видно, какие действия образуют одну последовательность, и легко пройти по всем путям от начала до конца. Если на ветке записан запрещённый выбор, её не продолжают, а каждый оставшийся путь считают отдельным вариантом.
Таблица упорядочивает варианты, если каждый из них состоит из двух выборов. Для этого объекты первого вида записывают в строках, второго — в столбцах, а на пересечении отмечают их сочетание. Такая запись удобна потому, что каждой паре соответствует своя клетка: можно последовательно проверить все строки и столбцы. Если некоторые сочетания запрещены, их отмечают отдельно и не включают в ответ.
В конце пересчитай результат другим способом или проверь, что список устроен без пробелов и повторов. Например, варианты из списка можно разложить по строкам и столбцам таблицы либо сравнить с ветвями дерева. Другая запись полезна не только для подтверждения числа: она помогает заметить, что один случай пропущен или записан дважды. Если способы проверки дают разные результаты, вернись к группам и найди, где именно разошёлся перебор.
| Способ | Как записывают варианты | Когда удобно применять | Что помогает проверить |
|---|---|---|---|
| Последовательный перебор | Записывают случаи один за другим, следуя заранее выбранному порядку. | Когда вариантов немного и их можно разбить на понятные группы. | Полноту списка и отсутствие повторов в каждой группе. |
| Дерево вариантов | Выборы изображают ветвями, а последовательности — путями от начала до конца. | Когда вариант получается в результате нескольких выборов по шагам. | Все возможные продолжения каждого выбора. |
| Таблица вариантов | Сочетания двух выборов записывают в клетках на пересечении строк и столбцов. | Когда каждый вариант состоит из пары объектов из двух групп. | Все ли пары учтены и какие сочетания запрещены. |
Выбирай запись по устройству задачи: для цепочки выборов подходит дерево, для двух групп — таблица, а небольшой список можно перебрать по порядку. В любой записи сначала задай порядок, по которому будешь проверять варианты. Затем отметь запрещённые случаи и пересчитай оставшиеся.
Условие: у Маши есть красная, синяя и зелёная ленты. Сколькими способами она может выбрать одну ленту? Здесь один вариант — выбранный цвет, а выбрать нужно ровно одну ленту. Повторять выбор нельзя, но это и не требуется, потому что рассматривается только один предмет.
Ответ: 3 способа. Такой простой перебор удобен, когда предметов мало, а каждый из них можно записать отдельно. Проверка по условию показывает, что других лент у Маши нет.
Условие: для завтрака можно выбрать один из двух напитков и одну из трёх булочек. Сколько разных завтраков можно составить? Один завтрак — это пара из напитка и булочки, поэтому нужно учесть каждую допустимую пару. Обозначим напитки А и Б, а булочки — 1, 2 и 3.
Ответ: 6 разных завтраков. Ту же работу можно выполнить таблицей: строки задают напитки, столбцы — булочки, а каждая клетка соответствует одному завтраку. Дерево тоже подойдёт: от каждого напитка проведём по три ветви к булочкам.
Условие: из цифр 1, 2 и 3 составляют двузначные числа без повторения цифр. Сколько чисел получится? Здесь первая и вторая цифры занимают разные места, поэтому числа 12 и 21 — не один и тот же вариант. Запрет повтора означает, что цифра, уже поставленная на первое место, не может появиться на втором.
Ответ: 6 чисел. Разбиение по первой цифре помогает не смешивать случаи и не пропустить число. Повторяющихся цифр в записях нет, а каждое число встречается только в своей группе.
При неупорядоченном переборе легко пропустить вариант: список кажется полным, хотя один случай не попал ни в одну группу. Это происходит, когда переходят от одного предмета к другому без заранее выбранного порядка. Проверь себя, разбив список, например, по первому выбору и перечислив продолжения для каждой группы. Если получается заполнить дерево или таблицу без пустых допустимых мест, вероятность пропуска меньше.
Иногда один вариант считают несколько раз, записывая то же сочетание в разном порядке. Так бывает, если в задаче важен состав набора, а порядок предметов не имеет значения. Перед подсчётом спроси себя, изменился ли сам вариант или только порядок записи. Затем сравни пары и убери повторные записи, если условие не различает их перестановку.
Ещё одна ошибка — не учитывать ограничение, например использовать одну и ту же цифру дважды, хотя повторение запрещено. Обычно так случается, если перебор ведут по привычке и не возвращаются к условию при каждом шаге. После составления списка проверь каждый вариант по всем ограничениям задачи. Если хотя бы один нарушает условие, удали его и пересчитай оставшиеся случаи.
Можно перепутать задачи, где порядок важен, с задачами, где важен только состав набора. Причина в том, что внешне записи похожи: например, цифры 1 и 2 можно поставить в двух местах или выбрать две карточки. Решает не вид записи, а вопрос задачи: получаются ли разные результаты после перестановки? Для чисел 12 и 21 результаты разные, а пара тех же карточек обычно остаётся той же парой.
Для комбинаторных задач нужно внимательно читать условие, уметь перечислять предметы и вести записи в выбранном порядке. Эти навыки помогают отделять разрешённые варианты от запрещённых и не терять случаи при подсчёте. Перебор пригодится в задачах на выбор предметов, составление чисел и расписаний, где нужно рассмотреть возможные сочетания или последовательности. Позже такие способы помогут изучать вероятность: чтобы оценить шанс события, сначала часто перечисляют все возможные исходы.
Как понять, что задача является комбинаторной?
В такой задаче нужно найти или подсчитать возможные варианты выбора, составления или расположения предметов. Например, можно считать все способы выбрать напиток и булочку.
Как проверить, что я перечислил все варианты?
Разбей варианты на группы и проверь, что каждая рассмотрена полностью, а группы не пересекаются. Затем пересчитай результат другим способом или проверь его по таблице или дереву.
Когда удобнее использовать дерево вариантов?
Дерево удобно, если выбор делают по шагам: сначала один предмет, затем другой. Ветви показывают, какие продолжения возможны после каждого выбора.
Как составить таблицу вариантов?
Запиши объекты первого выбора в строках, а второго — в столбцах. В каждой клетке укажи сочетание соответствующих объектов и проверь, что все клетки с допустимыми сочетаниями учтены.
Нужно ли считать варианты в разном порядке разными?
Это зависит от условия задачи. Если важен порядок, например в двузначном числе, 12 и 21 — разные варианты; если важен только состав набора, перестановка тех же предметов не создаёт новый вариант.
8. Комбинаторные задачи
