Подробнее о преподавателях 7 класса
Смена организована И.С.Рубановым. Я веду занятия почти исключительно в группе 7 класса совместно с С.Г.Волченковым, Л.А.Емельяновым и Р.С.Ефремовым. Мои отдельные занятия в группах 8 класса выделены цветом.
|
Тест |
1 июня |
10 задач на краткий ответ. |
|
|
Много не мало, или Мнимые противоречия |
2 июня |
Много и мало – понятия относительные. Если надо выигрывать чаще, а силы равны, то надо много раз выиграть по чуть-чуть, а проиграть много, но один раз. |
|
|
Эйлеровы пути и обходы-1 |
2 июня |
Связь существования путей и обходов по всем ребрам с четностью кружковцам хорошо известна, необходимость очевидна. В процессе обсуждения неожиданно выясняется, что у них есть средства доказать и достаточность, и алгоритм Флёри обхода графа по эйлеровому циклу. |
|
|
Жадный алгоритм |
2 июня |
Если цель – максимум какой-то величины, то ее часто достигают с помощью «жадного алгоритма», то есть добиваясь максимально возможного приращения на каждом шаге. А если цель – максимум числа шагов на фиксированном расстоянии, то жадный алгоритм советует выбирать самые короткие шаги. |
|
|
Разворачивание сумм и произведений |
3 июня |
Метод телескопических сумм: представьте все слагаемые в виде разности так, чтобы в «развернутой» сумме почти все члены взаимно уничтожились с соседями. Кажется, что это применимо только к небольшому списку искусственно подобранных сумм. Однако, если мы «подозреваем» формулу F(n) для суммы n первых членов, это немедленно дает нам представление n-го члена как разности F(n)-F(n-1) |
|
|
Площадь целого и частей |
3 июня |
Одну и ту же площадь можно посчитать многими способами. Сравнивая результаты, можно получать нетривиальные следствия в виде равенств и неравенств. |
|
|
Эйлеровы пути и обходы-2 |
3 июня |
"Игрушечный" факт о рисовании одним росчерком пера помогает решать и задачи потруднее. |
|
|
Индуктивные конструкции |
4 июня |
Многоэтажные здания строят, ставя по очереди следующий этаж на предыдущий. В математике этому соответствует индуктивное построение, когда, например, конструкция для n+1 строится из конструкции для n. Бывают конструкции, где удобнее надстраивать сразу по нескольку этажей. |
|
|
Посредники в неравенствах |
4 июня |
Чтобы доказать неравенство A<B, можно выбрать посредник P и доказать, например, A<P и P≤B. Искусство состоит в выборе P. Можно выбирать несколько посредников: отдельные посредники для слагаемых или сомножителей, или цепочку посредников. |
|
|
Формула Пика |
4 июня |
Формула Пика для площади многоугольника с вершинами в узлах квадратной сетки. Вывод её даёт пример построения маленькой теории. Данное доказательство основано на разбиении многоугольника на треугольники без узлов внутри. |
|
|
Гамильтоновы пути |
5 июня |
Гамильтонов путь в графе проходит ровно по разу через все его вершины. Такой путь есть во многих "естественных" графах, в частности, в графах платновых тел. Однако нет общего критерия существования гамильтонова пути. Теорема Дирака гарантирует существование его для некоторой категории графов. |
|
|
ГМТ и замечательные точки треугольника |
5 июня |
Принадлежность точки ГМТ часто дает равенство. Пересечение двух ГМТ дает два равенства, они влекут третье. Значит, через точку проходит и третье ГМТ. Так доказывается пересечение серединных перпендикуляров, биссектрисс, медиан, а также теорема Чевы. |
|
|
Уравнение за кадром |
5 июня |
Важнее заметить и написать уравнение или систему уравнений, чем его/их решить. Методы решения известны и стандартны, а правильно составить (и применить решение) можно только по-настоящему разобравшись в задаче. Когда переменных слишком много, стоит выделять их группы, ведущие себя одинаково, и обозначать сумму группы за новое неизвестное – тогда уравнения упрощаются. Кроме сумм, часто годятся произведения или суммы произведений. |
|
|
Гамильтоновы пути-2 |
7 июня |
Доказательство теоремы Дирака о существовании гамильтонова пути в графах с достаточно большой степенью вершин. |
|
|
Целочисленные неравенства |
7 июня |
По сравнению с обычными, целочисленные неравенства обладают дополнительными свойствами: |
|
|
Решётки |
7 июня |
Продолжение темы, начатой формулой Пика (см. 4 июня). Изучается, какие правильные многоугольники можно разместить на клетчатой плоскости так, чтобы их вершины попали в узлы квадратной сетки. |
|
|
Непрерывная комбинаторика-1: |
|
В некоторых задачах возникают комбинации из конечного числа объектов, но сами объекты выбираются из бесконечного набора, заданного непрерывным параметром или параметрами. Решение обычно состоит в комбинировании неравенств. Этому помогает наглядное представление в виде наборов точек на прямой и окружности, и применения для полученных отрезков и дуг принципа Дирихле. |
|
|
Слепые алгоритмы |
8 июня |
В "слепых" алгоритмах нет или почти нет обратной связи: надо добиться конечного результата, не зная почти ничего о результатах отдельных шагов. |
|
|
Разрезания и счет углов |
8 июня |
В задачах на разрезание узким местом часто служат углы. Особенно это касается разрезаний не по клеточкам. |
|
|
Относительное движение |
8 июня |
Если все персонажи движутся равномерно и прямолинейно (или по кругу с постоянными скоростями), часто выгодно одного из них объявить неподвижным и рассматривать движение остальных относительно него. |
|
|
Непрерывная комбинаторика-1: |
|
В некоторых задачах возникают комбинации из конечного числа объектов, но сами объекты выбираются из бесконечного набора, заданного непрерывным параметром или параметрами. Решение обычно состоит в комбинировании неравенств. Этому помогает наглядное представление в виде наборов точек на прямой и окружности, и применения для полученных отрезков и дуг принципа Дирихле. |
|
|
Гамильтоновы пути-3: Турниры |
9 июня |
Условия существования гамильтоновых путей и обходов в ориентированных графах, где каждые две вершины связаны ровно одним ребром. |
|
|
Покрытия |
9 июня |
Покрывающие фигуры могут пересекаться и вылезать за края. Невозможность покрытия доказывают, выделяя подмножество, которое невозможно покрыть (узкое место). При покрытии помогают посредники и разбиение на части: нужную фигуру покрывают по частям. |
|
|
Сортировки |
9 и 11 июня |
Поиск алгоритмов сортировки и оценка их сложности. Попутно доказана лемма Холла о свадьбах. |
|
|
Взаимное расположение |
10 июня |
При построении чертежа в геометричсекой задаче бывает важно знать, в каком порядке следуют точки на прямой, лежат ли они по одну или по разные стороны прямой, пересекает ли прямая сторону или её продолжение и т.п. |
|
|
Неравенство помогает уравнению |
10 июня |
При решении задач, сводящихся к уравнениям (особенно целочисленным) часто помогает предварительное исследование с помощью неравенств. |
|
|
Непрерывная комбинаторика-1: |
|
В некоторых задачах возникают комбинации из конечного числа объектов, но сами объекты выбираются из бесконечного набора, заданного непрерывным параметром или параметрами. Решение обычно состоит в комбинировании неравенств. Этому помогает наглядное представление в виде наборов точек на прямой и окружности, и применения для полученных отрезков и дуг принципа Дирихле. |
|
|
Неравенство треугольника и его площадь |
11 июня |
Составление треугольника из трех одноименных отрезков: медиан, высот, биссектрис. Как меняется его площадь при согласованном изменении сторон? |
|
|
Редукция |
11 июня |
Не решается задача – реши её упрощённый вариант. Оттуда можно взять и результат, и метод. Результат – простая конструкция – может стать частью конструкции сложной задачи, послужить основой или строительным блоком. Так, первый этаж – важная часть многоэтажки. Но и двухэтажный дом может стать частью могоэтажного. Научившись надстраивать этаж, мы свели постройку трехэтажного дома к постройке двухэтажного. Такое сведение называют ещё редукцией. Цепочка редукций сведёт постройку могоэтажного дома к постройке одноэтажного: такой приём называют индукцией. |
|
|
Треугольник Жергонна |
13 июня |
Радиусы вписанной и вневписных окружностей прямоугольного треугольника. Обращение формул радиусов. Треугольник Жергонна. Определение, свойства, углы, направление сторон, гомотетия с треугольником из центров внеписанных окружностей. Внешние треугольники Жергонна. Аналогия с внутренним треугольником Жергонна. |
|
|
Свяжитесь с графом |
13 июня |
Выкинем из графа все ребра, будем восстанавливать их по одному и следить за числом компонент. Так получим неравенство, связывающее число вершин, ребер и компонент. Это неравенство позволяет получать оценки в ситуации, когда удается ситуацию описать с помощью графа (порой, весьма неожиданно). |
|
|
Линейные представления целых чисел |
13 и 14 июня |
Всякое целое число, кратное НОД(a, b), представляется в виде xa+yb, где x,y - целые. К поиску целых или натуральных x и y сводятся многие задачи. |
|
|
Непрерывная комбинаторика-2: порядок и комбинирование |
|
В некоторых задачах возникают комбинации из конечного числа объектов, но сами объекты выбираются из бесконечного набора, заданного непрерывным параметром или параметрами. Решение обычно состоит в комбинировании неравенств. Этому помогает расстановка объектов по возрастанию параметра. |
|
|
Задача о беспризорнике Васе и окурках |
14 июня |
|
|
|
Перевод на другой язык (изоморфизм) |
14 июня |
Задача, переведенная на другой язык, может оказаться гораздо легче. Не забудьте только перевести решение обратно! Переводят обычно на знакомый язык, где начинает работать интуиция! Переводят и для того, чтобы обойти препятствие: так, туристы, идущие вдоль берега и натолкнувшиеся на скалы, могут обойти их, временно переправившись на другой берег. |
|
|
Непрерывная комбинаторика-2: порядок и комбинирование |
|
В некоторых задачах возникают комбинации из конечного числа объектов нецелого веса. Важный прием – упорядочить объекты по весу. Это помогает комбинировать их в пары и группы. Группы, в свою очередь, тоже можно комбинировать. |
|
|
Неоднозначные данные |
15 июня |
Чтобы доказать, что информации недостаточно для получения однозначного ответа, можно построить два примера, которые удовлетворяют всем условиям, но дают разные ответы. Неразличимые примеры и контрпримеры могут строится после того, как испытания уже проведены и ответы даны, с использованием уже полученной информации. Этот метод часто применяется, чтобы опровергнуть предположение о наличие «гарантированного» алгоритма. |
|
|
Китайская теорема об остатках |
15 июня |
|
|
|
Теремы Чевы и Менелая |
15 июня |
|
|
|
Непрерывная комбинаторика-3: Процессы и игры. |
|
В некоторых задачах возникают комбинации из конечного числа объектов нецелого веса. В играх и других процессах часто помогает принцип крайнего. |
|
|
Индукция.Спуск по лестнице |
16 июня |
Когда число объектов растет с ростом n, индукция похожа карабкание по ветвящемуся дереву. Будешь тупо подниматься вверх – промахнешься. Чтобы установить связь между уровнями n+1 и n, надо начинать с объекта на уровне n+1 и уже для него подбирать подходящий объект на уровне n. Но так мы делаем при спуске с дерева, нащупывая ветку ногой! |
|
|
Равномерное распределение ресурса |
16 июня |
Задачи на оценку+пример для недискретных величин. Неожиданно оказывается, что "справедливое" или "жадное" распределение оказывается самым выгодным. |
|
|
Задача об Очень Быстрой Собаке |
16 июня |
|
|
|
Индукция.Доказывай больше. |
17 июня |
Не получается шаг индукции? При этом связь между ступеньками есть, но её немного не хватает для доказательства? Расширьте ступеньку: поменяйте утверждение индукции. Добавленная часть – это строительные леса, в конце концов мы их уберем, но процесс строительства они облегчают. |
|
|
Подмена объекта |
17 июня |
Объекты или величины, о которых говорится в условии задачи, могут оказаться не самыми удобными для решения. Бывает выгодно их заменить на другие, похожие, лучше отражающие суть задачи. Примеры таких замен мы уже видели в занятии про изоморфизм. |
|
|
Графики в задачах на движение |
17 июня |
|
|
|
Симметричные части |
19 июня |
Геометрические задачи на разрезания и покрытия, где части не заданы явно, а только сказано что это "равнобедренные треугольники" или "симметричные фигуры". Здесь остается достаточно много свободы, чтобы развивать фантазию, и достаточно много ограничений, чтобы решение не бросалось в глаза и было, где применить знанияе геометрии. |
|
|
Модули |
19 июня |
|
|
|
Игры: Дополнительные приемы |
20 июня |
Кроме парных стратегий, передачи хода и дерева игры («ставь на минус»), бывают еще игры-шутки и игра на опережение.
В шутках побеждает всегда одна из сторон независимо от ее желания. Часто число ходов неизменно, и победа зависит только от его четности. В серьезных играх один из игроков удачным ходом сводит игру к игре-шутке, когда уже ни соперник, ни сам игрок не смогут предотвратить его победы. В почти шутке допустим любой ход, если нет выигрыша в один ход или вы не даёте противнику выигрыш в один ход. |
|
|
Средние и смеси |
20 и 21 июня |
|
|
|
Непрерывная комбинаторика-1: |
|
В некоторых задачах возникают комбинации из конечного числа объектов, но сами объекты выбираются из бесконечного набора, заданного непрерывным параметром или параметрами. Решение обычно состоит в комбинировании неравенств. Этому помогает наглядное представление в виде наборов точек на прямой и окружности, и применения для полученных отрезков и дуг принципа Дирихле. |
|
|
Разнобой |
|
Самостоятельное решение и прием неразобранных задач из моих листков. |
|
|
Теоретические вопросы к зачету |
|
Зачет проводится письменно: 1 теоретический вопрос (каждому свой) и единая для всех олимпиада. |
|
|
Заключительная олимпиада |
|
Олимпиада проводилась письменно: сразу выдавались 4 задачи, а после сдачи их решений выдавалась 5-я. |