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

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

Решения. 1999 год. 9 класс 241

Если первым провести соревнование по (n + 1)-му виду

спорта, то останется группа A

. По предположению ин-

дукции 2

−n спортсменов из этой группы могут стать

победителями.

Рассмотрим любого спортсмена из группы A, который

может быть победителем в примере E

. Рассмотрим после-

довательность соревнований, при которой он становится

победителем. Пусть при этом не проводится соревнование

по j-му виду спорта. Проведем его первым — останется

группа A. Теперь проведем оставшиеся соревнования в

порядке, необходимом, чтобы сделать этого спортсмена по-

бедителем в примере E

Итак, из группы A

победителями можно сделать 2

−n

человек, а из A — 2

−1 человек. Итого получаем 2

−n +

+ 2

−1 = 2

n+1

−(n + 1) возможных победителей.

Д о к а з а т е л ь с т в о л е м м ы. Докажем более силь-

ное утверждение: Пусть 2

спортсменов соревнуют-

ся в n + 1 виде спорта. При этом соревнование по

(n + 1)-му виду спорта проводится обязательно, а из

оставшихся видов спорта выбирается n−1 (соревнование

по (n + 1)-му виду спорта может проводиться любым

номером). Тогда может оказаться, что все, кроме одного

спортсмена (а именно, кроме самого слабого в (n + 1)-м

виде спорта), являются возможными победителями, а

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

вать его аутсайдером) может выйти в финал.

Б а з а (n = 1) очевидна.

И н д у к т и в н ы й п е р е х о д. Строим пример E

n+1

исходя из существования примера E

. Опять разделим

n+1

спортсменов на равные группы B и B

. Определим

их силы так, чтобы в 1-м виде спорта любой из B

был

сильнее любого из B, в остальных видах — наоборот, а в

виде j (2 6 j 6 n + 2) спортсмены внутри каждой из групп

B и B

были упорядочены, как спортсмены в примере E

в виде j −1. Дополнительно потребуем, чтобы аутсайдер

в B был самым сильным среди B в 1-м виде спорта.

Проводя сначала соревнования по 1-му виду спорта,

получим 2

−1 возможных победителей из B

, причем при

некотором порядке проведения соревнований аутсайдер

из B

выйдет в финал (индуктивное предположение).

242 Решения. 1999 год. 10 класс

Если вообще не проводить соревнования по 1-му виду

спорта, то в первом соревновании выбывают все спортсме-

ны из B

, а далее проводится n соревнований. По предпо-

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

нования и порядок проведения соревнований по осталь-

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

−1

спортсменов из B.

Осталось объяснить, как сделать победителем аутсайде-

ра в B. Для этого первым проводим тот вид соревнова-

ний, который является последним при порядке соревно-

ваний, обеспечивающем выход аутсайдера в финал. После

этого останутся только спортсмены из B. Далее проводим

соревнования в таком порядке, который обеспечивает вы-

ход аутсайдера из B в финал, а завершаем — 1-м видом

спорта. В нем аутсайдер побеждает.

10 к л а с с

1. П е р в ы й с п о с о б. Если a = 0, то b 6= 0 (иначе

< 0). Поэтому b

> 0 = 4ac, и все доказано.

Если a 6= 0, то рассмотрим квадратный трехчлен f(x) =

= ax

+ bx + c. Имеем f(1) = a + b + c, f(0) = c. По условию

f(1)f(0) = (a + b + c)c < 0.

Значит, среди чисел f(1) и f(0) одно отрицательно, а дру-

гое положительно. Поэтому парабола y = f(x) пересекает

ось x. Значит, дискриминант этого квадратного трехчлена

положителен: b

−4ac > 0.

В т о р о й с п о с о б. Можно избежать рассмотрения

двух случаев. Рассмотрим квадратный трехчлен g(x) =

= x

+ bx + ac. Из условия следует, что g(c) = c

+ bc + ac =

= (a + b + c)c < 0. Так как рога параболы y = g(x) направ-

лены вверх и g (c) < 0, эта парабола пересекает ось Ox в

двух точках, т. е. имеет два различных корня. Значит,

дискриминант этого квадратного трехчлена положителен:

−4ac > 0.

2. Треугольники APB и DPC равнобедренные, так как

AP, BP, CP и DP — радиусы третьей окружности. Обо-

значим углы при основаниях: ∠ABP = ∠BAP = , ∠DCP =

= ∠CDP = . Четырехугольники ABQP и DCQP вписанные,

Решения. 1999 год. 10 класс 243

Рис. 108

отсюда следует, что ∠AQP =

= ∠ABP = и ∠DQP = ∠DCP =

= (рис. 108). По теореме об

углах, вписанных в окруж-

ность, получаем:

∠AQD = ∠AQP + ∠DQP = + .

Далее, ∠BQP = −∠BAP = −

− , также ∠CQP = − и

∠BQC = 2 −∠BQP −∠CQP =

= + .

3. Докажем вначале, что x и y взаимно просты. Пред-

положим противное. Тогда x и y делятся на некоторое

простое число p. Пусть p входит в разложения на про-

стые множители чисел x и y в степенях a > 1 и b > 1

соответственно (см. факт 10). Не ограничивая общности,

можно считать, что a > b. Тогда максимальная степень p,

на которую делится x

+ y, равна b (поскольку x

делится

на p

и тем более на p

b+1

, но y делится на p

и не

делится на p

b+1

). С другой стороны, x

+ y

делится на

, следовательно, x

+ y не мож ет делиться на x

+ y

Это противоречие показывает, что x и y взаимно просты

(см. факт 5).

Далее, по условию x(x

+ y

) −(x

+ y) = y(xy −1) должно

делиться на x

+ y

. Заметим, что y и x

+ y

не могут

иметь общий делитель, больший 1 (так как x и y взаимно

просты), значит xy −1 делится на x

+ y

(см. факт 9). Но

если предположить, что xy −1 > 0, то это невозможно, так

как x

+ y

> 2xy > xy −1. Итак, xy = 1, а значит, x = y = 1.

4. Условимся называть красными числа, стоящие в

красных секторах, и синими — стоящие в синих секторах.

Расстоянием между двумя числами a и b назовем ко-

личество чисел, расположенных на меньшей дуге между

числами a и b. Числа, расставленные по окружности,

разбиваются на пары равных. Выберем ту пару равных

чисел, расстояние между которыми наименьшее (если

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

244 Решения. 1999 год. 10 класс

Заметим, что в задаче существенен только циклический

порядок чисел от 1 до n. Поэтому, если нумерацию сдви-

нуть по циклу (на одно и то же число для красных и си-

них чисел!), то задача заменится на равносильную. Поэто-

му можно считать, что выбранная пара — красная единица

и синяя единица. Также можно считать, что меньшая

дуга между ними идет от красной единицы к синей

против часовой стрелки (рис. 109). На дуге либо нет

n−1

Рис. 109

чисел (т. е. две единицы стоят ря-

дом), либо все числа одного цвета.

Действительно, если на этой дуге есть

и красные, и синие числа, то на ней

находятся красное и синее числа n, но

тогда расстояние между ними меньше,

чем расстояние между единицами.

Пусть все числа на этой дуге (если

они есть) — синие (случай, когда они

красные, аналогичен). Проведем диа-

метр, отделяющий синюю единицу от

числа, следующего за ним по часовой стрелке (это число —

синее n или красная единица); покажем, что этот диаметр

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

щий синюю единицу. Прочтем синие числа, записанные

в этом полукруге, начиная с единицы, против часовой

стрелки — это числа 1, 2, . . . , l (l — некоторое число). Про-

чтем теперь красные числа (тоже против часовой стрелки).

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

рассматриваемом полукруге будет число n. Значит, крас-

ные числа на этой дуге — это числа n, n −1, . . . , n −m

(m — некоторое число).

Итак, в рассматриваемом полукруге l синих и m + 1

красное число. Всего в полукруге n чисел, следователь-

но, l + (m + 1) = n, т. е. n −m = l + 1. Поэтому в полукруге

записаны синие числа от 1 до l и красные числа от n до

l + 1, а значит, в нем записаны все числа от 1 до n по

одному разу.

5. Пусть

f, g : [0; 1] →[0; 1], f(x) =

√

, g(x) =

√



1 −

√



Решения. 1999 год. 10 класс 245

— функции, отвечающие прыжкам кузнечика. Область

значений функции f — отрезок [0; 1/

√

3], область значе-

ний функции g — отрезок [1 −1/

√

3; 1]. Каждый из этих

отрезков имеет длину 1/

√

3, и вместе они покрывают

отрезок [0; 1].

Пусть n — некоторое натуральное число. Рассмотрим

всевозможные композиции функций вида

(...(h

(x))...)): [0; 1] →[0; 1],

где каждая функция h

— либо f, либо g. Легко ви-

деть, что область значений каждой из этих функций

есть отрезок длины (1/

√

. Докажем индукцией по n

(см. факт 24), что эти отрезки покрывают весь отрезок

[0; 1]. Для n = 1 это утверждение уже проверено. Пред-

положим, что области значений всевозможных функций

(...(h

k−1

(x))...)) покрывают отрезок [0; 1]. Фик-

сируем одну из этих функций h

(...(h

k−1

(x))...)).

Ясно, что область значений этой функции покрывается

областями значений функций h

(...(h

k−1

(f(x)))...)) и

(...(h

k−1

(g(x))) . . . )). Тем самым нужное утвержде-

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

Пусть теперь на отрезке [0; 1] выбрана точка a. Рас-

смотрим интервал (a −0,01; a + 0,01) и покажем, что куз-

нечик сможет в него попасть. Выберем n столь большим,

чтобы было выполнено неравенство (1/

√

< 0,01 (на-

пример, годится n = 10). По доказанному, можно выбрать

такую функцию h

(...(h

(x))...)), что точка a принад-

лежит области ее значений. Тогда вся область значений

рассматриваемой функции (отрезок длины (1/

√

) лежит

внутри интервала (a −0,01; a + 0,01). Это означает, что

из любой точки отрезка [0; 1] кузнечик попадет внутрь

интервала (a −0,01; a + 0,01), выполнив последовательно

прыжки, соответствующие функциям h

, h

n−1

, . . . , h

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

◦

. Сравните с задачами 4 и 7 для 11 класса.

◦

. Эта задача и задача 4 для 11 класса — задачи о сжимающих

отображениях. Пусть есть два сжимающих отображения f : [0; 1] →

→[0; 1] и g: [0; 1] →[0; 1] (дифференцируемое отображение называется

сжимающим, если его производная ограничена числом < 1).

Возникает следующая задача: возьмем точку x на отрезке [0; 1].

Что можно сказать о положении этой точки после последовательного

применения большого числа отображений f и g? Точнее, рассмотрим

246 Решения. 1999 год. 10 класс

бесконечную последовательность отображений f и g. Пусть x

— ре-

зультат последовательного применения первых n отображений.

Так как отображения сжимающие, lim

n→∞

не будет зависеть от x.

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

ются отображения f и g.

В случае, если области значений отображений f и g покрывают весь

отрезок [0; 1], x

может стремиться к любой точке отрезка [0; 1] (это,

фактически, и утверждается в нашей задаче). В противном случае,

множество возможных пределов похоже на канторово множество. На-

пример, если f (x) =

, g (x) =

x + 2

, то получится в точност и канторово

множество. По этому поводу см. [32], гл. 1.

6. Л е м м а. Пусть по окружности расставлено 1999

различных положительных чисел a

, a

, . .., a

1999

, и

пусть a

> a

1998

. Для всех 2 6 i 6 999 проделаем следующую

операцию: числа a

и a

1999−i

поменяем местами, если a

< a

1999−i

, и не будем менять в противном случае. Если

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

то сумма произведений десяток чисел, идущих подряд,

увеличилась.

Д о к а з а т е л ь с т в о л е м м ы. Рассмотрим симмет-

ричные группы по 10 чисел: a

, . . . , a

i+9

и a

1999−i

, . . .

..., a

1990−i

. Покажем, что сумма произведений в таких

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

она увеличилась. Из этого будет следовать утверждение

леммы.

Пусть z — произведение чисел, содержащихся одновре-

менно и в первой, и во второй группе (если таковых нет,

то считаем z = 1); x и x

— произведения чисел, содержа-

щихся соответственно только в первой и только во вто-

рой группе, оставшихся на своем месте после проведения

наших операций; y и y

— произведение чисел, содержа-

щихся соответственно только в первой и только во второй

группе, поменявшихся местами после проделанных опера-

ций (опять же, если таких чисел нет, то считаем, что со-

ответствующее произведение равно 1). Тогда сумма произ-

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

ции равна s

= zxy + zx

, а после операции s

= zxy

+ zx

Имеем: s

−s

= z(x−x

)(y−y

). Нетрудно видеть, что x > x

и y 6 y

. Значит, s

−s

6 0.

Решения. 1999 год. 10 класс 247

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

операции не все числа остались на своих местах, то хотя

бы для одной пары симметричных групп из 10 чисел эта

разность будет строго отрицательна. Нетрудно видеть, что

> y, если хотя бы одна пара чисел (из данной десят-

ки) поменялась. Если же хотя бы одна пара чисел не

поменялась, то x

< x, так как все числа различны. Зна-

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

группы по 10 чисел для которых хотя бы одна пара не

поменялась, и хотя бы одна пара поменялась (напомним,

что a

и a

1998

не поменялись местами). Но это очевидно.

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

Р е ш е н и е з а д а ч и. Будем считать, что числа 1,

2, . . . , 1999 расставлены так, что дуги между соседними

числами равны. Пусть числа расставлены оптимальным

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

седних чисел максимальна. Проведем какую-нибудь ось

симметрии 1999-угольника (это — диаметр, проходящий

через одно из чисел k и середину противоположной дуги).

Тогда для всех пар чисел, симметричных относительно

этого диаметра, меньшие числа расположены в одном

полукруге, а большие — в другом. Действительно, зануме-

руем числа переменными a

, . . . , a

1999

по кругу, начиная

с большего из чисел, соседних с числом k, и заканчивая

числом k. Тогда a

> a

1998

, так что можно применить

лемму: так как расстановка оптимальная, никакая пара

чисел не поменяется местами, а значит, большие числа

расположены в одном полукруге, а меньшие — в другом.

Оказывается, что с точностью до поворотов и симмет-

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

творяющая этому свойству для всех диаметров. Действи-

тельно, число 2 должно быть рядом с числом 1. Иначе

найдется диаметр, отделяющий число 2 от числа 1, при-

чем 1 и 2 не симметричны относительно этого диаметра.

Обозначим числа, симметричные числам 1 и 2 относитель-

но этого диаметра, через A и B соответственно. Тогда A > 1

и 2 < B, что противоречит оптимальности в силу леммы.

Далее строим искомую расстановку по индукции (см.

факт 24). Пусть мы доказали, что числа 1, 2, . . . , 2k

(1 6 k 6 998) расставлены как в ответе, т. е. в порядке

248 Решения. 1999 год. 11 класс

(для определенности по часовой стрелке) 2k, 2k −2, . . . , 2,

1, 3, ..., 2k −1 подряд. Обозначим через A и B соответ-

ственно числа, следующее за 2k против часовой стрелки и

2k−1

2k+1

Рис. 110

следующее за 2k −1 по часовой стрел-

ке (рис. 110). Предположим, число

2k + 1 отлично от A и B. Тогда пусть

C — число, следующее за 2k + 1 по

часовой стрелке. C отлично от 1,

2, . . . , 2k. Числа C и 2k −1, а также

2k + 1 и B симметричны относительно

одного и того же диаметра, но C > 2k −

−1, а 2k + 1 < B — противоречие. Зна-

чит, либо A = 2k + 1, либо B = 2k + 1.

Но предположение A = 2k + 1 сразу приводит к противоре-

чию — достаточно рассмотреть диаметр, относительно ко-

торого симметричны числа 2k и 2k −1. Значит, B = 2k + 1.

Аналогично доказывается, что A = 2k + 2. Это завершает

доказательство индуктивного перехода.

11 к л а с с

1. Из неравенства треугольника a > |b −c |. Возводя обе

части в квадрат, получаем: a

> (b −c)

. Отсюда следует,

что a

+ 2bc > b

+ c

. Правая часть положительна, значит,

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

в условии задачи больше 1. То же верно для двух других

слагаемых. Поэтому их сумма больше 3.

2. а) Нетрудно построить середину ломаной BAC, т. е.

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

длины. Осталось провести прямую через эту точку и сере-

дину дуги.

Рис. 111

б) Пусть D — середина дуги

(рис. 111). Сегменты, опирающиеся

на хорды BD и DC, равны. Поэтому

достаточно провести через точку D

прямую, которая делит пополам пло-

щадь четырехугольника ABDC.

Пусть точка F — середина диагона-

ли BC. Проведем через точку F пря-

Решения. 1999 год. 11 класс 249

мую l, параллельную диагонали AD. Пусть прямая l

пересекает отрезок AC (случай пересечения прямой l

с отрезком AB рассматривается аналогично). Обозначим

E = l ∩AC; прямая DE — искомая.

Действительно, сумма площадей треугольников ABF и

BDF равна половине площади четырехугольника ABDC.

Нам достаточно доказать, что площадь треугольника AED

равна площади треугольника AFD, но эти треугольники

имеют общее основание и равные высоты (см. факт 18).

3. П е р в ы й с п о с о б. Плоскости, которым принадле-

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

тетраэдры. Это можно представить следующим образом.

Рис. 112

Рассмотрим куб ABCDEFGH

(рис. 112) и два тетраэдра:

ACFH и BDEG. Пересечение

этих тетраэдров есть октаэдр.

Действительно, вершины пере-

сечения есть середины граней

куба, а середины граней куба

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

Черные грани октаэдра лежат

на одном тетраэдре, а белые —

на другом.

Утверждение задачи следует

из того, что сумма расстояний

от внутренней точки правильно-

го тетраэдра до его граней постоянна и равна утроенному

объему тетраэдра, деленному на площадь грани.

Докажем последнее утверждение. Пусть A, B, C и D —

вершины тетраэдра, O — точка внутри тетраэдра, h

, h

и h

— расстояния от точки O до плоскостей BCD,

ACD, ABD и ABC соответственно. Пусть S — площадь

грани тетраэдра ABCD. Тогда объемы тетраэдров BCDO,

ACDO, ABDO и ABCO равны

соответственно. Поэтому объем тетраэдра ABCD равен

+ h

откуда следует требуемое утверждение.

250 Решения. 1999 год. 11 класс

В т о р о й с п о с о б (не совсем элементарный). Рас-

смотрим ориентированные расстояния от точки до плос-

костей граней. Точнее говоря, если точка и октаэдр лежат

по одну сторону от плоскости, то расстояние берется со

знаком плюс, иначе — со знаком минус.

Докажем утверждение, более сильное, чем утверждение

задачи:

Сумма ориентированных расстояний от любой точки

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

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

(даже если точка не лежит внутри октаэдра).

Ориентированное расстояние до плоскости представляет

собой линейный функционал в пространстве (см. факт 25).

Значит, сумма расстояний до граней какого-нибудь цве-

та — тоже линейный функционал. Обозначим сумму рас-

стояний от точки X до белых граней через l

(X), а сумму

расстояний до черных граней — через l

(X). Мы хотим

доказать, что l

−l

= 0. Пусть это не так. Тогда множество

нулей линейного функционала l

−l

является плоскостью.

Но нетрудно проверить, что он обращается в нуль во всех

вершинах октаэдра. Противоречие. Значит, l

−l

обраща-

ется в нуль тождественно.

4. Пусть сторона квадрата имеет длину 1. Разделим

каждую сторону на 2

равных частей, а через точки деле-

ния проведем прямые, параллельные сторонам. При этом

квадрат разделен на квадратики со стороной 2

−n

. Если n

достаточно велико, то один из этих квадратиков окажется

целиком в лунке (например, если взять n таким, чтобы

−n

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

квадратик, содержащий центр лунки).

Поэтому достаточно доказать, что при любом n кузне-

чик сможет попасть в любую из 4

получившихся клеток.

Докажем это утверждение по индукции (см. факт 24).

При n = 0 факт тривиален. Проведем индуктивный пере-

ход от n к n + 1. Рассмотрим какую-нибудь из клеток

размера 2

−(n+1)

×2

−(n+1)

Разрежем исходный квадрат на 4 квадрата со сторо-

нами 1/2 (рис. 113). Без ограничения общности можно

считать, что наша клетка находится в левом нижнем