А.В.Шаповалов =>Занятия и кружки=>Московские сборы

2012 осень

2013 весна

2013 осень

2014 весна

2014 осень

2015 весна

2018 осень



Сборы московских школьников
с 1 по 13 апреля 2019 г.
в лагере "Команда"

Комбинаторика в группах 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

 

 

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