Введение в комбинаторику

Эта тема является частью раздела о комбинаторике в Quant GMAT Focus.

Этот урок открывает модуль Counting. На первый взгляд он может показаться странным: ведь считать умеют все. Разумеется, в количественном разделе GMAT или GRE никто не попросит вас просто посчитать от 1 до 20.

Под «счётом» в экзаменационном контексте понимаются задачи другого типа. Например:
сколькими способами можно расставить на полке 4 романа и 3 справочника при заданных условиях — скажем, чтобы романы стояли по краям, а справочники в центре, или наоборот.

Речь идёт о порядке, наборах и комбинациях объектов. Именно это и изучается в данном модуле: сколькими способами можно выбрать или упорядочить большое количество элементов.

С точки зрения математики эта область называется комбинаторикой. Термин звучит сложно, поэтому в рамках подготовки к экзаменам мы будем использовать более простое слово — counting. Формально же речь идёт об элементарной комбинаторике.

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

Значение слов «и» и «или» в задачах на счёт

Хотя слова и и или привычны в повседневной речи, в задачах на счёт они имеют строгое математическое значение.

В комбинаторике (и позже — в теории вероятностей):

• «или» означает сложение

   

• «и» означает умножение

   

Это фундаментальная идея, которую нужно запомнить.

Пример 1. Слово «или» → сложение

Представим, что на торжественном ужине вы можете выбрать:

• один из 3 мясных вариантов, или

   

• один из 2 вегетарианских вариантов

   

Сколько всего вариантов основного блюда у вас есть?

Все возможные варианты — это любые из 3 мясных или любые из 2 вегетарианских.
Общее количество вариантов:

3 + 2 = 5

Здесь слово «или» означает, что мы складываем количества.

Пример 2. Слово «и» → умножение

Теперь рассмотрим другую ситуацию. Допустим:

• есть 3 варианта основного блюда, и

   

• к каждому из них можно выбрать 1 из 2 десертов

   

Сколько существует комбинаций «основное блюдо + десерт»?

К каждому из 3 основных блюд можно выбрать:

• либо десерт №1,

   

• либо десерт №2.

   

Таким образом, для каждого основного блюда есть 2 варианта, а всего:

3 × 2 = 6

Здесь слово «и» означает, что мы умножаем количества.

Перечисление вариантов как стартовая стратегия

Ещё одна важная идея — перечисление возможных вариантов.

Разумеется, на экзамене почти никогда нельзя решить задачу на счёт, просто выписав все возможные комбинации. Часто их бывает сотни или даже тысячи, и такой подход был бы слишком медленным.

Однако перечисление первых нескольких вариантов — это очень полезный начальный шаг. Он помогает:

• понять структуру задачи,

   

• увидеть закономерность,

   

• выбрать правильный метод решения.

   

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

Выводы

• Задачи на counting (комбинаторику) посвящены подсчёту большого числа комбинаций и перестановок.

   

• В таких задачах:

   

  • слово «или» означает сложение,

     

  • слово «и» означает умножение.

     

• Перечисление нескольких вариантов — полезная предварительная стратегия, которая часто помогает найти правильный подход к решению.

   

Этот фундамент понадобится нам во всех последующих уроках по комбинаторике в Quant-разделе GMAT и GRE.