Занятия двух групп: 9-1(Эверест) и 9-2(Монблан). Листки сильно пересекаются, но группа Монблан менее опытная, поэтому задачи там в среднем чуть проще.
|
Группа «Эверест» |
Группа «Монблан» |
|
31 марта Задача, переведенная на другой язык, может оказаться гораздо легче. Надо знать "типовых переводчиков": метод координат, метод шаров и перегородок. Геометрические задачи можно перевести в алгебраические, введя координаты. Но с помощью координат можно и алгебраические задачи решать на геометрическом языке! |
|
|
1 апреля Переводят для того, чтобы обойти препятствие: так, туристы, идущие вдоль берега и натолкнувшиеся на скалы, могут обойти их, временно переправившись на другой берег. |
1 апреля Задача, переведенная на другой язык, может оказаться гораздо легче. Не забудьте только перевести решение обратно! Переводят обычно на знакомый язык, где начинает работать интуиция. |
|
2 апреля Если есть строгий полуинвариант, то позиция не может повториться (и, в частности, процесс не может зациклиться). Если полуинвариант может принимать лишь конечное число значений, или убывает, принимая лишь натуральные значения, то он достигнет «крайнего» значения. |
2 апреля Полуинвариант – это связанное с позицией число, которое при разрешенных действиях все время растет или все время убывает (возможно, нестрого). Типичные полуинварианты: сумма, произведение, модуль разности, сумма модулей, сумма квадратов. |
|
3 апреля Есть набор позиций (состояний) и переходы между ними. Пусть с каждой позицией можно связать инвариант: величину, которая при переходах не меняется. Значения инварианта разбивают граф позиций на компоненты связности. Между позициями с разными значениями инварианта маршрутов нет. Типичные инварианты: четность, общий делитель, сумма. |
3 апреля Кодировка устанавливается взаимно-однозначное соответствие между объектами (состояниями) из задачи и стандартными комбинаторными комбинациями. В частности, соответствие последовательностям из 0 и 1 называют двоичной кодировкой. |
|
4 апреля Если какая-то целочисленная величина в процессе меняется на каждом шаге не больше чем на 1 (в ту или другую сторону), то она обязательно проходит через все промежуточные значения между начальным и конечным. Если процесса нет, организуй сам. Подбери начало и конец процесса так, чтобы они были по разные стороны от нужного значения. |
4 апреля Соответствие между множествами позволяет подсчитывать элементы "удобного" множества вместо элементов "неудобного". Соответствие между решениями разных уравнений устанавливается заменой переменных. |
|
5 апреля |
4 задачи по алгебре, теории чисел, комбинаторике и геометрии. Для каждой указана решаемость, то есть доля набранных баллов по отношению к возможному максимуму. |
|
7 апреля Доказать, что фигура Ф покрывает фигуру Q можно через посредника: Ф покрывает П, а П покрывает Q. При покрытии несколькими фигурами полезно разрезать Q на части-посредники. |
7 апреля Есть набор позиций (состояний) и переходы между ними. Пусть с каждой позицией можно связать величину, которая при переходах обычно не меняется: например, четность, общий делитель, сумма. Если есть путь с разными значениями на концах, то есть и переход, меняющий значение. |
|
8 апреля Вместо запуска процесса "последовательного улучшения" удобнее рассмотреть случай с экстремальным значением полуинварианта, например, с минимальным количеством плохих пар. |
8 апреля Доказать, что фигура Ф покрывает фигуру Q можно через посредника: Ф покрывает П, а П покрывает Q. При покрытии несколькими фигурами полезно разрезать Q на части-посредники. |
9 апреля 2-я олимпиада
|
5 задач по алгебре, теории чисел, комбинаторике и геометрии. Не самые сложные, но с подвохами. |
|
10 апреля Чтобы доказать, что информации недостаточно для получения однозначного ответа, можно построить два примера, которые удовлетворяют всем условиям, но дают разные ответы. |
10 апреля Комбигеометрия: оценки периметра и площади Для доказательства неравенств про периметр можно использовать площадь, и наоборот. |
|
11 апреля Индуктивное построение, "целься сверху", редукция и рекурсия. |
11 апреля Чтобы доказать, что информации недостаточно для получения однозначного ответа, можно построить два примера, которые удовлетворяют всем условиям, но дают разные ответы. |
|
12 апреля Если нет минимального контрпримера, то нет никакого. |
12 апреля Вместо запуска процесса "последовательного улучшения" удобнее рассмотреть случай с экстремальным значением полуинварианта, например, с минимальным количеством плохих пар. |