Большая часть курса посвящена методам решения задач на графы, наиболее часто встречающихся на экзаменах в ШАД. Также обсуждаются такие базовые темы, как делимость, комбинаторика, индукция, игры, информация. Часть теории носит характер ликбеза и необходима любому изучающему математику, в частности, для полноценного освоения других курсов Школы.
Длительность предмета 4 недели.
1 неделя
Теория чисел.
Делимость, сравнения по модулю, алгоритм Евклида, линейные диофантовы уравнения, китайская теорема об остатках. Простые и составные числа, основная теорема арифметики. Функция Эйлера.
2 неделя
Комбинаторика.
Перестановки, размещения, сочетания с повторения и без. Бином Ньютона, треугольник Паскаля. Формула включений и исключений. Линейные рекуррентные последовательности и комбинаторные задачи, к ним приводящие, числа Фибоначчи.
3 неделя
Графы.
Степень вершины, лемма о рукопожатиях. Связные графы, циклы, деревья. Двудольные графы, теорема Холла о свадьбах. Эйлеровы и гамильтоновы графы. Раскраски графов. Ориентированные графы.
4 неделя
Информация и игры.
Задачи на упорядочение, взвешивания, отгадывание чисел, выигрышные стратегии.