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

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

А сколько получится способов, если шары одинаковые?
Задача. Сколькими способами можно разложить пять одинаковых шаров по трём различным ящикам? На число шаров в ящике ограничений нет.
Решение. Представим себе, что ящики стоят вплотную друг к другу. Три таких ящика — это фактически две перегородки между ними. Обозначим шар нулём, а перегородку — единицей.
Тогда любому способу раскладывания пяти шаров по трём ящикам однозначно соответствует последовательность из пяти нулей и двух единиц; и наоборот, каждая такая последовательность однозначно определяет некоторый способ раскладывания. Например, 0010010 означает, что в первом ящике лежат два шара, во втором — два шара, в третьем — один шар; последователь- ность 0000011 соответствует случаю, когда все пять шаров лежат в первом ящике.
Теперь ясно, что способов разложить пять шаров по трём ящикам существует ровно столько же, сколько имеется последовательностей из пяти нулей и двух единиц. А число таких после- довательностей равно C
2 7

Задача. Сколько решений в целых неотрицательных числах имеет уравнение x + y + z = 5?
Решение. Если вдуматься, то это — в точности предыдущая задача, только по-другому сфор- мулированная. В самом деле, рассмотрим пять одинаковых шаров и три различных ящика.
Тогда числа x, y и z есть просто количества шаров, положенных соответственно в первый, вто- рой и третий ящик, причём любое из этих чисел может равняться нулю. Следовательно, данное уравнение имеет C
2 7
решений.
Задача. В магазине продаётся апельсиновый, виноградный, персиковый и яблочный сок. Нуж- но купить семь пакетов сока. Сколько различных наборов можно составить?
Решение. Четыре вида сока — это четыре различных ящика, в которые нужно положить семь шаров. Снова обозначаем шары нулём, а перегородки — единицей. Тогда, например, по- следовательность 0000110100 означает, что куплены четыре пакета апельсинового, один пакет персикового и два пакета яблочного сока (виноградный сок не покупали — второй ящик пуст).
25

Поэтому число способов покупки семи пакетов сока четырёх видов — это число способов разложить семь одинаковых шаров по четырём ящикам, то есть число последовательностей из семи нулей и трёх единиц. Число таких последовательностей равно C
3 10
В данной задаче мы могли купить несколько пакетов сока данного вида (хоть все семь).
Поэтому в подобных ситуациях говорят о сочетаниях с повторениями. Сформулируем общую задачу о числе сочетаний с повторениями.
Задача. Сколькими способами можно выбрать m пакетов сока, если в продаже имеется n видов сока? Иными словами, сколькими способами можно разложить m одинаковых шаров по n различным ящикам (в ящике может быть любое количество шаров)?
Решение. Рассуждаем, как и выше: имеем m шаров и n − 1 перегородок, то есть последова- тельность из m нулей и n − 1 единиц. Всего таких последовательностей будет C
m m+n−1
Число способов, которыми можно разложить m одинаковых шаров по n различным ящикам,
называется числом сочетаний с повторениями из n по m и обозначется ¯
C
m n
. Таким образом,
¯
C
m n
= C
m m+n−1
Теперь немного изменим условие исходной задачи о раскладывании шаров по ящикам.

Задача. Сколькими способами можно разложить пять одинаковых шаров по трём различным ящикам так, чтобы ни один ящик не пустовал?
Решение. Положим вначале по одному шару в каждый ящик — тогда ни один ящик пустым не будет. У нас остались два шара, которые надо разложить по трём ящикам произвольным образом. Число таких раскладываний есть число последовательностей из двух нулей и двух единиц, то есть C
2 4
Можно рассуждать и по-другому. Положим в ряд пять шаров. Перегородки могут быть только в промежутках между шарами. Таким образом, нам нужно поместить две перегородки в какие-то два из четырёх промежутков, а выбрать две позиции из четырёх можно C
2 4
способами.

Задача. Сколько решений в натуральных числах имеет уравнение x + y + z = 5?
Решение. Это — в точности предыдущая задача, поскольку ни одна из переменных теперь не может равняться нулю. Уравнение имеет C
2 4
= 6 решений в натуральных числах. Нетрудно решить задачу и непосредственным перебором (сделайте это).
Задача. Сколькими способами можно разложить m одинаковых шаров по n различным ящи- кам так, чтобы ни один ящик не пустовал (m
> n)?
Решение. Рассуждаем, как и выше. Сначала кладём по одному шару в каждый ящик, а осталь- ные m − n шаров раскладываем произвольным образом. Получается ¯
C
m−n n
= C
n−1
m−1
способов.
Знание сочетаний с повторениями (то есть схемы шаров и перегородок) поможет не «изоб- ретать велосипед» на олимпиаде.
Задача. («Физтех», 2011, 9 ) 19 депутатов Городского Собрания выбирают Председателя из
5 кандидатов. Каждый голосует ровно за одного из них. После голосования составляется про- токол заседания, в котором указывается лишь количество голосов за каждого кандидата (без указания, кто за кого проголосовал). Сколько различных протоколов может получиться?
Решение. Пусть за первого кандидата проголосовало x
1
депутатов, за второго — x
2
депутатов,
. . . , за пятого — x
5
депутатов. Тогда x
1
+ x
2
+ x
3
+ x
4
+ x
5
= 19,
(5)
поскольку каждый депутат голосовал лишь за одного кандидата. Теперь ясно, что искомое количество протоколов равно количеству решений уравнения (
5
) в целых неотрицательных
26

числах. А это количество, в свою очередь, есть число способов разложить 19 одинаковых шаров по пяти различным ящикам, то есть число последовательностей из 19 нулей (шаров) и 4 единиц
(перегородок). Таких последовательностей имеется C
4 23
= 8855.
4.6
Маршруты
Маршрутом мы будем называть ломаную, у которой вершины имеют целочисленные коорди- наты, а звенья направлены либо вправо, либо вверх.

Задача. Сколько маршрутов ведут из точки A(0, 0) в точку B(10, 6)? Сколько таких маршру- тов проходит через точку M (6, 4)?
Решение. Возможный маршрут из A в B показан на рисунке.
A
B
Каждый такой маршрут состит из 16 звеньев — 10 горизонтальных и 6 вертикальных. По- этому любой маршрут можно закодировать словом из 16 букв Г и В, в котором будет 10 букв Г
и 6 букв В. Так, изображённый выше маршрут обозначается словом ГВГГВГВВГВГГГВГГ.
Следовательно, маршрутов будет столько же, сколько имеется 16-буквенных слов из 10
букв Г и 6 букв В, то есть C
6 16
Ограничимся теперь маршрутами, проходящими через точку M (6, 4).
A
B
M
Каждый такой маршрут состоит из двух частей: маршрута из A в M и маршрута из M в B.
Рассуждая, как и выше, находим, что маршрутов из A в M будет C
4 10
, а маршрутов из M в B
будет C
2 6
. Всего маршрутов из A в B, проходящих через M , будет C
4 10
C
2 6
4.7
Бином Ньютона
Вам известны формулы (a + b)
2
= a
2
+ 2ab + b
2
и (a + b)
3
= a
3
+ 3a
2
b + 3ab
2
+ b
3
. Выведем общую формулу для (a + b)
n
Задача. (Бином Ньютона) Доказать, что
(a + b)
n
= a n
+ na n−1
b +
n(n − 1)
2
a n−2
b
2
+
n(n − 1)(n − 2)
6
a n−3
b
3
+ . . . + b n
=
n
X
k=0
C
k n
a n−k b
k
27

Решение. Начнём со следующей записи, иллюстрирующей основную идею:
(a + b)
3
= (a + b)(a + b)(a + b) = aaa + aab + aba + abb + baa + bab + bba + bbb.
Точно так же раскроем скобки в произведении
(a + b)
n
= (a + b)(a + b) . . . (a + b)
|
{z
}
n
,
просто записывая получающиеся одночлены как слова длины n, состоящие из букв a и b (можно упорядочить их по алфавиту, как и выше, но это не обязательно). После приведения подобных членов слагаемое a n−k b
k дадут те и только те слова, которые составлены из k букв b и n − k букв a. Таких слов C
k n
; это и будет коэффициент при a n−k b
k в получившейся сумме. Поэтому числа C
k n
называются ещё биномиальными коэффициентами.
Задача. («Высшая проба», 2014, 10 ) Сколько слагаемых получится после раскрытия скобок и приведения подобных слагаемых в выражении (1 + x
2
)
100
(1 + x
5
)
100
?
Решение. Бином Ньютона для нашего выражения даёт:
1 + C
1 100
x
2
+ C
2 100
x
4
+ . . . + C
99 100
x
198
+ x
200


1 + C
1 100
x
5
+ C
2 100
x
10
+ . . . + C
99 100
x
495
+ x
500

=
=
100
X
k=0
C
k
100
x
2k
100
X
m=0
C
m
100
x
5m
=
100
X
k,m=0
a km x
2k+5m
, (6)
где a km
= C
k
100
C
m
100
(вид этих коэффициентов на самом деле не важен). Итак, после раскрытия скобок получается сумма одночленов со всевозможными показателями степени вида 2k + 5m,
где k и m пробегают целые значения от 0 до 100.
Имеем очевидную оценку: 0 6 2k + 5m 6 700, и если бы каждое промежуточное значе- ние достигалось, то после приведения подобных членов в сумме оказалось бы 701 слагаемое.
Выясним, какие промежуточные значения достигаются на самом деле, а какие запрещены.
Мы расмотрим всевозможные остатки, которые может давать 2k + 5m при делении на 10.
Имеем, соответственно, 10 случаев.
1. Пусть 2k + 5m = 10n. Тогда k = 5p, m = 2q (p и q — целые неотрицательные числа),
откуда p + q = n. Имеем:
0 6 5p 6 100 ⇒ 0 6 p 6 20;
0 6 2q 6 100 ⇒ 0 6 q 6 50.
Следовательно, величина 2k + 5m = 10(p + q) может принимать любые целые значения от 0 до 700 = 10(20 + 50). В этом случае запрещённых промежуточных значений нет.
2. Пусть 2k+5m = 10n+1. Перебор остатков от деления на 5 и на 2 показывает, что возможен лишь вариант k = 5p + 3, m = 2q − 1 (и тогда снова p + q = n). Имеем:
0 6 5p + 3 6 100 ⇒ 0 6 p 6 19;
0 6 2q − 1 6 100 ⇒ 1 6 q 6 50.
Поэтому величина 2k + 5m = 10(p + q) + 1 может принимать любые целые значения от 11
до 691. Значение 1 оказывается запрещённым (что очевидно — уравнение 2k + 5m = 1 не имеет решений в натуральных числах).
Оставшиеся случаи разбираются по той же схеме и описываются менее подробно.
28

3. 2k + 5m = 10n + 2 ⇒ k = 5p + 1, m = 2q, p + q = n. Получаем: 0 6 p 6 19, 0 6 q 6 50,
откуда 2 6 10(p + q) + 2 6 692. Запрещённых значений нет.
4. 2k + 5m = 10n + 3 ⇒ k = 5p + 4, m = 2q − 1, p + q = n. Имеем: 0 6 p 6 19, 1 6 q 6 50,
откуда 13 6 10(p + q) + 3 6 693. Значение 3 не достигается.
5. 2k + 5m = 10n + 4 ⇒ k = 5p + 2, m = 2q, p + q = n. Имеем: 0 6 p 6 19, 0 6 q 6 50, откуда
4 6 10(p + q) + 4 6 694. Запрещённых значений нет.
6. 2k + 5m = 10n + 5 ⇒ k = 5p, m = 2q + 1, p + q = n. Имеем: 0 6 p 6 20, 0 6 q 6 49, откуда
5 6 10(p + q) + 5 6 695. Запрещённых значений нет.
7. 2k + 5m = 10n + 6 ⇒ k = 5p + 3, m = 2q, p + q = n. Имеем: 0 6 p 6 19, 0 6 q 6 50, откуда
6 6 10(p + q) + 6 6 696. Запрещённых значений нет.
8. 2k + 5m = 10n + 7 ⇒ k = 5p + 1, m = 2q + 1, p + q = n. Имеем: 0 6 p 6 19, 0 6 q 6 49,
откуда 7 6 10(p + q) + 7 6 687. Значение 697 не достигается.
9. 2k + 5m = 10n + 8 ⇒ k = 5p + 4, m = 2q, p + q = n. Имеем: 0 6 p 6 19, 0 6 q 6 50, откуда
8 6 10(p + q) + 8 6 698. Запрещённых значений нет.
10. 2k + 5m = 10n + 9 ⇒ k = 5p + 2, m = 2q + 1, p + q = n. Имеем: 0 6 p 6 19, 0 6 q 6 49,
откуда 9 6 10(p + q) + 9 6 689. Значение 699 не достигается.
Итак, величина 2k + 5m при 0 6 k, m 6 100 принимает все значения от 0 до 700, кроме 1, 3,
697 и 699. Значит, в сумме (
6
) окажется 701 − 4 = 697 слагаемых.
4.8
Три задачи о функциях
Мы уже видели выше, что задачи с внешне непохожими формулировками могут оказаться в сущности одной и той же задачей. Приведём ещё три примера такого рода.
Напомним, что функцией f из множества A в множество B (обозначается f : A → B) назы- вается правило, по которому каждому элементу x множества A сопоставляется единственный элемент f (x) множества B. При этом элемент f (x) называется образом элемента x, а сам эле- мент x называется прообразом элемента f (x).
Задача. Найти число всех функций f : {1, . . . , m} → {1, . . . , n}.
Решение. Каждую такую функцию можно описать следующим образом. Представим себе m клеток с номерами 1, 2, . . . , m. В клетку с номером i впишем число f (i) — образ числа i. Таким образом, любая наша функция f однозначно задаётся полоской из m клеток, заполненных числами от 1 до n. Очевидно, что число таких полосок (а значит, и искомое число функций)
равно n m
Нетрудно видеть, что данная задача есть по сути задача о разложении m различных шаров в n различных ящиков (без ограничений на число шаров в ящике). Число наших функций —
это число размещений с повторениями ¯
A
m n
Задача. Пусть m 6 n. Найти число возрастающих функций f : {1, . . . , m} → {1, . . . , n} (удо- влетворяющих условию i < j ⇒ f (i) < f (j)).
Решение. Возрастающая функция полностью задаётся множеством своих значений; то есть,
любое m-элементное подмножество множества {1, . . . , n} определяет единственную возрастаю- щую функцию f : {1, . . . , m} → {1, . . . , n}. Поэтому таких функций столько же, сколько имеется m-элементных подмножеств у n-элементного множества, то есть число сочетаний C
m n
29

Задача. Найти число неубывающих функций f : {1, . . . , m} → {1, . . . , n} (удовлетворяющих условию i < j ⇒ f (i)
6 f (j)).
Решение. Чтобы проще было разобраться в общей ситуации, начнём с частного случая. Имен- но, найдём число неубывающих функций f : {1, 2, 3, 4} → {1, 2, 3}.
Каждая такая функция однозначно кодируется неубывающей последовательностью дли- ны 4, составленной из чисел 1, 2 и 3. Например, последовательность 1123 задаёт функцию f ,
для которой f (1) = 1, f (2) = 1, f (3) = 2, f (4) = 3; аналогично, последовательность 1222 задаёт функцию f , для которой f (1) = 1, f (2) = f (3) = f (4) = 2.
А каждую такую последовательность можно описать в терминах шаров и ящиков. Пред- ставим себе три ящика (это числа 1, 2 и 3, из которых составляются последовательности) и четыре одинаковых шара. Число единиц в последовательности — это число одинаковых шаров в первом ящике; число двоек — это число одинаковых шаров во втором ящике; число троек —
это число одинаковых шаров во третьем ящике. Так, последовательность 1123 означает, что в первом ящике лежат два шара, во втором — один и в третьем — один; аналогично, последо- вательность 1222 означает, что в первом ящике находится один шар, во втором — три шара, а третий ящик пуст.
Следовательно, искомое число функций равно числу способов разложить четыре одинако- вых шара по трём ящикам, то есть числу сочетаний с повторениями ¯
C
4 3
= C
4 6
Теперь, разобравшись в этом примере, нетрудно перейти к общему случаю. Число неубы- вающих функций f : {1, . . . , m} → {1, . . . , n} равно числу неубывающих последовательностей длины m, составленных из чисел 1, 2, . . . , n. Возьмём m одинаковых шаров и n различных ящиков. Число единиц в последовательности — это число шаров в первом ящике; число дво- ек в последовательности — это число шаров во втором ящике, и так далее. Следовательно,
количество наших неубывающих последовательностей равно числу способов разложить m оди- наковых шаров по n различным ящикам (без ограничений на число шаров в ящике), то есть числу сочетаний с повторениями ¯
C
m n
= C
m m+n−1 4.9
Задачи

1. На прямой отметили 10 различных точек. Сколько при этом получилось отрезков?
45 2. На окружности отметили 12 различных точек. Сколько при этом получилось дуг?

132 3. Сколько диагоналей в выпуклом 12-угольнике?
54 4. На плоскости проведены 10 прямых так, что никакие две прямые не параллельны и никакие три прямые не пересекаются в одной точке.
а) Найдите число точек пересечения этих прямых.

б) Сколько треугольников образовано этими прямыми?
а)45;
б)120 5. («Высшая проба», 2013, 11 ) В классе 12 учеников. Их нужно разбить на две группы (первую и вторую), состоящие из чётного числа учеников. Сколькими способами это можно сделать?
2046 30

6. («Покори Воробьёвы горы!», 2014, 10–11 ) Сколькими способами тренер может скомплекто- вать хоккейную команду, состоящую из одного вратаря, двух защитников и трёх нападающих,

если в его распоряжении есть два вратаря, 5 защитников и 8 нападающих?
1120 7. («Покори Воробьёвы горы!», 2014, 10–11 ) Из трёх математиков и десяти экономистов нужно составить комиссию, в состав которой войдёт семь человек. При этом в ней должен участвовать хотя бы один математик. Сколькими способами может быть составлена комиссия?
1596 8. («Физтех», 2014, 7–9 ) Сколько существует делящихся на 9 одиннадцатизначных натураль- ных чисел, в записи которых участвуют только цифры 0 и 8?
45 9. («Высшая проба», 2014, 7–8 ) Трамвайный билет состоит из шести цифр от 0 до 9. Сколько билетов содержат ровно 5 одинаковых цифр?
540 10. («Физтех», 2014, 7–8 ) Сколько существует способов составить комиссию из семи человек,

выбирая её членов из восьми супружеских пар, но так, чтобы члены одной семьи не входили в комиссию одновременно?
1024 11. («Физтех», 2014, 9 ) У Васи есть семь книг по математике, а у Вани — девять. Все 16 книг разные. Сколькими способами они смогут обменяться тремя книгами (то есть дать три книги в обмен на три книги)?

2940 12. («Физтех», 2014, 10 ) Сколько существует 23-значных чисел, сумма цифр которых равна четырём?
2300 13. («Физтех», 2014, 7–8 ) Лёша принес в класс 36 орехов и решил разделить их между собой,

Максом и Борей. Сколько способов существует это сделать, если у каждого в итоге должен оказаться хотя бы один орех?
595 14. («Покори Воробьёвы горы!», 2014, 10–11 ) Три пирата Джо, Билл и Том нашли клад, со- держащий 80 одинаковых золотых монет, и хотят разделить их так, чтобы каждому из них досталось не менее 15 монет. Сколько существует способов это сделать?
666 31

15. («Покори Воробьёвы горы!», 2014, 9 ) У Игоря Горшкова есть все семь книг про Гарри
Поттера. Сколькими способами Игорь может расставить эти семь томов на три различные книжные полки так, чтобы на каждой полке стояла хотя бы одна книга? (Расстановки, которые отличаются порядком книг на полке, считаются различными.)
75600 16. («Физтех», 2014, 11 ) Найдите количество семизначных чисел, в десятичной записи кото- рых могут встречаться только цифры 4, 5, 6, 7 и таких, что каждая цифра не меньше преды- дущей.
120 17. В треугольнике Паскаля заменим числа точками и соединим точки отрезками следующим образом:
Путём назовём ломаную с началом в вершине треугольника, звенья которой идут по линиям получившейся сетки только вниз. Докажите, что количество путей, ведущих в k-ю точку n-й строки, равно C
k n
(строки нумеруются сверху с нуля; точки в строке нумеруются слева с нуля).
18. («Высшая проба», 2014, 9, 11 ) Приведённая ниже диаграмма состоит из 24 единичных квад- ратов. Лягушка из каждой клетки может прыгнуть либо на одну клетку вниз, либо на одну клетку влево-вниз по диагонали (не выходя при этом за границы диаграммы). Сколько суще- ствует путей лягушки, ведущих из верхнего ряда квадратов в нижний? (На рисунке показан один из путей лягушки. Верхний и нижний ряды квадратов выделены серым фоном.)
128 32

19. («Высшая проба», 2014, 9–10 ) В выражении
(1 + x)(1 + x
2
)(1 + x
3
) . . . (1 + x
1000
)