Комбинаторика в группах 9 и 10-го класов.
Первая половина - 10 классы, группы Провода и Трубы. Мне помогали Аскар Назмутдинов и Владислав Новиков.
Вторая половина - 9 классы, группы Гвозди, Шурупы и Винты. Мне помогали Артур Герасименко и Юлий Тихонов.
Одноименные листки сильно пересекаются, но в менее опытных группах Шурупы и Винты задачи в среднем попроще.
10 класс |
Естественный алгоритм
|
1 апреля |
Провода и Трубы: doc pdf
|
|
|
Естественный алгоритм легко найти, но трудно поверить или проверить, что он срабатывает (осуществим, достигает цели, оптимален).
|
10 класс |
Свяжитесь с графом
|
2 апреля |
Трубы: doc pdf
|
|
|
Увидеть граф за условием задачи помогают выделенные пары объектов, в частности, соседние объекты или клетки с общей границей. Выписывая для таких графов уравнения и неравенства для вершин, рёбер и компонентах связности, можно получать нетривиальные оценки.
|
10 класс |
Индукция
|
3 апреля |
Трубы: doc pdf
|
|
|
Если конструкция для n+1 не единственна, то связь с конструкцией для n надо осуществлять «спуском из n+1», а не «подъёмом из n». В частности, надо убедиться, что всякая конструкция для n+1 получается из конструкции для n. Из такого индукционного рассуждения затем часто получают «обратным ходом» построение снизу вверх.
|
10 класс |
Фазовое пространство
|
3 апреля |
|
Провода: doc pdf
|
|
Фазовое пространство – это наглядное геометрическое представление множества вариантов. Классическое фазовое пространство получаем, заменяя пары чисел точками координатной плоскости, а тройки чисел – точками пространства. Рассуждениям помогают графики и непрерывность.
|
10 класс |
Испытания и оценки
|
4 апреля |
Трубы: doc pdf
|
|
|
Чаще всего перед нами ситуация одного неизвестного варианта из некоторого множества (пространства) возможных элементарных вариантов. В задачах попроще варианты совпадали с предметами, но это не обязательно. Полезно выписать все возможные варианты и делать такие испытания, чтобы количество подозрительных вариантов в наихудшем случае было как можно меньше.
|
10 класс |
Бесконечные алгоритмы
|
4 апреля |
|
Провода: doc pdf
|
|
Бесконечный объект часто строят индуктивно, последовательно наращивая конечный объект. Обычно есть бесконечно много вариантов наращивания, а число запретов конечно в каждый момент. Индуктивное построение может вестись группами, когда один из объектов группы – обязательный (например, минимальный из непостроенных), а остальные – вспомогательные.
|
10 класс |
Двудольные графы
|
5 апреля |
Трубы: doc pdf
|
|
|
|
10 класс |
Конструкции с подсчетами и доводкой
|
5 апреля |
|
Провода: doc pdf
|
|
Понять, как такое могло быть, помогают подсчеты. Результаты можно и нужно использовать при построении. Сначала строим неполноценную конструкцию, а потом её подправляем.
|
10 класс |
Испытания: индукция и графы
|
6 апреля |
Трубы: doc pdf
|
|
|
Каждое испытание сводит задачу к меньшему числу случаев. Обратный ходом от меньшего к большему по индукции получаем искомый алгоритм и нетривиальную рекуррентную оценку на число случаев и другие подобные величины. Испытание можно считать ребром графа. Тогда оценка на число ребер в графе позволит оценить число испытаний.
|
10 класс |
Комбинаторная геометрия: оценки площади и периметра
|
6 апреля |
|
Провода: doc pdf
|
|
Связь площади и периметр через радиус вписанного круга, сюжеты вокруг. Накрытие и вырезание из треугольника симметричной фигуры.
|
9 класс |
Неоднозначные данные
|
8 апреля |
|
Шурупы: doc pdf
|
Винты: doc pdf
|
Чтобы доказать недостаток данных, постройте два примера: оба удовлетворяют условиям, но дают разные ответы.
|
9 класс |
Свяжитесь с графом
|
9 апреля |
|
Шурупы: doc pdf
|
Винты: doc pdf
|
В графе карты вершинами служат области, а ребром считается общая граница. Выписывая для таких графов уравнения и неравенства для вершин, рёбер и компонент связности, можно получать нетривиальные оценки.
|
9 класс |
Неоднозначные данные
|
11 апреля |
Гвозди: doc pdf
|
|
|
Чтобы доказать недостаток данных, постройте два примера: оба удовлетворяют условиям, но дают разные ответы./FONT>
|
9 класс |
Увидеть граф
|
11 апреля |
|
Шурупы: doc pdf
|
|
Увидеть граф за условием задачи помогают выделенные пары объектов. Применяя теоремы для подсчета степеней вершин и числа рёбер, можно получать нетривиальные оценки.
|
9 класс |
Увидеть граф
|
12 апреля |
|
|
Винты: doc pdf
|
Увидеть граф за условием задачи помогают выделенные пары объектов. Применяя теоремы для подсчета степеней вершин и числа рёбер, можно получать нетривиальные оценки.
|
9 класс |
Свяжитесь с графом
|
12 апреля |
Гвозди: doc pdf
|
|
|
В графе карты вершинами служат области, а ребром считается общая граница. Выписывая для таких графов уравнения и неравенства для вершин, рёбер и компонент связности, можно получать нетривиальные оценки.
|
9 класс |
Увидеть граф
|
12 апреля |
Гвозди: doc pdf
|
|
|
Увидеть граф за условием задачи помогают выделенные пары объектов. Применяя теоремы для подсчета степеней вершин и числа рёбер, можно получать нетривиальные оценки.
|