Правила комбинаторики в задаче B10
Решая задачи по теории вероятностей, мы постоянно используем одну и ту же формулу, которая одновременно является классическим определением вероятности:
где k — число благоприятных исходов, n — общее число исходов (см. «Тест по теории вероятностей»).
И эта формула прекрасно работает до тех пор, пока задачи были легкими, а числа, стоящие в числителе и знаменателе — очевидными.
Однако последние пробные экзамены показали, что в настоящем ЕГЭ по математике могут встречаться значительно более сложные конструкции. Отыскание значений n и k становится проблематичным. В таком случае на помощь приходит комбинаторика. Ее законы работают там, где искомые значения не выводятся непосредственно из текста задачи.
В сегодняшнем уроке не будет строгих формулировок и длинных теорем — они слишком сложны и, к тому же, совершенно бесполезны для решения настоящих задач B10. Вместо этого мы рассмотрим простые правила и разберем конкретные задачи, которые действительно встречаются на ЕГЭ. Итак, поехали!
Число сочетаний и факториалы
Определение
Пусть имеется n объектов (карандашей, конфет, бутылок водки — чего угодно), из которых требуется выбрать ровно k различных объектов. Тогда количество вариантов такого выбора называется числом сочетаний из n элементов по k. Это число обозначается Cnk и считается по специальной формуле.
Обозначение
Замечание
Выражение n! читается как «эн-факториал» и обозначает произведение всех натуральных чисел от 1 до n включительно: n! = 1 · 2 · 3 ·... · n.
Кроме того, в математике по определению считают, что 0! = 1 — подобный бред редко, но все же встречается в задачах по теории вероятностей.
Что дает нам эта формула? На самом деле, без нее не решается практически ни одна серьезная задача.
К сожалению, в школе совершенно не умеют работать с факториалами. Кроме того, в формуле числа сочетаний очень легко запутаться: где стоит и что обозначает число n, а где — k. Поэтому для начала просто запомните: меньшее число всегда стоит сверху — точно так же, как и в формуле определения вероятности (вероятность никогда не бывает больше единицы).
Для лучшего понимания разберем несколько простейших комбинаторных задач:
Задача
У бармена есть 6 сортов зеленого чая. Для проведения чайной церемонии требуется подать зеленый чай ровно 3 различных сортов. Сколькими способами бармен может выполнить заказ?
Решение
Тут все просто: есть n = 6 сортов, из которых надо выбрать k = 3 сорта. Число сочетаний можно найти по формуле:
Ответ
Задача
В группе из 20 студентов надо выбрать 2 представителей для выступления на конференции. Сколькими способами можно это сделать?
Решение
Опять же, всего у нас есть n = 20 студентов, а выбрать надо k = 2 студента. Находим число сочетаний:
Обратите внимание: красным цветом отмечены множители, входящие в разные факториалы. Эти множители можно безболезненно сократить и тем самым значительно уменьшить общий объем вычислений.
Ответ
Задача
На склад завезли 17 серверов с различными дефектами, которые стоят в 2 раза дешевле нормальных серверов. Директор купил в школу 14 таких серверов, а сэкономленные деньги своровал и купил дочке шубу из меха соболя за 200 000 рублей. Сколькими способами директор может выбрать бракованные серверы?
Решение
В задаче довольно много лишних данных, которые могут сбить с толку. Наиболее важные факты: всего есть n = 17 серверов, а директору надо k = 14 серверов. Считаем число сочетаний:
Красным цветом снова обозначены множители, которые сокращаются. Итого, получилось 680 комбинаций. В общем, директору есть из чего выбрать.
Ответ
Как видите, число сочетаний из n по k считается достаточно просто. Проблема в том, что многие школьники никогда не работали с факториалами. Для них это новый и незнакомый математический объект, и для его освоения требуется некоторая тренировка.
Хорошая новость состоит в том, что во многих задачах формулы Cnk оказывается вполне достаточно для нахождения ответа. Но есть и плохая новость: в тех редких случаях, когда нужны дополнительные правила, решение задачи резко усложняется. Эти правила мы сейчас и рассмотрим.
Закон умножения
Определение
Закон умножения в комбинаторике: число сочетаний (способов, комбинаций) в независимых наборах умножается.
Другими словами, пусть имеется A способов выполнить одно действие и B способов выполнить другое действие. Путь также эти действия независимы, т.е. никак не связаны между собой. Тогда можно найти число способов выполнить первое и второе действие по формуле: C = A · B.
Задача
У Пети есть 4 монеты по 1 рублю и 2 монеты по 10 рублей. Петя, не глядя, достал из кармана 1 монету номиналом 1 рубль и еще 1 монету номиналом 10 рублей, чтобы купить сигарету за 11 рублей у бабули в подземном переходе. Сколькими способами он может выбрать эти монеты?
Решение
Итак, сначала Петя достает k = 1 монету из n = 4 имеющихся монет номиналом 1 рубль. Число способов сделать это равно C 41 =... = 4.
Затем Петя снова лезет в карман и достает k = 1 монету из n = 2 имеющихся монет номиналом 10 рублей. Здесь число сочетаний равно C 21 =... = 2.
Поскольку эти действия независимы, общее число вариантов равно C = 4 · 2 = 8.
Ответ
Задача
В корзине лежат 8 белых шаров и 12 черных. Сколькими способами можно достать из этой корзины 2 белых шара и 2 черных?
Решение
Всего в корзине n = 8 белых шаров, из которых надо выбрать k = 2 шара. Это можно сделать C 82 =... = 28 различными способами.
Кроме того, в корзине имеется n = 12 черных шаров, из которых надо выбрать опять же k = 2 шара. Число способов сделать это равно C 122 =... = 66.
Поскольку выбор белого шара и выбор черного — события независимые, общее число комбинаций считается по закону умножения: C = 28 · 66 = 1848. Как видим, вариантов может быть довольно много.
Ответ
Закон умножения показывает, сколькими способами можно выполнить сложное действие, которое состоит из двух и более простых — при условии, что все они независимы.
Именно этой формулы многим не хватило для решения задачи B10 на пробном ЕГЭ по математике. Разумеется, существуют и другие методы решения, в которых комбинаторика не используется — и мы обязательно рассмотрим их ближе к настоящему экзамену. Однако ни один из них не сравнится по надежности и лаконичности с теми приемами, которые мы сейчас изучаем.
Закон сложения
Если закон умножения оперирует «изолированными» событиями, которые не зависят друг от друга, то в законе сложения все наоборот. Здесь рассматриваются взаимоисключающие события, которые никогда не случаются одновременно.
Например, «Петя вынул из кармана 1 монету» и «Петя не вынул из кармана ни одной монеты» — это взаимоисключающие события, поскольку вынуть одну монету и при этом не вынуть ни одной невозможно.
Аналогично, события «Выбранный наугад шар — белый» и «Выбранный наугад шар — черный» также являются взаимоисключающими.
Определение
Закон сложения в комбинаторике: если два взаимоисключающих действия можно выполнить A и B способами соответственно, то эти события можно объединить. При этом возникнет новое событие, которое можно выполнить X = A + B способами.
Другими словами, при объединении взаимоисключающих действий (событий, вариантов) число их комбинаций складывается.
Можно сказать, что закон сложения — это логическое «ИЛИ» в комбинаторике, когда нас устраивает любой из взаимоисключающих вариантов. И наоборот, закон умножения — это логическое «И», при котором нас интересует одновременное выполнение и первого, и второго действия.
Задача
В корзине лежат 9 черных шаров и 7 красных. Мальчик достает 2 шара одинакового цвета. Сколькими способами он может это сделать?
Решение
Если шары одинакового цвета, то вариантов немного: оба они либо черные, либо красные. Очевидно, что эти варианты — взаимоисключающие.
В первом случае мальчику предстоит выбирать k = 2 черных шара из n = 9 имеющихся. Число способов сделать это равно C 92 =... = 36.
Аналогично, во втором случае выбираем k = 2 красных шара из n = 7 возможных. Число способов равно C 72 =... = 21.
Осталось найти общее количество способов. Поскольку варианты с черными и красными шарами — взаимоисключающие, по закону сложения имеем: X = 36 + 21 = 57.
Ответ
Задача
В ларьке продаются 15 роз и 18 тюльпанов. Ученик 9-го класса хочет купить 3 цветка для своей одноклассницы, причем все цветы должны быть одинаковыми. Сколькими способами он может составить такой букет?
Решение
По условию, все цветы должны быть одинаковыми. Значит, будем покупать либо 3 розы, либо 3 тюльпана. В любом случае, k = 3.
В случае с розами придется выбирать из n = 15 вариантов, поэтому число сочетаний равно C 153 =... = 455. Для тюльпанов же n = 18, а число сочетаний — C 183 =... = 816.
Поскольку розы и тюльпаны — это взаимоисключающие варианты, работаем по закону сложения. Получаем общее число вариантов X = 455 + 816 = 1271. Это и есть ответ.
Ответ