Бесплатная открытая неделя подготовки к к Перечневым олимпиадам: выполняй условия из поста [ Ссылка ]
Материалы: [ Ссылка ]
Курсы олимпиадной математики
Перечень 10-11: [ Ссылка ]
ВсОШ 8-9 класс: [ Ссылка ]
ВсОШ 10-11 класс: [ Ссылка ]
Кружок 4-7 класс: [ Ссылка ]
Открытая неделя Перечня в апреле завершилась, но доступна в записи: [ Ссылка ]
Открытая неделя курса ВсОШ в мае завершилась, но доступна в записи: [ Ссылка ]
Телеграм Дмитрия Алексеевича👉🏻[ Ссылка ]
Группа ВК по олимпиадной математике 👉🏻[ Ссылка ]
Тайм-коды!
0:00 Что будет на этом вебе? Обязательно ли всем-всем сидеть 5 часов?
3:43 Графы. Вершины, рёбра, степень вершины
6:06 Задача 1. Граф государства. Вершины – города, рёбра – дороги. Подсчёт количества рёбер
8:09 Лемма о рукопожатиях. Общий случай подсчёта из предыдущей задачи
11:20 Задача 2. Рисуем графы-1. Граф шахматного коня. Цикл и изолированная вершина. Идея чередования цветов
21:10 Задача 3 [ОММО, 2020]. Рисуем графы-2. Кратные рёбра. Построение графа по степеням вершин и выкидывание готовых для удобного рисунка
32:35 Задача 4. Отрезки на плоскости и при чём тут графы. Вершины – отрезки, рёбра – пересечение отрезков. Противоречие с леммой о рукопожатиях
37:20 Задача 5. Граф из простых чисел с соответствующими степенями вершин. Единственное чётное простое
40:46 Задача 6. Связный граф. Удаление ребра и сохранение связности. Когда удобно решать от противного?
49:40 Задача 7. Полный граф. Раскраска полного графа. Идея посмотреть на все рёбра одного цвета
58:24 Задача 8. Мешочки со значениями степеней вершин, принцип Дирихле и спасающая лемма о рукопожатиях
1:06:44 Задача 9. Ищем конструкцию: полный граф на 4-ёх вершинах. Идея что-то начать набирать
1:17:19 Задача 10. Ищем конструкцию: цикл на 4-ёх вершинах. Произвольный Артём и проблемы с существованием Бориса
1:31:03 Задача 11 [Курчатов, 2017, 8 класс]. Двудольный граф и двойной подсчёт. Ищем конструкцию: два школьника, решившие всё. Вершина максимальной степени
1:43:50 Задача 12 [Высшая Проба, 2017, 9 класс]. Ориентированный граф. Двойной подсчёт стрелочек
1:50:24 Задача 13. Идея подсчёта треугольников: на каждом ребре 5 и посчитали всё 3 раза. Комба помогает доказать делимость!
1:59:17 Задача 14 [Ломоносов, 2016, 7–9 класс]. Отсутствие треугольников и 6 галочек на антиребре. Двойной подсчёт интересных нам конструкций с антиребром
2:21:18 Задача 15. Идея ранжирования графа – подвешиваем граф за вершину. Оценка количества вершин на каждом ранге и max вершин во всём графе
2:33:24 Задача 16. Удаление вершины в связном графе с сохранением связности. Удаляем вершину с последнего ранга!
2:38:57 Задача 17. Оценка количества вершин снизу на 2-ом ранге с помощью отсутствия каких-то циклов. Сложно догадаться до ранжирования!
2:45:40 Задача 18. Двудольный граф. Критерий двудольности об отсутствии нечётных циклов. Идея чередования долей и снова ранжирование
3:00:22 Задача 19 [Всеросс, 1993, округ, 11.8]. Минимальное количество рёбер в пути – намёк на ранжирование! Тройки рангов
3:16:16 Задача 20. Гуляем по графу-1. Граф, в котором степень каждой вершины = 2: вошли и вышли!
3:24:02 Задача 21. Гуляем по графу-2. Простой цикл. Из-за чего мы не можем продолжить путешествие? Самая ранняя вершина
3:36:34 Задача 23. Гуляем по графу-3. Существование чётного цикла. Работа с чётностью индексов в пути
3:46:40 Паросочетание. Определение. Перерывчик
4:00:01 Задача 24. Принцип крайнего: выбираем максимальное паросочетание. Работа с рёбрами от оставшихся вершин и общая оценка рёбер
4:05:56 Задача 25. Выделение паросочетания на всех вершинах. Вновь максимальное паросочетание. Две вершины не из паросочетания и количество рёбер из них
4:14:33 Задача 26 [Одна задача, чтобы стать призёром Турнира Городов-2009]. Максимальное паросочетание. Идём в вершину вне паросочетания, затем всегда ходить по рёбрам паросочетания
4:27:30 Задача 27 [Лемма Холла]. Критерий выделения паросочетания на всех вершинах одной доли двудольного графа. Неженатый парень, все девушки, с которыми он знаком, все их мужья и так далее – устраиваем переженитьбу!
4:52:36 Задача 28. Разбиение двух квадратов на равновеликие части, наложение и протыкание. Вершины – куски, рёбра – частичное наложение. Красивое применение леммы Холла!
5:03:25 Задача 30 [Самая сложная задача Всеросса–2006]. Размышления и анализ. Хотим покрасить, чтобы ВСЕ соседи были разных цветов. Что-то вроде ранжирования
5:20:17 Формальное решение. Убираем часть рёбер, чтобы степени остались от 20 до 70. Неожиданное появление леммы Холла! На кого влияет цвет пилотки пионера? Подсчёт запретов на цвет пионера. Фуууф!
