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

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

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

найдется несамопересекающийся путь из X в Z, идущий

только по городам области (рис. 162).

Но тогда из X можно добраться до Z двумя несамопере-

секающимися путями: не выезжая из области и через Y.

Но по условию такое невозможно.

Следовательно, путь из Y в X не содержит других горо-

дов области, кроме X. Теперь присоединим все города на

этом пути (включая Y) к автономной области и отнесем

их поочередно в те две губернии, в которые X не входит.

Рис. 163

Заметим, что можно проехать из

любого добавленного города в лю-

бой другой добавленный или в лю-

бой город области и наоборот, т. е.

получилась опять автономная об-

ласть. Докажем, что она правиль-

но разделена на губернии. Так как

из каждого города в любой другой

можно проехать ровно одним пу-

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

один и тот же город, то все доро-

ги, соединяющие присоединенные

города, — это дороги на пути Y →X.

Аналогично, есть только две дороги, соединяющие какой-

либо присоединенный город с городом, уже имевшимся в

области — это дорога из X в Y и последняя дорога на пути

Y →X (рис. 163). Поэтому нет дорог, соединяющих города

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

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

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

не лежащий в автономной области, мы получим автоном-

ную область, совпадающую со всей страной, при этом она

будет правильно разделена на губернии. Утверждение за-

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

К о м м е н т а р и й. Подумайте сами, какую форму может иметь

граф, удовлетворяющий условию задачи.

6. Пусть, например,

f(x) = + arctg x,

g(x) = x + ,

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

h(x) — функция, которая на интервале



−

+ n;

+ n



равна P

(tg x) (т. е. график многочлена P

«сжат» в ин-

тервал



−

+ n;

+ n



, рис. 164).

3 /2/2 5 /2

(tg x) P

(tg x)

Рис. 164

Тогда

(x) = h(arctg x + n ) = h(g(g(...(g(f(x)))...)))

(функция g используется n −1 раз).

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

◦

. Рассмотрим множество пар (x, n), где x —

действительное число, а n — натуральное. Это множество обозначается

Рис. 165

R ×N и называется декартовым произведением

множества действительных чисел и множе-

ства натуральных чисел. Можно представлять

себе это множество как множество прямых на

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

сцисс, и проходящих через точку (0, n), где

n = 1, 2, 3, . .. (рис. 165).

Теперь рассмотрим отображения:

H: R ×N →R, H(x, n) = P

(x),

F: R →R ×N, F(x) = (x, 1),

G: R ×N →R ×N, G(x, n) = (x, n + 1).

Отображение H «кодирует» все многочлены P

(x), и нетрудно видеть,

что

(x) = H(G(G( .. . (G(F(x))). .. ))),

где отображен ие G используется n −1 раз. К сожалению, это еще не

дает решения нашей задачи, так как в задаче треб уется предъявить

функции, т. е. отображения из R в R, а не из R в R ×N. Идея

решения задачи состоит в том, чтобы «уложить» R ×N на прямую.

Такое укладывание задается отображением A(x, n) = arctg x + n.

◦

. Утверждение задачи остается верным для любой последователь-

ности функций P

(x) (не обязательно многочленов).

Решения. 2003 год. 11 класс 333

11 к л а с с

1. Освободившись от знаменателя, приведем наше ра-

венство к виду

z −x

y + z

y −z

x + y

x −y

z = 0. (1)

Разложим левую часть на множители:

z −x

y + z

y −z

x + y

x −y

z =

= x

(z −y) + z

(y −x) + y

(x −z) =

= x

((z −x) + (x −y)) + z

(y −x) + y

(x −z) =

= x

(z −x) + y

(x −z) + x

(x −y) + z

(y −x) =

= (z −x)(x

−y

) + (x −y)(x

−z

) =

= (z −x)(x −y)(x

+ xy + y

) + (x −y)(x −z)(x

+ xz + z

) =

= (x−y)(x−z)(xz+z

−xy−y

) = (x−y)(x−z)(z−y)(x+y+ z).

Заметим, что при положительных x, y, z выражение в

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

числа различны, то все множители отличны от нуля. По-

этому (1) не может выполняться.

К о м м е н т а р и й. Как догадаться до такого разложения на мно-

жители? Обозначим левую часть равенства (1) через P(x, y, z). То-

гда P(x, y, z) = 0, если x = y. Из этого можно вывести, что многочлен

P(x, y, z) делится на x −y (идея доказательства: проверьте, что много-

член P(x, y, z)−P(y, y, z) делится на x −y). По аналогичным соображе-

ниям P(x, y, z) делится на x −z и z −y (см. факт 21). Итак, P(x, y, z)

делится на (x −y)(x −z)(z −y).

Оказывается, то, что частное равно x + y + z, тоже можно понять

ничего не вычисляя. Дело в том, что многочлен P(x, y, z) обладает

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

то его значение умножится на −1 (такие многочлены называются ко-

сосимметрическими). Аналогичным свойством обладает и многочлен

(x −y)(x −z)(z −y). Значит, их частное является симметрическим мно-

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

Теперь уже нетрудно понять, что частное имеет вид C(x + y + z), где

C — константа (используйте, что частное есть многочлен степени 1).

Значит,

P(x, y, z) = C(x −y)(x −z)(z −y)(x + y + z).

Чтобы убедится в том, что C = 1, достаточно приравнять коэффициен-

ты, скажем, при x

2. См. решение задачи 3 для 10 класса при n = 2003.

334 Решения. 2003 год. 11 класс

3. Пусть U и V — точки, симметричные H относительно

AB и AD соответственно, X — точка пересечения прямых

UC и AB, Y — точка пересечения прямых VC и AD. Преж-

де всего отметим, что точки U и V лежат на описанной

X H Y

Рис. 166

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

(рис. 166). Для доказательства

заметим, что

∠AUB = ∠AHB = ∠ADB.

Значит, точка U лежит на ука-

занной окружности по теореме,

обратной к теореме об углах,

вписанных в окружность. Дока-

зательство для точки V анало-

гично.

Как следствие,

∠XHY = ∠XHU + ∠UHV + ∠VHY =

= ∠DUC + ∠DHB + ∠CVB = ∠DAC + −∠DAB + ∠CAB = .

Значит, точки X, H, Y лежат на одной прямой.

Симметрия относительно прямой AB показывает, что

прямая PH проходит через X, а QH — через Y. Утвержде-

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

К о м м е н т а р и й. Наше решение годится лишь если точки рас-

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

использовать ориентированные углы (см. [46], гл. 2).

4. Примем некоторую точку окружности за начало от-

счета. Пусть a

— длина дуги от начала отсчета до i-й

вишенки по часовой стрелке. Рассмотрим числа b

= a

−i.

Л е м м а. |b

−b

|< 1 для любых m, k.

Д о к а з а т е л ь с т в о. Без ограничения общности мож-

но считать, что m > k. Нам нужно доказать, что b

−b

< 1

и b

−b

< 1. Рассмотрим k-ю и m-ю вишенки, они делят

окружность на две дуги. Рассмотрим, сначала, дугу, ко-

торая «заметается», если двигаться от a

к a

по часовой

стрелке. Длина этой дуги — a

−a

, а число вишенок на

ней — m −k −1. По условию число вишенок на этой дуге

меньше длины этой дуги, т. е. m −k −1 < a

−a

. Тогда

−b

= (a

−k) −(a

−m) = a

−a

+ m −k < 1.

Решения. 2003 год. 11 класс 335

Рассмотрим теперь вторую дугу между m-й и k-й ви-

шенками. Длина этой дуги — n −(a

−a

), а число више-

нок на ней — n −(m −k) −1, т. е.

n −(m −k) −1 < n −(a

−a

откуда b

−b

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

Пусть b

— наименьшее из чисел b

. Тогда 0 6 b

−b

< 1

для любого i. Пусть x чуть-чуть меньше, чем b

. Тогда

x< b

< x+ 1 для всех i. То есть x + i < a

< x+ 1+ i для всех i.

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

динатами x, x + 1, ..., x + n −1, — искомый.

К о м м е н т а р и й. Данная задача близка к известной «задаче про

бензоколонки»: на кольцевой дороге расположено несколько безоколо-

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

Известно, что суммарное количество бензина во всех бензоколонках

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

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

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

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

5. Для каждой из граней рассмотрим вектор внешней

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

направленный вовне многогранника.

◦

. Докажем, что угол между любыми двумя внешними

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

Рис. 167

нашлись две грани Г

и Г

внешние нормали к которым

образуют угол не больше /2.

Тогда грани Г

и Г

при-

надлежат полуплоскостям П

и П

, которые образуют дву-

гранный угол величиной не

меньше /2.

Возьмем точку P на гра-

ни Г

. Пусть P

— проекция

точки P на плоскость гра-

ни Г

. Так как угол между

внешними нормалями к гра-

ням Г

и Г

не больше чем /2, а наш многогранник —

выпуклый, точка P

лежит вне многоугольника Г

. Следо-

вательно, найдется прямая, содержащая некоторое ребро r

336 Решения. 2003 год. 11 класс

грани Г

и отделяющая P

от Г

. Многогранник лежит

внутри острого двугранного угла, соответствующего ре-

бру r, но P лежит вне этого двугранного угла (рис. 167).

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

◦

. Остается показать, что в пространстве не существует

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

тупые или развернутые.

Пусть это не так, и u

, u

— пять векторов,

попарные углы между которыми тупые или развернутые.

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

Oz была сонаправлена с u

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

проекцию вектора u

на плоскость

Oxy. Пусть u

= (x

, y

, z

), тогда x

= y

= 0, z

> 0 и v

= 0.

Условие, что все углы — тупые или развернутые, рав-

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

тельны. В частности,

= (u

, u

) < 0,

откуда z

< 0 при 1 6 i 6 4. Значит, z

> 0 при 1 6 i, j 6 4,

так что

, v

) = (u

, u

) −z

< (u

, u

) < 0

при i 6= j, i, j > 0. Значит, v

, v

— четыре вектора на

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

Но это невозможно.

Итак, у многогранника четыре грани. Заметим, что

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

тетраэдром.

И д е я д р у г о г о р е ш е н и я. Сначала докажем, что

в каждой вершине многогранника сходятся три грани.

Для этого достаточно доказать, что сумма двугранных уг-

лов любого n-гранного угла больше, чем (n −2). Так как

n-гранный угол можно разрезать на n −2 трехгранных,

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

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

каждой из вершин тоже острые. Из этого нетрудно выве-

сти, что все грани — треугольники. Теперь уже нетрудно

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

6. Приведем пример, показывающий, что при k 6 290

описанная ситуация возможна. Упорядочим всех борцов

Решения. 2003 год. 11 класс 337

по силе и перенумеруем их по возрастанию силы (пер-

вый — самый слабый). Назовем 210 слабейших новичками,

а 190 сильнейших — мастерами. В частности, любой но-

вичок окажется слабее любого мастера. Пронумеруем де-

ревни против часовой стрелки. Поместим в первую дерев-

ню одного слабейшего новичка и 19 слабейших мастеров;

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

18 мастеров, слабейших из оставшихся; в третью — трех

слабейших из оставшихся новичков и 17 мастеров, сла-

бейших из оставшихся, и т. д.; в последнюю деревню мы

поместим 20 сильнейших новичков. Это размещение по

деревням указано в таблице (в столбце «Борцы» числа,

набранные прямым шрифтом, означают силы мастеров,

набранные курсивом — силы новичков).

Деревни Борцы Деревни Борцы

1 1, 211—229 11 56—66, 356—364

2 2—3, 230—247 12 67—78, 365—372

3 4—6, 248—264 13 79—91, 373—379

4 7—10, 265—280 14 92—105, 380—385

5 11—15, 281—295 15 106—120, 386—390

6 16—21, 296—309 16 121—136, 391—394

7 22—28, 310—322 17 137—153, 395—397

8 29—36, 323—334 18 154—171, 398—399

9 37—45, 335—345 19 172—190, 400

10 46—55, 346—355 20 191—210

Покажем, что i-я деревня сильнее (i −1)-й при i > 1.

Действительно, в i-й деревне есть i новичков и 20 −i

мастеров. При этом мастера i-й деревни победят всех в

(i −1)-й, а новички победят новичков, и всего побед будет

20(20 −i) + i(i −1) = i

−21i + 400. Вершина этой параболы

находится в точке i = 10,5, а ветви направлены вверх,

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

ровно при двух значениях — i = 10 и i = 11 — и равно

−21 · 10 + 400 = 290. То есть i-я деревня сильнее (i −1)-й

338 Решения. 2003 год. 11 класс

при k 6 290. Кроме того, мастера первой деревни победят

новичков 20-й, и всего побед будет 20 · 19 = 380 > 290, т. е.

все условия выполнены.

Покажем, что при k > 290 такая ситуация невозможна.

Упорядочим в каждой деревне борцов по убыванию си-

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

Покажем, что деревня, в которой живет слабейший из

выбранных борцов, не может быть сильнее следующей за

ней. Обозначим выбранных борцов в нашей и следующей

деревнях через A и B соответственно. Тогда в нашей де-

ревне 11 борцов не сильнее, чем A, а в следующей — 10

борцов хотя бы такой же силы, как B. Все поединки меж-

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

этих поединков — 110, т. е. поединков, в которых выиграл

борец нашей деревни, не больше, чем 20 · 20 −110 = 290.

7. Значения a = 2 и a = 3 возможны: например, 2

−1 =

= 2 + 1, (3 −1)

= 3 + 1. Предположим, что при некотором

a > 3 требуемое равенство выполнено:

A = (a

−1) . . . (a

−1) = (a

+ 1) . . . (a

+ 1). (1)

Л е м м а 1. Как любое m

, так и a −1 являются сте-

пенями двойки.

Д о к а з а т е л ь с т в о. Пусть — произвольный нечет-

ный делитель числа m

(возможно, = 1), а p — любой

простой делитель числа a −1. Тогда A делится на p (см.

факт 8), значит, в правом произведении найдется множи-

тель a

+ 1, делящийся на p (см. факт 9). Заметим, что

((a

) + 1) −((a )

−1) = 2.

С другой стороны, (a

) + 1 делится на p, так как a

+ 1

делится на p, а (a )

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

делится на p. Значит, 2 делится на p, откуда p = 2. Итак,

2 — единственный простой делитель числа a −1, значит,

a −1 — степень двойки (см. факт 10), т. е. найдется такое

K, что 2

= a −1 = (a

−1

+ . . . + a + 1)(a −1). Так как —

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

числа 2

, т. е. 1. Значит, = 1. Следовательно, a −1 = 2

Кроме того, мы доказали, что единица — единственный

Решения. 2004 год. 8 класс 339

нечетный делитель числа m

, значит, m

— степень двойки.

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

Так как a −1 > 2, то a −1 делится на 4, поэтому a

+ 1

дает остаток 2 при делении на 4 при любом k (см. факт 7).

Обозначим a

+ 1

. Тогда a

— нечетное число. Нам

понадобится следующая формула:

−1 = (a −1)(a + 1)(a

+ 1)(a

+ 1) . . . (a

d−1

+ 1) =

= 2

· 2

· a

...a

d−1

. (2)

Л е м м а 2. Все a

попарно взаимно просты.

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

и a

и до-

кажем, что они взаимно просты. Можно считать, что i > j.

В силу (2) a

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

, c другой стороны, a

+ 1

делится на a

. Поэтому любой общий делитель чисел a

является также и делителем числа

2 = (a

+ 1) −(a

−1).

Для завершения доказательства остается заметить, что

числа a

и a

нечетны. Лемма доказана.

Перемножив представления (2) для a

−1, получим,

что A представляется в виде A = 2

)

...(a

)

, причем

N > N

+ . . . + N

. Поскольку любое из чисел a

+ 1 дает

остаток 2 при делении на 4, то l = N (см. (1)). Но каждое

из a

+ 1 делится на одно из чисел a

(действительно, если

= 2

s, где s нечетно, то a

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

). Тогда, по-

скольку l > N

+ . .. + N

, то на какое-то из чисел a

делится

больше, чем N

чисел a

+ 1, а следовательно, A делится

на a

. Противоречие с тем, что a

нечетны и попарно

взаимно просты.

2004 год

8 к л а с с

1. Нетрудно проверить, что корнями уравнения x

+ 3x + 2 = 0 являются −1 и −2. После увеличения коэф-

фициентов на единицу получится уравнение x

+ 4x + 3 = 0

с корнями −1 и −3, потом уравнение с корнями −1 и −4,

340 Решения. 2004 год. 8 класс

затем — с корнями −1 и −5, и, наконец, уравнение с кор-

нями −1 и −6.

Чтобы проверить вышесказанное, придется решить 5

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

ваться теоремой Виета. Все наши уравнения имеют вид

+ (p + 1)x + p = 0,

где p — целое число. Тогда, по обратной теореме Виета,

корнями этого уравнения будут целые числа −1 и −p:

(−1) + (−p) = −(p + 1), (−1)(−p) = p.

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

◦

. Ср. с задачей 2 для 9 класса.

◦

. Годится любое уравнение, у которого один корень −1, а дру-

гой — целый. При увеличении коэффициентов на единицу корень −1

будет сохраняться, а второй корень — уменьшаться на единицу.

◦

. То, что корень −1 сохраняется, можно понять еще и так: уве-

личение коэффициентов p и q на единицу означает прибавление x + 1

к исходному трехчлену. При этом значение трехчлена в точке −1

меняться не будет. Значит, если число −1 было корнем, то оно и

останется корнем.

◦

. Попробуем объяснить, как догадаться, что один из корней нуж-

но брать равным −1. Пусть x

и x

— корни. Тогда (по теореме Виета)

+ x

= −p, x

= q.

Значит, при увеличении p и q на единицу, сумма корней уменьшается

на единицу. Самый простой способ этого добиться — это оставить x

неизменным, уменьшив x

на 1:

+ (x

−1) = −(p + 1).

Посмотрим, что произойдет с произведением корней:

−1) = x

−x

Итак, произведение корней уменьшится на x

, но оно должно увели-

читься на 1. Значит, нужно взять x

= −1.

2. Нужное разрезание изображено на рис. 19 на с. 75.

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

бьем трапецию на квадрат площади 4 и треугольник пло-

щади 1. Мы видим, что площадь трапеции равна 5. Зна-

чит, и площадь искомого квадрата равна 5, поэтому его

сторона равна

√

5. По теореме Пифагора длину

√

5 име-

ет гипотенуза прямоугольного треугольника с катетами 1

и 2. Теперь уже легко придумать нужное разрезание.