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

1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
19
Замечание. В данном случае подпоследовательность — это то,
что получается из последовательности вычеркиванием некоторых её членов.
1.3.8.
Имеется 10 яблок, каждое из которых весит не более 100 г, и две одинаковые тарелки. Докажите, что можно положить в тарелки
(a) несколько яблок так, чтобы веса в тарелках отличались мень- ше, чем на 1 г.
(b) по одинаковому количеству яблок так, чтобы веса в тарелках отличались меньше, чем на 2 г
При этом на тарелках должно лежать хотя бы одно яблоко, но не обязательно должны лежать все яблоки (и в пункте (a) не обяза- тельно, чтобы на каждой тарелке лежало хотя бы одно яблоко).
1.3.9.
Для любых n векторов v
1
, . . . , v n
длины 1 на плоскости су- ществует такой набор ε
1
, . . . , ε
n
=
±1, что
(a) |
∑
n k=1
ε
k v
k
| 6
√
n
, (b) |
∑
n k=1
ε
k v
k
| >
√
n.
1.4 Комбинаторика булева куба
1.4.1.
Расставьте на шахматной доске нескольких коней, чтобы каждый бил четырёх других.
1.4.2.
33 буквы русского алфавита кодируются последовательно- стями из нулей и единиц.

20
Элементы дискретной математики в задачах
(b) Best in their own ways. В математической олимпиаде участво- вало k школьников. Выяснилось, что для любых двух школьников
A
и B нашлась задача, которую решил A и не решил B, и задача,
которую решил B, но не решил A. Какое наименьшее возможное количество задач могло быть при этом условии? Иными словами,
найдите наименьшее возможное n, для которого найдётся такое се- мейство из k подмножеств n-элементного множества, что ни одно из подмножеств семейства не содержится (собственно) в другом.
1.4.4.
Имеется табло с n горящими лампочками. Каждый пере- ключатель может быть подсоединён к некоторым лампочкам. При нажатии на кнопку переключателя соединённые с ним лампочки меняют свое состояние: горящие тухнут, а не горящие загораются.
Какое наименьшее число переключателей необходимо, чтобы мож- но было зажечь любой набор лампочек (не входящие в этот набор лампочки гореть не должны)?
1.4.5.
В первый день своего правления король организует партии среди n своих подданных. На второй день советник приносит ко- ролю список фамилий некоторых подданных (в первый день этот список неизвестен). На третий день король может выбрать несколь- ко партий и отправить в тюрьму всех подданных, участвующих в каждой из них. Какое наименьшее число партий необходимо ор- ганизовать в первый день, чтобы в третий день заведомо можно было отправить в тюрьму всех подданных из принесенного списка

(и только их)?
Замечание. Следующая важная конструкция полезна (хотя и не обязательна) для решения вышеприведенных (и многих других)
задач. Нарисуем точки, соответствующие всем подмножествам мно- жества R
n
. При этом на k-й этаж поместим точки, соответствую- щие k-элементным множествам. Соединим стрелкой те из них, кото- рые получаются друг из друга добавлением одного элемента. Тогда соединяемые стрелкой точки лежат на соседних этажах. Получен- ный граф называется n-мерным кубом. Его вершины соответствуют векторам из Z
n
2
Определение множества Z
n
2
приведено в начале §7.1. Подмноже- ство L ⊂ Z
n
2
называется линейным подпространством, если x + y ∈

1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
21
L
для любых x, y ∈ L (не обязательно различных). Иными сло- вами, линейное подпространство — такое семейство подмножеств n
-элементного множества, которое вместе с любыми двумя подмно- жествами содержит их симметрическую разность (т. е., сумму по модулю 2).
1.4.6.
(a) Любое линейное подпространство содержит нулевой на- бор (0, . . . , 0).
(b) Число элементов в любом линейном подпространстве явля- ется степенью двойки.
Обозначим через n
k количество линейных подпространств в
Z
n
2
, состоящих из 2
k элементов (такие линейные подпространства в
Z
n
2
называют k-мерными, ср. §7.1).
1.4.7.
(a) Найдите
2
k для k = 0, 1, 2.
(b) Найдите
3
k для k = 0, 1, 2, 3.
(c)
n
0
=
n n
= 1,
n
1
=
n n
− 1
= 2
n
− 1.
(d)
n k
=
n n
− k
(e)
n + 1
k + 1
=
n k + 1
+ 2
n
−k n
k
(f) Найдите n
2
(g) Найдите n
k
Для решения этой задачи нужны некоторые понятия, приведен- ные в начале §7.1.
1.5 Обращение Мёбиуса
Под значком
∑
d
|n подразумевается сумма по всем натуральным делителям числа n.

24
Элементы дискретной математики в задачах
(a) Найдите
∑
d
|n
M
r
(d)
(b) Выразите T
r
(n)
через все M
r
(d)
, где d | n.
(c) T
r
(n) =
∑
l
|n
1
l
∑
d
|l
µ(d)r l
d
(d) T
r
(n) =
1
n
∑
d
|n
φ(d)r n
d
(Более простой способ доказательства этой формулы приведен в [ZSS, §23].)
1.5.6.
Найдите количество различных раскрасок карусели из n ва- гончиков в r цветов, в которых
(a) цвет s встречается n s
раз для каждого s = 1, . . . , r. (Здесь в качестве ответа принимается формула с суммированием по делите- лям, аналогичная 1.5.5.c.)
(b) присутствует ровно 4 цвета из r = 5 данных.
1.6 Подсчёт двумя способами
Мы приводим простейший вариант вероятностного метода в ком- бинаторике. Ср. §6.2, §6.3. Этот метод также применяется при ре- шении задач 2.4.3, 2.6.5, 2.6.7, 2.7.2, 3.1.11.b, 4.1.5, 4.3.4.
Комбинаторные решения нижеприведенных задач можно изло- жить на вероятностном языке. Решения без явного построения ве- роятностного пространства могут привести к бессмыслице и ошиб- ке. (Подумайте, например, с какой вероятностью случайный тре- угольник будет остроугольным.) Поэтому строгие решения на ве- роятностном языке должны начинаться с явного построения веро- ятностного пространства.
1.6.1.
(a) Даны 21 девятиэлементных подмножеств 30-элементного множества. Тогда какой-то элемент 30-элементного множества со- держится по крайней мере в семи данных подмножествах.
(b) Комиссия собиралась 40 раз. На каждом заседании было ров- но 10 человек, любые два не были вместе больше 1 раза. Тогда в комиссии хотя бы 60 человек.
(c) В компании у любых двух знакомых друг с другом человек есть ровно 5 общих знакомых (кроме них самих). Тогда количество пар знакомых между собой людей в компании делится на 3.

1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
25
(d) Обозначим через P
n
(k)
число перестановок множества нату- ральных чисел от 1 до n, оставляющих ровно k чисел на своем месте. Тогда n
∑
k=0
k
· P
n
(k) = n!
1.6.2.
Пусть F — любое семейство k-элементных подмножеств n- элементного множества.
(a) Если k
> l и каждое l-элементное подмножество n-элементного множества содержится в некотором подмножестве из F, то
|F| >
(
n l
) /(
k l
)
(b) Количество (k − 1)-элементных подмножеств n-элементного множества, целиком содержащихся хотя бы в одном из подмножеств семейства F, не меньше k
|F|
n
− k + 1 1.6.3.
На планете Марс 100 государств объединены в блоки, в каж- дом из которых не больше 50 государств. Известно, что любые два государства состоят вместе хотя бы в одном блоке. Найдите мини- мально возможное число блоков. (Ср. с задачей 1.6.2.a.)
1.6.4.
Ровно 19 вершин правильного 97-угольника покрашено в бе- лый цвет, остальные вершины покрашены в чёрный. Тогда число равнобедренных одноцветных треугольников с вершинами в вер- шинах 97-угольника не зависит от способа раскраски. (Треугольник одноцветный, если все его вершины или белые, или чёрные.)
1.6.5.
Даны числа n
> k и множество S из n точек на плоскости.
Если любые три точки из множества S не лежат на одной прямой и для любой точки P ∈ S существуют хотя бы k различных точек из множества S, равноудаленных от P , то k <
1 2
+
√
2n
1.6.6.
В любом множестве из n различных натуральных чисел най- дётся подмножество из более чем n/3 чисел, в котором нет трёх чисел, сумма двух из которых равна третьему.
1.6.7.
По каждому из 100 видов работ в фирме имеется ровно 8
специалистов. Каждому сотруднику нужно дать выходной в суббо- ту или в воскресенье. Докажите, что это можно сделать так, чтобы

50
Элементы дискретной математики в задачах
2 Основы теории графов
2.1 Основные определения
Графом G = (V, E) называется конечное множество V = V (G),
некоторые двухэлементные подмножества (т. е. неупорядоченные пары несовпадающих элементов) которого выделены. Множество выделенных подмножеств обозначается E = E(G). Таким образом,
E
⊂
(
V
2
)
Элементы данного множества V называются вершинами. Выде- ленные пары вершин называются рёбрами. Хотя эти пары неупоря- доченные, в теории графов их традиционно обозначают круглыми скобками. Вершина, принадлежащая ребру, называется его верши- ной. Если вершины a и b соединены ребром, они называются сосед- ними или смежными, а само ребро (a, b) называется проходящим через вершину a и вершину b или инцидентным вершине a и вер- шине b.
Общепринятый термин для понятия графа, данного здесь —
граф без петель и кратных рёбер или простой граф.
Если не оговорено противное, то через n и e обозначаются ко- личества вершин и рёбер рассматриваемого графа, соответственно.
Граф можно представлять себе как набор точек (например, на плоскости), некоторые пары которых соединены ломаными. См.
рис. 2, 3, 4, 7, 8, 10 и 11 ниже. При этом только концы каждой ломаной являются вершинами графа и каждая пара вершин не со- единена более чем одной ломаной. Точки называются вершинами графа, а ломаные — рёбрами. Ломаные могут пересекаться, но точ- ки пересечения «не считаются», т.е. не являются вершинами.
Путем P
n называется граф с вершинами 1, 2, . . . , n и ребрами
(i, i + 1)
, i = 1, 2, . . . , n − 1. Циклом C
n называется граф с верши- нами 1, 2, . . . , n и ребрами (1, n) и (i, i + 1), i = 1, 2, . . . , n − 1. (Не путайте эти графы с путем в графе и циклом в графе, определенны- ми ниже.) Граф с n вершинами, любые две из которых соединены ребром, называется полным и обозначается K
n
. Если вершины гра- фа можно разделить на две части так, что нет рёбер, соединяющих вершины из одной и той же части, то граф называется двудольным,

2. ОСНОВЫ ТЕОРИИ ГРАФОВ
51
а части называются долями. Через K
m,n обозначается двудольный граф с долями из m и из n вершин, в котором имеются все mn рёбер между вершинами разных долей.
2.1.1.
В любом графе есть двудольный подграф, содержащий не менее половины рёбер графа.
Степенью deg v вершины v графа называется число выходящих из нее рёбер. Изолированной вершиной называется вершина, из ко- торой не выходит ни одного ребра.
Грубо говоря, подграф данного графа — это его часть. Формаль- но, граф G называется подграфом графа H, если каждая вершина графа G является вершиной графа H, и каждое ребро графа G
является ребром графа H. При этом две вершины графа G, со- единённые ребром в графе H, не обязательно соединены ребром в графе G.
k
-кликой в графе называется его подграф с k вершинами, яв- ляющийся полным. Независимым множеством или антикликой в графе называется набор его вершин, между которыми нет рёбер.
Путем в графе называется последовательность v
1
e
1
v
2
e
2
. . . e n
−1
v n
,
в которой для любого i ребро e i
соединяет вершины v i
и v i+1
. Число n
− 1 называется длиной пути. (Ребра e
1
, e
2
, . . . , e n
−1
не обязательно попарно различны.)
Циклом в графе называется последовательность v
1
e
1
v
2
e
2
. . . e n
−1
v n
e n
,
в которой для любого i < n ребро e i
соединяет вершины v i
и v i+1
, а ребро e n
соединяет вершины v n
и v
1
. Циклы считаются одинаковы- ми, если они отличаются циклическим сдвигом последовательности.
Число n называется длиной цикла. Несамопересекающимся называ- ется цикл, для которого вершины v
1
, v
2
, . . . , v n
попарно различны и рёбра e
1
, e
2
, . . . , e n
попарно различны. Стандартный термин (менее удобный для начинающего) — простой цикл.
2.1.2.
(a) Любой цикл, не проходящий ни по одному ребру два- жды, содержит несамопересекающийся цикл.
(b) Любой цикл нечётной длины содержит несамопересекающийся цикл обход нечётной длины.

(c) Справедливо ли аналогичное утверждение для циклов чётной длины, не проходящих ни по одному ребру дважды?

52
Элементы дискретной математики в задачах
(d) В графе есть несамопересекающийся цикл, проходящий через рёбра a и b, а также есть несамопересекающийся цикл, проходящий через рёбра b и c. Тогда есть несамопересекающийся цикл, прохо- дящий через рёбра a и c.
Граф называется связным, если любые две его вершины можно соединить путём, и несвязным иначе.
2.1.3.
Если степень каждой из n вершин графа больше n
2
− 1,
то граф связен.
Ясно, что «соединённость некоторым путём» является отноше- нием эквивалентности на множестве вершин графа. Связной ком- понентой графа называется любой класс этой эквивалентности.
Рис. 1: Удаление ребра G − e, стягивание ребра G/e и удаление вершины G − x
Определение операций удаления ребра и удаления вершины яс- но из рис. 1. Операция стягивания ребра (рис. 1) удаляет из графа это ребро и заменяет вершины A и B этого ребра на одну вершину
D
, а все рёбра, выходящие из вершин A и B в некоторые вершины,
заменяет на рёбра, выходящие из вершины D в те же вершины. (Эта операция отличается от стягивания ребра в мультиграфах, см. §2.5,
тем, что каждое получившееся ребра кратности больше 1 заменяет- ся на ребро кратности 1.) Например, если граф — цикл с четырьмя