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

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

Решения. 2003 год. 9 класс 321

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

этом же этаже в течение дня.

По условию, из покупателей, вошедших на втором

этаже, половина едет вниз, а половина — вверх. Значит,

со второго этажа на третий приехало y/2 покупателей, и

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

записать так: z < (x + y + z)/3, или 2z < x + y.

С первого этажа на третий было совершено z −

по-

ездок, так как всего на третьем этаже вышли из лифта

z человек, а y/2 из них приехали со второго этажа. А с

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

в лифт на первом этаже, кто не ехал на третий, т. е.

x −



z −



. Для решения задачи требуется сравнить эти

два выражения

z −

? x −



z −



Прибавив к каждому из них z +

, мы получим

z −

+ z +

? x −



z −



+ z +

или

2z ? x + y.

Но 2z < x + y. Значит, z −

< x −



z −



. То есть с первого

этажа на третий за этот день приехало меньше покупате-

лей, чем с первого на второй.

В т о р о й с п о с о б. Обозначим через n

количество

поездок с первого этажа на второй. Аналогично определим

числа n

, n

. Все поездки разобьем на три

группы: поездки на третий этаж (n

+ n

), поездки с

третьего этажа (n

+ n

) и поездки между первым и

вторым этажом (n

+ n

). По условию задачи, первая

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

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

покупателей, приехавших на третий этаж, равно числу

уехавших с третьего этажа. Значит, последняя группа —

самая большая:

+ n

) = (n

+ n

) < (n

+ n

322 Решения. 2003 год. 9 класс

Подставляя в это неравенство n

= n

, получим n

< n

с первого этажа чаще ездили на второй, нежели на тре-

тий.

4. После первого хода всегда образуется равнобедренная

трапеция. Посмотрим какие фигуры могут образоваться

на последующих ходах при правильной игре.

а) б)

Рис. 159

Пусть на каком-то ходу один из игроков (назовем его А)

получил шоколадку в форме равнобедренной трапеции с

меньшим основанием a и большим основанием b (длина

боковой стороны такой трапеции равна b −a). Если А от-

ломит треугольник, сторона которого меньше, чем b −a,

то другой игрок (назовем его Б) отломит треугольник со

стороной 1, и у игрока А не будет возможности сделать

ход и он проиграет (рис. 159, а). Следовательно, в этой

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

b −a. После этого хода остается параллелограмм, длины

сторон которого равны a и b −a.

Пусть игрок получил шоколадку в форме параллело-

грамма со сторонами a и b, причем a < b. Тогда по ана-

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

со стороной a. После этого хода остается равнобедренная

трапеция с основаниями b −a и b.

Таким образом, если в некоторый момент один из иг-

роков получил шоколадку в форме параллелограмма со

сторонами a и b (a < b), то через два хода он получит

шоколадку в форме параллелограмма со сторонами a и

b −a.

Если же один из игроков получил параллелограмм с

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

ется треугольник (рис. 159, б).

Решения. 2003 год. 9 класс 323

Теперь приведем выигрышную стратегию для второго

игрока при простом n: ему достаточно каждый раз от-

ламывать кусок наибольшего размера. Покажем, что эта

стратегия приводит к выигрышу. Пусть первый игрок от-

ломал треугольник со стороной k. После хода второго иг-

рока образовался параллелограмм со сторонами k и n −k.

Эти числа взаимно просты, так как n — простое число. Да-

лее, после каждого хода второго игрока будет получаться

параллелограмм (пока в конце концов не получится ромб).

Длины сторон этого параллелограмма взаимно просты (ес-

ли k и n взаимно просты, то k и n −k тоже взаимно

просты, см. факт 5). Значит, длины сторон ромба тоже

взаимно просты. Но это означает, что получится ромб со

стороной 1! Первый будет вынужден отломать от него тре-

угольник со стороной 1, после чего второй выигрывает.

Если n = 1, то первый уже выиграл. Пусть теперь число

n составное. Обозначим через p любой простой делитель

числа n (см. факт 10). Пусть первый сначала отломает

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

вает самый большой кусок. Через некоторое время второй

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

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

К о м м е н т а р и й. Заметим, что описанный процесс есть не что

иное, как алгоритм Евклида (см. [30], гл. 3).

Рис. 160

5. Пусть точка O — центр

окружности (рис. 160). Так как

треугольник ABC прямоугольный,

точка O совпадает с серединой

гипотенузы AB (см. факт 14).

Угол NOK прямой: действитель-

но, средняя линия NO треуголь-

ника ABC параллельна его сто-

роне BC, а прямая OK содержит

высоту равнобедренного треуголь-

ника BOC (так как луч OK явля-

ется биссектрисой угла BOC).

Нетрудно видеть, что точки E, N и O лежат на од-

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

ки ECO и EAO равны по катету и гипотенузе, поэтому

324 Решения. 2003 год. 9 класс

EO — биссектриса угла AEC. С другой стороны, треуголь-

ник AEC — равнобедренный, так как касательные, прове-

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

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

является и биссектрисой. Поэтому лучи EN и EO совпа-

дают как биссектрисы угла AEC.

Точки A, E, C и O лежат на одной окружности, так как

∠ECO = ∠EAO = 90

◦

. Из теоремы о пересекающихся хордах

окружности следует, что

AN · NC = EN · NO. (1)

Применяя ту же теорему к хордам AC и MK исходной

окружности, получаем

AN · NC = MN · NK. (2)

Комбинируя (1) и (2), получаем, что

MN · NK = EN · NO.

По теореме, обратной к теореме о пересекающихся хор-

дах, получаем, что точки M, K, E и O лежат на одной

окружности.

Углы EMK и EOK равны, как опирающиеся на одну

дугу. Но угол EOK — прямой, значит, и угол EMK —

прямой.

6. Приведем одну из возможных стратегий узников.

Выберем одного из узников (будем называть его «счет-

чиком», а остальных узников — «обычными»). Он будет

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

образом. Вначале число подсчитанных узников равно 0.

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

свет включен, то он прибавляет к уже посчитанному чис-

лу узников единицу и выключает свет, если же свет не

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

свою камеру. Каждый из «обычных» узников действует

по такому правилу: если, приходя в комнату, он обна-

руживает, что свет не горит, и он до этого ни разу не

включал свет, то он его включает. В остальных случаях

он ничего не меняет. Когда число посчитанных узников

становится равным 99, «счетчик» говорит, что все узники

уже побывали в комнате.

Решения. 2003 год. 10 класс 325

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

бождение. В самом деле, действуя согласно этой стра-

тегии, каждый узник, кроме «счетчика», включит свет

в комнате не более одного раза, а «счетчик» вообще

не включает свет. Если «счетчик» насчитает 99, значит

каждый из оставшихся узников побывал в комнате хотя

бы раз. И «счетчик» там, конечно, уже был.

Остается доказать, что «счетчик» в какой-то момент

«досчитает» до 99, т. е. что каждый из 99 узников вклю-

чит свет. Предположим, что это не так — свет будет вклю-

чен менее 99 раз, т. е., досчитав до некоторого числа

m < 99, «счетчик» выключит свет, и больше свет никогда

зажжен не будет (иначе, зайдя в комнату после следую-

щего включения света, «счетчик» досчитает до m + 1). Так

как «обычных» узников больше m, то найдется «обыч-

ный» узник, который свет никогда не зажигал. По усло-

вию он окажется в комнате и после указанного выше

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

жен будет включить свет. Противоречие.

К о м м е н т а р и й. Придумайте стратегию узников, если неизвест-

но, включена вначале лампа или выключена.

10 к л а с с

1. Решение может состоять просто в проверке того,

что числа a = 1, b = 5, c = 6 действительно удовлетворяют

условию. Попробуем объяснить, как можно найти такие

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

Заметим, во-первых, что корни уравнений, отличающих-

ся только знаком при bx, противоположны, поэтому

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

+ bx + c = 0 и ax

+ bx −c = 0 были целыми. Тогда кор-

ни уравнений ax

−bx + c = 0 и ax

−bx −c = 0 окажутся

целыми автоматически.

Далее, если x

и x

— целые корни уравнения ax

+ bx + c, то по теореме Виета b = −(x

+ x

)a, c = x

a, т. е.

все коэффициенты уравнения можно сократить на a, при

этом опять получится уравнение с натуральными коэффи-

циентами и такими же корнями. Поэтому без ограничения

общности можно считать, что a = 1.

326 Решения. 2003 год. 10 класс

Если x

и x

— корни первого уравнения, то по теореме

Виета x

= c, x

+ x

= −b. Аналогично, если y

и y

—

корни второго уравнения, то по теореме Виета y

= −c,

+ y

= −b. Осталось подобрать такие x

, x

, y

, что

+ x

= y

+ y

, x

= −y

Годятся, например, x

= −2, x

= −3, y

= 1, y

= −6.

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

ний x

+ bx + c = 0 и x

+ bx −c = 0 были целыми, необхо-

димо, чтобы дискриминанты этих уравнений были точны-

ми квадратами: b

−4c = m

, b

+ 4c = n

. Это же условие

оказывается и достаточным — ведь b

−4c той же четно-

сти, что и b, а значит и

√

−4c (если этот корень це-

лый) оказывается той же четности (см. факт 23). Тем са-

мым, x

1,2

−b ±

√

−4c

(корни уравнения x

+ bx + c = 0) —

целые числа. Аналогичное рассуждение верно и для вто-

рого уравнения.

На самом деле, таких b, c, m, n, что b

−4c = m

+ 4c = n

, существует бесконечно много. Для решения

задачи достаточно предъявить один пример таких b, c,

m, n. Покажем, как такой пример можно было подо-

брать. Исключая c, получаем n

−b

= b

−m

, при этом,

чтобы c было целым, необходимо, чтобы b, m и n были

одной четности. Перебрав квадраты нечетных чисел от

1 до 9, находим одно из решений: 7

−5

= 5

−1 = 24;

c = 24/4 = 6. Мы нашли b и c такие, что дискриминанты

обоих уравнений — полные квадраты.

К о м м е н т а р и й. Для того чтобы найти пример, нам потребова-

лось подобрать представление 2b

в виде суммы m

+ n

, отличное от

+ b

. Мы нашли такие b, m и n просто подбором, но в действи-

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

квадратов хорошо изучена. См. комментарий к задаче 4 для 11 класса

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

2. Выберем любую из получившихся частей. Рассмот-

рим сумму a

+ a

+ ... + a

, где a

— количество сторон i-й

грани.

Каждое ребро многогранника, по которому ломаная не

проходит, посчитано в этой сумме дважды, и поэтому чет-

ность суммы не зависит от числа таких ребер (факт 23).

Решения. 2003 год. 10 класс 327

Каждое ребро, через которое проходит ломаная, входит

в сумму ровно один раз. Таких ребер 2003, поэтому вся

сумма нечетна.

Если бы количество граней с нечетным числом сторон

было четно, то рассмотренная сумма также была бы чет-

на. Значит, это количество нечетно.

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

◦

. Приведите пример такого многогранника и

такой ломаной.

◦

. Сравните эту задачу с хорошо известной задачей про марсиан.

У марсиан произвольное число рук. Однажды все марсиане взялись

за руки так, что все руки оказались занятыми. Докажите, что число

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

3. Если степень многочлена P(x) равна 0, то P(x) = 1

(старший коэффициент равен 1). Но тогда P(a

) 6= 0. Ес-

ли степень многочлена равна 1, то, например, многочлен

P(x) = x −1 и последовательность 1, 2, 3, ... (a

= n) удо-

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

Докажем, что нет таких многочленов степени 2 и вы-

ше. Пусть такой многочлен P(x) существует.

Л е м м а. Найдется такая положительная констан-

та C, что если |x|> C, то |P(x) |> |x |.

Д о к а з а т е л ь с т в о. Пусть P(x) = x

+ b

n−1

+ ...

... + b

+ b

x + b

. Возьмем C = |b

n−1

|+ . . . + |b

|+ |b

|+ 1.

Если |x|> C, то

|P(x)|> |x|

−|b

n−1

+ . . . + b

x + b

> |x |

−(|b

n−1

|· |x|

n−1

+ . . . + |b

|· |x|+ |b

|) >

> |x |

−(|b

n−1

|· |x|

n−1

+ . . . + |b

|· |x|

n−1

+ |b

|· |x|

n−1

) =

= |x |

n−1

· (|x |−(|b

n−1

|+ ... + |b

|)) > |x|

n−1

> |x |

(мы два раза воспользовались тем, что |x|> 1). Лемма до-

казана.

Заметим теперь, что все члены последовательности

по модулю ограничены числом C. Действительно, если

|> C, то C < |a

|< |P(a

)|= |a

n−1

|. Продолжая, получим:

C < |a

|< |P(a

)|= |a

n−1

|< |P(a

n−1

)|= |a

n−2

|< . . .

... < |P(a

)|= |a

|< |P(a

)|= |0|,

что неверно.

328 Решения. 2003 год. 10 класс

Мы получили, что все члены последовательности по

модулю не превосходят C; с другой стороны, по условию

задачи все они целые. Но таких чисел только конечное

число, значит, в последовательности обязательно будут по-

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

4. П е р в ы й с п о с о б. Обозначим

BC = a, CA = b, AB = c, MA

= x, MB

= y, MC

= z.

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

дения равны нулю:

(z, c) = (x, a) = (y, b) = 0, (1)

((x −y), (a −b)) = ((x −z), (a −c)) = 0. (2)

Раскрывая в (2) скобки и учитывая (1), получим

(a, y) + (b, x) = (a, z) + (c, x) = 0.

Поскольку a = −b −c и b = −c −a, получаем:

0 = (a, y) + (b, x) = (−b −c, y) + (−a −c, x) = −(c, y) −(c, x).

Аналогично,

0 = (a, z) + (c, x) = (−b −c, z) + (−a −b, x) = −(b, z) −(b, x).

Нужно доказать, что

x + y + z = 0,

для чего достаточно, чтобы

(b, x + y + z) = (c, x + y + z) = 0.

Действительно,

(b, x + y + z) = (b, x) + (b, z) = 0,

(c, x + y + z) = (c, x) + (c, y) = 0.

В т о р о й с п о с о б. Идея решения состоит в сведении

задачи к эквивалентной для некоторой более простой си-

туации. (Так, например, в алгебре решают уравнения, сво-

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

ми.) Сведем задачу аффинными преобразованиями к слу-

чаю равностороннего треугольника.

Решения. 2003 год. 10 класс 329

В исходном треугольнике точки A

, B

и C

задаются

условиями

⊥BC, MB

⊥AC, MC

⊥AB, A

⊥MC, A

⊥MB.

Повернув треугольник A

вокруг точки M на 90

◦

против

часовой стрелки (рис. 161, а), получим треугольник A

причем на точки A

, B

и C

будут выполнены условия

kBC, MB

kAC, MC

kAB, A

kMC, A

kMB. (3)

При этом медианы треугольника A

пересекаются в

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

ника A

пересекаются в точке M. Проведем аффинное

преобразование, переводящее треугольник ABC в равно-

сторонний. При аффинном преобразовании точки пересе-

чения отрезков переходят в пересечения их образов, а

параллельные прямые — в параллельные.

A C

а) б)

Рис. 161

Итак, если вместо точек M, A, B, C, A

, B

, C

взять

точки, получившиеся из них после аффинного преобразо-

вания, то условия (3) будут выполняться. Поэтому доста-

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

треугольника A

пересекаются в точке M в предполо-

жении, что треугольник ABC равносторонний.

В этом случае медиана MC образует равные углы со сто-

ронами AC и BC. Тогда из 1-го, 2-го и 4-го условий (3) следу-

ет, что A

— равнобедренный треугольник (рис. 161, б).

Аналогично, A

M = C

M. Теперь уже нетрудно понять, что

треугольник A

равносторонний, а M — его центр.

330 Решения. 2003 год. 10 класс

5. Покажем, как разделить страну на губернии так,

чтобы выполнялось условие задачи. Если в стране всего

один город, то задача тривиальна: можно взять две губер-

нии пустыми.

Назовем несколько городов страны автономной обла-

стью, если из каждого города этой автономной области

можно проехать в любой другой город этой автономной об-

ласти, не выезжая за ее пределы. (Легко видеть, что тогда

для этой автономной области будет выполнятся условие

задачи, т. е. такой путь, не проходящий два раза через

один город, будет единственным.)

Возьмем произвольный город. Очевидно, он образует

автономную область, и эту автономную область можно

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

последовательно увеличивать автономную область, добав-

ляя к ней на каждом шаге несколько городов так, чтобы

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

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

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

города страны. Тогда найдется дорога, ведущая из города

Рис. 162

области (обозначим его через X) в

город, еще не принадлежащий этой

области (назовем его Y). Действи-

тельно, если все дороги, выходя-

щие из городов автономной обла-

сти, ведут в города этой области,

то из городов области можно про-

ехать только в города этой области.

Рассмотрим несамопересекающийся

путь (последовательность дорог, не

проходящих два раза через один

город), ведущий из Y в X. Вооб-

ще говоря, он может до города X

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

это невозможно, т. е. на этом пути не могут встретить-

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

города X.

Пусть Z — первый город автономной области на пути из

Y в X. Предположим, что Z и X — разные города этой об-

ласти. Так как для области выполнялось условие задачи,