Олимпиадные задачи по комбинаторике. Задача о беспорядках

• Название: Задача о беспорядках
• Анкор: Олимпиадные задачи по комбинаторике
• Дата: 12.04.2022
• Размер: 0.5 Mb.
• Имя файла: kombinatorika.pdf
• Тип: Задача; #468020
• страница: 2 из 6

25 детей, слово «НЯНЯ» — 30 детей, а слово «МАНЯ» — 36 детей. У скольких ребят все три карточки одинаковы?
Решение. Возможны четыре вида наборов из трёх карточек:
— МА, МА, МА; пусть a детей имеют такой набор;
— МА, МА, НЯ; пусть b детей имеют такой набор;
— МА, НЯ, НЯ; пусть c детей имеют такой набор;
— НЯ, НЯ, НЯ; пусть d детей имеют такой набор.
Очевидно, что a + b = 25, c + d = 30, b + c = 36. Нас интересует величина a + d. Имеем:
a + d = (a + b) + (c + d) − (b + c) = 25 + 30 − 36 = 19.
Итак, три карточки одинаковы у 19 детей.
2.4
Задачи
1. Докажите, что для любых трёх множеств A, B и C выполнены равенства:
а) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C);
б) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C);
в) (A ∪ B) \ C = (A \ C) ∪ (B \ C);
г) A \ (B ∪ C) = (A \ B) ∩ (A \ C).
2. (Математический праздник, 1990, 6–7 ) Среди математиков каждый седьмой — философ, а среди философов каждый девятый — математик. Кого больше — философов или математиков?
Философов(в предполо жении ихсуществования)
3. («Физтех», 2013, 8 ) На маленьком острове 2/3 всех мужчин женаты и 3/5 всех женщин замужем. Сколько жителей острова состоят в браке, если всего там проживает 1900 человек?
1200 4. («Физтех», 2014, 7–8 ) На данный момент в классе 20 учеников, получивших с начала учеб- ного года хотя бы одну двойку, 17 учеников, получивших не менее двух двоек, 8 учеников,
получивших не менее трёх двоек, три ученика, получивших не менее четырёх двоек, один уче- ник, получивший пять двоек. Больше пяти двоек нет ни у кого. Сколько всего двоек в журнале?
49 5. («Физтех», 2014, 9–10 ) Сколько одинаковых членов находится среди первых 2000 членов арифметических прогрессий 9, 11, 13, . . . и 3, 8, 13, . . . ?
400 6. («Высшая проба», 2014, 9 ) В детский сад завезли карточки трёх видов для обучения чтению:
на некоторых написано «па», на некоторых «сть», и на некоторых «ко». Каждый из 40 детей взял три карточки (не обязательно разные) и стал составлять из них слова. Оказалось, что слово «папа» могут сложить из своих карточек 23 ребёнка, слово «пасть» — 19 детей, слово
«кость» — 11 детей, слово «пакость» — 4 ребёнка. При этом каждый ребёнок может сложить хотя бы одно слово из перечисленных. Сколько детей взяли себе три карточки со слогами «па»,

«па», «сть»?
9 9

7. (Московская математическая олимпиада, 1985, 10 ) Даны 1985 множеств, каждое из кото- рых состоит из 45 элементов, причём объединение любых двух множеств содержит ровно 89

элементов. Сколько элементов содержит объединение всех этих 1985 множеств?
87341 8. (Всероссийская олимпиада по математике, 1997, 11 ) Члены Государственной Думы обра- зовали фракции так, что для любых двух фракций A и B (не обязательно различных) A ∪ B —
тоже фракция (через C обозначается множество всех членов Думы, не входящих в C). Дока- жите, что для любых двух фракций A и B A ∪ B — также фракция.
10

3
Правила суммы и произведения
Правило суммы и правило произведения — основные комбинаторные принципы, которые ис- пользуются в комбинаторике повсеместно.
3.1
Правило суммы
Правило суммы мы уже фактически использовали в задаче про карточки, разобранной в конце предыдущего раздела. Проиллюстрируем его ещё на двух элементарных задачах.

Задача. На подносе лежат 5 яблок и 3 груши. Сколькими способами можно выбрать фрукт с подноса?
Решение. Яблоко можно выбрать пятью способами. Грушу можно выбрать тремя способами.
Стало быть, один из этих фруктов можно выбрать 5 + 3 = 8 способами.
Задача. На полке стоят десять томов Пушкина, четыре тома Лермонтова и шесть томов Го- голя. Сколькими способами можно выбрать с полки одну книгу?
Решение. Понятно, что 10 + 4 + 6 = 20 способами.
Правило суммы. Пусть объект a можно выбрать m способами, а объект b можно выбрать n способами, причём выбор одного объекта исключает одновременный выбор другого объекта.
Тогда выбор «либо a, либо b» можно сделать m + n способами.
Более общим образом, пусть объект a
1
можно выбрать n
1
способами, объект a
2
можно вы- брать n
2
способами, . . . , объект a k
можно выбрать n k
способами, причём выбор одного объекта исключает одновременный выбор другого объекта. Тогда выбор «либо a
1
, либо a
2
, . . . , либо a k
»
можно осуществить n
1
+ n
2
+ . . . + n k
способами.
Правило суммы отражает тот очевидный факт, что число элементов в объединении попарно непересекающихся множеств равно сумме числа элементов в каждом из множеств. Так, в первой задаче множество яблок (Я) состоит из пяти элементов, а множество груш (Г) состоит из трёх элементов; эти множества не пересекаются, так что множество фруктов (Я ∪ Г) состоит из 5 + 3
элементов. Аналогично, во второй задаче множество П ∪ Л ∪ Г (обозначения очевидны) состоит из 10+4+6 элементов. Соответственно, имеем вторую (эквивалентную) формулировку правила суммы.
Правило суммы в терминах множеств. Пусть множество A состоит из m элементов, а мно- жество B состоит из n элементов, причём множества A и B не пересекаются. Тогда множество
A ∪ B состоит из m + n элементов.
Более общим образом, пусть множество A
1
состоит из n
1
элементов, множество A
2
состоит из n
2
элементов, . . . , множество A
k состоит из n k
элементов, и множества A
1
, A
2
, . . . , A
k попарно не пересекаются. Тогда множество A
1
∪ A
2
∪ . . . ∪ A
k состоит из n
1
+ n
2
+ . . . + n k
элементов.
3.2
Правило произведения
При решении комбинаторных задач часто приходится умножать число способов выбора одного объекта на число способов выбора другого объекта. Рассмотрим некоторые примеры.
Задача. Имеются три города: A, B и C. Из A в B ведут три дороги, из B в C — пять дорог.
Сколько различных путей ведут из A в C? Прямого пути между A и C нет.
Решение. Обозначим дороги буквами и цифрами. Именно, дороги из A в B назовём a, b, c;
дороги из B в C назовём 1, 2, 3, 4, 5.
11

A
B
C
a 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).
Более общим образом, пусть объект a
1
можно выбрать n
1
способами, после чего объект a
2
можно выбрать n
2
способами, . . . , после чего объект a k
можно выбрать n k
способами. То- гда цепочку (a
1
, a
2
, . . . , a k
) можно выбрать n
1
n
2
. . . n k
способами; иными словами, существует n
1
n
2
. . . n k
цепочек (a
1
, a
2
, . . . , a k
).

Задача. Сколько подмножеств у 5-элементного множества? У n-элементного?
Решение. Пусть имеется множество из 5 элементов A = {a
1
, a
2
, a
3
, a
4
, a
5
}. Каждому его под- множеству B можно дать уникальное имя в виде упорядоченной пятёрки нулей и единиц по следующему правилу: если на i-й позиции пятёрки стоит единица, то a i
∈ B; если же на i-й позиции пятёрки стоит нуль, то a i
/
∈ B.
Например, пятёрка 10010 обозначает подмножество {a
1
, a
4
}. Пятёрки 00000 и 11111 обозна- чают соответственно пустое множество и само множество A.
Таким образом, у множества A имеется ровно столько подмножеств, сколько существует упорядоченных пятёрок из нулей и единиц. Каждую позицию пятёрки можно заполнить двумя
12

способами (0 или 1), поэтому таких пятёрок 2 · 2 · 2 · 2 · 2 = 2 5
= 32. Это и есть число подмножеств
5-элементного множества.
Для n-элементного множества рассуждение аналогично. Каждое его подмножество получает уникальное имя (по тому же правилу) в виде цепочки длины n, состоящей из нулей и единиц.
Всего таких цепочек 2
n
. Следовательно, число всех подмножеств n-элементного множества равно 2
n
Задача. (Размещения с повторениями) Сколькими способами можно разложить m различных шаров в n различных ящиков? На число шаров в ящике ограничений нет.
Решение. Представим себе m клеток (это шары). В каждую клетку можно вписать любое число от 1 до n (номер ящика, в который кладётся шар). Всего получится n m
всевозможных способов заполнить клетки, то есть разложить шары по ящикам.
Число разложений m различных шаров по n различным ящикам (без ограничений на число шаров в ящике) называется иногда числом размещений с повторениями из n по m и обознача- ется ¯
A
m n
. Таким образом, ¯
A
m n
= n m
. О более содержательном понятии — числе размещений (без повторений) — речь пойдёт в следующем разделе.

Задача. Сколько делителей у числа 720?
Решение. Разложим на простые множители: 720 = 2 4
· 3 2
· 5. Следовательно, всякий делитель числа 720 должен иметь вид 2
a
· 3
b
· 5
c
, где a ∈ {0, 1, 2, 3, 4}, b ∈ {0, 1, 2}, c ∈ {0, 1}. Мы видим,
что каждому делителю соответствует единственная упорядоченная тройка (a, b, c) и наоборот —
каждой упорядоченной тройке (a, b, c) с элементами из данных множеств отвечает единственный делитель числа 720. Можно сказать, что (a, b, c) — это уникальное имя делителя, и потому делителей будет ровно столько же, сколько получится упорядоченных троек (a, b, c).
Но число a можно выбрать 5 способами, число b можно выбрать 3 способами, число c мож- но выбрать 2 способами; значит, упорядоченную тройку (a, b, c) можно выбрать 5 · 3 · 2 = 30
способами. Таким образом, у числа 720 имеется 30 делителей.
Решение последней задачи можно обобщить и найти количество делителей произвольного натурального числа, представленного своим разложением на простые множители.
Задача. Пусть p
1
, p
2
, . . . , p n
— различные простые числа; k
1
, k
2
, . . . , k n
— целые неотрица- тельные числа. Сколько делителей у числа a = p k
1 1
p k
2 2
. . . p k
n n
?
Решение. Каждый делитель числа a имеет вид p m
1 1
p m
2 2
. . . p m
n n
, где целые числа m
1
, m
2
, . . . ,
m n
удовлетворяют условиям 0 6 m
1 6 k
1
, 0 6 m
2 6 k
2
, . . . , 0 6 m n
6 k n
. Следовательно,
цепочка (m
1
, m
2
, . . . , m n
) есть уникальное имя делителя, и потому делителей будет столько же,
сколько получится цепочек (m
1
, m
2
, . . . , m n
). Первый элемент этой цепочки можно выбрать k
1
+ 1 способами, второй элемент k
2
+ 1 способами, . . . , n-й элемент k n
+ 1 способами. Значит,
всего имеется (k
1
+ 1)(k
2
+ 1) . . . (k n
+ 1) делителей числа a.
В комбинаторной задаче могут использоваться также факты, связанные с делимостью.

Задача. («Физтех», 2013, 9–11 ) Сколько пар натуральных чисел (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. Отсюда
13

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
· 67
s
, где числа p, q, r, s могут принимать значения 0 или 1. Поэтому количество делителей числа 2010 равно
2 · 2 · 2 · 2 = 16. Это и есть искомое число пар (x, y).
Часто в задачах работают одновременно оба правила — суммы и произведения.

Задача. Сколько трёхзначных чисел содержат ровно одну цифру 7?
Решение. Единственная цифра 7 может стоять либо на первом месте, либо на втором, либо на третьем. Соответственно находим количества чисел в каждом из этих случаев, после чего пользуемся правилом суммы.
Найдём количество n
1
трёхзначных чисел, у которых единственная цифра 7 будет первой.
На второй и третьей позициях может стоять любая из цифр, кроме 7; следовательно, вторую и третью позицию мы можем заполнить 9 · 9 = 81 способами. Итак, n
1
= 81.
Теперь найдём количество n
2
трёхзначных чисел, у которых единственная цифра 7 стоит на втором месте. Первая цифра может быть любой, кроме 0 и 7 (то есть 8 способов выбора).
Вторая цифра — любая, кроме 7 (это 9 способов). Следовательно, n
2
= 8 · 9 = 72.
Аналогично находим количество n
3
трёхзначных чисел, у которых единственная цифра 7
стоит на третьем месте: n
3
= 8 · 9 = 72.
По правилу суммы искомое количество чисел равно n
1
+ n
2
+ n
3
= 81 + 72 + 72 = 225.
Задача. («Высшая проба», 2014, 8 ) Сколько существует способов расставить на шахматной доске 8 × 8 белую ладью и чёрного короля так, чтобы ладья била короля, но король не бил ладью? Способы расстановки, получающиеся друг из друга поворотом доски, считаются раз- ными.
Решение. Где бы ни стояла на доске ладья, она держит под боем ровно 14 клеток — 7 по горизонтали и 7 по вертикали.
Если король стоит в углу доски (таких клеток 4), то в своих горизонтали и вертикали он бьёт две клетки. Значит, ладью можно поставить на 12 клеток (рисунок слева).
K
K
K
14

Если король стоит на краю доски, но не в углу (таких клеток 24), то в своих горизонтали и вертикали он бьёт три клетки. Значит, ладью можно поставить на 11 клеток (рисунок в центре).
Если же король стоит не на краю доски (таких клеток 36), то в своих горизонтали и вер- тикали он бьёт четыре клетки. В этом случае ладью можно поставить на 10 клеток (рисунок справа).
Всего требуемых расстановок короля и ладьи получается
4 · 12 + 24 · 11 + 36 · 10 = 672.
3.3
Задачи
1. (Математический праздник, 1998, 6 ) На глобусе проведены 17 параллелей и 24 меридиана.
На сколько частей разделена поверхность глобуса? Меридиан — это дуга, соединяющая Север- ный полюс с Южным. Параллель — это окружность, параллельная экватору (экватор тоже является параллелью).
432 2. (Математический праздник, 1996, 6 ) Каких пятизначных чисел больше: не делящихся на 5

или тех, у которых ни первая, ни вторая цифра слева — не пятёрка?
Поровну
3. (Всеросс., 2014, I этап, 7–9 ) Назовём число зеркальным, если слева направо оно «чита- ется» так же, как справа налево. Например, число 12321 — зеркальное. Сколько существует пятизначных зеркальных чисел, которые делятся на 5?
100 4. («Ломоносов», 2012, 7 ) Города A, B, C и D соединены дорогами так, как показано на рисунке.
A
B
C
D

Сколькими способами можно проделать путь из города A в город D, побывав в каждом городе ровно по одному разу?
20 5. («Высшая проба», 2014, 8 ) Сколько существует способов расставить на шахматной доске

8 × 8 белого слона и чёрного короля так, чтобы слон бил короля, но король не бил слона?
364 6. («Высшая проба», 2014, 9 ) Из множества {1, 2, 3, 4} выбираются три натуральных числа a,
b, c (не обязательно различных). Сколько существует способов сделать это так, чтобы число a
(b c
)

делилось на 4?
28 15

7. («Покори Воробьёвы горы!», 2011, 11 ) Сколько существует четырёхзначных чисел, делящих- ся на 4, в десятичной записи которых нет цифр 4, 5, 6, 8?
180 8. («Ломоносов», 2013, 7 ) Сколькими различными способами шахматный король может пройти с поля e1 на поле h5, если ему разрешается ходить только на одну клетку вправо, вверх или по диагонали вправо вверх?
129 9. («Ломоносов», 2013, 8 ) Сколькими различными способами шахматный ферзь может пройти с поля d1 на поле h8, если ему разрешается ходить только вправо, вверх или по диагонали вправо вверх на любое число клеток?
39625 10. («Ломоносов», 2013, 8 ) Найдите количество девятизначных чисел, в которых каждая цифра от 1 до 9 встречается ровно один раз, цифры 1, 2, 3, 4, 5 расположены в порядке возрастания,
а цифра 6 стоит раньше цифры 1 (например, 916238457).
504 11. («Ломоносов», 2013, 9 ) Сколькими различными способами можно выбрать целые числа a, b, c ∈ [1; 100] так, чтобы точки с координатами A(−1, a), B(0, b) и C(1, c) образовывали пря- моугольный треугольник?