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

Сборы московских школьников
с 30 марта по 10 апреля 2015 г.
в лагере "Команда"

Комбинаторика в группах 9-го класса Белые ферзи и Чёрные ферзи. Мне помогает Аскар Назмутдинов.
Одноименные листки сильно пересекаются, но группа Белые ферзи менее опытная, поэтому задачи там в среднем проще.

Пишите

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