Файл: Элементы комбинаторики.pdf

Оглавление
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 1
Элементы комбинаторики . . . . . . . . . . . . . . . . 11 1.1
Подсчёт и комбинаторные тождества . . . . . . 11 1.2
Формула включений и исключений . . . . . . . 13 1.3
Принцип Дирихле . . . . . . . . . . . . . . . . . 17 1.4
Комбинаторика булева куба . . . . . . . . . . . 19 1.5
Обращение Мёбиуса . . . . . . . . . . . . . . . . 21 1.6
Подсчёт двумя способами . . . . . . . . . . . . 24 1.7
Комбинаторные покрытия. А.Я. Канель . . . . 26 1.8
Подсказки . . . . . . . . . . . . . . . . . . . . . 28 1.9
Указания . . . . . . . . . . . . . . . . . . . . . . 30 2
Основы теории графов . . . . . . . . . . . . . . . . . . 50 2.1
Основные определения . . . . . . . . . . . . . . 50 2.2
Перечисление деревьев . . . . . . . . . . . . . . 53 2.3
Графы с точностью до изоморфизма . . . . . . 56 2.4
Плоские графы . . . . . . . . . . . . . . . . . . 57 2.5
Эйлеровы пути и циклы . . . . . . . . . . . . . 62 2.6
Гамильтоновы пути и циклы . . . . . . . . . . . 65 2.7
Экстремальные задачи (теорема Турана) . . . 67 2.8
Теорема Менгера . . . . . . . . . . . . . . . . . 69 2.9
Метод минимального контрпримера. А. Канель 70 2.10
Степенн´ые последовательности. В.А. Волков,
М.Н. Вялый и А.Б. Скопенков . . . . . . . . . . 72 2.11
Подсказки . . . . . . . . . . . . . . . . . . . . . 79 2.12
Указания . . . . . . . . . . . . . . . . . . . . . . 82 3
Раскраски графов и многочлены . . . . . . . . . . . . 95 3

4
Элементы дискретной математики в задачах
3.1
Раскраски графов . . . . . . . . . . . . . . . . . 95 3.2
Хроматические число и индекс . . . . . . . . . 97 3.3
Хроматический многочлен и многочлен Татта
98 3.4
Подсказки . . . . . . . . . . . . . . . . . . . . . 101 3.5
Указания . . . . . . . . . . . . . . . . . . . . . . 102 4
Основы теории Рамсея . . . . . . . . . . . . . . . . . . 105 4.1
Двухцветные числа Рамсея . . . . . . . . . . . 105 4.2
Многоцветные числа Рамсея . . . . . . . . . . . 106 4.3
Числа Рамсея для гиперграфов . . . . . . . . . 108 4.4
Результаты рамсеевского типа . . . . . . . . . . 109 4.5
Числа Рамсея для подграфов . . . . . . . . . . 111 4.6
Подсказки . . . . . . . . . . . . . . . . . . . . . 112 4.7
Указания . . . . . . . . . . . . . . . . . . . . . . 115 5
Системы множеств (гиперграфы) . . . . . . . . . . . . 126 5.1
Пересечения подмножеств . . . . . . . . . . . . 126 5.2
Системы общих представителей . . . . . . . . . 127 5.3
Системы различных представителей . . . . . . 129 5.4
Перманент . . . . . . . . . . . . . . . . . . . . . 131 5.5
Размерность Вапника-Червоненкиса . . . . . . 132 5.6
Подсолнухи . . . . . . . . . . . . . . . . . . . . . 134 5.7
Оценка Виссера мощности пересечений . . . . 135 5.8
Структуры на конечном множестве . . . . . . . 137 5.9
Подсказки . . . . . . . . . . . . . . . . . . . . . 142 5.10
Указания . . . . . . . . . . . . . . . . . . . . . . 144 6
Аналитические и вероятностные методы . . . . . . . . 153 6.1
Асимптотики . . . . . . . . . . . . . . . . . . . . 153 6.2
Независимость и доказательства существования 156 6.3
Случайные графы . . . . . . . . . . . . . . . . . 174 6.4
Случайные графы-2 . . . . . . . . . . . . . . . . 178 6.5
Подсказки . . . . . . . . . . . . . . . . . . . . . 181 6.6
Указания . . . . . . . . . . . . . . . . . . . . . . 184 7
Алгебраические методы . . . . . . . . . . . . . . . . . . 195 7.1
Линейно-алгебраический метод в комбинаторике195 7.2
Матрицы Адамара . . . . . . . . . . . . . . . . 199 7.3
Подсказки . . . . . . . . . . . . . . . . . . . . . 201 7.4
Указания . . . . . . . . . . . . . . . . . . . . . . 202

ОГЛАВЛЕНИЕ
5 8
Теоремы об инцидентностях в геометрии . . . . . . . . 207 8.1
Задачи . . . . . . . . . . . . . . . . . . . . . . . 207 8.2
Подсказки . . . . . . . . . . . . . . . . . . . . . 209 8.3
Указания . . . . . . . . . . . . . . . . . . . . . . 209 9
Аддитивная комбинаторика . . . . . . . . . . . . . . . 212 9.1
Задачи . . . . . . . . . . . . . . . . . . . . . . . 212 9.2
Подсказки . . . . . . . . . . . . . . . . . . . . . 215 9.3
Указания . . . . . . . . . . . . . . . . . . . . . . 216 10
Графы: задачи для исследования . . . . . . . . . . . . 218 10.1
Степенные последовательности. А. Скопенков 218 10.2
Гамильтоновость (А. Веснин, А. Скопенков) . 219 10.3
Изоморфизмы графов. И.Н. Шнурников . . . . 221 10.4
Турниры. Д. Пермяков . . . . . . . . . . . . . . 222
Предметный указатель . . . . . . . . . . . . . . . . . . . . . 223
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 11
Программа курса ДА 2014-16 уч. годов . . . . . . . . 233

6
Элементы дискретной математики в задачах
Введение

Зачем эта книга?
Мы приводим подборки задач по комбинаторным разделам ма- тематики. Эти задачи подобраны так, что в процессе их решения читатель (точнее, решатель) освоит основы важных теорий — как классических, так и современных. Ср. [S4],[Z],[J]. Книга будет полез- на руководителям и участникам кружков для старшеклассников и младшекурсников (в частности, ориентированных на олимпиады).
Некоторые приводимые красивые задачи и важные темы малоиз- вестны в традиции кружков по математике, но полезны как для математического образования, так и для подготовки к олимпиадам.
Решение этих задач (т. е. изучение соответствующих теорий)
будет полезно также всем, кто хочет стать математиком, специали- стом по computer science или программистом, работающим в науко-
ёмких отраслях информационных технологий. Именно таких спе- циалистов мы готовим на факультете инноваций и высоких техно- логий Московского Физико-Технического Института. Приведенные задачи используются при изучении курсов дискретных структур и дискретного анализа на этом факультете. Эти курсы читают А.Б.
Дайняк и А.М. Райгородский, а остальные авторы ведут семина- ры по этим курсам. Некоторые материалы основаны на занятиях,
проведенных А.Б. Скопенковым в Кировской летней математиче- ской школе, Московской выездной олимпиадной школе, а также на кружках «Математический семинар» и «Олимпиады и математи- ка».
Комбинаторика — один из самых красивых разделов современ- ной математики. Постановки задач этого раздела зачастую доступ- ны школьникам. А результаты, тем не менее, носят фундаменталь- ный характер и важны как для развития других разделов матема- тики, так и для приложений в информатике, биологии, экономике и др. Мы постараемся рассказать о тех мощных современных ме- тодах, благодаря которым кристаллизуется серьезная научная дис- циплина — комбинаторика. Среди этих методов, помимо более или менее стандартных, вероятностный и линейно-алгебраический ме- тоды. Они лежат в основе самых продвинутых комбинаторных ре- зультатов, полученных за последние десятилетия.

ОГЛАВЛЕНИЕ
7
Параграфы второй половины книги дают экскурс в активно раз- вивающиеся области математики. Хотя здесь изучаются только са- мые простые результаты и методы, они дают некоторое представ- ление об основных направлениях научных исследований в соответ- ствующих областях. Этому посвящены замечания, которые не ис- пользуются ни в формулировках, ни в решениях задач. Важные факты выделены словом «теорема» или «следствие».
Используемый материал.
Формулировки большинства задач доступны старшеклассникам,
интересующимся математикой;
1
мы приводим все определения, не так часто изучаемые на кружках. Без определения используются только простейшие определения и результаты теории чисел [O, §8-
§9], [Vi, §§1-3], [Z, §§3.1-3.4 и 3.7]. Если в некотором разделе для по- нимания условий или для решения задач нужны дополнительные сведения (или консультация специалиста), то в начале соответству- ющего раздела приводятся ссылки.
При этом многие задачи трудны: для их решения нужно пред- варительно прорешать другие приведенные задачи на данную тему.
Как устроена книга.
Эту книгу не обязательно читать (точнее, прорешивать) под- ряд. Параграфы и разделы книги практически независимы друг от друга (кроме разделов в §3 и §4, которые желательно прорешивать подряд). Если в задаче одного из разделов все-таки используется материал другого раздела, то либо эту задачу можно игнорировать,
либо посмотреть конеретно указанный материал другого раздела.
Основные обозначения приведены в конце введения. Основные по- нятия и обозначения теории графов введены в §2.1.
При этом параграфы расположены примерно в порядке возрас- тания сложности материала.
К важнейшим задачам приводятся подсказки, указания и реше- ния. Подсказки и указания расположены в конце каждого парагра-
1
Часть материала (например, §1.1) на некоторых кружках и летних шко- лах изучается даже 6-классниками. Однако приводимые подсказки, указания и решения рассчитаны на читателей с некоторой математической культурой
(необходимой для освоения б´ольшей части книги). Разбирать эти решения с
6-классниками нужно по-другому, см., например, [GIF].

8
Элементы дискретной математики в задачах фа. Однако к ним стоит обращаться после прорешивания каждой задачи.
Общие замечания к формулировкам задач.
Задачи обозначаются жирными цифрами. Если в условии за- дачи написано «найдите», то нужно дать ответ без знака суммы и многоточия. Если же условие задачи является формулировкой утверждения, то в задаче требуется это утверждение доказать. Как правило, мы приводим формулировку утверждения перед его до- казательством.
2
В таких случаях для доказательства утвержде- ния могут потребоваться следующие задачи. Это всегда явно ого- варивается в подсказках, а иногда и прямо в тексте. (На занятии задача-подсказка выдается только тогда, когда школьник или сту- дент немного подумал над самой задачей.)
Большинство задач не оригинальны, но установить первоисточ- ник не представляется возможным. Многие задачи взяты из [IKRS],
[Z], [L] и из неопубликованных материалов кафедры дискретной ма- тематики ФИВТ МФТИ.
О литературе.
В список литературы не вошли многие хорошие стандартные учебники по комбинаторике и теории графов (ввиду необъятности их количества). Мы цитировали те из них, которые по тем или иным причинам чаще используем в преподавании. Мы цитировали всю известную нам более продвинутую учебно-научную литературу. Но этот список тоже не претендует на полноту, поскольку мы можем не знать о некоторых публикациях.
В списке литературы [Ga, GKP, Gr, Har, Hal, K, M, R1, R2, R3,
R4, S1, S2, VS, 8] и [AM, BKS, BKKSS, I, Ja, J, KZP, KR, O, P, Vi, R5,
R6, S3, S5] — базовые учебники и статьи по темам этой книги и по связанным темам, [AS, B, Bo, G, L, S7, So] — более продвинутая ли- тература. Остальное — источники замечаний, основное содержание
2
Часто происходит обратное: формулировки красивых результатов и важ- ных проблем, ради которых была придумана теория, приводятся только после продолжительного изучения этой теории (или не приводятся совсем). Это спо- собствует появлению представления о математике как науке, изучающей немо- тивированные понятия и теории. Такое представление принижает ценность ма- тематики.

10
Элементы дискретной математики в задачах
Основные обозначения
• [x] — (нижняя) целая часть числа x.
• d | n — число n делится на число d (для целых d и n).
• R
n
— множество {1, 2, . . . , n}.
• N — множество {1, 2, . . . , n, . . .} целых положительных чисел.
• R, Q, Z — множества всех действительных, рациональных и целых чисел, соответственно.
• Z
2
— множество {0, 1} остатков от деления на 2 с операциями сложения и умножения по модулю 2.
• Z
m
— множество {0, 1, . . . , m − 1} остатков от деления на m с операциями сложения и умножения по модулю m.
•
(
n k
)
— количество k-элементных подмножеств n-элементного множества (другое обозначение: C
k n
).
•
(
X
k
)
— множество всех k-элементных подмножеств множе- ства X.
• |X| — число элементов во множестве X.
• A \ B = {x | x ∈ A и x /
∈ B} — разность множеств A и B (не путайте этот знак с /).
• A⊔B — дизъюнктное объединение множеств A и B. Оно равно
A
∪ B, если A ∩ B = ∅.
• A ⊂ B — «множество A содержится в множестве B». (В неко- торых других книгах это обозначают A ⊆ B, а A ⊂ B означает
«множество A содержится в множестве B и не равно B».)
• фраза ‘обозначим x = a’ сокращается до x := a.

1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
11 1 Элементы комбинаторики
1.1 Подсчёт и комбинаторные тождества
1.1.1.
(a)
(
n k
)
=
(
n n
− k
)
. (b) Найдите сумму
(
n
0
)
+ . . . +
(
n n
)
1.1.2.
(a) Правило Паскаля.
(
n + 1
k + 1
)
=
(
n k + 1
)
+
(
n k
)
, если 0 6
k
6 n − 1. (Подсказка приведена после задачи 1.1.4.a.)
(b)
{
n + 1
k + 1
}
= (k + 1)
{
n k + 1
}
+
{
n k
}
. Здесь
{
n k
}
— количество разбиений n-элементного множества на k частей (т. е. непустых под- множеств); разбиения считаются неупорядоченными, т. е. разбиение множества {1, 2, 3} на части {1, 2} и {3} и разбиение того же мно- жества на части {3} и {1, 2} считаются одинаковыми. Ср. с задачей
1.4.7.e.
Замечание. Числа
{
n k
}
называются числами Стирлинга вто- рого рода; подробнее о них см., например, [GKP, с. 287].
1.1.3.
(a) Во скольких подмножествах множества R
11

не найдётся двух подряд идущих чисел?
(b) То же для трёх подряд идущих чисел.
1.1.4.
(a)
(
n k
)
=
n!
k!(n
− k)!
=
n(n
− 1) . . . (n − k + 1)
k!
(b) Бином Ньютона. (a + b)
n
=
∑
n j=0
(
n j
)
a j
b n
−j
Как решать задачи этого раздела? Мы предлагаем три метода,
которые продемонстрируем на примере трех доказательств правила
Паскаля 1.1.2.a.
(Большинство задач этого раздела решаются несколькими ме- тодами из трех предложенных Но, конечно, не каждый метод при- меним к каждой задаче. Обычно в указаниях для краткости при- водится только один способ решения.)

1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
13 1.1.5.
Найдите суммы:
(a)
(
n
0
)
−
(
n
1
)
+ . . . + (
−1)
n
(
n n
)
;
(b)
(
n
0
)
+
1 2
(
n
1
)
+
1 3
(
n
2
)
+ . . . +
1
n + 1
(
n n
)
;
(c)
(
n
1
)
+ 2
(
n
2
)
+ 3
(
n
3
)
+ . . . + n
(
n n
)
;
(d)
(
n k
)
+
(
n + 1
k + 1
)
+ . . . +
(
n + m k + m
)
;
(e)
(
n
0
)
2
+ . . . +
(
n n
)
2
;
(f)
(
n
0
)(
m k
)
+
(
n
1
)(
m k
− 1
)
+ . . . +
(
n k
)(
m
0
)
;
(g)
(
2n
0
)
−
(
2n
− 1 1
)
+
(
2n
− 2 2
)
− . . . + (−1)
n
(
n n
)
;
(h)
(
2n n
)
+ 2
(
2n
− 1
n
)
+ 4
(
2n
− 2
n
)
+ . . . + 2
n
(
n n
)
1.1.6.
Найдите «явную» формулу для
(a)
∑
k
>0
(
n
2k
)
;
(b)
∑
k
>0
(
n
4k
)
;
(c)
∑
k
>0
(
n
3k
)
В ответе используйте только целочисленные функции целочис- ленного аргумента.
1.1.7.
(a) По кругу стоят числа 1, 2, . . . , n. Найдите число способов выбрать k из них, чтобы никакие два выбранных не стояли рядом.
(Формально — число k-элементных подмножеств, в которых ника- кие два элемента не соседние.)
(b) Найдите число способов рассадить n пар враждующих ры- царей за круглый стол с нумерованными местами, чтобы никакие два враждующих рыцаря не сидели рядом.
1.2 Формула включений и исключений
Этот раздел посвящен доказательству и использованию фор- мулы включения-исключения. Она позволяет отвечать на вопрос
’Сколько существует объектов с данными свойствами?’ во многих непростых случаях. Потребуются базовые навыки решения задач по

14
Элементы дискретной математики в задачах комбинаторике. В частности, уметь приводить строгие доказатель- ства с использованием взаимно-однозначных соответствий, правил суммы и произведения. Например, полезно прорешать предыдущий пункт.
В этом пункте использован материал Д.А. Пермякова.
Обозначим через φ(n) функцию Эйлера, т. е. количество чисел от 1 до n, взаимно простых с числом n.
1.2.1.
(a) Найдите количество чисел, не превосходящих 1001 и не делящихся ни на одно из чисел 7, 11, 13.
(b) Найдите φ(1), φ(p), φ(p
2
)
, φ(p
α
)
, где p — простое число, α > 2.
(c) φ(n) = n(1−
1
p
1
) . . . (1
−
1
p s
)
, где n = p
α
1 1
·. . .·p
α
s s
— каноническое разложение числа n.
1.2.2.
(a) На полу комнаты площадью 24 м
2
расположены три ковра (произвольной формы) площади 12 м
2
каждый. Тогда пло- щадь пересечения некоторых двух ковров не меньше 4 м
2
(b) На кафтане расположено пять заплат (произвольной формы).
Площадь каждой из них больше трех пятых площади кафтана. То- гда площадь общей части некоторых двух заплат больше одной пя- той площади кафтана.
(c) То же, что в (b), если площадь каждой заплаты больше поло- вины площади кафтана.
1.2.3.
Сколькими способами можно переставить числа от 1 до n,
чтобы

(a) и 1, и 2 не оказалось на своем месте?
(b) ровно одно из чисел 1, 2 и 3 оказалось на своем месте?

(c) каждое из чисел 1, 2 и 3 оказалось не на своем месте?
(d) каждое из чисел 1, 2, 3 и 4 оказалось не на своем месте?
1.2.4.
На полке стоят 10 различных книг.

(a) Сколькими способами их можно переставить так, чтобы ни одна книга не осталась на своем месте?
(b) Количество таких перестановок книг, при которых на месте остаётся ровно 4 книги, больше 50000.
В этом разделе предлагаются задачи следующего типа: дано конечное множество U и набор свойств (подмножеств) A
k
⊂ U,