Комбинаторика олимпиаднику

• Название: Комбинаторика олимпиаднику
• Дата: 15.07.2022
• Размер: 0.51 Mb.
• Имя файла: kombinatorika (2).pdf
• Тип: Документы; #631437
• страница: 4 из 6

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

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

поскольку каждый депутат голосовал лишь за одного кандидата. Теперь ясно, что искомое количество протоколов равно количеству решений уравнения (
5
) в целых неотрицательных числах. А это количество, в свою очередь, есть число способов разложить 19 одинаковых шаров по пяти различным ящикам, то есть число последовательностей из 19 нулей (шаров) и 4 единиц
(перегородок). Таких последовательностей имеется C
4 23
= 8855.
4.6
Маршруты
Маршрутом мы будем называть ломаную, у которой вершины имеют целочисленные координаты, а звенья направлены либо вправо, либо вверх.
Задача. Сколько маршрутов ведут из точки A(0, 0) в точку B(10, 6)? Сколько таких маршрутов проходит через точку M (6, Решение. Возможный маршрут изв показан на рисунке.
A
B
Каждый такой маршрут состит из 16 звеньев — 10 горизонтальных и 6 вертикальных. Поэтому любой маршрут можно закодировать словом из 16 букв Г и В, в котором будет 10 букв Г
и 6 букв В. Так, изображённый выше маршрут обозначается словом ГВГГВГВВГВГГГВГГ.
Следовательно, маршрутов будет столько же, сколько имеется буквенных слов из букв Г и 6 букв В, то есть C
6 Ограничимся теперь маршрутами, проходящими через точку M (6, Каждый такой маршрут состоит из двух частей маршрута изв и маршрута изв Рассуждая, как и выше, находим, что маршрутов изв будет C
4 10
, а маршрутов изв будет C
2 6
. Всего маршрутов изв, проходящих через M , будет C
4 10
C
2 Бином Ньютона
Вам известны формулы (a + b)
2
= a
2
+ 2ab + и (a + b)
3
= a
3
+ 3a
2
b + 3ab
2
+ b
3
. Выведем общую формулу для (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
29

Решение. Начнём со следующей записи, иллюстрирующей основную идею + b)
3
= (a + b)(a + b)(a + b) = aaa + aab + aba + abb + baa + bab + bba + Точно также раскроем скобки в произведении + b)
n
= (a + b)(a + b) . . . (a + просто записывая получающиеся одночлены как слова длины n, состоящие из букв a и b (можно упорядочить их по алфавиту, как и выше, но это необязательно. После приведения подобных членов слагаемое a n−k b
k дадут те и только те слова, которые составлены из k букв b и n − k букв a. Таких слов C
k n
; это и будет коэффициент при a n−k b
k в получившейся сумме. Поэтому числа C
k называются ещё биномиальными коэффициентами.
Задача. (Высшая проба, 2014, 10 ) Сколько слагаемых получится после раскрытия скобок и приведения подобных слагаемых в выражении (1 + x
2
)
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
, (где a km
= вид этих коэффициентов на самом деле неважен. Итак, после раскрытия скобок получается сумма одночленов со всевозможными показателями степени вида 2k + где k и m пробегают целые значения от 0 до Имеем очевидную оценку 0 6 2k + 5m 6 700, и если бы каждое промежуточное значение достигалось, то после приведения подобных членов в сумме оказалось бы 701 слагаемое.
Выясним, какие промежуточные значения достигаются на самом деле, а какие запрещены.
Мы расмотрим всевозможные остатки, которые может давать 2k + 5m при делении на Имеем, соответственно, 10 случаев. Пусть 2k + 5m = 10n. Тогда k = 5p, m = 2q (p и q — целые неотрицательные числа),
откуда p + q = n. Имеем 6 5p 6 100 ⇒ 0 6 p 6 20;
0 6 2q 6 100 ⇒ 0 6 q 6 Следовательно, величина 2k + 5m = 10(p + q) может принимать любые целые значения от 0 до 700 = 10(20 + 50). В этом случае запрещённых промежуточных значений нет. Пусть 2k+5m = 10n+1. Перебор остатков отделения на 5 и на 2 показывает, что возможен лишь вариант k = 5p + 3, m = 2q − 1 (и тогда снова p + q = n). Имеем 6 5p + 3 6 100 ⇒ 0 6 p 6 19;
0 6 2q − 1 6 100 ⇒ 1 6 q 6 Поэтому величина 2k + 5m = 10(p + q) + 1 может принимать любые целые значения от до 691. Значение 1 оказывается запрещённым (что очевидно — уравнение 2k + 5m = 1 не имеет решений в натуральных числах).
Оставшиеся случаи разбираются по той же схеме и описываются менее подробно

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

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

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

6. (Покори Воробьёвы горы, 2014, 10–11 ) Сколькими способами тренер может скомплектовать хоккейную команду, состоящую из одного вратаря, двух защитников и трёх нападающих,
если в его распоряжении есть два вратаря, 5 защитников и 8 нападающих 7. (Покори Воробьёвы горы, 2014, 10–11 ) Из трёх математиков и десяти экономистов нужно составить комиссию, в состав которой войдёт семь человек. При этом в ней должен участвовать хотя бы один математик. Сколькими способами может быть составлена комиссия 8. (Физтех, 2014, 7–9 ) Сколько существует делящихся на 9 одиннадцатизначных натуральных чисел, в записи которых участвуют только цифры 0 и 8?
45 9. (Высшая проба, 2014, 7–8 ) Трамвайный билет состоит из шести цифр от 0 до 9. Сколько билетов содержат ровно 5 одинаковых цифр 10. (Физтех, 2014, 7–8 ) Сколько существует способов составить комиссию из семи человек,
выбирая её членов из восьми супружеских парно так, чтобы члены одной семьи не входили в комиссию одновременно 11. (Физтех, 2015, 9, 11 ) У Миши есть пять банок с красками разного цвета. Сколькими различными способами он может покрасить забор, состоящий из 7 досок, так, чтобы любые две соседние доски были разных цветов и при этом он использовал краски не менее чем трёх цветов 12. (Физтех, 2014, 9 ) У Васи есть семь книг по математике, ау Вани — девять. Все 16 книг разные. Сколькими способами они смогут обменяться тремя книгами (то есть дать три книги в обмен натри книги 13. (Физтех, 2014, 10 ) Сколько существует 23-значных чисел, сумма цифр которых равна четырём?
2300 14. (Физтех, 2014, 7–8 ) Лёша принес в класс 36 орехов и решил разделить их между собой,
Максом и Борей. Сколько способов существует это сделать, если у каждого в итоге должен оказаться хотя бы один орех 33

15. (Покори Воробьёвы горы, 2014, 10–11 ) Три пирата Джо, Билли Том нашли клад, содержащий одинаковых золотых монет, и хотят разделить их так, чтобы каждому из них досталось не менее 15 монет. Сколько существует способов это сделать 16. (Ломоносов, 2015, 10–11 ) Сколько 9-значных чисел, делящихся на 5, можно составить путём перестановки цифр числа 377 353 752?
1120 17. (Ломоносов, 2015, 10–11 ) Старуха Шапокляк решила обзавестись коллекцией из 50 саквояжей. В магазине ей на выбор предложили оранжевые, зелёные, фиолетовые и голубые саквояжи. Сколькими способами она может сделать покупку Саквояжи одного цвета считаются идентичными 18. (Покори Воробьёвы горы, 2014, 9 ) У Игоря Горшкова есть все семь книг про Гарри
Поттера. Сколькими способами Игорь может расставить эти семь томов натри различные книжные полки так, чтобы на каждой полке стояла хотя бы одна книга (Расстановки, которые отличаются порядком книг на полке, считаются различными 19. (Физтех, 2014, 11 ) Найдите количество семизначных чисел, в десятичной записи которых могут встречаться только цифры 4, 5, 6, 7 и таких, что каждая цифра не меньше предыдущей. (Ломоносов, 2016, 9–11 ) Даны две параллельные прямые, расстояние между которыми равно 2 см, на каждой отмечено по 10 точек, идущих через 1 см. Нужно из этих 20 точек выбрать 9 таких точек, чтобы расстояние между любыми двумя из них было не менее 2 см.
Сколькими способами это можно сделать 1
4 7
10 5
8 11 2
9 12 3
6 21. (Покори Воробьёвы горы, 2015, 7–9 ) а) В таблице 3 × 4 надо расставить числа от 1 до 12 так, чтобы разность любых двух чисел,
стоящих водной строке была кратна 3, а разность любых двух чисел водном столбце — кратна 4. Пример такой расстановки приведён на рисунке. Сколькими способами можно это сделать?
б) Можно ли расставить числа от 1 до 24 в таблице 6 × 4 так, чтобы разность любых двух чисел водной строке была кратна 6, а разность любых двух чисел водном столбце была кратна 4?
а)144;
б)нет
34

22. (Покори Воробьёвы горы, 2015, 9 ) а) На плоскости расположены точек в виде решётки 3 × 3, как показано на рисунке.