Теория курса

Комбинаторика. Книга 1

Book 1. Foundations of Olympiad Combinatorics

1. Принципы подсчёта
2. Перестановки и размещения
3. Сочетания
4. Подсчёт двумя способами
5. Принцип Дирихле I
6. Инварианты I
7. Раскраски и задачи на досках
8. Игры и стратегии I
9. Графы I
10. Рекурсии и последовательности
11. Смешанные задачи I
12. Пробные олимпиады I

Глава

Принципы подсчёта

Модуль вводит олимпиадный подсчёт через порядок выбора, правило суммы, правило произведения, случаи, метод дополнения и первые ловушки переучёта.

Ключевая идея Подсчёт начинается не с формулы, а с вопроса: что выбирается первым, что потом, и зависит ли следующий выбор от предыдущего? Правило суммы используется для непересекающихся случаев, правило произведения — для последовательных независимых или зависимых шагов, где число вариантов на каждом шаге известно. Олимпиадная трудность часто не в арифметике, а в том, чтобы не посчитать объект дважды и не пропустить запрещённый случай. Поэтому в этом модуле важны аккуратный порядок выбора, разбиение на случаи и метод дополнения. Основные факты Если объект можно получить одним из \(a\) способов первого типа или одним из \(b\) способов второго типа, и типы не пересекаются, всего \(a+b\) способов. Если первый шаг можно сделать \(a\) способами, а после каждого первого шага второй — \(b\) способами, всего \(a\cdot b\) способов. Если число вариантов на втором шаге зависит от первого, нужно записывать произведение по случаям или строить дерево выбора. Метод дополнения: иногда проще посчитать все объекты и вычесть запрещённые. Переучёт возникает, когда один и тот же объект можно получить несколькими путями; тогда нужен другой порядок выбора или деление на число повторов. Когда применять метод Нужно посчитать количество чисел, слов, путей, выборов или раскрасок с простыми ограничениями. Условие естественно разбивается на непересекающиеся случаи. Проще посчитать запрещённые варианты, чем разрешённые. Есть опасность, что разные описания дают один и тот же объект. Как распознать метод Слова “или” обычно намекают на правило суммы, если случаи не пересекаются. Слова “сначала”, “затем”, “после этого” намекают на правило произведения. Если в задаче есть “хотя бы один”, “не менее одного”, “без такого свойства”, проверьте метод дополнения. Если вы выбираете несколько объектов, спросите: порядок важен или нет? Если порядок не важен, нельзя просто умножать варианты как для последовательности без последующей проверки. Типичные ошибки Складывают варианты, хотя выборы должны выполняться одновременно. Умножают варианты, хотя случаи пересекаются. Забывают, что первая цифра числа не может быть \(0\). Считают “хотя бы один” прямым перебором, хотя дополнение короче. Дважды считают один объект из-за разного порядка выбора. Мини-чеклист Что именно является одним объектом? Порядок выбора важен? Случаи действительно не пересекаются? Есть ли запрещённые варианты, которые проще вычесть? Зависит ли следующий выбор от предыдущего? Не получаем ли один объект несколькими способами?

Пример 1. Правило суммы Случаи должны быть непересекающимися. Задача. У ученика есть \(5\) книг по математике и \(4\) книги по физике. Сколькими способами он может выбрать одну книгу? Решение. Он выбирает либо математическую книгу, либо физическую. Эти случаи не пересекаются. Поэтому всего \(5+4=9\) способов. Комментарий. Если бы нужно было выбрать две книги, одну по математике и одну по физике, было бы произведение, а не сумма. Пример 2. Правило произведения Последовательные шаги дают произведение. Задача. Из города \(A\) в город \(B\) ведут \(3\) дороги, а из \(B\) в \(C\) — \(4\) дороги. Сколько маршрутов из \(A\) в \(C\) через \(B\)? Решение. Сначала выбираем дорогу \(A o B\): \(3\) варианта. Затем дорогу \(B o C\): \(4\) варианта. Всего \(3\cdot4=12\) маршрутов. Комментарий. Здесь каждый первый выбор совместим с каждым вторым. Пример 3. Выбор без повторений Число вариантов меняется после каждого шага. Задача. Сколько трёхзначных чисел можно составить из цифр \(1,2,3,4,5\), если цифры не повторяются? Решение. Сотни можно выбрать \(5\) способами, десятки — \(4\) способами, единицы — \(3\) способами. Всего \(5\cdot4\cdot3=60\) чисел. Комментарий. После выбора первой цифры она уже недоступна. Пример 4. Первая цифра не ноль Ограничение на первый шаг нельзя забывать. Задача. Сколько трёхзначных чисел с различными цифрами можно составить из цифр \(0,1,2,3,4\)? Решение. Сотни можно выбрать \(4\) способами: \(1,2,3,4\). После этого остаётся \(4\) цифры для десятков и \(3\) для единиц. Всего \(4\cdot4\cdot3=48\). Комментарий. Если начать с \(5\cdot4\cdot3\), будут посчитаны записи, начинающиеся с нуля. Пример 5. Метод дополнения “Хотя бы один” часто лучше считать через противоположное. Задача. Сколько двоичных строк длины \(6\) содержат хотя бы одну единицу? Решение. Всего двоичных строк \(2^6=64\). Строка без единиц только одна: \(000000\). Значит нужных строк \(64-1=63\). Комментарий. Прямой подсчёт по числу единиц был бы длиннее. Пример 6. Случаи по последней цифре Разбиение на случаи помогает учитывать делимость. Задача. Сколько четырёхзначных чисел с различными цифрами из \(0,1,\ldots,7\) делятся на \(5\)? Решение. Последняя цифра должна быть \(0\) или \(5\). Если последняя \(0\), первую цифру выбираем \(7\) способами, затем \(6\) и \(5\): \(210\). Если последняя \(5\), первая цифра не \(0\) и не \(5\): \(6\) способов, затем \(6\) и \(5\): \(180\). Всего \(390\). Комментарий. Случаи непересекающиеся, поэтому результаты складываются. Пример 7. Переучёт Иногда порядок выбора создаёт лишние копии. Задача. Сколькими способами можно выбрать двух дежурных из \(8\) учеников, если роли одинаковые? Решение. Если выбирать первого и второго по порядку, получим \(8\cdot7=56\) вариантов. Но каждая пара посчитана дважды: \(AB\) и \(BA\). Поэтому ответ \(56/2=28\). Комментарий. Это первый сигнал: порядок выбора не всегда является частью объекта. Пример 8. Дополнение с двумя запретами Два запрета требуют аккуратного возвращения пересечения. Задача. Сколько слов длины \(5\) над алфавитом \(\{A,B,C\}\) содержат хотя бы одну букву \(A\) и хотя бы одну букву \(B\)? Решение. Всего слов \(3^5=243\). Без \(A\): \(2^5=32\). Без \(B\): \(2^5=32\). Слова без \(A\) и без \(B\) состоят только из \(C\), такое слово одно. По методу дополнения получаем \(243-32-32+1=180\). Комментарий. Пересечение запретов вычли дважды, поэтому его нужно вернуть.

Глава

Перестановки и размещения

Модуль развивает перестановки, размещения, повторяющиеся объекты, круговые рассадки, блоки, запреты соседства и первые задачи на включение-исключение.

Ключевая идея Перестановка — это расположение объектов в порядке. Главное отличие от простого выбора: порядок теперь является частью объекта. Если объекты различны, \(n\) объектов можно упорядочить \(n!\) способами. Если некоторые объекты одинаковы, нужно убрать переучёт от перестановок одинаковых копий. Олимпиадные задачи на перестановки редко сводятся к одной формуле. Чаще нужно выбрать правильный приём: склеить блок, вычесть запрещённые соседства, зафиксировать поворот в круговой рассадке или разбить по позициям. Основные факты \(n\) различных объектов можно расположить в ряд \(n!\) способами. Если из \(n\) различных объектов выбирают и упорядочивают \(k\), число способов равно \(n(n-1)\cdots(n-k+1)\). Если среди \(n\) объектов есть группы одинаковых размеров \(a,b,c,\ldots\), число различных перестановок равно \(n!/(a!b!c!\cdots)\). В круговой рассадке повороты считаются одинаковыми, поэтому \(n\) разных людей можно посадить за круглый стол \((n-1)!\) способами. Если несколько объектов должны стоять вместе, их часто склеивают в один блок, а потом учитывают внутренний порядок блока. Когда применять метод Нужно расположить людей, книги, буквы, цифры или предметы в ряд или по кругу. В условии есть слова “рядом”, “не рядом”, “в определённом порядке”, “на фиксированных местах”. Есть одинаковые буквы или повторяющиеся объекты. Проще посчитать все расположения и вычесть запрещённые. Как распознать метод Если объекты должны быть рядом, попробуйте блок. Если объекты не должны быть рядом, часто удобнее вычесть случаи, где они рядом. Если расположение круговое, сначала зафиксируйте один объект или используйте \((n-1)!\). Если есть одинаковые буквы, сначала посчитайте как разные, затем разделите на перестановки одинаковых копий. В задачах с запретами на позиции полезно спросить: запреты независимы или пересекаются? Если пересекаются, может понадобиться включение-исключение. Типичные ошибки Считают круговую рассадку как линейную. Забывают внутренний порядок склеенного блока. Вычитают запрещённые случаи, но забывают, что несколько запретов могут выполняться одновременно. Делят на факториалы повторов там, где одинаковые объекты уже были выбраны как неразличимые. Путают “\(A\) перед \(B\)” и “\(A\) рядом с \(B\)”. Мини-чеклист Объекты различны или есть одинаковые? Расположение линейное или круговое? Есть ли блоки “должны быть рядом”? Запрет “не рядом” проще считать напрямую или через дополнение? Порядок внутри выбранной группы важен? Не пересекаются ли запрещённые условия?

Пример 1. Перестановка разных объектов Базовая техника: каждый следующий выбор уменьшает число вариантов. Задача. Сколькими способами можно расставить \(6\) разных книг на полке? Решение. На первое место можно поставить \(6\) книг, на второе \(5\), затем \(4,3,2,1\). Всего \(6!=720\). Комментарий. Это линейное расположение разных объектов. Пример 2. Повторяющиеся буквы Одинаковые буквы создают переучёт. Задача. Сколько различных слов можно получить перестановкой букв слова \(BANANA\)? Решение. Всего \(6\) букв. Буква \(A\) повторяется \(3\) раза, буква \(N\) — \(2\) раза. Если считать все копии различными, будет \(6!\), но каждое слово посчитано \(3!\cdot2!\) раз. Ответ \(6!/(3!\cdot2!)=60\). Комментарий. Делим только на перестановки одинаковых букв. Пример 3. Блок рядом Если два объекта должны стоять рядом, склейте их. Задача. Сколькими способами можно расставить \(6\) человек в ряд, если Антон и Борис должны стоять рядом? Решение. Склеим Антона и Бориса в блок. Тогда есть \(5\) объектов: блок и ещё \(4\) человека. Их можно расставить \(5!\) способами. Внутри блока \(2\) порядка. Ответ \(2\cdot5!=240\). Комментарий. Нельзя забыть внутренний порядок блока. Пример 4. Не рядом через дополнение Запрет часто проще считать как все минус плохие. Задача. Сколькими способами можно расставить \(6\) человек в ряд, если Антон и Борис не должны стоять рядом? Решение. Всего \(6!=720\) расположений. Рядом они стоят \(2\cdot5!=240\) способами. Значит не рядом: \(720-240=480\). Комментарий. Это дополнение к предыдущей задаче. Пример 5. Круговая рассадка В круге повороты считаются одинаковыми. Задача. Сколькими способами можно посадить \(5\) разных людей за круглый стол? Решение. Зафиксируем одного человека. Оставшихся \(4\) можно расположить вокруг него \(4!\) способами. Ответ \(24\). Комментарий. Фиксация одного человека убирает поворот. Пример 6. Круг и соседство Блок работает и за круглым столом. Задача. Сколькими способами можно посадить \(6\) людей за круглый стол, если двое заданных должны сидеть рядом? Решение. Склеим этих двоих в блок. Получаем \(5\) объектов на круге, их можно расположить \((5-1)!=24\) способами. Внутри блока \(2\) порядка. Ответ \(48\). Комментарий. Сначала учитываем круг, потом внутренний порядок блока. Пример 7. Перед, но не обязательно рядом Половина перестановок имеет \(A\) перед \(B\). Задача. Сколько перестановок чисел \(1,2,3,4,5\) имеют \(1\) раньше \(2\)? Решение. Во всех \(5!\) перестановках числа \(1\) и \(2\) симметричны: ровно в половине \(1\) стоит раньше \(2\), в половине наоборот. Ответ \(5!/2=60\). Комментарий. Это не условие соседства. Пример 8. Первое включение-исключение Запреты на неподвижные точки пересекаются. Задача. Сколько перестановок \(1,2,3,4\) не оставляют ни одно число на своём месте? Решение. Всего \(4!=24\). Вычтем перестановки с хотя бы одной неподвижной точкой: \(4\cdot3!\). Вернём пересечения двух неподвижных точек: \(6\cdot2!\). Вычтем три: \(4\cdot1!\). Вернём четыре: \(1\). Ответ \(24-24+12-4+1=9\). Комментарий. Это первая версия задачи о беспорядках.

Глава

Сочетания

Модуль учит выбирать подмножества без порядка, считать через дополнение, работать с позициями, доказывать базовые тождества и решать первые задачи без соседних элементов.

Ключевая идея Сочетание — это выбор объектов без учёта порядка. Если порядок выбора не является частью ответа, то последовательный подсчёт обычно создаёт переучёт. Число способов выбрать \(k\) объектов из \(n\) обозначается \(\binom{n}{k}\). В олимпиадной комбинаторике сочетания важны не только как формула. Они помогают кодировать объекты: выбрать позиции единиц, выбрать вершины многоугольника, выбрать границы прямоугольника, выбрать элементы подмножества или выбрать места для разделителей. Основные факты \(\binom{n}{k}\) — число способов выбрать \(k\) объектов из \(n\) без учёта порядка. \(\binom{n}{k}=\binom{n}{n-k}\): выбрать \(k\) объектов всё равно что выбрать \(n-k\), которые не взяты. Тождество Паскаля: \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\). Метод дополнения: “хотя бы один” часто считается как все варианты минус варианты без этого объекта или свойства. Выбор без соседних элементов часто сводится к сдвигу: \(a_1<\cdots Когда применять метод Нужно выбрать команду, подмножество, позиции, вершины или набор объектов. Порядок выбора не важен. В задаче есть “ровно \(k\)”, “не менее \(k\)”, “хотя бы один”. Нужно доказать комбинаторное тождество, посчитав один и тот же набор двумя способами. Как распознать метод Если объект полностью задаётся набором выбранных элементов, используйте сочетания. Если объект задаётся позициями специальных символов, выбирайте позиции. Если условие “не подряд”, попробуйте сначала записать выбранные числа \(a_1<\cdots Если формула выглядит алгебраически, попробуйте задать вопрос: что именно считает левая часть, и что считает правая? Типичные ошибки Считают упорядоченные выборы, хотя порядок не важен. Забывают вычесть запрещённые варианты при словах “хотя бы”. Используют формулу сочетаний, не объясняя, что именно выбирается. Путают выбор \(k\) объектов и разбиение объектов на группы. В задачах без соседних элементов забывают обязательный зазор между выбранными числами. Мини-чеклист Один ответ — это набор или порядок? Какие элементы выбираются? Можно ли считать дополнение? Если есть ограничение “не соседние”, где находятся обязательные промежутки? Если доказывается тождество, какой общий объект считают обе стороны? Нужно ли разбивать выбор по числу объектов разных типов?

Пример 1. Выбор без порядка Команда не зависит от порядка выбора. Задача. Сколькими способами можно выбрать \(3\) учеников из \(8\)? Решение. Если выбирать по порядку, получим \(8\cdot7\cdot6\), но каждая команда из трёх учеников посчитана \(3!\) раз. Поэтому ответ \(8\cdot7\cdot6/3!=56\). Комментарий. Это и есть \(\binom{8}{3}\). Пример 2. Дополнение Иногда проще выбрать тех, кто не входит. Задача. Сколькими способами можно выбрать \(4\) книги из \(10\), если одна заданная книга должна быть выбрана? Решение. Заданная книга уже выбрана. Остаётся выбрать ещё \(3\) книги из остальных \(9\). Ответ \(\binom{9}{3}=84\). Комментарий. Не нужно отдельно рассматривать место заданной книги. Пример 3. Хотя бы одна девочка Метод дополнения сокращает перебор случаев. Задача. Из \(5\) мальчиков и \(4\) девочек выбирают команду из \(3\). Сколько команд содержат хотя бы одну девочку? Решение. Всего команд \(\binom{9}{3}=84\). Команд без девочек: \(\binom{5}{3}=10\). Значит нужных \(84-10=74\). Комментарий. Слова “хотя бы” часто зовут дополнение. Пример 4. Тождество Паскаля Одно и то же множество можно посчитать по наличию специального элемента. Задача. Докажите \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\). Решение. Выбираем \(k\)-элементное подмножество из \(n\)-элементного множества и фиксируем один элемент \(x\). Либо \(x\) не выбран: тогда выбираем все \(k\) элементов из остальных \(n-1\). Либо \(x\) выбран: тогда надо выбрать ещё \(k-1\) из остальных \(n-1\). Получаем тождество. Комментарий. Это доказательство лучше запоминается, чем формула. Пример 5. Положительные решения Разделители кодируют распределение. Задача. Сколько положительных решений имеет \(x+y+z=10\)? Решение. Положим сначала по \(1\) в каждую переменную. Остаётся распределить \(7\) единиц между \(3\) переменными. Это задаётся двумя разделителями среди \(9\) позиций, значит \(\binom{9}{2}=36\). Комментарий. Можно также думать о строке из единиц и двух перегородок. Пример 6. Без соседних чисел Сдвиг убирает обязательные промежутки. Задача. Сколько \(3\)-элементных подмножеств \(\{1,\ldots,10\}\) не содержат соседних чисел? Решение. Пусть выбраны \(a_1 Комментарий. Это стандартная техника для запрета соседства. Пример 7. Сумма по числу девочек Разбиение по типу выбранных объектов. Задача. Сколько команд из \(4\) человек можно выбрать из \(6\) мальчиков и \(5\) девочек так, чтобы в команде было ровно \(2\) девочки? Решение. Выбираем \(2\) девочки из \(5\) и \(2\) мальчика из \(6\). Эти выборы независимы. Ответ \(\binom{5}{2}\binom{6}{2}=10\cdot15=150\). Комментарий. Типичная задача на выбор из двух групп. Пример 8. Небольшая теорема о сравнимых подмножествах Сочетания помогают понимать размер слоёв. Задача. Почему среди \(7\) подмножеств четырёхэлементного множества найдутся два, одно из которых содержится в другом? Решение. Все \(16\) подмножеств можно разбить на \(6\) цепочек по включению, например так: одна длинная цепочка от \(\varnothing\) до всего множества, три цепочки длины \(3\) и две одиночные пары среднего слоя. Тогда по принципу Дирихле \(7\) выбранных подмножеств попадут в одну цепочку, а в цепочке любые два сравнимы. Комментарий. Это preview будущих идей о цепях и антицепях.

Глава

Подсчёт двумя способами

Модуль вводит двойной подсчёт как метод: пары, инцидентности, сумма степеней, средний аргумент, тождества с подмножествами и первые оценки.

Ключевая идея Метод двойного подсчёта состоит в том, что мы считаем один и тот же набор объектов двумя разными способами. Результатом может быть равенство, тождество, среднее значение или доказательство существования объекта с нужным свойством. Чаще всего считаются пары: \((ученик, кружок)\), \((вершина, ребро)\), \((подмножество, элемент)\), \((точка, прямая)\). Если правильно выбрать, какие пары считать, задача часто становится короткой. Основные факты Если посчитать один и тот же конечный набор двумя способами, получаются равные ответы. Сумма степеней вершин графа равна \(2E\), потому что каждое ребро имеет два конца. Если всего \(T\) объектов распределены по \(m\) ящикам, то в некотором ящике не меньше среднего \(T/m\). Число пар \((S,x)\), где \(x\) принадлежит подмножеству \(S\), можно считать по \(S\) или по \(x\). Двойной подсчёт часто превращает “докажите существует” в утверждение о среднем. Когда применять метод В задаче есть отношения между объектами: ученик посещает кружок, точка лежит на прямой, вершина соединена ребром. Нужно доказать комбинаторное тождество. Есть таблица, строки и столбцы, и можно считать единицы двумя способами. Нужно доказать существование объекта с большой или малой нагрузкой. Как распознать метод Ищите фразы “каждый объект связан с”, “в каждой группе”, “каждая пара”, “сколько всего участий”, “среднее число”. Они почти всегда подсказывают набор пар или инцидентностей. Если видите сумму вида \(0C(n,0)+1C(n,1)+\cdots+nC(n,n)\), попробуйте считать пары “выбранное подмножество и отмеченный элемент в нём”. Типичные ошибки Считают разные множества объектов, а не одно и то же. Забывают, что ребро в графе даёт два конца. Используют среднее, но не формулируют вывод “существует не меньше среднего”. Путают пары и неупорядоченные пары. В задачах на тождества не объясняют, что именно считается. Мини-чеклист Какой набор объектов мы считаем? Можно ли описать объект как пару \((a,b)\)? Что получится, если считать по первому компоненту? Что получится, если считать по второму компоненту? Нужно равенство или достаточно оценки? Как из среднего получить существование?

Пример 1. Рукопожатия Каждое рукопожатие можно считать по двум участникам. Задача. В комнате \(10\) человек, каждый пожал руку каждому. Сколько рукопожатий было? Решение. Считаем пары людей: нужно выбрать \(2\) человека из \(10\), получаем \(45\). Иначе можно сказать: каждый человек дал \(9\) рукопожатий, всего \(90\) концов рукопожатий, каждое рукопожатие имеет два конца, значит \(90/2=45\). Комментарий. Это первая версия суммы степеней. Пример 2. Членства в кружках Считаем пары “ученик — кружок”. Задача. В школе \(30\) учеников, каждый ходит ровно в \(2\) кружка. Сколько всего ученических членств в кружках? Решение. Каждый ученик даёт \(2\) пары \((ученик, кружок)\). Всего \(30\cdot2=60\) членств. Комментарий. Если известны размеры кружков, их сумма тоже должна быть \(60\). Пример 3. Среднее даёт существование Если среднее большое, кто-то не меньше среднего. Задача. В \(8\) кружках всего \(60\) членств. Докажите, что в некотором кружке не менее \(8\) учеников. Решение. Если бы в каждом кружке было не более \(7\) учеников, всего было бы не более \(8\cdot7=56\) членств. Но их \(60\). Значит в некотором кружке хотя бы \(8\) учеников. Комментарий. Это средний аргумент в форме противоречия. Пример 4. Сумма степеней Каждое ребро имеет два конца. Задача. Докажите, что в любом графе сумма степеней всех вершин равна удвоенному числу рёбер. Решение. Считаем пары \((v,e)\), где вершина \(v\) является концом ребра \(e\). Если считать по вершинам, получаем сумму степеней. Если считать по рёбрам, каждое ребро даёт \(2\) пары. Значит сумма степеней равна \(2E\). Комментарий. Это главная лемма графового подсчёта. Пример 5. Тождество с подмножествами Считаем подмножество и отмеченный элемент. Задача. Докажите, что \(\sum_{k=0}^n kC(n,k)=n2^{n-1}\). Решение. Считаем пары \((S,x)\), где \(S\) — подмножество \(n\)-элементного множества, а \(x\in S\). По размеру \(S=k\): получаем левую часть. По элементу \(x\): выбираем \(x\) \(n\) способами, а остальные элементы подмножества выбираются произвольно из \(n-1\), значит \(n2^{n-1}\). Комментарий. Тождество стало задачей о парах. Пример 6. Пары подмножеств Каждый элемент может быть вне обоих множеств, только в большем или в обоих. Задача. Сколько пар \((A,B)\) подмножеств множества из \(n\) элементов удовлетворяют \(A\subset B\)? Решение. Для каждого элемента есть три варианта: не входит в \(B\), входит в \(B\), но не в \(A\), входит в \(A\) и \(B\). Значит пар \(3^n\). Комментарий. Это тоже двойной взгляд: по элементам вместо по множествам. Пример 7. Инцидентности точек и прямых Одна и та же таблица “точка лежит на прямой” считается по строкам или столбцам. Задача. Есть \(9\) прямых, на каждой отмечено \(5\) точек. Каждая отмеченная точка лежит ровно на \(3\) прямых. Сколько отмеченных точек? Решение. Считаем инцидентности \((точка, прямая)\). По прямым их \(9\cdot5=45\). По точкам их \(3N\), где \(N\) — число точек. Значит \(3N=45\), откуда \(N=15\). Комментарий. Классическая задача на инцидентности. Пример 8. Ограничение через пары Если каждая тройка содержит \(3\) пары, можно ограничить число троек. Задача. Имеются трёхэлементные подмножества \(10\)-элементного множества, причём никакая пара элементов не встречается в двух разных подмножествах. Докажите, что таких подмножеств не больше \(15\). Решение. Каждое трёхэлементное подмножество содержит \(3\) пары элементов. Всего пар элементов в \(10\)-элементном множестве \(45\). Так как пары не повторяются, \(3m\le45\), где \(m\) — число подмножеств. Значит \(m\le15\). Комментарий. Это уже олимпиадная оценка двойным подсчётом.

Глава

Принцип Дирихле I

Модуль развивает простой и усиленный принцип Дирихле: остатки, пары, интервалы, геометрические разбиения, частичные суммы, subset sums и первые Ramsey/Erdos-Szekeres идеи.

Ключевая идея Принцип Дирихле говорит: если предметов больше, чем ящиков, то в каком-то ящике окажется не менее двух предметов. Усиленная форма: если \(N\) предметов распределены по \(k\) ящикам, то в некотором ящике не меньше \(\lceil N/k ceil\) предметов. Олимпиадная часть метода — правильно выбрать “ящики”. Это могут быть месяцы, остатки, суммы, интервалы, цвета, нечётные части чисел, клетки разбиения фигуры или пары параметров. Основные факты Если \(k+1\) предметов лежат в \(k\) ящиках, то два предмета лежат в одном ящике. Если \(N\) предметов лежат в \(k\) ящиках, то есть ящик с не менее чем \(\lceil N/k ceil\) предметами. Остатки по модулю \(n\) дают \(n\) ящиков. Для задач “сумма делится на \(n\)” часто используют частичные суммы. В геометрии ящиками часто становятся маленькие области, на которые разбита большая фигура. Когда применять метод Нужно доказать, что среди многих объектов найдутся два с одинаковым свойством. Есть остатки, месяцы, цвета, интервалы, классы чётности или другие конечные категории. Нужно доказать существование пары с маленьким расстоянием или специальной суммой. Задача утверждает “при любом выборе достаточно многих объектов”. Как распознать метод Спросите: какое свойство может принимать мало значений? Если объектов больше, чем возможных значений свойства, два объекта совпадут по этому свойству. Если нужно получить делимость, ящиками часто являются остатки. Если нужно получить близость, ящиками являются интервалы или маленькие клетки. Если речь о суммах подмножеств, попробуйте рассмотреть частичные суммы или все суммы подмножеств и сравнить число сумм с числом возможных значений. Типичные ошибки Выбирают ящики, но не доказывают, что их действительно меньше, чем предметов. Получают два объекта в одном ящике, но не объясняют, почему это даёт нужное свойство. В задачах на остатки забывают про остаток \(0\). В геометрических задачах разбивают фигуру на области слишком большого диаметра. В задачах на суммы подмножеств забывают убрать общие элементы у двух подмножеств с равной суммой. Мини-чеклист Что является предметом? Что является ящиком? Сколько предметов и сколько ящиков? Что означает попадание двух предметов в один ящик? Нужна простая или усиленная форма принципа? Если используются суммы, можно ли перейти от равных сумм к непустым disjoint-наборам?

Пример 1. Дни рождения Самая простая модель ящиков. Задача. Докажите, что среди \(13\) человек найдутся двое, родившиеся в один месяц. Решение. Ящики — \(12\) месяцев. Предметы — \(13\) человек. Так как предметов больше, чем ящиков, в каком-то месяце окажутся хотя бы два человека. Комментарий. Важно назвать ящики явно. Пример 2. Остатки Остатки по модулю дают готовые ящики. Задача. Докажите, что среди любых \(n+1\) целых чисел найдутся два с одинаковым остатком при делении на \(n\). Решение. Возможных остатков \(n\): \(0,1,\ldots,n-1\). Чисел \(n+1\), значит два попали в один класс остатков. Комментарий. Их разность делится на \(n\). Пример 3. Усиленный принцип Иногда нужно не два, а много в одном ящике. Задача. В коробке \(25\) шаров трёх цветов. Докажите, что есть цвет, шаров которого не меньше \(9\). Решение. Если каждого цвета было бы не больше \(8\), всего шаров было бы не больше \(3\cdot8=24\), противоречие. Значит некоторого цвета не меньше \(9\). Комментарий. Это форма \(\lceil25/3 ceil=9\). Пример 4. Сумма \(11\) Ящиками могут быть пары чисел. Задача. Из чисел \(1,2,\ldots,10\) выбрали \(6\). Докажите, что среди выбранных есть два с суммой \(11\). Решение. Разобьём числа на пары \((1,10),(2,9),(3,8),(4,7),(5,6)\). Есть \(5\) ящиков-пар и \(6\) выбранных чисел. В одной паре выбраны оба числа, их сумма \(11\). Комментарий. Это не остатки, а специально подобранные ящики. Пример 5. Делимость одного числа на другое Ящики — нечётные части чисел. Задача. Докажите, что среди любых \(10\) чисел из \(1,\ldots,18\) найдутся два, одно из которых делит другое. Решение. Каждое число представим как \(2^k m\), где \(m\) нечётно. Возможные нечётные части в \(1,\ldots,18\): \(1,3,5,7,9,11,13,15,17\), всего \(9\). У \(10\) чисел две нечётные части совпадают. Тогда эти два числа отличаются только степенью двойки, значит меньшее делит большее. Комментарий. Это важный нестандартный выбор ящиков. Пример 6. Геометрический ящик Разбиение фигуры контролирует расстояние. Задача. В квадрате со стороной \(2\) выбрали \(5\) точек. Докажите, что две из них находятся на расстоянии не больше \(\sqrt{2}\). Решение. Разобьём квадрат на \(4\) единичных квадрата. По принципу Дирихле в одном маленьком квадрате окажутся две точки. Диагональ маленького квадрата равна \(\sqrt{2}\), значит расстояние между этими точками не больше \(\sqrt{2}\). Комментарий. Диаметр ящика должен быть не больше требуемого расстояния. Пример 7. Частичные суммы Сумма подряд идущего блока появляется из равных остатков. Задача. Докажите, что среди \(n\) целых чисел найдётся непустой подряд идущий блок, сумма которого делится на \(n\). Решение. Рассмотрим частичные суммы \(s_1,\ldots,s_n\). Если какая-то делится на \(n\), готово. Иначе у \(n\) сумм есть только \(n-1\) ненулевых остатков, значит две суммы имеют одинаковый остаток. Их разность — сумма некоторого подряд идущего блока и делится на \(n\). Комментарий. Это один из главных шаблонов модуля. Пример 8. Монотонная подпоследовательность Сложный ящик может быть парой чисел. Задача. Докажите, что среди \(10\) различных чисел найдётся возрастающая подпоследовательность длины \(4\) или убывающая подпоследовательность длины \(4\). Решение. Для каждого числа запишем пару \((a,b)\): длина самой длинной возрастающей подпоследовательности, начинающейся с него, и длина самой длинной убывающей подпоследовательности, начинающейся с него. Если нет ни возрастающей, ни убывающей длины \(4\), то \(a,b\in\{1,2,3\}\), всего \(9\) пар. Но чисел \(10\). Две позиции имели бы одинаковую пару; для более ранней и более поздней позиции это невозможно, потому что если первое число меньше второго, возрастная длина первого больше, а если больше — убывающая длина первого больше. Комментарий. Это сильный пример принципа Дирихле.

Глава

Инварианты I

Модуль вводит инварианты через чётность, сумму, остатки, раскраску, произведение знаков, координатные инварианты и паритет инверсий.

Ключевая идея Инвариант — это величина или свойство, которое не меняется при разрешённых операциях. Если начальное и конечное состояния имеют разные значения инварианта, то перейти из одного состояния в другое невозможно. В олимпиадных задачах инвариант часто не виден сразу. Его нужно искать среди чётности, суммы, остатка по модулю, раскраски, произведения знаков, числа объектов определённого цвета или паритета перестановки. Основные факты Если операция меняет величину на чётное число, её чётность сохраняется. Если операция прибавляет к одной части и вычитает из другой, часто сохраняется сумма. Если операция меняет состояние на кратное \(m\), сохраняется остаток по модулю \(m\). При раскраске доски важно, сколько клеток каждого цвета покрывает или меняет фигура. При смене знаков полезно смотреть на произведение всех знаков или чётность числа минусов. Когда применять метод Нужно доказать, что получить одно состояние из другого невозможно. Есть повторяющаяся операция, меняющая конфигурацию. В задаче есть фишки, монеты, лампы, знаки, клетки доски или перестановки. Прямой перебор ходов невозможен или быстро становится хаотичным. Как распознать метод Спросите: что операция точно не меняет? Если меняется число объектов, проверьте чётность. Если переносятся предметы, проверьте сумму. Если операция локальная на доске, раскрасьте доску. Если меняются знаки, проверьте произведение или число минусов. Иногда инвариант — не сама величина, а её остаток. Например, сумма может меняться, но всегда на число, кратное \(3\), поэтому сохраняется остаток суммы по модулю \(3\). Типичные ошибки Показывают, что величина иногда не меняется, но не проверяют все возможные ходы. Выбирают величину, которая почти сохраняется, но один тип хода её ломает. Доказывают невозможность, но не сравнивают начальное и конечное значения инварианта. В задачах на доске используют раскраску, но не проверяют цвета фигуры. Забывают, что инвариант может быть составным: например, “паритет инверсий плюс число ходов”. Мини-чеклист Какое начальное состояние? Какое конечное состояние требуется? Что меняет один ход? Какая величина сохраняется при любом ходе? Различаются ли значения инварианта в начале и в конце? Если один инвариант не работает, стоит ли попробовать модуль, раскраску или произведение?

Пример 1. Чётность Самый частый инвариант — чётность. Задача. На доске написано число \(0\). За ход можно прибавить \(2\) или вычесть \(2\). Можно ли получить число \(101\)? Решение. Чётность числа не меняется: к числу прибавляют или вычитают чётное число. Начальное число \(0\) чётно, а \(101\) нечётно. Значит получить \(101\) нельзя. Комментарий. Инвариант: остаток по модулю \(2\). Пример 2. Переворот двух монет Количество орлов меняется на чётное число. Задача. Есть \(15\) монет орлом вверх. За ход переворачивают ровно две монеты. Можно ли получить все монеты решкой вверх? Решение. Число орлов при перевороте двух монет меняется на \(-2\), \(0\) или \(2\). Поэтому чётность числа орлов сохраняется. В начале орлов \(15\), это нечётно; в конце должно быть \(0\), это чётно. Нельзя. Комментарий. Неважно, какие именно монеты переворачивают. Пример 3. Сумма сохраняется Операция переносит единицу из одного места в другое. Задача. В двух кучах \(7\) и \(11\) камней. За ход можно переложить один камень из одной кучи в другую. Можно ли получить кучи \(5\) и \(20\)? Решение. Общее число камней сохраняется. В начале \(18\), а в состоянии \(5\) и \(20\) всего \(25\). Значит получить его невозможно. Комментарий. Инвариант может быть совсем простым. Пример 4. Остаток по модулю Сумма может меняться, но остаток сохраняется. Задача. На доске написана сумма чисел. За ход к ней можно прибавить \(6\) или вычесть \(9\). Если в начале сумма равна \(2\), можно ли получить \(100\)? Решение. Оба изменения кратны \(3\), значит остаток суммы по модулю \(3\) сохраняется. В начале \(2\pmod3\), а \(100\equiv1\pmod3\). Получить \(100\) нельзя. Комментарий. Инвариант: сумма по модулю \(3\). Пример 5. Раскраска доски Домино покрывает одну чёрную и одну белую клетку. Задача. Можно ли покрыть домино доску \(8\) на \(8\), если удалены две противоположные угловые клетки? Решение. В шахматной раскраске противоположные углы имеют один цвет. После удаления двух таких клеток одного цвета остаётся на две клетки меньше, чем другого. Каждое домино покрывает одну чёрную и одну белую клетку, значит покрытие невозможно. Комментарий. Это главный пример раскрасочного инварианта. Пример 6. Произведение знаков Смена двух знаков сохраняет произведение. Задача. На доске \(9\) плюсов. За ход можно изменить знаки у ровно двух символов. Можно ли получить ровно один минус? Решение. Произведение всех знаков при смене двух знаков не меняется: оно умножается на \((-1)^2=1\). В начале произведение \(+1\), а при одном минусе произведение \(-1\). Нельзя. Комментарий. Можно также смотреть на чётность числа минусов. Пример 7. Цвет клетки при ходе коня Некоторые ходы меняют цвет обязательно. Задача. Конь стоит на чёрной клетке шахматной доски. Может ли он после \(7\) ходов оказаться на чёрной клетке? Решение. Ход коня всегда меняет цвет клетки. После нечётного числа ходов цвет будет противоположным начальному. После \(7\) ходов конь будет на белой клетке, значит на чёрной оказаться не может. Комментарий. Инвариант: цвет плюс чётность числа ходов. Пример 8. Инверсии и число ходов Иногда сохраняется сумма двух паритетов. Задача. Из строки \(12345678\) соседними обменами хотят получить \(87654321\) ровно за \(27\) ходов. Возможно ли это? Решение. Один соседний обмен меняет чётность числа инверсий. В начале инверсий \(0\). В обратной строке инверсий \(C(8,2)=28\), чётность снова чётная. После \(27\) обменов чётность инверсий должна быть нечётной, противоречие. Нельзя. Комментарий. Инвариант: чётность инверсий совпадает с чётностью числа сделанных соседних обменов.

Глава

Раскраски и задачи на досках

Модуль учит использовать раскраски досок для доказательства невозможности, поиска необходимого положения клетки и анализа ходов фигур.

Ключевая идея Раскраска превращает геометрическую картинку на доске в счет. Если каждая фигура покрытия закрывает клетки цветов в фиксированном соотношении, то вся покрываемая область должна иметь такое же соотношение цветов. Главный прием: выбрать не красивую, а полезную раскраску. Для домино часто достаточно шахматной раскраски. Для прямых тримино и тетрамино работают диагональные раскраски по модулю \(3\) и \(4\). Для ходов коня полезно помнить, что конь меняет цвет клетки при каждом ходе. Основные факты Домино \(1\times2\) на шахматной доске покрывает одну черную и одну белую клетку. Прямое тримино \(1\times3\), если красить клетку \((i,j)\) по остатку \(i+j\pmod3\), покрывает по одной клетке каждого из трех цветов. Прямое тетрамино \(1\times4\), если красить клетку \((i,j)\) по остатку \(i+j\pmod4\), покрывает по одной клетке каждого из четырех цветов. При раскраске вертикальными полосами горизонтальное домино покрывает два цвета, а вертикальное - две клетки одного цвета. Ход коня меняет цвет клетки в обычной шахматной раскраске. Когда применять метод Нужно доказать, что доску нельзя замостить заданными фигурами. Обычная площадь подходит по делимости, но задача все равно кажется невозможной. Удалены клетки с особым расположением: углы, диагональ, центр, клетки одного цвета. Есть условие на число вертикальных или горизонтальных фигур. Фигура двигается по доске, и важно, где она может оказаться после заданного числа ходов. Как распознать метод Сначала проверьте площадь. Если площадь не дает противоречия, попробуйте шахматную раскраску. Если фигуры длинные, используйте раскраску по модулю длины. Если есть направление фигур, покрасьте строки или столбцы полосами. Хорошая проверка: посчитать, сколько клеток каждого цвета покрывает одна фигура. Если это число одинаково для каждой фигуры, то такое же соотношение обязано быть у всей области. Типичные ошибки Останавливаются на проверке площади и не проверяют раскраску. Используют шахматную раскраску там, где нужна раскраска по модулю \(3\) или \(4\). Не учитывают, что фигура может поворачиваться. Считают цвета всей доски, но забывают вычесть удаленные клетки. Доказывают необходимое условие и случайно считают его достаточным. Мини-чеклист Какова площадь области и площадь одной фигуры? Что покрывает одна фигура в шахматной раскраске? Если фигура имеет длину \(3\) или \(4\), что дает раскраска \(i+j\pmod3\) или \(i+j\pmod4\)? Удаленные клетки имеют какие цвета? Получается ли нужное количество клеток каждого цвета? Если задача про ход фигуры, как меняется цвет после одного хода?

Пример 1. Домино и два угла Базовый пример показывает, почему одной площади недостаточно. Задача. Можно ли покрыть домино доску \(8\times8\), если удалены две противоположные угловые клетки? Решение. В шахматной раскраске противоположные углы имеют один цвет. После удаления этих двух клеток одного цвета остается на две клетки меньше, чем другого. Каждое домино покрывает одну черную и одну белую клетку. Значит, покрыть оставшуюся доску домино невозможно. Комментарий. Инвариант: разность чисел черных и белых клеток. Пример 2. Нечетная доска Иногда раскраска сразу определяет, какая клетка должна остаться свободной. Задача. Доска \(7\times7\) покрыта домино так, что ровно одна клетка осталась непокрытой. Какого цвета эта клетка в шахматной раскраске? Решение. На доске \(7\times7\) одного цвета \(25\) клеток, другого \(24\). Каждое домино покрывает по одной клетке каждого цвета. После покрытия \(24\) домино они закроют \(24\) клетки каждого цвета. Останется единственная клетка цвета, которого было \(25\). Комментарий. На нечетной доске большинство имеют клетки того же цвета, что и углы. Пример 3. Диагональная раскраска по модулю \(3\) Прямое тримино требует не шахматной, а трехцветной раскраски. Задача. Можно ли покрыть прямыми тримино \(1\times3\) доску \(5\times5\), если удалена угловая клетка \((1,1)\)? Решение. Покрасим клетку \((i,j)\) по остатку \(i+j\pmod3\). Любое прямое тримино, горизонтальное или вертикальное, покрывает по одной клетке каждого цвета. На доске \(5\times5\) чисел цветов \(9,8,8\). Угловая клетка \((1,1)\) имеет цвет \(2\), поэтому после удаления получаются числа \(9,8,7\). Они не равны, значит, покрытия нет. Комментарий. Для прямых фигур длины \(3\) диагональная раскраска лучше, чем обычная шахматная. Пример 4. Полосы и направление домино Раскраска может учитывать не только форму, но и направление фигур. Задача. Можно ли покрыть доску \(6\times6\) домино так, чтобы ровно \(5\) домино стояли вертикально? Решение. Покрасим столбцы попеременно в черный и белый цвет. Горизонтальное домино покрывает одну черную и одну белую клетку. Вертикальное домино покрывает две клетки одного цвета. На всей доске черных и белых клеток поровну. Значит, вертикальные домино должны давать одинаковое число клеток черного и белого столбцовых цветов, то есть вертикальных домино в черных и белых столбцах должно быть поровну. Но всего вертикальных домино \(5\), а нечетное число нельзя разбить поровну. Нельзя. Комментарий. Эта идея часто появляется в задачах с ограничением на число горизонтальных или вертикальных плиток. Пример 5. Ход коня Раскраска работает не только для замощений, но и для движений. Задача. Конь стоит на черной клетке шахматной доски. Может ли он после \(9\) ходов снова оказаться на черной клетке? Решение. Каждый ход коня меняет цвет клетки. После нечетного числа ходов цвет будет противоположным начальному. Так как \(9\) нечетно, конь окажется на белой клетке, а не на черной. Комментарий. Здесь сохраняется не сам цвет, а связь между цветом и четностью числа ходов. Пример 6. Четырехцветная раскраска Для прямых тетрамино нужна раскраска по модулю \(4\). Задача. Можно ли покрыть прямыми тетрамино \(1\times4\) доску \(8\times8\), если удалены четыре угла? Решение. Покрасим клетку \((i,j)\) по остатку \(i+j\pmod4\). Любое прямое тетрамино покрывает по одной клетке каждого из четырех цветов. На полной доске \(8\times8\) каждого цвета по \(16\) клеток. Углы имеют цвета \(2,1,1,0\), поэтому после удаления четырех углов числа цветов уже не равны. Следовательно, замощение прямыми тетрамино невозможно. Комментарий. Обычная шахматная раскраска здесь не дает противоречия: удалены две черные и две белые клетки. Пример 7. Один мономино среди тримино Иногда раскраска не просто запрещает, а указывает, где должна быть особая клетка. Задача. Доску \(8\times8\) хотят покрыть \(21\) прямым тримино \(1\times3\) и одной отдельной клеткой. Докажите, что отдельная клетка должна иметь цвет \(0\) при раскраске \((i,j)\mapsto i+j\pmod3\). Решение. В этой раскраске каждое прямое тримино покрывает по одной клетке каждого цвета. Значит, \(21\) тримино покроют по \(21\) клетке каждого цвета. На доске \(8\times8\) цветов \(0,1,2\) соответственно \(22,21,21\). Единственная непокрытая тримино клетка должна быть лишней клеткой цвета \(0\). Комментарий. Это необходимое условие. Оно не утверждает автоматически, что такое покрытие существует. Пример 8. Когда две раскраски различаются по силе Сильная задача часто требует заменить привычную шахматную раскраску другой. Задача. С доски \(10\times10\) удалены все клетки обеих диагоналей. Можно ли покрыть оставшуюся область прямыми тетрамино \(1\times4\)? Решение. Площадь равна \(100-20=80\), она делится на \(4\). Шахматная раскраска тоже не дает противоречия: одна диагональ состоит из клеток одного цвета, другая из клеток другого цвета. Теперь покрасим клетку \((i,j)\) по остатку \(i+j\pmod4\). Прямое тетрамино покрывает по одной клетке каждого из четырех цветов. На полной доске \(10\times10\) цветов \(0,1,2,3\) соответственно \(25,24,25,26\). По двум диагоналям удаляются клетки цветов: на главной диагонали по \(5\) цветов \(0\) и \(2\), на побочной диагонали \(10\) клеток цвета \(3\). После удаления числа цветов не могут стать равными. Значит, покрытия нет. Комментарий. Смысл примера: если простая раскраска молчит, меняем раскраску.

Глава

Игры и стратегии I

Модуль вводит выигрышные и проигрышные позиции, остаточные стратегии, симметрию, пары, фиксированную длину игры и первые ним-идеи.

Ключевая идея В играх с полной информацией обычно ищут не один удачный ход, а класс позиций: выигрышные позиции, из которых есть ход в проигрышную, и проигрышные позиции, из которых любой ход ведет в выигрышную. Для первого уровня достаточно освоить четыре инструмента: остатки в играх с кучей камней, стратегию симметрии, стратегию пар и обратный разбор от конца игры. Основные факты Если из позиции есть ход в проигрышную позицию, то позиция выигрышная. Если все допустимые ходы ведут в выигрышные позиции, то позиция проигрышная. В игре «взять от \(1\) до \(k\) камней, последний выигрывает» проигрышны кратные \(k+1\). В игре «добавлять от \(1\) до \(k\), кто достиг цели, выигрывает» часто нужно сохранять суммы, отличающиеся на \(k+1\). Симметрия работает, если после хода соперника можно сделать отраженный ход, который всегда легален. Когда применять метод Нужно определить, кто выигрывает при правильной игре. В игре повторяются однотипные ходы с кучами, числами или клетками доски. Есть естественные пары объектов: числа с одинаковой суммой, симметричные клетки, равные кучи. Конец игры понятен, а начало кажется сложным. Тогда идем назад от проигрышных конечных позиций. Как распознать метод Если игра на одной куче, проверьте остатки. Если два игрока выбирают объекты из симметричного множества, ищите парную стратегию. Если доска имеет центр или ось симметрии, попробуйте зеркальный ответ. Если правила необычные, выпишите последние несколько позиций и отметьте их как выигрышные или проигрышные. Типичные ошибки Показывают хороший первый ход, но не объясняют, как отвечать дальше. Называют позицию проигрышной, не проверив все допустимые ходы из нее. Используют симметрию, но не доказывают, что отраженный ход не занят и разрешен. Путают обычную игру и вариант, где взявший последний камень проигрывает. В задачах на достижение числа забывают проверить первый ход и последнюю цель. Мини-чеклист Какие позиции являются конечными? Кто выигрывает или проигрывает в конечной позиции? Можно ли разбить позиции по остаткам? Есть ли симметрия или пары, которые можно сохранять? После любого хода соперника есть ли заранее описанный ответ? Доказана ли стратегия до конца игры, а не только первый ход?

Пример 1. Одна куча и остатки Самый важный первый шаблон: оставить сопернику кратное число. Задача. В куче \(20\) камней. За ход можно взять \(1\), \(2\) или \(3\) камня. Кто берет последний камень, выигрывает. Кто выигрывает? Решение. Проигрышные позиции: \(0,4,8,12,16,20\), то есть кратные \(4\). Из кратной \(4\) позиции любой ход оставляет не кратное \(4\), а из любой не кратной можно взять \(1\), \(2\) или \(3\) камня и оставить кратное \(4\). Число \(20\) кратно \(4\), значит первый игрок находится в проигрышной позиции, а второй выигрывает, каждый раз дополняя ход первого до \(4\) камней. Комментарий. Важно уметь доказать не только первый ответ, но и всю стратегию. Пример 2. Кто взял последний, проиграл Малое изменение правила меняет проигрышные остатки. Задача. В куче \(28\) камней. За ход можно взять от \(1\) до \(3\) камней. Игрок, взявший последний камень, проигрывает. Кто выигрывает? Решение. При таком правиле позиции \(1,5,9,13,17,21,25\) проигрышные: если остался \(1\) камень, игрок вынужден взять последний и проиграть; дальше работает шаг \(4\). Из позиции \(28\) первый берет \(3\) камня и оставляет \(25\), проигрышную позицию. Затем он каждый раз дополняет ход соперника до \(4\). В конце сопернику останется \(1\) камень. Комментарий. Перед решением всегда уточняйте, кто выигрывает при последнем ходе. Пример 3. Достичь числа Здесь цель - не оставить ноль, а управлять текущей суммой. Задача. Игроки по очереди прибавляют к текущей сумме число от \(1\) до \(6\). Начальная сумма \(0\). Кто первым получит \(50\), тот выигрывает. Кто выигрывает? Решение. Так как \(50\equiv1\pmod7\), первый игрок сначала прибавляет \(1\). После каждого хода соперника на \(a\), где \(1\le a\le6\), первый прибавляет \(7-a\). Тогда после ходов первого сумма будет \(1,8,15,\ldots,50\). Значит первый достигнет \(50\) и выиграет. Комментарий. Это та же идея дополнения, но примененная к суммам. Пример 4. Две равные кучи Парная стратегия часто означает: повторяй ход соперника в симметричной части. Задача. Есть две кучи по \(13\) камней. За ход можно взять любое положительное число камней из одной кучи. Кто берет последний камень, выигрывает. Докажите, что второй игрок выигрывает. Решение. После каждого хода первого во второй куче второй берет столько же камней из другой кучи. Равенство куч восстанавливается. Если первый смог сделать ход, то в одной куче были камни, а значит после симметричного ответа второй тоже делает легальный ход. Последний ход также будет сделан вторым. Комментарий. Позиции с равными двумя кучами проигрышны для игрока, который ходит. Пример 5. Симметрия на доске Симметричный ответ может быть полной стратегией. Задача. Игроки по очереди ставят фишки на пустые клетки доски \(5\times5\). Проигрывает тот, кто не может сделать ход. Кто выигрывает? Решение. Первый ставит фишку в центральную клетку. После этого на любой ход второго первый отвечает постановкой фишки в клетку, центрально-симметричную выбранной. Такая клетка не занята: если бы она была занята раньше, то вместе с ней была бы занята и клетка второго. Поэтому первый всегда имеет ответ и сделает последний ход. Комментарий. Нужно отдельно проверить, что отраженная клетка свободна. Пример 6. Разбиение на пары Стратегия пар работает даже без геометрии. Задача. Игроки по очереди выбирают по одному числу из \(1,2,\ldots,20\). После выбора всех чисел сравнивают суммы выбранных чисел; выигрывает тот, у кого сумма больше. Докажите, что второй может не проиграть. Решение. Второй заранее разбивает числа на пары с суммой \(21\): \((1,20),(2,19),\ldots,(10,11)\). Какое бы число ни выбрал первый, второй берет его пару. В каждой паре игроки получают по одному числу, значит суммарно у них будут равные суммы. Второй гарантирует ничью, то есть не проигрывает. Комментарий. Пары должны покрывать все объекты без пересечений. Пример 7. Ладьи на доске Иногда число ходов заранее фиксировано. Задача. Игроки по очереди ставят ладьи на доску \(7\times7\), причем никакие две ладьи не должны бить друг друга. Проигрывает тот, кто не может сделать ход. Кто выигрывает? Решение. После \(k\) ходов занято \(k\) строк и \(k\) столбцов. Пока \(k<7\), есть свободная строка и свободный столбец, значит можно поставить еще одну ладью. Поэтому игра всегда длится ровно \(7\) ходов. Последний, седьмой ход делает первый игрок. Он выигрывает. Комментарий. Это не стратегия выбора клетки, а доказательство фиксированной длины игры. Пример 8. Три кучи и ним-сумма Сильный предварительный пример показывает, куда метод будет развиваться дальше. Задача. Есть кучи \(3\), \(4\) и \(5\) камней. За ход можно взять любое положительное число камней из одной кучи. Кто берет последний камень, выигрывает. Найдите выигрышный ход. Решение. Используем побитовое сложение без переносов: \(3\oplus4\oplus5=2\). Нужно уменьшить одну кучу так, чтобы ним-сумма стала \(0\). Кучу \(3\) уменьшаем до \(1\), потому что \(1\oplus4\oplus5=0\). После этого на любой ход соперника можно снова восстановить ним-сумму \(0\). Значит выигрышный первый ход: \(3\to1\). Комментарий. Это лишь вводная версия ним-метода, но она полезна для сильных задач.

Глава

Графы I

Модуль вводит вершины, ребра, степени, формулу рукопожатий, связность, деревья, циклы, двудольные графы и первые экстремальные рассуждения.

Ключевая идея Граф - это способ заменить отношения между объектами на вершины и ребра. Люди и знакомства, города и дороги, команды и матчи, клетки и допустимые ходы часто становятся одной и той же схемой. Первый главный инструмент графов - сумма степеней: каждое ребро имеет два конца, поэтому \(\sum \deg(v)=2E\). Из этой простой формулы следуют четность числа нечетных степеней, оценки через среднее и многие задачи на невозможность. Основные факты Степень вершины - число ребер, выходящих из нее. В любом конечном неориентированном графе \(\sum \deg(v)=2E\). Число вершин нечетной степени всегда четно. В полном графе на \(n\) вершинах \(\binom{n}{2}\) ребер. Связный граф на \(n\) вершинах имеет не меньше \(n-1\) ребер; дерево имеет ровно \(n-1\) ребер. Двудольный граф не содержит циклов нечетной длины. Когда применять метод В задаче есть пары объектов: знакомые люди, дороги между городами, сыгранные матчи, возможные переходы. Нужно доказать, что какая-то система связей невозможна. Даны степени или количество связей, и нужно найти число ребер или противоречие. Нужно доказать существование вершины с большой или малой степенью. Есть запрет на треугольники, циклы или связи внутри двух групп. Как распознать метод Спросите: что будет вершинами, а что ребрами? Если связь взаимная, используйте неориентированный граф. Если связь направленная, это может быть турнир или ориентированный граф, но часто достаточно считать входящие и исходящие степени. Если в условии встречаются слова «каждый», «ровно», «не менее», «знаком с», «соединен с», почти всегда полезно выписать степени вершин и применить сумму степеней. Типичные ошибки Считают каждое ребро один раз в сумме степеней, хотя оно дает вклад \(2\). Путают количество ребер полного графа с \(n^2\) вместо \(\binom{n}{2}\). Доказывают связность, не исключив несколько компонент. Используют свойства деревьев для графов, в которых есть циклы. В задачах про знакомства забывают, что отношение обычно взаимное. Мини-чеклист Что является вершинами? Что является ребрами? Какие степени известны или ограничены? Что дает формула \(\sum \deg(v)=2E\)? Нужна ли связность, дерево, цикл или двудольность? Можно ли применить среднее: есть вершина степени не меньше или не больше среднего?

Пример 1. Сумма степеней Первое действие в графе - посчитать степени. Задача. В графе степени вершин равны \(2,3,3,4,4\). Сколько в графе ребер? Решение. Сумма степеней равна \(2+3+3+4+4=16\). Каждое ребро дает вклад \(2\) в сумму степеней, поэтому число ребер равно \(16/2=8\). Комментарий. Если сумма степеней нечетна, такого графа не существует. Пример 2. Нечетные степени Четность часто дает быстрое противоречие. Задача. Может ли в графе быть ровно \(5\) вершин нечетной степени? Решение. Нет. Сумма всех степеней равна \(2E\), то есть четна. Сумма четных степеней четна, значит сумма нечетных степеней тоже должна быть четной. Сумма \(5\) нечетных чисел нечетна. Противоречие. Комментарий. Отсюда следует: число вершин нечетной степени всегда четно. Пример 3. Полный граф Полный граф появляется, когда каждая пара объектов связана. Задача. Сколько ребер в полном графе на \(9\) вершинах? Решение. Каждое ребро задается парой вершин. Поэтому число ребер равно \(\binom{9}{2}=36\). Комментарий. Не считайте упорядоченные пары: ребро \(AB\) и \(BA\) одно и то же. Пример 4. Знакомства Графовая модель убирает лишний текст. Задача. В компании \(8\) человек каждый знаком ровно с \(3\) другими. Сколько всего пар знакомых? Решение. Построим граф: вершины - люди, ребра - пары знакомых. Сумма степеней равна \(8\cdot3=24\). Каждая пара знакомых посчитана дважды, значит пар \(24/2=12\). Комментарий. Взаимность знакомства важна: это неориентированный граф. Пример 5. Связный граф Связность требует хотя бы \(n-1\) ребер. Задача. Докажите, что связный граф на \(n\) вершинах имеет не меньше \(n-1\) ребер. Решение. Начнем с одной вершины и будем добавлять остальные вершины по одной вдоль пути из уже добавленной части. Чтобы новая вершина стала связанной с прежними, нужно хотя бы одно новое ребро. Для добавления \(n-1\) вершин нужно хотя бы \(n-1\) ребер. Комментарий. Равенство достигается на деревьях. Пример 6. Дерево имеет листья В дереве всегда есть вершины степени \(1\). Задача. Докажите, что в дереве с хотя бы двумя вершинами есть не менее двух листьев. Решение. Возьмем самый длинный простой путь в дереве. Если у одного его конца была бы степень больше \(1\), из него выходило бы ребро к вершине вне пути, иначе возник бы цикл или путь можно было бы продолжить. Это противоречит максимальности пути. Поэтому оба конца пути имеют степень \(1\). Комментарий. Аргумент с самым длинным путем встречается очень часто. Пример 7. Двудольность Двудольные графы распознаются через запрет нечетных циклов. Задача. Докажите, что в двудольном графе нет цикла нечетной длины. Решение. Пусть вершины разбиты на две доли, и каждое ребро идет между долями. При движении по циклу доли чередуются. Чтобы вернуться в начальную долю, нужно сделать четное число шагов. Значит длина любого цикла четна. Комментарий. Это тот же принцип чередования, что в раскраске шахматной доски. Пример 8. Маленький Рамсей Граф помогает доказывать утверждения о знакомствах и незнакомствах. Задача. Докажите, что среди любых \(6\) человек найдутся либо \(3\) попарно знакомых, либо \(3\) попарно незнакомых. Решение. Возьмем одного человека \(A\). Среди остальных \(5\) он либо знаком как минимум с \(3\), либо незнаком как минимум с \(3\). Пусть, например, он знаком с \(B,C,D\). Если среди \(B,C,D\) есть знакомая пара, то вместе с \(A\) получаем тройку попарно знакомых. Если знакомых пар среди них нет, то \(B,C,D\) попарно незнакомы. Случай трех незнакомых с \(A\) аналогичен. Комментарий. Это сильный пример, но структура доказательства очень короткая.

Глава

Рекурсии и последовательности

Модуль учит строить рекурсии по последнему шагу, последней плитке, последнему символу и последней точке пути, а также вводит дополнительные состояния.

Ключевая идея Рекурсия появляется, когда объект можно построить из меньшего объекта последним шагом. Вместо того чтобы сразу считать большой случай, мы вводим \(a_n\): число способов для размера \(n\), а затем выражаем \(a_n\) через предыдущие значения. В олимпиадных задачах важно не угадывать последовательность, а объяснять разбиение: по последнему шагу, последней плитке, последнему символу, последнему столбцу или последней точке пути. Основные факты Если последний шаг имеет длину \(1\) или \(2\), часто возникает \(a_n=a_{n-1}+a_{n-2}\). Замощения полосы \(2\times n\) домино дают ту же рекурсию Фибоначчи. Двоичные строки без соседних единиц удобно делить по последнему символу. Пути по решетке считаются рекурсией \(P(i,j)=P(i-1,j)+P(i,j-1)\) или формулой \(\binom{m+n}{m}\). Если одного состояния мало, вводят дополнительные состояния: например, «доска с одной дыркой справа». Когда применять метод Нужно посчитать число способов для длинной строки, полосы, лестницы или пути. Объект размера \(n\) естественно заканчивается одним из нескольких типов последних шагов. Малые случаи легко выписать, а общий случай похож на предыдущие. Прямой перебор быстро разрастается, но структура повторяется. Как распознать метод Спросите: как может выглядеть последний шаг? Если последний шаг удален, что осталось? Если осталось снова то же самое, нужна одна рекурсия. Если осталось несколько типов «почти той же» задачи, нужны несколько состояний. В задачах на строки смотрите на последний символ или последние два символа. В задачах на замощения смотрите на последний столбец. В задачах на пути смотрите, откуда пришли в последнюю клетку. Типичные ошибки Пишут рекурсию без начальных условий. Дважды считают объекты, когда случаи последнего шага пересекаются. Не проверяют малые значения \(n=0\), \(n=1\), хотя они нужны для рекурсии. Используют формулу Фибоначчи там, где есть третий тип последнего шага. В задачах на пути путают количество шагов с количеством точек решетки. Мини-чеклист Что обозначает \(a_n\)? Какие начальные значения нужны? По какому последнему элементу делим случаи? Случаи не пересекаются? Все варианты учтены? Нужно ли добавить второе состояние?

Пример 1. Лестница Последний шаг сразу дает рекурсию Фибоначчи. Задача. Сколькими способами можно подняться на \(7\) ступенек, если за раз можно подняться на \(1\) или \(2\) ступеньки? Решение. Пусть \(a_n\) - число способов подняться на \(n\) ступенек. Последний шаг был либо на \(1\) ступеньку из положения \(n-1\), либо на \(2\) ступеньки из положения \(n-2\). Поэтому \(a_n=a_{n-1}+a_{n-2}\). Начальные значения: \(a_0=1\), \(a_1=1\). Получаем \(a_2=2\), \(a_3=3\), \(a_4=5\), \(a_5=8\), \(a_6=13\), \(a_7=21\). Пример 2. Полоса \(2\times n\) Замощение домино имеет ту же структуру. Задача. Сколькими способами можно замостить доску \(2\times6\) домино? Решение. Пусть \(a_n\) - число замощений \(2\times n\). Последний столбец либо покрыт вертикальным домино, тогда остается \(2\times(n-1)\), либо последние два столбца покрыты двумя горизонтальными домино, тогда остается \(2\times(n-2)\). Поэтому \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=1\). Получаем \(a_6=13\). Пример 3. Двоичные строки Строки удобно делить по последнему символу. Задача. Сколько двоичных строк длины \(6\) не содержат двух соседних единиц? Решение. Пусть \(a_n\) - число таких строк длины \(n\). Если строка заканчивается на \(0\), перед ним может быть любая допустимая строка длины \(n-1\). Если строка заканчивается на \(1\), перед ним обязан стоять \(0\), и до этого идет допустимая строка длины \(n-2\). Значит \(a_n=a_{n-1}+a_{n-2}\). При \(a_0=1\), \(a_1=2\) получаем \(a_6=21\). Пример 4. Пути по решетке Последний шаг в точку приходит слева или снизу. Задача. Сколько кратчайших путей из \((0,0)\) в \((4,3)\), если можно идти только вправо и вверх? Решение. Всего нужно сделать \(4\) шагов вправо и \(3\) вверх, всего \(7\) шагов. Нужно выбрать места для \(4\) шагов вправо: \(\binom{7}{4}=35\). Пример 5. Путь через точку Иногда путь удобно разбить на две независимые части. Задача. Сколько кратчайших путей из \((0,0)\) в \((5,4)\) проходят через \((2,1)\)? Решение. До точки \((2,1)\) нужно сделать \(2\) шага вправо и \(1\) вверх: \(\binom{3}{1}=3\) пути. От \((2,1)\) до \((5,4)\) нужно сделать \(3\) шага вправо и \(3\) вверх: \(\binom{6}{3}=20\) путей. Итого \(3\cdot20=60\). Пример 6. Состав числа Разбиение по последнему слагаемому дает рекурсию с тремя предыдущими членами. Задача. Сколькими способами можно представить \(8\) как сумму слагаемых \(1\), \(2\), \(3\), если порядок важен? Решение. Пусть \(a_n\) - число способов получить сумму \(n\). Последнее слагаемое равно \(1\), \(2\) или \(3\), поэтому \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\). При \(a_0=1\), \(a_1=1\), \(a_2=2\) получаем \(a_3=4\), \(a_4=7\), \(a_5=13\), \(a_6=24\), \(a_7=44\), \(a_8=81\). Пример 7. Запрещенные три нуля Иногда нужно смотреть на последний блок. Задача. Сколько двоичных строк длины \(7\) не содержат трех нулей подряд? Решение. Пусть \(a_n\) - число таких строк. Допустимая строка заканчивается либо на \(1\), либо на \(01\), либо на \(001\), если рассматривать последний блок нулей перед последней единицей; для концов строки это дает ту же рекурсию \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\). Начальные значения: \(a_0=1\), \(a_1=2\), \(a_2=4\). Тогда \(a_7=81\). Пример 8. Дополнительное состояние Для сложного замощения одной переменной уже мало. Задача. Доску \(2\times n\) замощают домино и L-тримино. Объясните, зачем вводить второе состояние. Решение. Пусть \(A_n\) - число полных замощений \(2\times n\), а \(B_n\) - число замощений доски \(2\times n\) с одной удаленной угловой клеткой справа. Тогда последний блок может оставлять или закрывать такую «дырку», и рекурсии имеют вид \(B_n=A_{n-2}+B_{n-1}\), \(A_n=A_{n-1}+A_{n-2}+2B_{n-1}\). Второе состояние нужно, потому что после удаления L-тримино часто остается не прямоугольник, а почти прямоугольник.

Глава

Смешанные задачи I

Модуль тренирует выбор метода без подсказки темы: счет, Дирихле, инварианты, раскраски, игры, графы, пути и рекурсии.

Ключевая идея В смешанных задачах метод не написан в условии. Задача ученика - распознать структуру: что здесь надо считать, что разбивать на случаи, где искать ящики, что сохраняется, какую раскраску выбрать, есть ли игра, граф или рекурсия. Главная привычка: перед вычислениями задать вопрос «какой тип объекта здесь повторяется?» Если повторяются выборы - счет. Если объектов больше, чем типов - Дирихле. Если есть операции - инвариант. Если доска - раскраска. Если связи - граф. Если размер растет - рекурсия. Основные факты Метод выбирается по структуре, а не по словам в условии. Сначала ищите простой инвариант или простой счет; сложный метод нужен не всегда. Если нужно доказать существование, проверьте среднее, Дирихле или графовые степени. Если нужно доказать невозможность, проверьте четность, остатки, раскраску или сумму. Если нужно посчитать семейство объектов размера \(n\), ищите последний шаг и рекурсию. Когда применять метод После изучения нескольких тем, когда условие больше не указывает технику. Перед олимпиадным вариантом, где задачи идут в произвольном порядке. Когда первый очевидный подход дает много хаотичных случаев. Как распознать метод Составьте короткую диагностику: считаем варианты или доказываем существование? Есть ли повторяющаяся операция? Есть ли доска? Есть ли отношение между парами объектов? Можно ли удалить последний элемент и получить меньшую такую же задачу? Если два метода кажутся возможными, начинайте с более грубого: четность, остатки, сумма, среднее. Часто он сразу объясняет, почему задача устроена именно так. Типичные ошибки Узнают знакомую тему и применяют ее механически, не проверив условия. Пытаются считать напрямую там, где нужна дополнительная раскраска или инвариант. В задачах существования забывают сформулировать «ящики» или среднее. В играх называют первый ход, но не описывают стратегию дальше. В рекурсиях не доказывают, что случаи последнего шага не пересекаются. Мини-чеклист Что требуется: найти число, доказать существование, доказать невозможность или построить стратегию? Какие объекты повторяются? Есть ли естественные ящики, цвета, степени, остатки? Можно ли свести задачу к меньшему размеру? Проверены ли крайние случаи? Решение объясняет выбор метода?

Пример 1. Сначала диагностируем В условии нет слова «Дирихле», но оно прячется в остатках. Задача. Докажите, что среди любых \(8\) целых чисел найдутся два, разность которых делится на \(7\). Решение. Рассмотрим остатки чисел при делении на \(7\). Остатков всего \(7\), а чисел \(8\). По принципу Дирихле два числа имеют одинаковый остаток. Их разность делится на \(7\). Комментарий. Сигнал метода: больше объектов, чем типов. Пример 2. Не считать все покрытия Доска почти всегда просит раскраску. Задача. Можно ли покрыть домино доску \(6\times6\), если удалены две клетки главной диагонали? Решение. Все клетки главной диагонали имеют один цвет в шахматной раскраске. После удаления двух таких клеток цветов стало не поровну. Каждое домино покрывает одну клетку каждого цвета. Поэтому покрытие невозможно. Комментарий. Сигнал метода: доска и домино. Пример 3. Операция значит инвариант Если конфигурация меняется повторяемым ходом, ищем сохраняемую величину. Задача. На доске записано \(11\) плюсов. За ход меняют знаки у двух символов. Можно ли получить ровно один минус? Решение. Произведение всех знаков при смене двух знаков не меняется. В начале произведение равно \(+1\), а при одном минусе равно \(-1\). Значит получить такую конфигурацию нельзя. Комментарий. Сигнал метода: разрешенная операция. Пример 4. Слишком много связей В графовой задаче степени часто дают среднее. Задача. В графе \(9\) вершин и \(23\) ребра. Докажите, что есть вершина степени не меньше \(6\). Решение. Сумма степеней равна \(46\). Средняя степень равна \(46/9>5\). Если бы все степени были не больше \(5\), сумма была бы не больше \(45\). Значит есть вершина степени хотя бы \(6\). Комментарий. Сигнал метода: связи между парами объектов. Пример 5. Игра без перебора В играх ищем контрольные позиции. Задача. В куче \(41\) камень. За ход берут от \(1\) до \(4\). Последний ход выигрывает. Кто выигрывает? Решение. Проигрышны кратные \(5\). Так как \(41\equiv1\pmod5\), первый берет \(1\) камень и оставляет \(40\). Затем он дополняет ход соперника до \(5\). Первый выигрывает. Комментарий. Сигнал метода: правильная игра и повторяемые ходы. Пример 6. Рекурсия по последнему шагу Если размер меняется, ищем меньшую задачу. Задача. Сколько строк длины \(7\) из нулей и единиц не содержат двух соседних единиц? Решение. Пусть \(a_n\) - число таких строк. Строка заканчивается на \(0\) или на \(01\), поэтому \(a_n=a_{n-1}+a_{n-2}\). При \(a_0=1\), \(a_1=2\) получаем \(a_7=34\). Комментарий. Сигнал метода: семейство объектов длины \(n\). Пример 7. Путь через условие Иногда счет проще через дополнение. Задача. Сколько кратчайших путей из \((0,0)\) в \((4,4)\) не проходят через \((2,2)\)? Решение. Всего путей \(\binom{8}{4}=70\). Через \((2,2)\) проходят \(\binom{4}{2}\cdot\binom{4}{2}=36\). Значит не проходят \(70-36=34\). Комментарий. Сигнал метода: пути и запрещенная точка. Пример 8. Смешанный финал Иногда метод выбирается только после первого упрощения. Задача. В компании \(10\) человек каждый знаком не менее чем с \(6\) другими. Докажите, что найдутся трое попарно знакомых. Решение. Возьмем человека \(A\). У него есть хотя бы \(6\) знакомых. Если среди этих знакомых есть знакомая пара, то вместе с \(A\) получаем тройку. Если среди них нет знакомых пар, то каждый из этих \(6\) людей знаком с \(A\) и может быть знаком только с тремя людьми вне этой шестерки и вне \(A\), то есть его степень не больше \(4\), что противоречит условию \(6\). Комментарий. Это уже графовый экстремальный ход.

Глава

Пробные олимпиады I

Модуль содержит шесть мини-вариантов по четыре задачи для тренировки выбора метода и оформления решения.

Пример 1. Счет без перебора В пробном варианте первая задача часто решается правильным порядком выбора. Задача. Сколько четырехзначных чисел с различными цифрами можно составить из \(1,2,3,4,5\), если число должно быть нечетным? Решение. Последняя цифра должна быть \(1\), \(3\) или \(5\): \(3\) выбора. Остальные три позиции заполняются без повторений из оставшихся \(4\) цифр: \(4\cdot3\cdot2\). Итого \(3\cdot4\cdot3\cdot2=72\). Пример 2. Быстрый Дирихле Если объектов на один больше, чем типов, решение должно быть коротким. Задача. Докажите, что среди \(13\) человек найдутся двое, родившиеся в один месяц. Решение. Месяцев \(12\), людей \(13\). По принципу Дирихле два человека попадают в один месяц. Пример 3. Инвариант вместо поисков Операции редко требуют перебора всех состояний. Задача. На доске написано \(0\). За ход можно прибавить \(6\) или вычесть \(9\). Можно ли получить \(100\)? Решение. Оба изменения кратны \(3\), значит остаток по модулю \(3\) сохраняется. Был остаток \(0\), а \(100\equiv1\pmod3\). Получить \(100\) нельзя. Пример 4. Раскраска Доски нужно проверять цветом даже после проверки площади. Задача. Можно ли покрыть домино доску \(8\times8\) без двух противоположных углов? Решение. Противоположные углы одного цвета. После удаления цветов не поровну, а домино всегда покрывает одну черную и одну белую клетку. Поэтому нельзя. Пример 5. Игра В игре нужен не ответ, а стратегия. Задача. В куче \(29\) камней. За ход берут от \(1\) до \(4\). Последний ход выигрывает. Кто выигрывает? Решение. \(29\equiv4\pmod5\), поэтому первый берет \(4\) и оставляет \(25\). Далее он дополняет ход соперника до \(5\). Первый выигрывает. Пример 6. Граф Связи между парами почти всегда превращаются в граф. Задача. В графе \(8\) вершин и \(17\) ребер. Докажите, что есть вершина степени не меньше \(5\). Решение. Сумма степеней \(34\), средняя степень \(34/8>4\). Значит хотя бы одна вершина имеет степень не меньше \(5\).