Устранение повторного подсчёта

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

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

Именно это мы делали в теме про одинаковые объекты.

Откуда берётся повторный подсчёт

Повторы возникают по двум основным причинам:

1. Одинаковые объекты

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

2. Порядок не имеет значения

Наш основной инструмент до сих пор — основной принцип подсчёта (FCP) — по своей природе учитывает порядок.
Когда мы считаем варианты «шаг за шагом», порядок автоматически становится важным.

Но если задача спрашивает только о наборе объектов, а порядок не важен, то разные порядки одного и того же набора — это повторения.

Поэтому в любой задаче на счёт необходимо всегда задавать себе вопрос:

Имеет ли значение порядок или нет?

Связь с комбинациями

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

Все формулы для перестановок и комбинаций в конечном счёте выводятся из основного принципа подсчёта.

FCP — это фундаментальная идея, а все остальные методы являются её следствиями.

Пример 1. Рукопожатия

В комнате находится 20 человек. Каждый пожимает руку каждому другому.
Сколько всего рукопожатий происходит?

Наивный подсчёт

Каждый человек пожимает руки 19 другим, поэтому может показаться, что ответ:

20 × 19

Но это число слишком большое.

Почему возникает переучёт

Рукопожатие между двумя людьми:

• считается один раз как «я пожал руку Эллиоту»,

   

• и второй раз как «Эллиот пожал руку мне».

   

Но на самом деле это одно рукопожатие, а не два.

То есть каждое рукопожатие было посчитано дважды.

Исправление

Чтобы устранить повторный подсчёт, нужно разделить на 2:

(20 × 19) / 2

Упрощаем:

• 20 / 2 = 10

   

• 10 × 19 = 190

   

Ответ: 190 рукопожатий.

Связь с предыдущими темами

Это точно тот же принцип, который мы использовали ранее:

• если 3 элемента одинаковы, мы делим на 3! = 6,

   

• потому что каждая реальная конфигурация была посчитана 6 раз.

   

Пример 2. Выбор подарков (порядок не важен)

Из 10 различных предметов Лиза выбирает 3 в подарок.
Сколькими различными способами она может выбрать набор из 3 предметов?

Важно:
порядок выбора не имеет значения, важен только состав набора.

Шаг 1. Подсчёт с учётом порядка (FCP)

Используем основной принцип подсчёта:

• первый предмет — 10 вариантов,

   

• второй — 9 вариантов,

   

• третий — 8 вариантов.

   

Итого:

10 × 9 × 8

Шаг 2. Устранение повторов

Каждый набор из 3 предметов может быть выбран:

3! = 6 разными порядками.

Но все эти порядки соответствуют одному и тому же набору, поэтому подсчёт завышен в 6 раз.

Шаг 3. Деление на число повторов

(10 × 9 × 8) / 3!

Сокращаем:

• 3! = 3 × 2 = 6

   

• сокращаем 3 с 9 → 3

   

• сокращаем 2 с 8 → 4

   

Получаем:

10 × 3 × 4 = 120

Ответ: 120 различных наборов.

Ключевая идея

В этой задаче нас интересовал набор из 3 предметов, а не порядок их выбора.
Мы:

1. посчитали все варианты с учётом порядка (FCP),

    

2. затем устранили повторения, разделив на количество эквивалентных порядков.

    

Выводы

• При подсчёте всегда проверяйте, возникает ли повторный учёт.

   

• Повторы появляются, когда:

   

  • есть одинаковые элементы,

     

  • или порядок не имеет значения.

     

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

   

• Такой подход лежит в основе:

   

  • перестановок,

     

  • комбинаций,

     

  • и всех формул комбинаторики.

     

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

Следующий урок будет посвящен сочетаниям.