Федоров Р.М., Канель-Белов А.Я., Ковальджи А.К., Ященко И.В. Московские математические олимпиады 1993-2005

Подождите немного. Документ загружается.

О геометрических олимпиадных задачах 411

Аналогично,

|CA

= b

+ 2a

+ 2ab(sin −cos ).

Оба выражения достигают максимума в точке = 135

◦

ибо sin −cos =

√

2 cos(135

◦

− ). Значит,

max(|CA

|+ |CB

|) =

= (b

+ 2a

+ 2

√

2 ab)

1/2

+ (a

+ 2b

+ 2

√

2 ab)

1/2

√

2 a +

√

2 b + a + b = (

√

2 + 1)(a + b),

откуда по следствию 2 получаем, что

max(|OM|+ |ON|) =

√

2 + 1

(a + b).

Мы видим, что все эти четыре задачи являются вполне

школьными: для их решения не требуется ничего, кро-

ме небольшого набора геометрических фактов, которые на

протяжении веков преподаются в школе.

Однако не все олимпиадные задачи с геометрическим

содержанием таковы. Приведем две нестандартные зада-

чи из той же LVI олимпиады, которые оказались столь

трудными, что на олимпиаде их никто не решил, и более

того, корректное решение первой из них не было известно

почти до сдачи в набор данной книги. Вот эта задача.

10 класс, задача 3. От любой точки на любом из двух

берегов реки можно доплыть до другого берега, проплыв

не более одного километра. Всегда ли лоцман может про-

вести корабль вдоль реки так, чтобы находиться все время

на расстоянии не более чем а) 700 метров, б)* 800 метров

от каждого из берегов? П р и м е ч а н и е. Известно, что

река соединяет два круглых озера радиусом 10 километ-

ров каждое, а береговые линии состоят из отрезков и дуг

окружностей. Корабль следует считать точкой.

Хочу предложить свой план решения. То, что 700 м не

удовлетворяют условию задачи, хорошо и просто объясне-

но на с. 110. Докажем, что 800 м условию задачи удо-

влетворяют. Сначала рассмотрим простейшую ситуацию,

когда каждый из берегов представляет собой функцию

x →f

(x), i = 1, 2, x ∈[a; b], в декартовой системе коорди-

нат. Для каждого x на отрезке [a; b] найдем единственный

максимальный круг, целиком расположенный в реке,

412 Дополнение A

центр c(x) которого расположен на вертикальной прямой,

пересекающей горизонтальную ось в точке (x, 0). Тогда

x →c(x) — искомая линия пути лоцмана (ибо радиус мак-

симального круга не может быть больше

√

2/2 км, что

меньше 800 м, а максимальный круг должен касаться обо-

их берегов). В общем случае надо рассмотреть все макси-

мальные круги, их центры и дадут искомую кривую. Мне

кажется, что, базируясь на этом плане, можно получить

достаточно короткое формализованное доказательство

Вторая задача — о мухе, я уже упоминал о ней.

11 класс, задача 6. Муха летает внутри правильного

тетраэдра с ребром a. Какое наименьшее расстояние она

должна пролететь, чтобы побывать на каждой грани и

вернуться в исходную точку?

Эта задача действительно трудна для начинающего ма-

тематика, но если кое-что знать, то решение ее напраши-

вается. Дело в том, что эта задача относится к выпуклому

программированию, где, в частности, исследуются задачи

о минимизации выпуклых функций при линейных огра-

ничениях, а данная задача именно такова. Существование

решения в данной задаче гарантируется общими сообра-

жениями компактности, которые проходятся на первом

курсе университета (или в специальных математических

школах). А для выпуклых задач, подобных задаче о мухе,

имеется способ сформулировать необходимое и достаточ-

ное условие минимума. В задаче о мухе оно состоит в том,

что если из точки на грани, на которую села муха (при

выборе оптимальной траектории), провести единичные

векторы по направлениям той точки, откуда муха приле-

тела и куда она должна лететь, то сумма этих векторов

должна быть ортогональна той грани, на которую муха се-

ла. Отсюда следует, что если путь состоит из кратчайших

отрезков, соединяющих медианы граней, то сформулиро-

ванное условие удовлетворится, и значит, решение найде-

но. А самих путей при этом можно выбрать три разных.

Аккуратное доказательство этого утверждения, приведенное в до-

полнении Б, занимает 3 страницы.

Впрочем, такое доказательство пока не получено (см. дополне-

ние Б).

ДОПОЛНЕНИЕ Б

Решение задачи 3б для 10 класса

олимпиады 1993 г.

Рассмотрим любой круг, лежащий целиком на воде, и

точки A

, A

, B

и B

на границе этого круга. Пусть

точки B

и B

разделяют точки A

и A

(т. е., двигаясь по

окружности, мы не можем из A

попасть в A

, не проходя

через B

или B

Пусть O — центр круга, обозначим первую точку пере-

сечения луча OA

с берегом через A

. Аналогично опре-

делим точки A

, B

и B

. Рассмотрим береговую линию,

т. е. объединение левого берега, правого берега и берегов

озер. Эта линия представляет собой замкнутую несамо-

пересекающуюся кривую, состоящую из отрезков и дуг

окружностей. Нам неоднократно понадобится следующее

«топологическое» утверждение.

Л е м м а 0. Точки B

и B

разделяют точки A

и A

т. е. нельзя попасть из A

в A

, двигаясь вдоль берега и

не проходя через точки B

и B

Д о к а з а т е л ь с т в о. Пусть это не так, обозначим

через Г участок берега, соединяющий точки A

и A

Рис. 196

(рис. 196) и не проходящий через

точки B

и B

. Ясно, что Г должен

пересекать один из лучей OB

, OB

(пусть OB

), причем дальше от

центра, чем B

. Рассмотрим кон-

тур, состоящий из Г и отрезков

и OA

. Этот контур разделяет

точки B

и B

, поэтому береговая

линия между B

и B

должна его

пересечь, но это невозможно. Лем-

ма доказана.

К о м м е н т а р и й. Мы воспользовались знаменитой теоремой Жор-

дана: замкнутая несамопересекающаяся кривая делит плоскость на

две части. Для кривых, состоящих из отрезков и дуг окружностей,

доказать ее несложно. По поводу общего случая см. [25].

Л е м м а 1. В условиях задачи не существует круга

радиуса 750 м с центром в реке, лежащего целиком на

воде.

414 Дополнение Б

Д о к а з а т е л ь с т в о. Пусть такой круг существует,

O — его центр. Докажем, что тогда найдется точка на

одном из берегов, расстояние от которой до другого берега

больше 1000 м.

Рассмотрим множество лучей с началом в точке O и

покрасим их в четыре цвета: в синий, если первое пересе-

чение луча происходит с правым берегом, в зеленый —

если с левым, в желтый — если с первым озером, и в

белый — если со вторым озером.

Соответственно покрасим точки окружности. Белые и

желтые точки будем называть светлыми, а остальные —

темными. Итак, окружность разбилась на разноцветные

дуги (быть может, имеется лишь одна дуга, совпадающая

со всей окружностью).

◦

. Имеется не более одной дуги каждого цвета.

Д о к а з а т е л ь с т в о. Пусть, например, зеленых дуг

две. Возьмем две зеленые точки A

и A

на разных ду-

гах. Эти точки разбивают окружность на две части, на

каждой из которых мы возьмем по точке другого цвета.

Обозначим их через B

и B

. Осталось применить лем-

му 0. Утверждение доказано.

Заметим, что каждая из дуг может быть открытой,

замкнутой, либо содержащей ровно один из своих кон-

цов.

К о м м е н т а р и й. Искушенный читатель может возразить, что

множества точек каждого цвета не обязаны быть объединениями

конечного числа дуг. Однако из приведенного рассуждения следует,

что эти множества связны, а связное множество на окружности

является дугой.

◦

. Если синяя и зеленая дуги присутствуют, то бе-

лая и желтая дуги не могут иметь общего конца.

Д о к а з а т е л ь с т в о. От противного. Пусть, например,

дуги расположены в следующем порядке: белая, желтая,

зеленая и синяя. Возьмем в качестве A

, A

, B

и B

белую, зеленую, желтую и синюю точки соответственно

и применим лемму 0. Остальные варианты разбираются

аналогично.

◦

. Каждая из светлых дуг меньше 180

◦

, потому что

точку, не лежащую в озере, можно отделить от озера пря-

мой. Значит, есть хотя бы одна темная дуга.

Решение задачи 93.10.3б 415

◦

. Либо каждая из темных дуг составляет 180

◦

(этот

случай мы будем называть исключительным), либо най-

дутся точки A

, A

и B на окружности, обладающие

следующими свойствами:

1) точки A

и A

диаметрально противоположны,

2) точка B является серединой одной из дуг A

3) точка B темная, а каждая из точек A

либо свет-

лая, либо одного цвета с B (этот случай мы будем назы-

вать общим).

Д о к а з а т е л ь с т в о. Можно считать, что синяя и зе-

леная дуги присутствуют, причем каждая из них меньше

180

◦

(остальные случаи очевидны). Предположим сначала,

что обе светлые дуги присутствуют. Используя утвержде-

ние 2

◦

, видим, что найдется диаметр d

, соединяющий

белую и желтую точки. Рассмотрим перпендикулярный

ему диаметр d

. Если один из концов этого диаметра тем-

ный, то можно взять этот конец в качестве точки B, а

концы диаметра d

в качестве точек A

и A

В противном случае, диаметры d

и d

разбивают

окружность на четыре части, причем каждая из темных

дуг содержится целиком в од ной из частей. Части, со-

держащие темные дуги, противоположны, так как иначе

одна из светлых дуг была бы не меньше 180

◦

. Теперь

ясно, что в качестве точки B можно взять любую из

темных точек.

Случай двух темных и одной светлой дуги мы оставля-

ем читателю.

◦

. Рассмотрим сначала общий случай. Будем считать,

что точка B — синяя. Как обычно определим точки A

, B

. Пусть Г — участок береговой линии между A

и A

содержащий точку B

. Выбирая при необходимости новые

точки A

и B, тоже удовлетворяющие условиям 4

◦

, мы

можем считать, что на Г нет точек левого берега.

Д о к а з а т е л ь с т в о. Точки A

и A

не лежат на ле-

вом берегу, значит, либо на Г нет точек левого берега,

либо Г содержит весь левый берег. В первом случае все

доказано, во втором случае Г содержит целиком берег од-

ного из озер (пусть первого). Тогда возможны два вари-

анта: точки A

и A

синие или одна из них синяя, а

другая белая. Если точки A

и A

синие, то в силу лем-

416 Дополнение Б

мы 0 вся окружность — синяя. Снова используя лемму 0,

нетрудно убедиться, что достаточно заменить точку B на

диаметрально противоположную. Если же точка B — бе-

лая, то окружность состоит только из желтой и синей

дуг, так что синяя дуга больше 180

◦

. Но тогда мы можем

выбрать новые точки A

и B синего цвета и свести все к

Рис. 197

предыдущему случаю. Утвержде-

ние доказано.

Построим контур (рис. 197),

состоящий из

1) береговой линии Г,

2) отрезков A

и A

3) полуокружности, соединя-

ющей точки A

и A

и не содер-

жащей точки B.

Так как на Г нет точек левого

берега, кратчайший путь от B

до левого берега пересекает участок A

в некоторой

точке X. В любом случае

∠B

OX > 90

◦

, B

O > 750 м, XO > 750 м.

Значит, по теореме косинусов,

X >

+ XO

> 750

√

2 > 1000 м.

Это противоречит условию.

Осталось рассмотреть исключительный случай. В этом

случае не получится взять диаметрально противополож-

ные точки синего цвета, но можно взять «почти» диамет-

рально противоположные. Точнее, мы потребуем, чтобы

выполнялось неравенство cos < 1/9, где 2 — меньшая из

дуг A

. Тогда предыдущие неравенства заменятся на:

X >

+ XO

−

O · XO

+ XO

−

+ XO

750

+ 750

= 1000 м.

Лемма доказана.

Л е м м а 2. Пусть расстояние от точки O на реке до

левого берега (по воде) не меньше 750 м, тогда расстоя-

ние до правого берега не превосходит 750 м.

Решение задачи 93.10.3б 417

Д о к а з а т е л ь с т в о. Пусть B — ближайшая к O точка

берега (или одна из ближайших, если таких несколько).

Согласно лемме 1, OB < 750 м.

Внутри отрезка OB нет точек берега, так что расстоя-

ние от O до B по воде равно расстоянию по прямой. Так

как расстояние от точки O до левого берега не меньше

750 м, B не может быть точкой левого берега. Если B —

Рис. 198

точка правого берега, то все доказано.

Остался случай, когда B — точка на бе-

регу озера. Соответствующее озеро пред-

ставляет собой круг, обозначим его K

Пусть левый берег переходит в озера

в точках P и Q, а правый — в R и S.

Пусть K

— круг радиуса OB с цен-

тром в точке O. Внутри этого круга нет

точек берега. Значит, либо круги K

касаются, либо B — одна из точек P, Q, R, S (рис. 198).

Во втором случае B — точка берега реки, а этот вариант

мы уже рассмотрели. Нетрудно видеть, что и в первом

случае B — одна из точек P, Q, R, S (иначе мы приплыли

бы к берегу озера снаружи). Лемма доказана.

Теперь мы можем изложить решение задачи.

И д е я р е ш е н и я. Пусть X — множество точек A, удо-

влетворяющих двум условиям:

1) точка A лежит на воде (на реке или в озере);

2) расстояние (по воде) от точки A до левого берега

меньше 800 м.

Тогда X — это связная область

. Связность следует из

того, что от любой точки области X можно доплыть до

левого берега по точкам, лежащим в X.

Рис. 199

Пусть Г — внешняя граница облас-

ти X, т. е. та компонента границы, из

точек которой можно уйти далеко от ре-

ки и озер (говоря математически — «на

бесконечность») по точкам, не лежащим

в X (рис. 199). Тогда Г — замкнутая

несамопересекающаяся кривая. (1)

Грубо говоря, множество называется связ-

ным, если оно состоит из одного куска.

418 Дополнение Б

Ясно, что Г состоит из точек двух типов:

1) точек, расстояние от которых до левого берега равно

800 м;

2) точек берега (реки или озер).

Кроме того, ясно, что весь левый берег (обозначим

его Г

) содержится в Г. Действительно, пусть A — точка

левого берега, если отплыть от нее чуть-чуть в реку, то

получится точка множества X, а если отойти от нее чуть-

чуть по суше, то получится точка, не лежащая в мно-

жестве X. Значит, точка A принадлежит границе множе-

ства X. Она лежит именно во внешней компоненте грани-

цы, так как из нее можно уйти по суше на бесконечность.

Итак, Г можно представить в виде объединения дуги

и ее дополнения Г \Г

. Заметим, что Г \Г

соединяет

концы левого берега, т. е. соединяет озера. Докажем, что

лоцман может провести корабль по этому дополнению.

Достаточно доказать, что расстояние от любой точки Г \Г

до каждого из берегов не превосходит 800 м, если только

эта точка не лежит в озере.

Рассмотрим любую точку Г \Г

. Расстояние до лево-

го берега не превосходит 800 м. Если эта точка — точка

правого берега, то расстояние до правого берега меньше

800 м. Если это точка на реке, то утверждение вытекает

из леммы 2. Задача решена.

Н а б р о с о к с т р о г о г о р е ш е н и я. Утверждение (1), выделен-

ное курсивом, верно не для всякой области, а лишь для достаточно

хорошей. Для нашей области оно верно, однако доказать это не про-

сто (см. комментарии 2 и 3). Более простой выход состоит в том,

чтобы приблизить берега (которые по условию состоят из отрезков и

дуг окружностей) ломаной. Подробное изложение этого рассуждения

заняло бы много страниц, поэтому мы разобьем его на относительно

несложные задачи.

Обозначим через

минимальное из расстояний по воде между

точками A и B, где A лежит на левом берегу реки, а B — на правом.

Обозначим = min(

/3, 50 м).

З а д а ч а. Можно проплыть из P в Q по некоторой ломаной L

так,

чтобы расстояние по воде до левого берега не превосходило .

Засыпем песком акваторию, ограниченную ломаной L

и левым

берегом. Аналогично проведем ломаную L

вдоль правого берега и

засыпем песком соответствующую акваторию. Пусть X

— множество

точек на воде, расстояние от которых по воде до ломаной L

меньше

d = 750 метров.

Решение задачи 93.10.3б 419

Назовем открытую ограниченную область X хорошей, если ее гра-

ница есть объединение конечного числа отрезков и дуг окружностей.

З а д а ч а. Внешняя граница связной хорошей области может быть

представлена как

i=1

, где Г

— либо отрезок, либо дуга окружности,

причем найдутся такие попарно различные точки F

(i = 1, . .. , M),

что Г

соединяет F

с F

i+1

, Г

соединяет F

с F

, причем Г

не пе-

ресекается с внутренностью Г

при i 6= j. У к а з а н и е. Рассмотрите

границу области как граф на плоскости, ребра которого — отрезки и

дуги окружностей. Тогда внешняя граница — подграф этого графа (см.

факт 3). Рассмотрите в этом подграфе цикл.

З а д а ч а. Выведите утверждение задачи из того, что X

— хорошая

область.

Осталось доказать, что X

— хорошая область.

Назовем основным путем любую ломанную A

.. . A

C, удовлетво-

ряющую условиям:

1) A

— вершины ломаной L

;

2) все звенья ломаной лежат на воде;

3) C — вершина L

либо основание перпендикуляра, опущенного из

на одно из звеньев L

Ясно, что число основных путей конечно.

З а д а ч а. Кратчайший путь от любой точки B до левого берега по

воде есть либо путь по прямой, либо объединение отрезка и основного

пути. У к а з а н и е. Зафиксируйте точку B и рассмотрите кратчайший

из путей указанного вида. Предположите, что есть более короткий

путь, и проведите убывающую индукцию по количеству вершин, через

которые этот путь проходит.

Пусть

, . .. ,

— все основные пути, d

, . .. , d

— их длины,

, . .. , E

— их начальные точки.

З а д а ч а. Кратчайшее расстояние по воде от точки B до лев ого

берега либо есть расстояние по прямой, либо равно минимальной из

величин

+ d

где минимум берется по тем i, для которых BE

целиком лежит на

воде.

Пусть X

— множество точек, для которых отрезок BE

лежит на

воде, и BE

< d −d

. Пусть Y

— множество точек, от которых можно

доплыть по прямой до i-й вершины ломаной L

, причем это рассто-

яние не превосходит d, наконец, Z

— множество точек, из которых

можно опустить перпендикуляр на i-е звено ломаной L

, причем этот

перпендикуляр лежит целиком на воде и его длина не превосходит d.

З а д а ч а. X

есть объединение всех X

, Y

и Z

З а д а ч а. Каждое из множеств X

и Y

есть пересечение много-

угольника и круга, каждое из множеств Z

— многоугольник.

З а д а ч а. Докажите, что X

— хорошая область. У к а з а н и е. До-

кажите, что объединение двух хороших областей является хорошей

областью.

420 Дополнение Б

К о м м е н т а р и и. 1

◦

. Если разрешить острова, то нетрудно при-

думать контрпример — рис. 200 (ширина реки чуть меньше километра,

Рис. 200

остров очень узкий).

◦

. Граница множества (даже открытого) может

быть устроена очень плохо. Например, можно постро-

ить 3 таких открытых множества, что любая точка

дополнения будет принадлежать границе каждого из

них! См., например, [25].

◦

. Неверно, что Г есть объединение отрезков и

дуг окружностей. Пусть, например, правый берег — это

отрезок, а левый содержит окружность радиуса 200 м

(рис. 201). Пусть A — такая точка окружности, что касательная в этой

точке перпендикулярна правому берегу. Пусть расстояние от A до

правого берега равно 400 м. Выпустим из каждой точки X верхней

Рис. 201

полуокружности касательную и отложим на ней рас-

стояние 400 м минус длина дуги AX. Получившаяся

кривая называется эвольвентой окружности. Рассто-

яние от изображенных на рисунке точек эвольвенты

до правого берега равно 800 м, так что часть этой

эвольвенты содержится в Г.

◦

. А. Акопян предложил следующее элегантное

рассуждение: покрасим точки на воде, расстояние от

которых до обоих берегов не превосходит 800 м, в

белый цвет, а остальные — в черный. Если можно

проплыть из одного озера в другое по белым точ-

кам, то задача решена, в противном случае черные

точки образуют перегородку между правым и левым

берегом. Нетрудно показать, что в этой перегородке найдется точка,

расстояние от которой до каждого из берегов не меньше 800 м. Оста-

ется использовать лемму 2. К сожалению, утверждение о перегородках

тоже не является элементарным.

◦

. Авторы книги не смогли сами решить эту задачу. Был объ-

явлен конкурс, и решение было найдено коллективными усилиями

А. Акопяна, В. Клепцына, М. Прохоровой и авторов. Идея другого

доказательства, основанного на рассмотрении точек, из которых берега

видны под равными углами, была предложена Д. Пионтковским.