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

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

ИВ. Яковлев
|
Материалы по математике
|
MathUs.ru
Комбинаторика — олимпиаднику
Содержание
1
Перебор вариантов Задачи Цепочки и множества Упорядоченные наборы Неупорядоченные наборы Операции надмножествами Задачи Правила суммы и произведения Правило суммы Правило произведения Задачи Размещения, перестановки и сочетания Размещения Перестановки Сочетания Перестановки с повторениями Сочетания с повторениями Маршруты Бином Ньютона Три задачи о функциях Задачи Формула включений и исключений Переход к дополнению Формула включений и исключений Задача о беспорядках Функция Эйлера Числа Стирлинга второго рода Задачи Разные комбинаторные примы 6.1
Подсчёт двумя способами Рекуррентные соотношения Задачи 1

Предисловие
Настоящее пособие предназначено для школьников 8–11 классов, желающих научиться комби- наторике.
В отличие от имеющейся литературы (например, [
1
]–[
7
]) данное пособие нацелено в первую очередь на подготовку к текущим олимпиадам оно, в частности, содержит почти все
1
задачи по комбинаторике, предлагавшиеся на олимпиадах Физтех, Высшая проба, Покори Воро- бьёвы горы и Ломоносов в 2011–2015 годах (больше всего комбинаторных задач встречается именно на этих олимпиадах, в особенности на их отборочных этапах).
Олимпиадные задачи публикуются с указанием названия олимпиады, года её проведения и классов, в которых задача предлагалась. В каждой задаче, где требуется получить число,
приведён численный ответ без комбинаторной формулы (содержащей в себе подсказку поэтому, размышляя над задачами, читатель оказывается в условиях, максимально приближённых к олимпиадным (в частности, к условиям отборочных онлайн-туров, где в поле ответа нужно вписать число).
Никаких предварительных знаний по комбинаторике у читателя не предполагается. Материал изложен с нуля и достаточен для решения приведённых олимпиадных задач. Мы,
однако, не ограничились необходимым минимумом и включили в пособие некоторые вопросы,
выходящие за рамки традиционной олимпиадной тематики. Сюда относятся красивые приложения формулы включений и исключений — задача о беспорядках, функция Эйлера и числа
Стирлинга второго рода эти разделы адресованы заинтересованному школьнику, стремящемуся расширить свой кругозор.
Список литературы Н. Я. Виленкин и др. Комбинаторика. М МЦНМО, 2013.
[2] С. А. Генкин, ИВ. Итенберг, Д. В. Фомин. Ленинградские математические кружки. Киров:
«АСА», 1994. Главы Комбинаторика и Комбинаторика Н. Б. Алфутова, А. В. Устинов. Алгебра и теория чисел. Сборник задач для математических школ. М МЦНМО, 2002. Глава 2. Комбинаторика.
В свободном доступе В. В. Прасолов. Задачи по алгебре, арифметике и анализу. М МЦНМО, 2007. Глава 14.
Комбинаторика.
В свободном доступе В. В. Прасолов. Задачи по планиметрии. М МЦНМО, 2006. Глава 27, § 2. Комбинаторика.
В свободном доступе В. В. Прасолов. Задачи по стереометрии. М МЦНМО, 2010. Глава 19, § 3. Комбинаторика.
В свободном доступе Сайт problems.ru
, раздел «
Комбинаторика
».
1
Исключены задачи параллельных вариантов, несущественно отличающиеся отданной задачи

Перебор вариантов
Основной вопрос комбинаторики — сколько, основная задача — подсчёт числа элементов конечного множества. В комбинаторных задачах нас обычно интересует, сколько комбинаций,
удовлетворяющих тем или иным условиям, можно составить из заданного конечного набора объектов.
В простейших случаях мы можем выписать все нужные нам комбинации и непосредственно подсчитать их. Однако при бессистемном выписывании легко упустить какую-то комбинацию или, наоборот, посчитать некоторую комбинацию дважды. Поэтому при переборе вариантов желательно придерживаться двух правил. Обозначаем наши комбинации буквами или цифрами так, что каждая комбинация будет обозначена своей уникальной последовательностью букв или цифр. Выписываем комбинации в алфавитном порядке (при обозначении буквами) или по возрастанию чисел (при обозначении цифрами).
При таком переборе ни один вариант не ускользнёт от нас и, с другой стороны, будет исключена возможность повторения вариантов.
Задача. Маша собирается съесть яблоко, сливу и мандарин, но пока не решила, в какой последовательности. Сколькими способами Маша может выбрать эту последовательность?
Решение. Обозначаем буквами Я — яблоко, С — слива, М — мандарин. Тогда, например,
СМЯ — это вариант, когда Маша сначала съест сливу, потом — мандарин, потом — яблоко.
Выпишем варианты в алфавитном порядке:
МСЯ, МЯС, СМЯ, СЯМ, ЯМС, ЯСМ.
Получилось 6 вариантов.
Задача. Сколько существует четырёхзначных чисел, сумма цифр которых меньше Решение. Здесь обозначать нечего — мы итак имеем дело с числами. Остаётся лишь выписать по возрастанию все четырёхзначные числа, сумма цифр которых равна 1, 2 или 3:
1000, 1001, 1002, 1010, 1011, 1020, 1100, 1101, 1110, 1200, 2000, 2001, 2010, 2100, Всего получилось 15 чисел.
Задача. (Леонард Эйлер) Четыре гостя при входе в ресторан отдали швейцару свои шляпы, а при выходе получили их обратно. Невнимательный швейцар раздал шляпы случайным образом.

Сколько существует вариантов, при которых каждый гость получил чужую шляпу?
Решение. Занумеруем гостей цифрами 1, 2, 3, 4 итак же занумеруем их шляпы. Считаем, что шляпа сданным номером принадлежит гостю с этим же номером (то есть, например, шляпа принадлежит гостю Тогда каждый вариант получения шляп обозначается четырёхзначным числом, составленным из цифр 1, 2, 3 ив котором номер позиции цифры есть номер гостя, а сама цифра есть номер полученной им шляпы (номера позиций будем считать слева направо).
Например, комбинация 4132 означает, что первый гость получил четвёртую шляпу, второй первую, третий — третью, а четвёртый — вторую. Такой вариант не годится по условию,
поскольку третий получил свою шляпу.
Теперь понятно, что нужно сделать — выписать по возрастанию все четырёхначные числа,
содержащие по одной цифре 1, 2, 3 и 4, такие, что никакая цифра не стоит на позиции со своим номером. Эти числа выписаны ниже под чертой. Красные цифры над чертой — номер позиции (номер гостя, с которым не должна совпадать цифра в соответствующем столбце
(номер шляпы

1 2
3 4
2 1
4 3
2 3
4 1
2 4
1 3
3 1
4 2
3 4
1 2
3 4
2 1
4 1
2 3
4 3
1 2
4 3
2 Как видим, всего имеется 9 вариантов нужной раздачи шляп.
Вариантов может быть довольно много, нов некоторых случаях, тем не менее, самый быстрый способ решения задачи — разумно организованный перебор.
Задача. (Высшая проба, 2013, 8 ) Сколько одночленов окажется в многочлене + t
3
+ t
6
+ . . . + t
30
)(1 + t
5
+ t
10

+ . . . + после раскрытия скобок и приведения подобных членов?
Решение. Раскроем скобки и (не приводя подобные члены) выпишем в таблицу все получающиеся степени одночленов. Первая строка таблицы — это степени, получающиеся приумножении первого многочлена-сомножителя на первое слагаемое второго многочлена (равное вторая строка — это степени, получающиеся приумножении первого многочлена на второе слагаемое второго многочлена (равное t
5
), и т. д 3
6 9
12 15 18 21 24 27 30 5
8 11 14 17 20 23 26 29 32 35 10 13 16 19 22 25 28 31 34 37 40 15 18 21 24 27 30 33 36 39 42 45 20 23 26 29 32 35 38 41 44 47 50 25 28 31 34 37 40 43 46 49 52 55 30 33 36 39 42 45 48 51 54 57 Всего в таблице 77 чисел, из них 24 входят в таблицу более одного раза (блоки повторяющихся чисел обведены рамкой. Следовательно, после приведения подобных членов получится − 24 = 53 одночлена.
В некоторых ситуациях не представляется возможным непосредственно выписать все варианты, но тем не менее очевидно, сколько их на самом деле.
Задача. (Физтех, 2013, 8 ) Сколько пар натуральных чисел удовлетворяет равенству + 5y = 90000 Решение. Переписав данное равенство в виде 2x = 90000 − 5y, мы видим, что правая часть делится на 5. Тогда 2x делится на 5, а значит, и x делится на 5; то есть x = 5n для некоторого натурального n. Аналогично заключаем, что y = 2k для некоторого натурального k.
4

Теперь исходное равенство принимает вид 10n + 10k = 90000, то есть n + k = 9000. Спрашивается сколько пар (n, k) удовлетворяют полученному равенству?
Понятно, что n может принимать значения от 1 до 8999. Число k однозначно определяется выбором n (поскольку k = 9000 − n). Следовательно, имеется 8999 пар чисел (n, Но число x однозначно определяется по n, а число y однозначно определяется поили по k). Значит, искомое количество пар (x, y) также равно Задачи. (Ломоносов, 2014, 8 ) Найдите количество пар целых чисел (m, n), для которых выполнено равенство n
2
+ 2 2014
= m
2 4026 2. (Высшая проба, 2013, 9–10 ) На шахматной доске 7 × 7 посчитайте количество всех квадратов, границы которых проходят по границам клеток 3. (Высшая проба, 2014, 11 ) Найдите количество натуральных чисел n 6 10 таких, что
НОК(16, n) = 16n.
5·
10 11 4. (Математический праздник, 1997, 7 ) Каких прямоугольников с целыми сторонами больше:
с периметром 1996 или с периметром 1998? (Прямоугольники a × b и b × a считаются одинако- выми.)
Поровну
5. (Покори Воробьёвы горы, 2014, 8 ) Найдите количество натуральных чисел от 1 до имеющих ровно четыре натуральных делителя, не менее чем три из которых не превосходят 10.
8 6. (Высшая проба, 2014, 9 ) Из множества {1, 2, 3, 4} выбираются три различных натуральных числа a, b, c. Сколько существует способов сделать это так, чтобы число a

(b делилось на 4?
10 7. (Высшая проба, 2013, 9 ) Сколько одночленов окажется в многочлене + t
4
+ t
8
+ . . . + t
40
)(1 + t
5
+ t
10
+ . . . + после раскрытия скобок и приведения подобных членов 5

8. (Высшая проба, 2011, 9 ) На клетчатой бумаге нарисован квадрат размером 3 × 3 клеточки. Требуется закрасить в этом квадрате три клеточки так, чтобы никакие две закрашенные клеточки не имели общей стороны. Сколькими способами это можно сделать Два способа раскраски считаются одинаковыми, если один можно получить из другого поворотом квадрата 9. (Высшая проба, 2013, 9 ) В стране четыре города А, Б, В и Г. Их хотят связать тремя авиалиниями так, чтобы из каждого города можно было (возможно, с пересадками) долететь до любого другого. Сколькими различными способами это можно сделать 10. (Высшая проба, 2014, 9, 11 ) Сколькими способами цифры от 1 до 9 можно разбить на несколько (больше одной) групп так, чтобы суммы цифр во всех группах были равны друг другу (Разбиения, отличающиеся только перестановкой групп, считаются одинаковыми 11. (Турнир Ломоносова, 1991 ) Шеренга солдат называется неправильной, если никакие три подряд стоящих солдата не стоят по росту (нив порядке возрастания, нив порядке убывания).
Сколько неправильных шеренг можно построить а) из четырёх;

б) из пяти солдат разного роста?
а)10;
б)32 12. (ОММО, 2014 ) Скуперфильд хочет выплатить наложенный на него штраф в 1000 фер- тингов монетами в 7 и 13 фертингов. Сколькими способами он может это сделать?
2

Каким наименьшим количеством монет он может обойтись?
11способов;
минимум82
монеты
13. (Покори Воробьёвы горы, 2012, 8–9 ) Сколькими способами можно поставить цифры от до 9 вместо букв так, чтобы все неравенства выполнялись b
c d
e f
g h
i
>
>
>
>
>
>
∨
∨
∨
∨
∨
∨
42 14. (Покори Воробьёвы горы, 2012, 9 ) Сколькими способами можно выписать вряд числа, 2, 3, 4, 5, 6 так, чтобы для любых трёх подряд идущих чисел a, b, c величина ac − была кратна 7?
12 На олимпиаде этого вопроса не было

15. (Высшая проба, 2013, 8 ) Сколько существует различных (те. неравных друг другу)
остроугольных треугольников с целыми длинами сторон и периметром 24? Выпишите длины трёх сторон всех этих треугольников и докажите, что других не бывает 16. (Высшая проба, 2013, 10 ) Сколько существует различных (те. неравных друг другу)
остроугольных треугольников с целыми длинами сторон и периметром 33? Обоснуйте свой ответ 17. (Ломоносов, 2016, 7–9 ) Сколькими различными способами можно разменять 1000 рублей,
используя только рублёвые, 5-рублёвые и 10-рублёвые монеты 18. (Физтех, 2015, 10–11 ) Сколькими способами можно разменять 120 000 рублей монетами в 1, 2 и 5 рублей 7

Цепочки и множества
Исчерпывающий перебор конечного числа вариантов является совершенно законным способом решения задач. Однако в задачах с большим числом вариантов следует искать другие подходы.
Ниже мы подробно рассмотрим наиболее распространённые комбинаторные схемы — размещения и сочетания. Однако прежде нам нужно обсудить понятия цепочки и множества (то есть упорядоченных и неупорядоченных наборов, которые лежат в основе этих схем.
2.1
Упорядоченные наборы
В некоторых ситуациях порядок следования объектов важен для нас, а в некоторых — не важен.
Пусть, например, нужно решить систему уравнений + y = 3,
x − y = Легко находим решение x = 2, y = 1 и пишем ответ в виде пары (2, 1). По общепринятому соглашению, первым числом нашей пары является значение x, а вторым числом — значение Такую пару называют упорядоченной, поскольку порядок следования чисел важен записывая ответ, мы не можем поменять числа местами Запись (1, 2) означала бы, что x = 1 и y = 2; эта пара, заметим, не является решением данной системы. Пары (2, 1) и (1, 2) — это две разные упорядоченные пары.
Упорядоченный набор объектов мы называем цепочкой, асами объекты — элементами цепочки. Цепочка, составленная по порядку из элементов a
1
, a
2
, . . ., a k
, записывается a
1
a
2
. . . a или (a
1
, a
2
, . . . , a k
); число k называется длиной цепочки. При изменении порядка следования элементов мы, вообще говоря, получим другую цепочку (той же длины. Рассмотрим некоторые примеры цепочек Пусть точка на координатной плоскости имеет абсциссу x = 0 и ординату y = 1. В таком случае мы записываем координаты точки в виде упорядоченной пары (0, 1). Это — цепочка длины 2, составленная из чисел 0 ив указанном порядке. Порядок следования чисел важен ведь (1, 0) — это уже другая точка плоскости (то есть другая упорядоченная пара или другая цепочка Аналогично, пусть точка координатного пространства имеет координаты x = 0, y = 1 и z = 2. Мы записываем её координаты в виде (0, 1, 2). Это — цепочка длины 3, составленная из чисел 0, 1 иона называется также упорядоченной тройкой чисел 0, 1 и 2. Порядок следования чисел важен при изменении порядка мы получим другую точку координатного пространства (другую упорядоченную тройку, другую цепочку Слово автор является цепочкой длины 5, составленной из буква, в, тор. Порядок следования букв важен например, слово отвар, составленное из тех же букв, — это уже другое слово (другая цепочка).
2.2
Неупорядоченные наборы
Допустим теперь, что требуется решить квадратное уравнение x
2
− 3x + 2 = Другое название упорядоченного набора — кортеж

Его корнями служат числа 1 и 2. Мы записываем пару этих корней в виде {1, 2}. Такую пару называют неупорядоченной, поскольку порядок следования чисел в данной записи не играет роли в самом деле, мы можем записать ответив виде {2, 1}, перечислив те же корни в другом порядке. Пары {1, 2} и {2, 1} — это одна и та же неупорядоченная пара.
Всякий неупорядоченный набор объектов есть нечто иное, как множество сами объекты являются элементами множества. Множество, состоящее из элементов a
1
, a
2
, . . ., a k
, записывается. Порядок следования элементов неважен при изменении порядка мы получим тоже множество. Например, как мы видели выше, {1, 2} = {2, 1}. Рассмотрим некоторые примеры множеств Множество корней уравнения x(x−1)(x−2) = 0 есть A = {0, 1, 2}. Это — неупорядоченная тройка чисел 0, 1 и 2, которые являются элементами множества A. Множество A можно записать ив любом другом порядке, например A = {2, 0, 1}.
• Множество букв русского алфавита состоит из 33 элементов а, б, в, . . . , ю, я Множество букв слова математика есть M = мате, и, к. Множество букв слова
«физика» есть F = физ, ка Запись a ∈ A означает, что объект a является элементом множества A, и читается «a принадлежит множеству A». Если a не является элементом множества A (a не принадлежит то это записывается так a /
∈ Множество A называется подмножеством множества B (обозначается A ⊂ B), если любой элемент множества A является элементом множества B. Например, {1, 2, 3} ⊂ {1, 2, 3, 4, Ясно, что для любого множества A выполнено A ⊂ Два множества называются равными, если они состоят из одних и тех же элементов. Иными словами, множество A равно множеству B в томи только в том случае, если A ⊂ B и B ⊂ Например, {1, 2, 3} = {3, 2, Имеется множество, которое не содержит элементов это пустое множество, которое обозначается. Например, множество действительных корней уравнения x
2
+ 1 = 0 пусто.
Любопытно, что пустое множество является подмножеством любого множества. Докажем данное утверждение от противного. Предположим, что это не так, то есть пустое множество не является подмножеством некоторого множества A. Тогда найдётся элемент пустого множества, который не принадлежит множеству A. Но пустое множество не содержит элементов.
Противоречие.
2.3
Операции надмножествами Наиболее важные для нас операции надмножествами объединение, пересечение и разность множеств.
Объединение множеств A и B есть множество A ∪ B, которое состоит из всех элементов,
принадлежащих хотя бы одному из множеств A или B. Так, для множеств M и F из рассмотренного выше примера имеем M ∪ F = мате, и, к, ф, з. Аналогично определяется объединение трёх и большего числа множеств.
Пересечение множеств A и B есть множество A ∩ B, которое состоит из всех элементов,
принадлежащих как множеству A, таки множеству B. Например, для тех же множеств M и имеем M ∩ F = аи, к. Множества, у которых нет общих элементов (то есть пересечение которых пусто, называются непересекающимися.
Разность множеств A и B есть множество A \ B, которое состоит из всех элементов множества, не принадлежащих множеству B. Например, M \ F = м, те Задача. (Высшая проба, 2014, 9 ) В детский сад завезли карточки для обучения чтению:
на некоторых написано МА, на остальных — «НЯ». Каждый ребёнок взял три карточки и

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

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

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