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

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

Решения. 1994 год. 10 класс 141

диагоналей триангуляции, для которой площадь меньшей

части максимальна. Пусть ABC — треугольник триангуля-

ции, примыкающий к AB со стороны большей части.

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

, S

и S

площади частей,

примыкающих к соответствующим сторонам треугольника

ABC и не содержащих этого треугольника. Тогда

S = S

+ S

ABC

Можно считать, что S

> S

. Теперь из условия макси-

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

> S

Из этих неравенств можно вывести, что S

+ S

ABC

> S/3.

Если S

> S/3, то задача решена, в противном случае

пусть X — такая точка на стороне AC, что S

+ S

ABX

= S/3. Проверьте, что хорда, проходящая через B и X,

удовлетворяет условию задачи.

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

◦

. В пункте «а» остается вопрос: нельзя ли

разрезать этот многоугольник хордой на три или более равновеликие

части (см. комментарий к условию). Нетрудно так подправить размеры

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

равны 0,3S, 0,33S и 0,36S. Докажите сами, что такой многоугольник

нельзя разрезать (одной хордой) ни на какое количество равновеликих

частей.

◦

. Можно нарисовать такое многоугольное кольцо, которое нельзя

разделить хордой на два многоугольника, площадь меньшего из кото-

рых не меньше S/3. В чем здесь дело? А дело в определении мно-

гоугольника: границей многоугольника служит одна ломаная. Иначе

говоря, многоугольное кольцо — это не многоугольник. Заметим также,

что не всякая хорда делит кольцо на части.

◦

. Второй способ решения пункта «б» показывает, что искомую

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

6. Важное наблюдение состоит в том, что достаточно

найти такой многочлен, что коэффициенты его квадрата

и куба положительны. Любая другая степень представима

в виде произведения квадратов и кубов.

Назовем многочлен

+ a

n−1

+ . . . + a

x + a

положительным, если все его коэффициенты положитель-

ны: a

> 0 при i = 0, ..., n.

142 Решения. 1994 год. 11 класс

Рассмотрим многочлен f(x) = x

+ x

+ x + 1. Нетрудно

видеть, что (f(x))

и (f(x))

— положительные многочле-

ны, но сам многочлен f(x) не является положительным:

коэффициент при x

равен нулю. Однако нам нужен

многочлен с отрицательным коэффициентом. Идея состоит

в том, чтобы немного «пошевелить» многочлен f(x).

Рассмотрим многочлен g(x) = f(x) − x

при достаточно

малом > 0. Коэффициенты многочленов (g(x))

и (g(x))

близки к коэффициентам многочленов (f(x))

и (f(x))

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

показаться нестрогим человеку, не знакомому с матема-

тическим анализом. В этом случае предлагается взять,

например, =

125

и проверить «руками», что соответству-

ющие многочлены положительны.

Итак, ответ дается многочленом

g(x) = f(x) − x

= x

+ x

− x

+ x + 1

при достаточно малом > 0.

К о м м е н т а р и й. При = 0 коэффициенты многочлена f(x) = x

+ x

− x

+ x + 1 можно записать как число: 11011, тогда коэффициен-

ты (f(x))

и (f(x))

можно записать в виде последовательности цифр

11011

= 121242121 и 11011

= 1334996994331 (многочлены перемножа-

ются «столбиком» так же, как многозначные числа).

11 к л а с с

1. Будем искать многогранник с наименьшим числом

граней. Из двух треугольников и двух квадратов нельзя

Рис. 56

составить многогранник.

Шестигранник с двумя треугольны-

ми, двумя четырехугольными и двумя

пятиугольными гранями сделать мож-

но: расположим два пятиугольника с об-

щим ребром в виде открытой ракушки,

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

(по краям) и двумя четырехугольниками

(рис. 56).

Такой многогранник получится, если

у тетраэдра срезать две соседние вершины. Другое реше-

ние — срезать две соседние вершины у куба.

Решения. 1994 год. 11 класс 143

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

◦

. На московской олимпиаде 1973 г. в 10 клас-

се была родственная задача: «Докажите, что у любого выпуклого мно-

гогранника найдутся две грани с одинаковым числом сторон.»

◦

. Подумайте над такой задачей: «Докажите, что в любом 10n-

граннике найдутся n граней с одинаковым числом сторон».

2. См. решение задачи 2 для 10 класса.

y = x

Рис. 57

3. Решим сначала другую задачу:

построим окружность с центром на

оси y, которая касается оси x и выяс-

ним, при каком наименьшем радиу-

се r она имеет с кривой y = x

общую

точку, отличную от начала координат

(рис. 57). Иначе говоря, при каком

наименьшем r система уравнений

y = x

, x

+ (y −r)

= r

имеет ненулевое решение. Интуитив-

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

ны, позже мы докажем это строго.

Подставим y = x

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

подобные члены и сократим на x

(x > 0):

−2rx

+ 1 = 0

Выразим r через x:

r(x) =





Искомое число r

есть минимум этой функции. Производ-

ная функции равна

(x) = 2x

−

При x > 0 эта производная ведет себя следующим образом:

она отрицательна при x < x

√

, равна нулю в точке

и положительна при x > x

. Значит, r(x) убывает при

0 < x < x

, достигает минимума при x = x

и возрастает при

x > x

Итак, наименьшее r, при котором окружность имеет

общую точку с кривой y = x

, —

= r(x

) =

√

144 Решения. 1994 год. 11 класс

Осталось показать, что это r

дает ответ и в исходной

задаче. Покажем, сначала, что соответствующая вишенка

целиком содержится в бокале. Действительно, при любом

x 6= 0 имеем r

6 r(x). Подставляя в это неравенство выра-

жение для r(x), получаем, что при любом x

−2r

+ 1 > 0.

Умножая обе части на x

и подставляя y = x

, получим

+ (y −r

)

> r

при всех x, y = x

. Но это и значит, что вишенка находит-

ся в бокале.

Осталось показать, что если r > r

, то вишенка не кос-

нется начала координат. Действительно, в этом случае

−2rx

+ 1 < 0,

поэтому при y

= x

имеем

+ (y

−r)

< r

Это означает, что окружность радиуса r, касающаяся оси

абсцисс в начале координат, пересекает график функции

y = x

. Поэтому вишенка не касается дна.

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

◦

. Нетрудно видеть, что «максимальная» ви-

шенка касается кривой y = x

в начале координат и еще в двух точках.

◦

. Аналогичную задачу можно решить для графика функции

y = |x|

при любом a. Для абсциссы точки касания «максимальной

вишенки» получаем уравнение x

2(a−1)

a − 2

а) При a > 2 есть ненулевое решение, и ситуация такая же, как и

при a = 4;

б) при a = 2 получим x = 0 и r = 1/2 — радиус кривизны графика в

точке (0; 0), — максимальная вишенка касается параболы в единствен-

ной точке;

в) при 0 < a < 2 никакой круг не может коснуться «дна» графика.

4. Сделаем гомотетию исходного многогранника M с

центром в точке A и коэффициентом 2. Объем растянутого

многогранника M

будет в 8 раз больше объема многогран-

ника M. Докажем, что все 8 «перенесенных» многогран-

ников содержатся в M

Пусть вершину A перенесли в вершину B, X — произ-

вольная точка многогранника M, Y — образ точки X при

Решения. 1994 год. 11 класс 145

соответствующем параллельном переносе (рис. 58). Дока-

жем, что точка Y принадлежит M

B Y

Рис. 58

Отрезок BX целиком содержится в

многограннике M, так как многогран-

ник — выпуклый. Значит, его середина K

принадлежит многограннику. Четырех-

угольник ABYX — параллелограмм, по-

этому Y получается из K гомотетией с

центром в точке A и коэффициентом 2,

следовательно, точка Y принадлежит M

Заметим, что точки вблизи вершины A не принадле-

жат ни одному из «перенесенных» многогранников. Дей-

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

на A была выше всех остальных вершин, тогда существует

плоскость, которая проходит ниже вершины A, но выше

всех остальных вершин. Эта плоскость отрезает от мно-

гогранника M маленький многогранник N, содержащий

точку A. Ясно, что он не пересекается ни с одним из

перенесенных многогранников.

Предположим теперь, что перенесенные многогранни-

ки не пересекаются по внутренним точкам, тогда объем

многогранника M

не меньше, чем сумма объема много-

гранника N и объемов перенесенных многогранников. Но

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

сти равен объему многогранника M

. Противоречие.

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

◦

. Задача легко обобщается для n-мерного про-

странства.

◦

. Более слабая формулировка задачи была на XIII Международ-

ной математической олимпиаде. Требовалось доказать, что пересекают-

ся хотя бы два из девяти (а не восьми) многогранников.

5*. Сделать чертеж к задаче очень трудно (точки пере-

сечения лежат далеко друг от друга), поэтому будем ис-

кать решение из общих соображений. Вспомним, что точ-

ки биссектрисы угла равноудалены от сторон этого угла.

Для каждой прямой, содержащей сторону четырех-

угольника ABCD, определим функцию f

— ориентирован-

ное расстояние до этой прямой: если точка лежит по

ту же сторону от прямой, что и четырехугольник, то

берем обычное расстояние, а если — по другую сторону,

146 Решения. 1994 год. 11 класс

то расстояние со знаком минус. Эти четыре функции f

, f

от координат точек являются линейными (см.

факт 25), т. е. записываются в виде f

(x, y) = a

x + b

y + c

Заметим, что точка лежит на биссектрисе внешнего

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

значений двух функций для сторон угла обращается в

нуль.

Для каждой из точек пересечения биссектрис, о кото-

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

рех функций обращается в нуль.

Но сумма линейных функций является линейной функ-

цией, а множество точек, на котором линейная функция,

отличная от константы, принимает постоянное значение,

есть прямая.

Сумма наших четырех функций не является тожде-

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

она положительна. Поэтому указанные точки пересечения

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

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

◦

. Зная идею решения с линейными функция-

ми, можно сделать пространственное обобщение задачи.

◦

. Есть более простая задача на ту же идею: найти геометрическое

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

сторон равна расстоянию до третьей. (Точки пересечения биссектрис

со сторонами треугольника удовлетворяют условию. Значит, и отрезки

между ними тоже удовлетворяют.)

◦

. В школьной математике линейными функциями называют мно-

гочлены степени не выше первой. В линейной алгебре линейная функ-

ция — это многочлен степени не выше первой и без свободного члена.

В этом смысле линейная функция от двух переменных имеет вид:

f (x, y) = ax + by. Функции вида ax + by + c называются аффинными.

6. От чего может появиться много девяток подряд в

степенях двойки? — Если степень двойки «чуть» меньше

числа, делящегося на большую степень десятки. Напри-

мер, 2

+ 4 делится на 100, 2

+ 8 делится на 1000.

Попробуем найти сначала числа вида 2

+ 1, которые

делятся на высокую степень пятерки. Затем домножим

эти числа на соответствующую степень двойки и полу-

чим числа вида 2

+ 1), делящиеся на высокую степень

десятки. Раскрывая скобки и отбрасывая меньшее слагае-

мое, получим нужную степень двойки.

Решения. 1995 год. 8 класс 147

Л е м м а. При всех k> 1 число 2

2·5

k−1

+ 1 делится на 5

Докажем это по индукции (см. факт 24). База (k = 1)

очевидна. Докажем шаг индукции: имеем

2·5

k−1

+ 1 = 4

k−1

+ 1.

Пусть a = 4

k−1

. По предположению индукции a + 1 делит-

ся на 5

. Тогда 4

+ 1 = a

+ 1 = (a + 1)(a

−a

+ a

−a + 1).

Поскольку a + 1 делится на 5

, достаточно доказать, что

второй сомножитель делится на 5. Действительно, a имеет

вид 5m −1, поэтому все слагаемые во втором сомножителе

при делении на 5 дают остаток 1 (см. факт 7), а их сумма

дает остаток нуль. Лемма доказана.

Итак, число 2

2·5

k−1

+ 1) оканчивается не меньше, чем

k нулями. Несложно убедиться, что при k > 1 количество

цифр числа 2

не превосходит k/2. Значит, среди послед-

них k цифр числа 2

2·5

k−1

не более k/2 цифр могут отли-

чаться от 9.

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

◦

. Похожими рассуждениями можно доказать,

что числа 4

, 4

, . .. , 4

−1

дают различные остатки при делении на

. Попробуйте доказать более общий факт: если x −1 делится на p

(p > 2 — простое, k > 0), но не делится на p

k+1

, то x

−1 делится на p

k+r

тогда и только тогда, когда n делится на p

. Это важное утверждение

(лемма Гензеля) часто используется в теории чисел.

◦

. На Ленинградской городской олимпиаде 1981 г. была похожая

задача: существует ли натуральная степень числа 5, в ста младших

разрядах которой встречается по крайней мере 30 нулей подряд?

1995 год

8 к л а с с

1. Обозначим цену хлеба через x, а цену кваса — через

y (до подорожания). Тогда, по условию: денежка = x + y.

После повышения цен хлеб стал стоить 1,2x, а квас —

1,2y. Поэтому

денежка = 0,5 хлеба + квас = 0,6x + 1,2y.

Из этих уравнений получаем:

x + y = 0,6x + 1,2y.

Упрощая, получим 2x = y.

148 Решения. 1995 год. 8 класс

Выразим денежку через y:

денежка = x + y = 1,5y.

После второго повышения цен квас стал стоить 1,2 · 1,2y =

= 1,44y. Так как 1,5y > 1,44y, денежки на квас хватит.

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

Б а з а и н д у к ц и и: 10017 делится на 53. Действи-

тельно, 10017 = 53 · 189.

Ш а г и н д у к ц и и. Покажем, что если число указан-

ного вида делится на 53, то и следующее за ним делится

на 53. Для этого вычислим разность двух соседних чисел:

1001...1

|{z}

k единиц

7 −1001...1

|{z}

k−1 единица

7 = (1001 −100) · 10

= 901 · 10

(последние k цифр сокращаются). Эта разность всегда де-

лится на 53, так как 901 = 53 · 17.

Если вычитаемое делится на 53 и разность делится на

53, то и уменьшаемое делится на 53 (см. факт 5). Наше

утверждение доказано по индукции.

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

◦

. Сравните с задачей 1 для 9 класса.

◦

. Можно показать, что частное от деления данного числа на 53

имеет вид 18 .. .89.

3. а) При повороте на 120

◦

по часовой стрелке вокруг

точки O отрезок AC переходит в BD, а значит, их длины

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

120

◦

Рис. 59

равны (рис. 59). Отрезок KL

является средней линией тре-

угольника ABC, поэтому он па-

раллелен отрезку AC, а его дли-

на равна половине длины отрез-

ка AC.

Аналогично, отрезок LM па-

раллелен отрезку BD, а его

длина равна половине длины

этого отрезка. Поэтому

KL =

AC =

BD = LM.

б) Так как отрезок AC переходит в BD при поворо-

те на 120

◦

, угол между этими отрезками равен 60

◦

. Так

Решения. 1995 год. 8 класс 149

как отрезки KL и LM параллельны отрезкам AC и BD,

угол между ними тоже равен 60

◦

. Используя утверждение

пункта «а», видим, что треугольник KLM правильный.

4. Достаточно взять коробку размером 11 ×13 ×14. Ее

объем равен 2002, т. е. достаточен; а общая площадь ее

стенок равна 2 · (11 · 13 + 11 · 14 + 13 · 14) = 958.

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

◦

. Как догадаться до такого решения? Извест-

но, что минимальную площадь поверхности при заданном объеме среди

всех параллелепипедов имеет куб — это следует из неравенства меж-

ду средним арифметическим и средним геометрическим, см. факт 26.

Однако куб с объемом 1995 будет иметь иррациональные длины сто-

рон. Таким образом, нужно пытаться подобрать коробку, близкую по

форме к кубу, но с целыми длинами сторон. «Ближайшие» кубы:

12 ×12 ×12 и 13 ×13 ×13 (их объе мы 1728 и 2197 соответственно).

Может показаться, что наиболее «экономный» вариант — 12 ×13 ×13.

К сожалению, этот параллелепипед дает лишь решение пункта «а».

Продолжая перебор параллелепипедов близких к кубу, можно найти

решение задачи.

◦

. 957 единиц материала не хватит на изготовление коробки.

5. П е р в ы й с п о с о б. Докажем сначала, что от пе-

рестановки порядка двух последовательных поездок сто-

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

автомобиль посетил некоторый населенный пункт M, а

потом — населенный пункт N. Покажем, что если бы он

сначала поехал в N, а потом — в M, то стоимость была бы

той же самой.

Пусть расстояния до M и N равны m и n соответ-

ственно. Тогда веса соответствующих грузов — тоже m

и n. Стоимость перевозки остальных грузов не меняется

от перестановки поездок в M и N. Стоимость перевозок

грузов m и n в города, отличные от M и N, тоже не

изменится. Вычислим стоимость перевозки грузов m и

n в города M и N. В первом случае эта стоимость равна

(m + n)m + nm + n

: первое слагаемое соответствует поездке

в пункт M, второе — поездке обратно в город, третье —

поездке в N.

Аналогично, стоимость перевозки грузов m и n во вто-

ром случае равна (m + n)n + mn + m

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

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

150 Решения. 1995 год. 9 класс

Пусть есть два разных порядка объезда населенных

пунктов. Первый порядок можно превратить во второй,

переставляя последовательные поездки. Это утверждение

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

что оно очень важно в теории перестановок, см. [23],

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

общая стоимость перевозки не меняется, значит, она не

зависит от порядка объезда населенных пунктов.

В т о р о й с п о с о б. Занумеруем грузы a

, a

, . . . , a

том порядке, в каком их развозят, тогда стоимость пере-

возки равна

+ 2a

+ . . . + 2a

) + a

+ 2a

+ . . . + 2a

) + . . .

... + a

n−1

+ 2a

) + a

= a

+ a

+ . . . + a

+ 2a

+ . . . + 2a

+ 2a

+ . ..

... + 2a

n−1

= (a

+ a

+ . . . + a

)

Получилось выражение, которое не зависит от порядка

нумерации грузов.

6. Будем считать, что N лежит на AB, а K лежит

на AF (рис. 60). Заметим, что FK = AN. Выберем точку

P на BC, точку R на CD, точку S на DE и точку T на EF

Рис. 60

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

FK = AN = BP = CR = DS = ET. Тогда

∠KBN = ∠TAK, ∠KCN = ∠SAT, ∠KDN =

= ∠RAS, ∠KEN = ∠PAR, ∠KFN = ∠NAP,

откуда

∠KAN + ∠KBN + ∠KCN + ∠KDN +

+ ∠KEN + ∠KFN =

= ∠KAN + ∠TAK + ∠SAT + ∠RAS +

+ ∠PAR + ∠NAP =

= ∠KAN + ∠KAN = 120

◦

+ 120

◦

= 240

◦

9 к л а с с

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

Б а з а и н д у к ц и и: 12008 делится на 19, действитель-

но, 12008 = 19 · 632.