Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду

• Название: Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
• Дата: 19.09.2022
• Размер: 3.42 Mb.
• Имя файла: matprob.pdf
• Тип: Сборник; #684321
• страница: 28 из 31

Где живут треугольники?
Еще, быть может, каждый атом Вселенная, где сто планет;
Там все, что здесь, в объеме сжатом,
А также то, чего здесь нет.
В. Брюсов
Из-за обилия случаев расположения прямых все попытки в них разобраться потерпели неудачу. Попробуем двигать прямые. Ради линейности будем двигать их параллельно самим себе. Что может произойти?
Пока прямые не проходят через точки пересечения других прямых,
картина в принципе не меняется. Но если несколько точек пересечения совпадут — произойдет катастрофа, — исчезнет один или несколько треугольников. После катастрофы произойдет перестройка, результат которой непредсказуем (рис. Рис. 5. Гибель одного треугольника и рождение трех при движении горизонтальной прямой

Треугольники и катастрофы
455
Поэтому доводить дело до катастрофы мы не будем, а остановимся заодно мгновение до нее, тогда треугольники не исчезнут и не появятся, а лишь сильно уменьшатся. То, что получится, назовем фокусом прямых. Фокус, таким образом, это несколько прямых, все точки взаимного пересечения которых лежат в малой области, почти точке, причем эта область не пересекается с другими прямыми (рис. Рис. 6. Два фокуса
Для нас особенно важно, что в фокусе наблюдается разбиение плоскости в миниатюре, нос меньшим числом прямых. Иначе говоря, фокусы это обособленные миры, в которых живут свои собственные крошечные треугольники. Поэтому если удастся развалить картинку на фокусы, то треугольники станет легче считать (поскольку для меньшего числа прямых задачу можно считать решенной по предположению индукции).
Вернемся к индукции
Итак, предположение индукции состоит в том, что любые k прямых при k < n разбивают плоскость на части, среди которых не меньше, чем k − 2 треугольника. Значит, в фокусе из k < n прямых найдутся k − 2
треугольника.
Пусть, к примеру, двигая прямые, нам удалось их все собрать в два фокуса в один — с й пою, в другой — с й пою, причем я прямая — общая. Тогда в фокусах наберется − 2) + (n − k + 1 − 2) = n − треугольника, и для индукционного перехода надо найти еще один треугольник вне фокусов. Однако удастся ли нам все прямые собрать ровно в два фокуса К сожалению, нет. А когда фокусов много, возникает разнообразие случаев. Что делать

Гл. 14. Комбинаторная геометрия

Где границы возможного?
Исследуем процесс образования фокусов. Вначале прямые могут двигаться независимо, но если образовался фокус, то его надо сохранять, те. прямые фокуса двигать как одно целое в виде ежа (мы запрещаем прямым фокуса двигаться относительно друг друга для того,
чтобы, во-первых, предотвратить катастрофу, а во-вторых, сохранить разбиение плоскости в миниатюре. Фокусы (почти точки) могут дополняться новыми прямыми или объединяться (в одну почти точку, а их сохранение будет все сильнее ограничивать свободу движения и, наконец, все возможности двигать прямые будут исчерпаны. При этом надо избежать стягивания всей картинки в один фокус (чтобы применить индукцию по числу прямых. Достаточно, например, зафиксировать две точки пересечения (чтобы они не попали в один фокус).
Теперь поймем, как связаны скорости прямых водном фокусе. Две прямые можно двигать произвольно, а остальные должны под них подстраиваться (рассмотрите случай трех прямых. Иначе говоря, сохранение фокуса из k прямых требует k − 2 соотношений между их скоростями. Нов этом же фокусе, по нашему предположению, найдутся k − 2 треугольника, — столько, сколько соотношений. Не здесь ли ключ к решению?
Попробуем оценить число треугольников через число соотношений в конечном состоянии (когда прямые потеряют подвижность. Вначале мы закрепили одну прямую и две точки пересечения на ней, те, фактически, три прямые. У нас остались n − 3 свободные прямые. Будем фокусировать их до упора. Для сохранения фокусов потребуется n − соотношения. По предположению индукции число треугольников в каждом фокусе не меньше числа соотношений, значит всего треугольников не меньше, чем n − Осталось найти еще один треугольник. Всего один, где-то между фокусами. Но как его искать — неясно...
Заключительный аккорд
Подумаем: если нам нужен еще один треугольник, то зачем его искать Нельзя ли сделать так, чтобы он был с самого начала Нам-то ведь все равно, какие три прямые зафиксировать вначале. Давайте зафиксируем те, которые уже образуют треугольник Задача решена!
Чистка решения
Наша работа еще далеко не окончена чтобы записать решение, надо наши рассуждения очистить, усовершенствовать и сделать строгими.
Важно понять связь между треугольниками и фокусами, в частности

Треугольники и катастрофы
457
почему число треугольников в фокусе не меньше числа соотношений,
нужных для его сохранения. Докажите с помощью движения одной прямой, что к ней примыкает треугольник.
Итак, мы сначала закрепили один произвольно выбранный треугольник это спасло нас от общего коллапса и дало треугольник вне фокусов. Ане сохранить ли нам, ради равноправия, сразу все треугольники Тогда при движении прямых фокусы вообще не появятся (поскольку в фокусе существует треугольник, который до этого сжимался, т. е.
не сохранялся).
Однако если картинка окажется нежесткой, то при некотором движении фокус все же появится. Это будет противоречием. Значит, сохранение всех треугольников гарантирует жесткость картинки, и нам достаточно показать, что, сохраняя меньше, чем n − 2 треугольника,
нельзя добиться жесткости.
Вспомним, как мы сохраняли фокус разрешали ему двигаться как целому. Простейший фокус — это треугольник. Поступим с обычным треугольником также разрешим перемещаться, но сохраним размер.
(Проверьте, что полное фиксирование n/3 треугольников может привести к потере подвижности прямых.)
Но теперь мы не зафиксировали полностью и начальный треугольник, поэтому, чтобы избавиться от неинтересных параллельных переносов всей картинки, закрепим две прямые. (Кстати, положение фокуса тоже определялось двумя прямыми.)
Каждый треугольник дает одно соотношение для скоростей прямых.
Следовательно, сколько мы сохраним треугольников столько получим соотношений.
Итак, надо выбрать n − 2 скорости, которые мы назовем параметрами. Если треугольников меньше числа параметров, то сохранение их размеров не обеспечит жесткости (рис. Но почему, если нет жесткости, можно получить фокус А вот почему. У нас, как ив задаче про пятиугольник, есть возможность двигать
Рис. 7. Сохраняя верхний треугольник, можно сжимать нижний

Гл. 14. Комбинаторная геометрия прямые в обратную сторону, те. менять знаки всех скоростей на противоположные, поэтому можно направить одну из прямых к точке пересечения закрепленных прямых, и тогда фокус неминуем. (Забавно, что при чистке решения индукция исчезла, как исчезают строительные леса при возведении зданий.)
Суммируем...
Сначала мы закрепили две прямые, а остальным разрешили двигаться с постоянными скоростями так, чтобы размеры всех треугольников сохранялись. Тогда если треугольников окажется меньше, чем n − то скорости некоторых прямых можно выбрать ненулевыми (будет доказано. Меняя, если надо, направления всех скоростей, можно создать фокус, где и обнаружится неучтенный треугольник. Противоречие.
Уточним рассуждения
Чтобы получить строгое доказательство, необходимо уточнить наши интуитивные рассуждения, и прежде всего — о жесткости. Переведем их на язык алгебры, где скорости — неизвестные, а соотношения — уравнения для них. Подвижность прямых означает, что существует ненулевое решение системы уравнений.
Каждый, кто возился с системами, знает, что, как правило, если число уравнений равно числу неизвестных, то система имеет конечное множество решений если уравнений больше, чем неизвестных (переопределенная система, то решений нет если уравнений меньше, чем неизвестных (недоопределенная система, то решений бесконечно много. Последним соображением мы и воспользовались. К сожалению, эти соображения верны только как правило. Например, система + y + z = 1,
x + y + z = решений не имеет, хотя число уравнений в ней меньше числа неизвестных. Однако в частном случае, когда все уравнения линейные и однородные, справедлива следующая теорема.
Теорема. Недоопределенная система m линейных однородных уравнений с n неизвестными (m < n)









a
11
x
1
+ a
12
x
2
+ . . . + a
1n x
n
= 0,
a
21
x
1
+ a
22
x
2
+ . . . + a
2n x
n
= 0,
a m1
x
1
+ a m2
x
2
+ . . . + a mn x
n
= имеет бесконечно много решений (а значит, имеет ненулевое

Треугольники и катастрофы
459
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
Рис. 8. Три параллелограмма. S
ADF C
+ S
BCF E
= Докажите эту теорему по индукции, последовательно избавляясь от неизвестных методом подстановки. (Доказательство можно найти в любом курсе линейной алгебры.)
Переведем разговоры о соотношениях для скоростей прямых на язык линейных уравнений (скорость прямой — это скорость ее удаления от начального положения).
Можно убедиться (выражая координаты или векторы, что точка пересечения двух прямых, движущихся с постоянными скоростями, тоже движется с постоянной скоростью и стороны треугольника меняются с постоянными скоростями, откуда вывести, что условие сохранения размера треугольника выражается линейным однородным уравнением для скоростей прямых.
Докажем последнее утверждение геометрически. При параллельном переносе треугольника образуются три параллелограмма (рис. 8), причем площадь одного из них равна сумме площадей остальных. Площадь параллелограмма есть произведение стороны треугольника на величину сдвига прямой.
Будем считать направление сдвига прямой положительным, если треугольник растет. Тогда условие равенства площадей параллелограммов можно записать в виде линейного однородного уравнения a
1
h
1
+ a
2
h
2
+ a
3
h
3
= 0, где a
1
, a
2
, a
3
— стороны треугольника, h
1
, h
2
,
h
3
— сдвиги прямых в ортогональном направлении. Таким же точно уравнением связаны и скорости прямых.
Итак, условие сохранения всех треугольников — это система линейных однородных уравнений. Как видите, линейность принесла плоды.
Упражнение 15. Покажите, что в системе координат (x, y) в момент времени t уравнение прямой, движущейся со скоростью v, можно записать в виде x sin u − y cos u = c − vt, где u — угол наклона прямой коси абсцисс

Гл. 14. Комбинаторная геометрия
Строгое доказательство
В заключение приведем строгое доказательство, в котором, как это и принято в серьезной литературе, скрыты все повороты мысли. Такие тексты напоминают ребусы или компьютерные программы без комментариев. Их смысл, по выражению академика В. И. Арнольда, подобно притчам, разъясняют лишь ученикам наедине.
Допустим, что число k треугольников разбиения меньше, чем n − Пусть d — минимальная из высот треугольников v
1
, . . . , v n
— скорости прямых в перпендикулярных направлениях, причем v
1
= v
2
= Условие сохранения размеров всех треугольников равносильно системе линейных однородных уравнений для скоростей v i
(i = 3, . . . , которая (согласно теореме) имеет ненулевое решение.
Можно считать (поменяв, если надо, направление времени, что некоторая прямая l движется в сторону точки пересечения прямых и Существует момент (катастрофа, когда три или больше прямых проходят через одну точку. Пусть t — первый такой момент, тогда в момент найдутся три прямые, которые образуют непересеченный треугольник с высотой меньше d. Это противоречит сохранению размеров всех треугольников. Утверждение доказано.
Замечания
1. Условие задачи о треугольниках обобщается для пространств любого числа измерений, в частности если в трехмерном пространстве провели n плоскостей общего положения, то среди частей разбиения пространства найдутся не меньше, чем n − 3 тетраэдра. (Почему треугольников, а тетраэдров n − 3? Что будет в одномерном случае. Просматривая решение, можно убедиться, что требование общего положения прямых можно ослабить если среди n прямых на плоскости любые две пересекаются и не все прямые проходят через одну точку, то среди частей разбиения плоскости найдутся n − 2 треугольника.
Главное отличие в доказательстве состоит в том, что в процессе движения могут разрушаться точки многократного пересечения прямых,
и тогда возникнут новые треугольники. Но эти треугольники будут расти с постоянной скоростью, и их легко отличить от искомого треугольника, который сжимается в точку.
Проведите соответствующие рассуждения самостоятельно

МОСКОВСКИЕ ВЫЕЗДНЫЕ
МАТЕМАТИЧЕСКИЕ ШКОЛЫ
А. Б. Скопенков
Es ist unm¨
oglich sagt die Erfahrung
Es ist was es ist sagt die Liebe.
Erich Fried. Was es Весной 2004 года возобновлена замечательная традиция проведения выездных Школ команды Москвы на Всероссийскую математическую олимпиаду (хотя формального решения о регулярном проведении Школ не принято. Школы проводятся Московским институтом открытого образования и Московским центром непрерывного математического образования. Эти школы продолжают замечательные традиции московских, ленинградско-петербургских, кировских, костромских,
краснодарско-южнороссийских и других летних школ.
Школы проводятся вначале ноября, начале апреля ив июле. Весенняя и осенняя школы проводятся для 9 –11 классов, а летняя — для перешедших в 9–10 классы.
Основная цель Школ — обучение математике высшего уровня. Обучение проходит в основном в форме решения и обсуждения интересных задач. Формулировки этих задач либо ясны школьникам, либо предва- ряются кратким теоретическим введением. Однако эти задачи подобраны так, что в процессе их решения и обсуждения ученики знакомятся с важными математическими идеями и теориями. Такое обучение одновременно готовит ученика и к математической науке, и к математическим олимпиадам, а также полезно для его развития в целом
1)
Полную версию статьи см. на сайте О ближайшей школе см. по адресу www.mccme.ru/circles/oim/SHKOLA.pdf. Обновляемая версия информации о школах и материалов занятий находится на сайте www.mccme.ru/circles/ Подробнее см. заметки А. Б. Скопенкова Олимпиады и математика и «Фило- софско-методическое отступление вначале данного сборника

Московские выездные математические школы
Кроме указанных тематических занятий, проводится сдача задач»:
школьники, находясь в аудитории, могут записывать решения задач,
решать устные задачи поуже пройденным темами сдавать их присутствующему на занятии преподавателю.
Чтобы разнообразить стиль занятий и заодно потренировать школьников к олимпиадам, разв несколько дней проводятся тренировочные олимпиады. На них каждый школьник решает варианты, близкие ква- риантам московских или всероссийских олимпиад или сборов (в зависимости от ближайшей олимпиады, в которой этому школьнику предстоит участвовать).
Чтобы научиться ясно записывать (в частности, проверять и уточнять) свои мыслимы учим школьников записывать решения задач
(примерно по одной вдень) настолько ясно, чтобы текст было не стыдно опубликовать.
Всего имеется ориентировочно 3 – 4,5 часов аудиторных занятий и 0–2 часа самостоятельных занятий вдень (расписания прошлых школ см. в приложении. Участники каждой школы делятся на группы в соответствии с уровнем подготовленности и возрастом. На каждом занятии школьникам предлагается подборка задач по некоторой теме. Как правило, ключевые задачи самостоятельно решаются некоторыми школьниками и после этого разбираются, а остальные сдаются школьниками как на занятии, таки после него. Впрочем, стиль проведения занятий зависит от конкретного преподавателя. Преподаватели Школы — и замечательные математики, и классные преподаватели, и члены жюри олимпиад высшего уровня как студенты, таки профессиональные математики, и учителя. Многие из них являются авторами настоящего сборника.
Настоящий результат такого обучения виден не сразу. Однако достигнуть высокой долгосрочной цели трудно, если не поставить конкретную доступную промежуточную цель. Участники школы получают зачет по итогам своей работы, и сдача зачета необходима для приглашения в следующие школы (см. зачетные требования в приложении. Одинаковые минимальные требования ко всем (без исключения)