Основы комбинаторики и теории чисел

А.А. ГЛИБИЧУК, Д.Г. ИЛЬИНСКИЙ, 
Д.В. МУСАТОВ, А.М. РАЙГОРОДСКИЙ, А.А. ЧЕРНОВ

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

Второе издание

ОСНОВЫ КОМБИНАТОРИКИ  
И ТЕОРИИ ЧИСЕЛ

СБОРНИК ЗАДАЧ

À.À. Ãëèáè÷óê, Ä.Ã. Èëüèíñêèé, Ä.Â. Ìóñàòîâ, À.Ì.
Ðàéãîðîäñêèé, À.À. ×åðíîâ
Îñíîâû êîìáèíàòîðèêè è òåîðèè ÷èñåë. Ñáîðíèê çàäà÷:
Ó÷åáíîå ïîñîáèå / À.À. Ãëèáè÷óê, Ä.Ã. Èëüèíñêèé, Ä.Â.
Ìóñàòîâ, À.Ì. Ðàéãîðîäñêèé, À.À. ×åðíîâ –  2-å èçä. –
Äîëãîïðóäíûé: Èçäàòåëüñêèé Äîì «Èíòåëëåêò», 2019. –
104 ñ.

ISBN 978-5-91559-259-8

Çàäà÷íèê ñîçäàí íà îñíîâå êóðñà «Îñíîâû êîìáèíàòîðèêè è òåîðèè ÷èñåë», ÷èòàåìîãî íà ôàêóëüòåòå èííîâàöèé è
âûñîêèõ òåõíîëîãèé ÌÔÒÈ.
Êóðñ ÷èòàåòñÿ â ïåðâîì æå ñåìåñòðå è ñëóæèò âåñüìà îñíîâàòåëüíûì ââåäåíèåì êàê â òåîðèþ ìíîæåñòâ, òàê è â êîìáèíàòîðèêó, è â òåîðèþ ÷èñåë. Òàêèì îáðàçîì, îí ñîçäàåò ïî÷âó
è äëÿ ìàòåìàòè÷åñêîãî àíàëèçà, è äëÿ ìàòåìàòè÷åñêîé ëîãèêè, è äëÿ òåîðèè âåðîÿòíîñòåé, è äëÿ òåõ ñïåöèôè÷åñêèõ
àëãîðèòìè÷åñêèõ êóðñîâ, â êîòîðûõ èñïîëüçóþòñÿ òåîðåòèêî÷èñëîâûå ïîäõîäû.
Çàäà÷è, ñîáðàííûå â ýòîé êíèãå, ðàçðàáàòûâàëèñü äëÿ âåäåíèÿ ñåìèíàðîâ ïî êóðñó. Ñðåäè çàäà÷ íàðÿäó ñî ñòàíäàðòíûìè åñòü è âåñüìà îðèãèíàëüíûå.  íàñûùåííîì êóðñå
çàòðàãèâàþòñÿ òåìû, êîòîðûå äîâîëüíî ðåäêî îáñóæäàþòñÿ
â ëèòåðàòóðå, íàïðèìåð, îáîáù¸ííàÿ ôîðìóëà îáðàùåíèÿ
̸áèóñà.
Âñå çàäà÷è ñíàáæåíû îòâåòàìè, à áîëüøèíñòâî èç íèõ —
ðåøåíèÿìè. Ó÷åáíîå ïîñîáèå àäðåñîâàíî âñåì, êòî èíòåðåñóåòñÿ îñíîâàìè ñîâðåìåííîé êîìáèíàòîðèêè è òåîðèè ÷èñåë  — øêîëüíèêàì, ñòóäåíòàì, ïðåïîäàâàòåëÿì ìàòåìàòè÷åñêèõ
êëàññîâ è ÂÓÇîâ.
Ïåðâîå èçäàíèå çàäà÷íèêà øèðîêî èñïîëüçóåòñÿ â âåäóùèõ
ðîññèéñêèõ óíèâåðñèòåòàõ.

© 2014, Êîëëåêòèâ àâòîðîâ
© 2019, ÎÎÎ Èçäàòåëüñêèé Äîì
«Èíòåëëåêò», îðèãèíàë-ìàêåò,
îôîðìëåíèå

ISBN 978-5-91559-259-8

ОГЛАВЛЕНИЕ

Вступление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

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

Глава 1. Операции над множествами . . . . . . . . . . . . . . . . . .
7

Глава 2. Отображения и соответствия . . . . . . . . . . . . . . . . .
10

Глава 3. Мощности множеств . . . . . . . . . . . . . . . . . . . . . . .
13

Глава 4. Отношения на множествах . . . . . . . . . . . . . . . . . .
16

Глава 5. Простейшая комбинаторика . . . . . . . . . . . . . . . . .
20

5.1. Принцип Дирихле . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
5.2. Размещения, перестановки, сочетания . . . . . . . . . . . . . .
21
5.3. Комбинаторные тождества . . . . . . . . . . . . . . . . . . . . . .
23
5.4. Формула включений и исключений . . . . . . . . . . . . . . . .
24
5.5. Полиномиальная формула . . . . . . . . . . . . . . . . . . . . . .
25

Глава 6. Формула обращения Мёбиуса . . . . . . . . . . . . . . . .
26

Глава 7. Разбиения, степенные ряды, производящие
функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30

7.1. Разбиения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
7.2. Степенные ряды . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
7.3. Производящие функции . . . . . . . . . . . . . . . . . . . . . . . .
34
7.4. Линейные рекуррентные соотношения . . . . . . . . . . . . . .
35

Оглавление

Глава 8. Основная теорема арифметики, системы вычетов
38

8.1. Основы теории делимости . . . . . . . . . . . . . . . . . . . . . .
38
8.2. Алгоритм Евклида. Основная теорема арифметики . . . . . .
38
8.3. Система вычетов. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40

Глава 9. Линейные и квадратичные сравнения . . . . . . . . .
42

Глава 10. Первообразные корни и индексы . . . . . . . . . . . . .
45

10.1. Первообразные корни. . . . . . . . . . . . . . . . . . . . . . . . .
45
10.2. Индексы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46

Глава 11. Цепные дроби . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47

Ответы, указания, решения . . . . . . . . . . . . . . . . . . . . . . . . . .
50

Глава 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
Глава 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
Глава 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
Глава 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
Глава 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
Глава 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
Глава 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
Глава 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
Глава 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
Глава 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
Глава 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95

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

Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
103

ВСТУПЛЕНИЕ

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

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ

N = {1, 2, 3, . . . } — множество натуральных чисел1);

Z — множество целых чисел;

Q — множество рациональных чисел;

R — множество действительных чисел;

x := y — означает «x по определению равен y» ил «x по определению
обозначается через y».

1) Вообще говоря, правильно начинать натуральные числа с 0. Однако мы
используем здесь «школьное» обозначение для N, чтобы не писать лишний
раз вместо N «целые положительные числа».

Г Л А В А
1

ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

Множеством называется произвольный набор каких-либо
объектов. Пустым множеством ∅ называется множество, не содержащее ни одного элемента.

1.1. Сколько элементов во множествах ∅; {∅}; {∅, {∅}}?

Если объект x принадлежит множеству A, пишут x ∈ A. Если любой
элемент A является элементом множества B, то A называется подмножеством множества B, обозначение: A ⊂ B. Два множества совпадают
(обозначение: A = B), если они состоят из одних и тех же элементов.

1.2. Покажите, что для произвольных множеств A, B и C выполнено:
а) A ⊂ A;
б) если A ⊂ B и B ⊂ A, то A = B;
в) если A ⊂ B и B ⊂ C, то A ⊂ C;
г) ∅ ⊂ A.

1.3. Может ли быть так, что одновременно A ∈ B и A ⊂ B?

1.4. Про каждое из следующих утверждений докажите, что оно
всегда верно, никогда не верно или может быть как верным, так и
неверным:
а) если a ∈ B и B ∈ C, то a ∈ C;
б) если a ∈ B и B ⊂ C, то a ∈ C;
в) если a ⊂ B и B ∈ C, то a ∈ C.

Объединением множеств A и B называется множество

A ∪ B = {x | x ∈ A или x ∈ B}.

Пересечением множеств A и B называется множество

A ∩ B = {x | x ∈ A и x ∈ B}.

Глава 1. Операции над множествами

Разностью множеств A и B называется множество

A \ B = {x | x ∈ A и x ̸∈ B}.

Симметрической разностью множеств A и B называется множество

A△B = {x | x ∈ A и x ̸∈ B, или x ∈ B и x ̸∈ A}.

Если задано некоторое множество U (универсум), которому заведомо принадлежат все рассматриваемые элементы, то дополнением множества A называется множество A = U \ A.
Объединение множеств A и B называется дизъюнктным объединением, если A и B не пересекаются. Обозначение: A ⊔ B.

1.5. Докажите, что:
а) A ∪ B = B ∪ A;
б) A ∩ B = B ∩ A;
в) A△B = B△A;
г) (A ∪ B) = A ∩ B;
д) (A ∩ B) = A ∪ B;
е) A△B = (A ∪ B) \ (A ∩ B);
ж) A \ (A \ B) = A ∩ B;
з) A ∪ B = A△B△(A ∩ B);
и) (A ∪ B) ∪ C = A ∪ (B ∪ C);
к) (A ∩ B) ∩ C = A ∩ (B ∩ C);
л) (A△B)△C = A△(B△C);
м) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C);
н) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C);
о) (A ∪ B) \ C = (A \ C) ∪ (B \ C);
п) A ∩ (B△C) = (A ∩ B)△(A ∩ C).

1.6. Решите уравнения:

а)

B ∩ X = A;
B ∪ X = C,
где A ⊂ B ⊂ C;

б)

A \ X = B;
X \ A = C,
где B ⊂ A и A ∩ C = ∅.

Кортежем длины 0 называется пустое множество.
Если T = (a1, . . . , an) — кортеж длины n, то

(a, a1, . . . , an) = {a, {a, T}}

есть кортеж длины n + 1.

Глава 1. Операции над множествами
9

Кортеж длины 2 называется упорядоченной парой.
Декартовым произведением множеств A и B называется множество
упорядоченных пар A × B = {(a, b) | a ∈ A, b ∈ B}.
Декартовой степенью An множества A называется множество кортежей длины n элементов A.

1.7. Пусть множество A состоит из k элементов, а множество B —
из m элементов. Сколько элементов во множествах A × B и An?

1.8. Пусть [a, b] ⊂ R — отрезок, S1 — окружность, а D2 — круг. Что
такое [a, b] × [c, d], [a, b] × S1, [a, b] × D2, S1 × S1, S1 × D2?

Если n1 ⩽ n2 ⩽ . . . ⩽ nk, а T1 = (a1, . . . , an1), T2 = (an1+1, . . . , an2), . . .
. . . , Tk = (ank−1+1, . . . , ank) — кортежи, то естественным образом отождествим кортежи (T1, . . . , Tk) и (a1, . . . , ank).

1.9. Докажите, что при таком отождествлении верны следующие
равенства:
а) A × (B × C) = (A × B) × C;
б) An = A × A × . . . × A (n раз);
в) An × Ak = An+k;
г) (An)k = Ank.

1.10. Докажите, что:
а) A × (B ∪ C) = (A × B) ∪ (A × C);
б) A × (B ∩ C) = (A × B) ∩ (A × C);
в) (A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D).

1.11. При каких условиях выполнено равенство

(A ∪ B) × (C ∪ D) = (A × C) ∪ (B × D)?

Г Л А В А
2

ОТОБРАЖЕНИЯ И СООТВЕТСТВИЯ

Соответствием двух множеств A и B называется произвольное множество F ⊂ A × B. Пишут F: A → B, а вместо (a, b) ∈ F
пишут b ∈ F(a). Формально, F(a) = {b ∈ B | (a, b) ∈ F}.
Отображением называется однозначное соответствие, т. е. такое,
при котором для любого a ∈ A есть единственное такое b ∈ B, что
(a, b) ∈ F. В этом случае пишут b = F(a).
Непустозначным соответствием называется такое соответствие,
при котором F(a) ̸= ∅ при всех a ∈ A.
Инъективным соответствием называется такое, при котором если
a1 ̸= a2, то F(a1) и F(a2) не пересекаются. Инъективное отображение
называется инъекцией.
Соответствие называется сюръективным, если для любого b ∈ B
есть такое a ∈ A, что b ∈ F(a).
Сюръективное отображение называется сюръекцией.
Отображение, являющееся одновременно инъекцией и сюръекцией,
называется биекцией или взаимно однозначным соответствием.
Обратным соответствием называется соответствие F−1 ⊂ B × A,
определяемое так: a ∈ F−1(b) ⇔ b ∈ F(a).

2.1. Сформулируйте определяющие свойства соответствий, обратных к инъективным и к сюръективным.

2.2. Докажите, что соответствие является биекцией тогда и только
тогда, когда и оно само, и обратное к нему являются отображениями.

2.3. Соответствие является одновременно инъективным и сюръективным. Обязательно ли оно является биекцией?

Образом F(S) множества S ⊂ A при соответствии F: A → B называется множество s∈S
F(s).

Глава 2. Отображения и соответствия
11

Прообразом F−1(T) множества T ⊂ B при соответствии F: A → B
называется множество {s ∈ A | F(s) ∩ T ̸= ∅}.

2.4. При каких условиях на соответствие F следующие условия выполняются для всех S, Q ⊂ A и всех T, U ⊂ B:
а) F(F−1(T)) ⊂ T;
б) F−1(F(S)) ⊂ S;
в) F(S ∪ Q) ⊂ F(S) ∪ F(Q);
г) F(S ∩ Q) ⊂ F(S) ∩ F(Q);
д) F(S \ Q) ⊂ F(S) \ F(Q);
е) F(S△Q) ⊂ F(S)△F(Q);
ж) F−1(T ∪ U) ⊂ F−1(T) ∪ F−1(U);
з) F−1(T ∩ U) ⊂ F−1(T) ∩ F−1(U);
и) F−1(T \ U) ⊂ F−1(T) \ F−1(U);
к) F−1(T△U) ⊂ F−1(T)△F−1(U);
л) пункты а)–к) для ⊃ вместо ⊂?

Областью определения соответствия F: A → B называется множество Dom F = F−1(B).
Областью значений соответствия F: A → B называется множество
Ran F = F(A).

2.5. Чему равны множества F(Dom F) и F−1(Ran F)?

Композицией соответствий F: A → B и G: B → C называется соответствие H = G ◦ F: A → C, определяемое соотношением

z ∈ H(x) ⇔ найдется такой y ∈ B, что y ∈ F(x) и z ∈ G(y).

Для отображений можно записать проще: (G ◦ F)(a) = G(F(a)). Именно этой формулой объясняется порядок функций в записи: в композиции G ◦ F сначала применяется F, а потом G.
Тождественным отображением на множестве A называется отображение idA : A → A, определяемое равенством idA(x) = x.

2.6. Докажите, что композиция отображений, инъективных соответствий, сюръективных соответствий и биекций является отображением, инъективным соответствием, сюръективным соответствием и биекцией соответственно.

2.7. Приведите пример таких соответствий F и G, что
а) F ◦ G = G ◦ F;
б) F ◦ G ̸= G ◦ F.

2.8. Пусть F: A → B, G: B → C и H: C → D — соответствия. Докажите, что H ◦ (G ◦ F) = (H ◦ G) ◦ F.

Глава 2. Отображения и соответствия

2.9. Докажите, что для любого соответствия F: A → B выполнено
равенство F ◦ idA = idB ◦F = F.

2.10. При каких условиях на соответствие F: A → B выполнено равенство F ◦ F−1 = idB? А F−1 ◦ F = idA?

2.11. Известно, что для соответствий F: A → B и G: B → A имеет
место равенство G ◦ F = idA. Верно ли, что G = F−1?

2.12. Известно, что для соответствий F: A → B, G: B → A и H: B → A
имеют место соотношения G ◦ F = idA и F ◦ H = idB. Верно ли, что
G = H?