План подготовки к олимпиадам по математике в Казахстане (Комбинаторика)

Содержание

• Лицензия
• Авторы Плана
• Введение
  • Problem Solving Strategies by Arthur Engel
  • Combinatorical Problems in Mathematical Competitions by Yao Zhang
• Подсчёт двумя способами
• Теория графов
• Принцип Дирихле
• Производящие функции
• Нелёгкая книга по комбинаторике
• Теория вероятностей

Лицензия

Настоящий план подготовки является предметом интеллектуальной собственности ОФ Beyond Curriculum и лицензирован под условиями CC BY-NC-ND 4.0 . Вы можете распространять этот план подготовки частично или целиком при следующих условиях: вы обязаны указать правообладателя (BY, ОФ "Beyond Curriculum") с активной ссылкой на первоисточник, при этом, вы не можете видоизменять план подготовки (ND) и вы должны использовать его исключительно в некоммерческих целях (NC).

Напоминаем, что Республика Казахстан (как и многие другие страны) присоединилась к Бернской конвенции Законом РК № 297-1 от 10.11.1998 г., и конвенция вступила в законную силу с 12 апреля 1999 года. Согласно данной конвенции, страны участницы уважают авторское право других стран участниц в той же мере, в которой они уважают авторские права своих граждан.

Авторы Плана

Идеи и материалы этого плана были предоставлены Мырзатай Айбеком и отредактированы Арсланом Даминовым. Айбек — золотой медалист IMO, абсолютный чемпион и золотой медалист республиканских олимпиад, абсолютный чемпион и золотой медалист IZhO. Арслан — серебряный медалист IZhO, АПМО, МОШП и республиканских олимпиад.

IZhO — Международная Жаутыковская олимпиада, IMO — Международная Математическая олимпиада (самая престижная в мире), BMO — Балканская Математическая олимпиада, АПМО — Азиатская Тихоокеанская Математическая олимпиада, МОШП — Международная Олимпиада Шелковый Путь.

Введение

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

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

Стоит сказать, что не существует конкретного плана подготовки, изучив которые вы станете успешно выступать на олимпиадах. Одна из причин — это то, что разным людям нужно разное кол-во времени для усвоения материала: одним достаточно 10 задач, чтобы понять общую суть метода, когда как другим на это понадобится 20-30 задач. Наша логика была в том, что лучше дать больше материалов для закрепления, чем меньше, поэтому если у вас возникает чувство, что задачи легкие — пропускайте их. И помните, что цель состоит не в изучении максимального кол-ва книг или статей, а в получении максимального объёма математических навыков и знаний, а уж как вы будете их добывать — решать вам, мы лишь даем рекомендации.

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

1. Chapter 7: Counting in Two Ways — Combinatorial Problems in Mathematical Competitions by Yao Zhang

2. Counting in Two Ways (MOP 2007 Black Group) by Yufei Zhao (ненужные части были вырезаны)

   Примечание: здесь следует решать только примеры.

3. Chapter 6: Counting in Two Ways — Olympiad Combinatorics by Pranav Sriram

Теория графов

Очень много задач можно свести к графам, даже если на первый взгляд этот раздел не имеет ничего общего с задачей. Идеи теории графов можно применять в любых задачи, в которых можно определить ребра и вершины. Также советуем посмотреть две статьи из Problems from the Book by Titu Andreescu, которые мы привели.

1. Hall's Marriage Theorem by Carl Joshua Quines
2. Подборка красивых задач на графы
3. Chapter 6: Some Classical Problems in Extremal Graph Theory — Problems from the Book by Titu Andreescu
4. Chapter 22: Cycles, Paths, and Other Ways — Problems from the Book by Titu Andreescu

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

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

1. Chapter 20: A Pigeonhole Principle Revisited — Problems from the Book by Titu Andreescu

Производящие функции

Хоть производящие функции и являются алгебраическим понятием, они помогают работать с комбинаторными объектами, что бывает полезным не только в комбинаторике, но и в теории чисел. Идея, заложенная в производящие функции, очень красива, и скорее всего вы получите удовольствие при решении задач на эту тему. Также хочется отметить, что задачи с применением производящих функций часто требуют понимания поведения корней из единицы и алгебраических чисел (чаще всего для Root Unity Filter), что вы можете узнать в 5-ой секции теории по многочленам.

1. Chapter 3: The Generating Functions — Combinatorial Problems in Mathematical Competitions by Yao Zhang

2. Lecture 11: Generating Functions — Awesome Math 2007 by Yufei Zhao

3. Snake oil method: Evaluation of sums

4. Chapter 7: Complex Combinatorics — Problems from the Book by Titu Andreescu

5. Chapter 8: Formal Series Revisited — Problems from the Book by Titu Andreescu

   Примечание: главы 7 и 8 опциональны, но красивы.

6. Generatingfunctionology by Herbert S. Wilf и Topics in Generating Functions by Qiaochu Yuan

   Примечание: Эти книги являются полными курсами по производящим функциям. Если вы не собираетесь становится профессором математики, вряд ли вам это понадобится. Вы можете воспринимать их как справочники, на случай если вам будет сложно найти решение к какой-то задаче в первых пяти источниках.

Нелёгкая книга по комбинаторике

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

1. Olympiad Combinatorics by Pranav Sriram

Форум по обсуждению задач из Olympiad Combinatorics by Pranav Sriram — AoPS.

Объявление о возможности скачать эту книгу вызвало обсуждение задачи и под этим постом.

Теория вероятностей

Вероятность делится на дискретную и вещественную. Формула для дискретной вероятности возникновения некоторого события является количество исходов при возникновении данного исхода деленное на общее количество возможных исходов. Проблемы возникают в тех случаях, когда количество и тех и других является бесконечностью. Такая вероятность называется вещественной. Один из примеров такой вероятности — это шанс того, что случайно выбранная точка на отрезке $[0, 1]$ будет лежать на отрезке $[0, 0.5]$. Может показаться весьма очевидным то, что вероятность этого события равна $0.5$, однако, не зная точного определения вероятности, вы можете легко запутаться, а также прийти к многим противоречиям, особенно при решении олимпиадных задач. Да что уж там говорить, множество значимых математиков в истории сталкивались с противоречиям, одна из которых была найдена Бертраном. Современное определение вероятности — это очень сложое для понимания определение, названное как аксиоматика Колмогорова.

Вообще, в олимпиадной математике вам будет достаточно хорошего понимания дискретной теории вероятностей, а также поверхностное понимание общепринятой (вещественной) теории вероятностей. Вещественный теорвер (так математики называют теорию вероятностей) решает очень специфичный тип задач, который вы можете встретить только в подборках, в то время как дискретный теорвер может применяться как в задачах по комбинаторике, так и в задачах по теории чисел. Следует понимать, что дискретный теорвер не предусмотрен для использования в олимпиадах, и его изучение полностью факультативно. Оно бывает полезным в задачах по комбинаторике и может вывести нужный результат пропуская рассуждения вида подсчёта двумя способами (в пример можно взять задачу Example 2.1 из статьи Evan Chen’а “Expected Uses of Probability”.

Изучать теорию вероятностей можно в том случае, если вы хотите расширить кругозор, а также укрепить понимание подсчёта двумя способами в комбинаторике. Советуется не изучать эту тему, если у вас остаётся мало дней до значимой олимпиады или если вы имеете слабую базу в олимпиадной математике.

Развить общее понимание дискретного теорвера поможет [1] до §3.2. Эти знания можно попробовать применить в задачах из [2] (в [2] решать геометрию не стоит). Затем вы уже можете дочитать до конца статью [1], решив сложные задачи для вас из раздела Practice Problems. Если вам нравятся сложные задачи, то можете продолжить ваше обучение через [3].

В секции Algebra в [2] нужно быть знакомым с такими понятиями как Распределения случайной величины $X$, Плотность распределения случайной величины $X$, Функция распределения, Математическое ожидание абсолютно непрерывной случайной величины $X$ (мы готовим из вас статистика!). Пусть эти понятия и звучат сложными, но на деле они интуитивно понятны, особенно при понимании поведения интегралов функций. Их можно будет скоро изучить в An Infinitely Large Napkin от Evan Chen-а (когда выйдет обновление на книгу).

Также при возникновении трудностей вы можете заглядывать в [4], используя его как справочник. К слову множество задач из первых трёх ресурсов были взяты оттуда.

1. Expected Uses of Probability by Evan Chen
2. Unexpected Uses of Probability by Ravi Boppana
3. Chapter 9: Probabilistic Method — Olympiad Combinatorics by Pranav Sriram
4. The Probabilistic Method by Noga Alon and Joel H. Spencer