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

ISBN 978-5-4439-1024-6

9 785443 910246 >

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

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

А. А. Глибичук
А. Б. Дайняк
Д. Г. Ильинский
А. Б. Купавский
А. М. Райгородский
А. Б. Скопенков
А. А. Чернов

Мы приводим подборки задач по комбинаторным разделам математики.

Эти задачи подобраны так, что в процессе их 
решения читатель (точнее, решатель) освоит основы важных теорий – как классических, так и 
современных.

Книга будет полезна участникам кружков для 
младшекурсников и старшеклассников (в частности, ориентированных на олимпиады), а также их руководителям.

Некоторые приводимые красивые задачи и 
важные темы малоизвестны в традиции кружков по математике, но полезны как для математического образования, так и для подготовки к 
олимпиадам. Решение этих задач (т. е. изучение 
соответствующих теорий) будет полезно также 
всем, кто хочет стать математиком, специалистом по computer science или программистом, 
работающим в наукоёмких отраслях информационных технологий.

А. А. Глибичук, А. Б. Дайняк, Д. Г. Ильинский,
А. Б. Купавский, А. М. Райгородский,
А. Б. Скопенков, А. А. Чернов

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

Рекомендовано Учебно-методическим объединением
высших учебных заведений Российской Федерации
по образованию в области прикладных математики и физики
в качестве учебного пособия для студентов вузов, обучающихся
по направлению «Прикладные математика и физика», а также
по другим математическим и естественнонаучным направлениям
и специальностям и смежным направлениям и специальностям
в области техники и технологий

Электронное издание

Москва
Издательство МЦНМО


УДК .
ББК .
Э

Авторский коллектив:

А. А. Глибичук, А. Б. Дайняк, Д. Г.Ильинский, А. Б. Купавский,
А. М. Райгородский, А. Б. Скопенков, А. А. Чернов

Научные редакторы:

А. В. Шаповалов, И. Д. Шкредов

А. А. Глибичук и др.
Элементы дискретной математики в задачах
Электронное издание
М.: МЦНМО, 
 с.
ISBN ----

Мы приводим подборки задач по комбинаторным разделам математики. Эти задачи подобраны так, что в процессе их решения читатель
освоит основы важных теорий –– как классических, так и современных.
Книга будет полезна студентам, руководителям и участникам кружков для старшеклассников (в частности, ориентированных на олимпиады). Некоторые приводимые красивые задачи и важные темы малоизвестны в традиции кружков по математике, но полезны как для математического образования, так и для подготовки к олимпиадам. Решение
этих задач (т. е. изучение соответствующих теорий) будет полезно также всем, кто хочет стать математиком, специалистом по computer science
или программистом, работающим в наукоёмких отраслях информационных технологий.

Подготовлено на основе книги: Элементы дискретной
математики в задачах / А. А. Глибичук и др. –– М.: МЦНМО, . ––
ISBN ----.

Издательство Московского центра
непрерывного математического образования
, Москва, Большой Власьевский пер., ,
тел. () ––.
http://www.mccme.ru

ISBN ----
© Коллектив авторов, .
© МЦНМО, .

Оглавление

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Основные обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . .


§ . Элементы комбинаторики
..
Подсчёт и комбинаторные тождества . . . . . . . . . . . . .

..
Формула включений и исключений . . . . . . . . . . . . . .

..
Принцип Дирихле . . . . . . . . . . . . . . . . . . . . . . . . . .

..
Комбинаторика булева куба . . . . . . . . . . . . . . . . . . .

..
Обращение Мёбиуса . . . . . . . . . . . . . . . . . . . . . . . .

..
Подсчёт двумя способами . . . . . . . . . . . . . . . . . . . . .

..
Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . .

..
Чётность перестановок . . . . . . . . . . . . . . . . . . . . . .

..
Комбинаторика классов эквивалентности . . . . . . . . . .

.. Подсказки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

..
Указания
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


§ . Основы теории графов
..
Основные определения . . . . . . . . . . . . . . . . . . . . . .

..
Перечисление деревьев . . . . . . . . . . . . . . . . . . . . . .

..
Графы с точностью до изоморфизма . . . . . . . . . . . . . .

..
Плоские графы . . . . . . . . . . . . . . . . . . . . . . . . . . . .

..
Эйлеровы пути и циклы . . . . . . . . . . . . . . . . . . . . . .

..
Гамильтоновы пути и циклы . . . . . . . . . . . . . . . . . . .

..
Экстремальные задачи (теорема Турана) . . . . . . . . . . .

..
Теорема Менгера . . . . . . . . . . . . . . . . . . . . . . . . . .

..
Подсказки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Указания
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


§ . Раскраски графов и многочлены
..
Раскраски графов . . . . . . . . . . . . . . . . . . . . . . . . . .

..
Хроматические число и индекс . . . . . . . . . . . . . . . . .

..
Хроматический многочлен и многочлен Татта . . . . . . .

..
Подсказки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

..
Указания
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


§ . Основы теории Рамсея
..
Двухцветные числа Рамсея . . . . . . . . . . . . . . . . . . . .

..
Многоцветные числа Рамсея . . . . . . . . . . . . . . . . . . .

..
Числа Рамсея для гиперграфов . . . . . . . . . . . . . . . . .



Оглавление

..
Результаты рамсеевского типа . . . . . . . . . . . . . . . . . .

..
Числа Рамсея для подграфов . . . . . . . . . . . . . . . . . . .

..
Подсказки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

..
Указания
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


§ . Системы множеств (гиперграфы)
..
Пересечения подмножеств . . . . . . . . . . . . . . . . . . . .

..
Системы общих представителей . . . . . . . . . . . . . . . . 
..
Системы различных представителей
. . . . . . . . . . . . . 
..
Перманент . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
..
Размерность Вапника––Червоненкиса . . . . . . . . . . . . . 
..
Подсолнухи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
..
Подсказки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
..
Указания
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


§ . Аналитические и вероятностные методы
..
Асимптотики . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

..
Независимость и доказательства существования
. . . . .

..
Случайные графы . . . . . . . . . . . . . . . . . . . . . . . . . . 
..
Подсказки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
..
Указания
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

§ . Алгебраические методы
..
Линейно-алгебраический метод в комбинаторике . . . . . 
..
Матрицы Адамара
. . . . . . . . . . . . . . . . . . . . . . . . . 
..
Подсказки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

..
Указания
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

§ . Теоремы об инцидентностях в геометрии
..
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
..
Подсказки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

..
Указания
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

§ . Аддитивная комбинаторика
..
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
..
Подсказки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
..
Указания
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . 

Литература
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

Сведения об авторах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

Введение

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


Введение

об основных направлениях научных исследований в соответствующих
областях. С этой же целью приводятся замечания, которые не используются ни в формулировках, ни в решениях задач. Важные факты выделены словом «теорема» или «следствие».
Используемый материал. Формулировки большинства задач доступны старшеклассникам, интересующимся математикой); мы приводим все необходимые определения, выходящие за рамки школьной
программы и редко изучаемые на кружках. Без определения используются только простейшие понятия и результаты теории чисел [GIM,
§§ , ], [Vi, §§ ––], [ZSS, §  «Делимость и деление с остатком», § 
«Умножение по простому модулю»]. Если в некотором разделе для понимания условий или для решения задач нужны дополнительные сведения, то в начале соответствующего раздела приводятся ссылки.
При этом многие задачи трудны: для их решения нужно предварительно прорешать другие приведённые задачи на данную тему.
Как устроена книга. Эту книгу необязательно читать (точнее, прорешивать) подряд. Параграфы и разделы книги практически независимы друг от друга (кроме разделов в §  и § , которые желательно прорешивать подряд). Если в задаче одного из разделов все-таки используется материал другого раздела, то либо эту задачу можно игнорировать,
либо посмотреть конкретно указанный материал другого раздела. Основные обозначения приведены в конце введения. Основные понятия
и обозначения теории графов введены в п. ..
При этом параграфы расположены примерно в порядке возрастания
сложности материала.
К многим задачам приводятся подсказки, указания и решения. Подсказки и указания расположены в конце каждого параграфа. Однако к
ним стоит обращаться после прорешивания каждой задачи.
Общие замечания к формулировкам задач. Задачи обозначаются жирными цифрами. Если в условии задачи написано «найдите», то
нужно дать ответ без знака суммы и многоточия. Если же условие
задачи является формулировкой утверждения, то в задаче требуется
это утверждение доказать. Как правило, мы приводим формулировку
утверждения перед его доказательством). В таких случаях для дока
)Часть материала (например, п. .) на некоторых кружках и летних школах изучается даже шестиклассниками. Однако приводимые подсказки, указания и решения рассчитаны на читателей с некоторой математической культурой (необходимой для освоения
б´ольшей части книги). Разбирать эти решения с шестиклассниками нужно по-другому,
см., например, [GIF].
)Часто происходит обратное: формулировки красивых результатов и важных проблем, ради которых была придумана теория, приводятся только после продолжительного

Введение


зательства утверждения могут потребоваться следующие задачи. Это
всегда явно оговаривается в подсказках, а иногда и прямо в тексте. (На
занятии задача-подсказка выдается только тогда, когда школьник или
студент немного подумал над самой задачей.)
Большинство задач не оригинальны, но установить первоисточник
не представляется возможным. Многие задачи взяты из [IKR, ZSS, L]
и из неопубликованных материалов кафедры дискретной математики
ФИВТ МФТИ, в котором работают авторы.
О литературе. В списке литературы мы приводим только те стандартные учебники по комбинаторике и теории графов, которые по тем
или иным причинам мы чаще используем в преподавании. Также мы
приводим ссылки на всю известную нам более серьёзную учебно-научную литературу. Но этот список также не претендует на полноту, поскольку мы можем не знать о некоторых публикациях.
В списке литературы [Ga, GKP, Gri, Hal, Har, KS, Mk, R, R, R, R,
S, S, VS, w] и [AM, GIM, I, J, JLR, KR, KZP, Mn, P, PS, R, R, S, S, S,
S, Vi, ZSS] –– базовые учебники и статьи по темам этой книги или по
близким к ней темам, [AS, BM, B, BF, Gra, L, NPP, S, So, Ve, w––w] ––
более продвинутая литература. Остальное –– источники замечаний, основное содержание которых может быть не связано с этой книгой, и
опубликованные ранние версии отдельных частей книги.
Благодарности. Мы благодарим за полезные замечания редакторов книги А. В. Шаповалова и И. Д. Шкредова, а также А. А. Полянского, М. Б. Скопенкова, И. Н. Шнурникова и членов редколлегии сборника «Математическое просвещение». Мы благодарим студентов за каверзные вопросы и указания на неточности. Мы благодарим А. Ю. Веснина за разрешение использовать рис. .

Грантовая поддержка.
А. А. Глибичук поддержан грантами Мол-а-вед № -- и грантом РФФИ № -- А.
А. Б. Купавский поддержан грантом РФФИ -- и грантом
Президента РФ МД-...
А. М. Райгородский поддержан грантом РФФИ --, грантом Президента РФ МД-.. и грантом ведущих научных школ
НШ-...
А. Б. Скопенков частично поддержан грантом фонда Саймонса.

изучения этой теории (или не приводятся совсем). Это способствует появлению представления о математике как науке, изучающей немотивированные понятия и теории.
Такое представление принижает ценность математики.

Основные обозначения

• [x] –– (нижняя) целая часть числа x

• d | n –– число n делится на число d (для целых d и n)

• НОД(m, n) –– наибольший общий делитель чисел m и n

• n –– множество {1,2,…, n}

• –– множество {1,2,…, n,…} целых положительных чисел

• , , –– множества всех действительных, рациональных и целых
чисел соответственно

• 2 –– множество {0,1} остатков от деления на 2 с операциями сложения и умножения по модулю 2

• 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»

§ . Элементы комбинаторики

.. Подсчёт и комбинаторные тождества

... ()
n
k

=
n
n − k

. () Найдите сумму
n
0

+ … +
n
n

.

... () Правило Паскаля.
n + 1
k + 1

=
n
k + 1

+
n
k

, если 0 ⩽ k ⩽
⩽ n − 1. (Подсказка приведена после задачи .. ().)

()
n + 1
k + 1

= (k + 1)
n
k + 1

+
n
k

. Здесь
n
k

–– количество разби
ений n-элементного множества на k частей (т. е. непустых подмножеств); разбиения считаются неупорядоченными, т. е. разбиение множества {1,2,3} на части {1,2} и {3} и разбиение того же множества на
части {3} и {1,2} считаются одинаковыми. Ср. с задачей .. ().

З. Числа
n
k

называются числами Стирлинга второго ро
да; подробнее о них см., например, [GKP, с. ].

... () Во скольких подмножествах множества 11 не найдётся
двух подряд идущих чисел?
() То же для трёх подряд идущих чисел.

... ()
n
k

=
n!

k!(n − k)! = n(n − 1)…(n − k + 1)

k!
.

() Бином Ньютона. (a + b)n =

nj=0

n
j

a jbn−j.

Как решать задачи этого раздела? Мы предлагаем три метода, которые продемонстрируем на примере трёх доказательств правила Паскаля .. (). (Большинство задач этого раздела решаются несколькими методами из трёх предложенных. Но, конечно, не каждый метод
применим к каждой задаче. Обычно в указаниях для краткости приводится только один способ решения.)
Первое доказательство: комбинаторные рассуждения. Неформально говоря, идея в следующем: чтобы выбрать k + 1 футболистов, нужно
либо выбрать k + 1 полевых, либо вратаря и k полевых. Приведём строгое изложение этой идеи.
Количество (k + 1)-элементных подмножеств множества n+1,

• содержащих число n + 1, равно
n
k

, так как такие подмножества
при выкидывании числа n + 1 становятся подмножествами в n;


§ . Элементы комбинаторики

• не содержащих число n + 1, равно
n
k + 1

, так как такие подмножества являются также подмножествами в n.
Другая запись этого решения. Определим отображение

f :
n+1
k + 1

→
n
k + 1

⊔
n
k

формулой
f (A) := A\ {n + 1}.

Остаётся доказать, что это –– биекция, т. е. взаимно однозначное соответствие (например, определив явной формулой обратное отображение).
Второе доказательство: использование явной формулы .. ().
Имеем
n
k + 1

+
n
k

=
n!

(n − k − 1)!(k + 1)! +
n!

(n − k)! k! =

=
n!

(n − k − 1)! k!

1

k + 1 +
1

n − k

=

=
n!

(n − k − 1)! k! ·
n + 1

(k + 1)(n − k) =
(n + 1)!

(n − k)!(k + 1)! =
n + 1
k + 1

.

Третье доказательство: использование бинома Ньютона .. ().

Число
n + 1
k + 1

является коэффициентом при xk+1 в многочлене

(1 + x)n+1 = (1 + x)n(1 + x) = x(1 + x)n + (1 + x)n.

Поэтому число
n + 1
k + 1

равно сумме коэффициентов при степенях xk и

xk+1 у многочлена (1 + x)n. Отсюда следует требуемое равенство.

... Найдите суммы:

()
n
0

−
n
1

+ … + (−1)nn
n

;

()
n
0

+ 1

2

n
1

+ 1

3

n
2

+ … +
1

n + 1

n
n

;

()
n
1

+ 2
n
2

+ 3
n
3

+ … + n
n
n

;

()
n
k

+
n + 1
k + 1

+ … +
n + m
k + m

;

()
n
0

2 + … +
n
n

2;

()
n
0

m
k

+
n
1

m
k − 1

+ … +
n
k

m
0

;

()
2n
0

−
2n − 1
1

+
2n − 2
2

− … + (−1)nn
n

;

()
2n
n

+ 2
2n − 1
n

+ 4
2n − 2
n

+ … + 2nn
n

.

.. Формула включений и исключений


... Найдите явную формулу для

()
k⩾0

n
2k

; ()
k⩾0

n
4k

; ()
k⩾0

n
3k

.

В ответе используйте только целочисленные функции целочисленного аргумента.

.. Формула включений и исключений

Обозначим через ϕ(n) функцию Эйлера, т. е. количество чисел от 1
до n, взаимно простых с числом n.

... () Найдите количество чисел, не превосходящих 1001 и не делящихся ни на одно из чисел 7, 11, 13.
() Найдите ϕ(1), ϕ(p), ϕ(p2), ϕ(pα), где p –– простое число, α > 2.

() ϕ(n) = n
1 − 1

p1

…
1 − 1

ps

, где n = pα1
1 · … · pαs
s –– каноническое
разложение числа n.
... () На полу комнаты площадью 24м2 расположены три ковра
(произвольной формы) площади 12м2 каждый. Тогда площадь пересечения некоторых двух ковров не меньше 4м2.
() На кафтане расположено пять заплат (произвольной формы).
Площадь каждой из них больше половины площади кафтана. Тогда площадь общей части некоторых двух заплат больше одной пятой площади
кафтана.
... Формула включений и исключений. Рассмотрим подмножества A1,…, An конечного множества U. Положим по определению
j∈∅
Aj
:= U.

() Пусть число α|S| :=
j∈S
Aj
зависит только от размера |S| набора

S ⊂ n индексов, а не от самого набора. Тогда

|A1 ∪ … ∪ An| =

n
k=1
(−1)k+1n
k

αk,

|U \ (A1 ∪ … ∪ An)| =

n
k=0
(−1)kn
k

αk.

() Обозначим Mk :=
S∈(n
k )

j∈S
Aj
. В частности, M0 := |U|. Тогда

|A1 ∪ … ∪ An| = M1 − M2 + M3 − … + (−1)n+1Mn,
|U \ (A1 ∪ … ∪ An)| = M0 − M1 + M2 + … + (−1)nMn.