Правило суммы
Задача. На подносе лежат 5 яблок и 3 груши. Сколькими способами можно выбрать фрукт с подноса?
Решение. Яблоко можно выбрать пятью способами. Грушу можно выбрать тремя способами. Стало быть, один из этих фруктов можно выбрать 5 + 3 = 8 способами.
Задача. На полке стоят десять томов Пушкина, четыре тома Лермонтова и шесть томов Гоголя. Сколькими способами можно выбрать с полки одну книгу?
Решение. Понятно, что 10 + 4 + 6 = 20 способами.
Правило суммы. Пусть объект a можно выбрать m способами, а объект b можно выбрать n способами, причём выбор одного объекта исключает одновременный выбор другого объекта. Тогда выбор «либо a, либо b» можно сделать m + n способами.
Более общим образом, пусть объект a1 можно выбрать n1 способами, объект a2 можно выбрать n2 способами, . . . , объект ak можно выбрать nk способами, причём выбор одного объекта исключает одновременный выбор другого объекта. Тогда выбор «либо a1, либо a2, . . . , либо ak» можно осуществить n1 + n2 + . . . + nk способами.
Правило суммы отражает тот очевидный факт, что число элементов в объединении попарно непересекающихся множеств равно сумме числа элементов в каждом из множеств. Так, в первой задаче множество яблок (Я) состоит из пяти элементов, а множество груш (Г) состоит из трёх элементов; эти множества не пересекаются, так что множество фруктов (Я ∪Г) состоит из 5 + 3 элементов.
Аналогично, во второй задаче множество П ∪Л∪Г (обозначения очевидны) состоит из 10+4+6 элементов. Соответственно, имеем вторую (эквивалентную) формулировку правила суммы.
Правило суммы в терминах множеств. Пусть множество A состоит из m элементов, а множество B состоит из n элементов, причём множества A и B не пересекаются. Тогда множество A ∪ B состоит из m + n элементов.
Более общим образом, пусть множество A1 состоит из n1 элементов, множество A2 состоит из n2 элементов, . . . , множество Ak состоит из nk элементов, и множества A1, A2, . . . , Ak попарно не пересекаются. Тогда множество A1 ∪ A2 ∪ . . . ∪ Ak состоит из n1 + n2 + . . . + nk элементов.
Правило произведения
При решении комбинаторных задач часто приходится умножать число способов выбора одного объекта на число способов выбора другого объекта. Рассмотрим некоторые примеры.
Задача. Имеются три города: A, B и C. Из A в B ведут три дороги, из B в C — пять дорог. Сколько различных путей ведут из A в C? Прямого пути между A и C нет.
Решение. Обозначим дороги буквами и цифрами. Именно, дороги из A в B назовём a, b, c; дороги из B в C назовём 1, 2, 3, 4, 5.
Тогда любой маршрут из A в C получает уникальное имя в виде пары из буквы и цифры. Например, маршрут b4 означает, что из A и B мы пошли по дороге b, а из B в C — по дороге 4.
Выпишем все такие пары в виде таблицы:
a1 a2 a3 a4 a5
b1 b2 b3 b4 b5
c1 c2 c3 c4 c5
Всего получилось 3 · 5 = 15 маршрутов. Как видим, число маршрутов равно произведению числа дорог из A в B на число дорог из B в C.
Задача. В магазине есть 7 видов пиджаков, 5 видов брюк и 4 вида галстуков. Сколькими способами можно купить комплект из пиджака, брюк и галстука?
Решение. Предположим, что пиджак уже выбран (это можно сделать 7 способами). К пиджаку выбираем брюки 5 способами. Итого пару (пиджак, брюки) можно выбрать 7 · 5 способами. К этой паре можно купить галстук 4 способами. Следовательно, для покупки пиджака, брюк и галстука имеется 7 · 5 · 4 = 140 способов.
Задача. Сколько существует пятизначных чисел, у которых все цифры чётные?
Решение. Представим себе пять последовательных позиций для цифр пятизначного числа. На первую позицию можно поставить четыре цифры: 2, 4, 6 или 8. На вторую позицию можно поставить пять цифр: 0, 2, 4, 6 или 8. На третью, четвёртую и пятую позиции можно поставить те же пять цифр: 0, 2, 4, 6 или 8. Всего имеем 4·5·5·5·5 = 2500 вариантов заполнения позиций; именно столько и будет искомых чисел.
Правило произведения. Пусть объект a можно выбрать m способами, после чего объект b можно выбрать n способами. Тогда упорядоченную пару (a, b) можно выбрать mn способами; иными словами, существует mn различных упорядоченных пар (a, b).
Более общим образом, пусть объект a1 можно выбрать n1 способами, после чего объект a2 можно выбрать n2 способами, . . . , после чего объект ak можно выбрать nk способами. Тогда цепочку (a1, a2, . . . , ak) можно выбрать n1n2 . . . nk способами; иными словами, существует n1n2 . . . nk цепочек (a1, a2, . . . , ak).
Задача. Сколько подмножеств у 5-элементного множества? У n-элементного?
Решение. Пусть имеется множество из 5 элементов A = {a1, a2, a3, a4, a5}. Каждому его подмножеству B можно дать уникальное имя в виде упорядоченной пятёрки нулей и единиц по следующему правилу: если на i-й позиции пятёрки стоит единица, то ai ∈ B; если же на i-й позиции пятёрки стоит нуль, то ai ∈/ B.
Например, пятёрка 10010 обозначает подмножество {a1, a4}. Пятёрки 00000 и 11111 обозначают соответственно пустое множество и само множество A.
Таким образом, у множества A имеется ровно столько подмножеств, сколько существует упорядоченных пятёрок из нулей и единиц. Каждую позицию пятёрки можно заполнить двумя способами (0 или 1), поэтому таких пятёрок 2·2·2·2·2 = 25 = 32. Это и есть число подмножеств 5-элементного множества.
Для n-элементного множества рассуждение аналогично. Каждое его подмножество получает уникальное имя (по тому же правилу) в виде цепочки длины n, состоящей из нулей и единиц. Всего таких цепочек 2n . Следовательно, число всех подмножеств n-элементного множества равно 2n.
Задача. Сколько пар натуральных чисел (x, y) удовлетворяют равенству НОД(x, y) + НОК(x, y) = 2011?
Решение. Напомним для начала некоторые простые факты касательно НОД и НОК. Они наверняка пригодятся вам на олимпиадах.
Пусть НОД(x, y) = d. Тогда x = ad и y = bd для некоторых натуральных a и b. При этом числа a и b являются взаимно простыми (то есть не имеют общих делителей, кроме 1). В самом деле, если у a и b есть общий делитель c > 1, то число cd будет общим делителем чисел x и y. Но это противоречит тому, что d — наибольший общий делитель этих чисел.
Пусть z есть общее кратное чисел x и y (не обязательно наименьшее). Поскольку z делится на x и на y, имеем: z = kx = kad и z = my = mbd для некоторых натуральных k и m. Отсюда kad = mbd, то есть ka = mb; но так как a и b взаимно просты, то m делится на a: m = na для некоторого натурального n. Следовательно, z = nabd, откуда видно, что наименьшее общее кратное получается при n = 1: НОК(x, y) = abd.
Заметим попутно, что НОД(x, y)·НОК(x, y) = d·abd = ad· bd = xy.
Теперь переходим к решению задачи. Имеем:
2011 = d + abd = d(1 + ab).
Отсюда следует, что 2011 делится на 1 + ab > 1. Однако 2011 — простое число (убедитесь в этом самостоятельно), поэтому единственным его делителем, большим единицы, может быть лишь оно само: 1 + ab = 2011, откуда ab = 2010. Тогда d = 1, то есть x = a и y = b.
Задача свелась к следующему вопросу: сколько пар натуральных чисел (a, b) удовлетворяют равенству ab = 2010? Из этого равенства b однозначно определяется по a; поэтому фактически нам надо выяснить, сколько делителей a имеется у числа 2010.
Для этого раскладываем 2010 на простые множители: 2010 = 2 · 3 · 5 · 67. Дальнейшее рассуждение вам уже знакомо: каждый делитель числа 2010 имеет вид 2 p · 3 q · 5 r · 67s , где числа p, q, r, s могут принимать значения 0 или 1. Поэтому количество делителей числа 2010 равно 2 · 2 · 2 · 2 = 16. Это и есть искомое число пар (x, y).
Часто в задачах работают одновременно оба правила — суммы и произведения.
Задача. Сколько существует способов расставить на шахматной доске 8 × 8 белую ладью и чёрного короля так, чтобы ладья била короля, но король не бил ладью? Способы расстановки, получающиеся друг из друга поворотом доски, считаются разными.
Решение. Где бы ни стояла на доске ладья, она держит под боем ровно 14 клеток — 7 по горизонтали и 7 по вертикали. Если король стоит в углу доски (таких клеток 4), то в своих горизонтали и вертикали он бьёт две клетки. Значит, ладью можно поставить на 12 клеток.
Правила суммы и произведения
