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

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

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

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

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

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

соседних чисел делится на 19 (см. факт 5):

1203...3

|{z}

k троек

08 −1203...3

|{z}

k − 1 тройка

08 = 1083 · 10

Эта разность делится на 19, так как 1083 = 19 · 57. Наше

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

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

◦

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

◦

. Можно показать, что частное будет иметь вид 63 .. .32.

2. Выберем произвольную точку A

на BC и проведем

отрезок AA

(рис. 61, а). Докажем, что среди отрезков

A C

а)

A C

б)

Рис. 61

с началом в точке C и концом на сто-

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

отрезку AA

— это такие отрезки CC

, что

∠C

CA = ∠A

AC, ∠C

CB = ∠A

AC.

Действительно, если рассмотреть сим-

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

соты, выходящей из точки B, то видно,

что CC

= AA

. Симметрия относительно

высоты, выходящей из точки C, пока-

зывает, что CC

= CC

То, что нет других таких точек C

что CC

= AA

, следует из того, что из

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

более двух наклонных данной длины.

Приведем более строгое доказательство.

Пусть CC

= AA

. Проведем высоты AH

(рис. 61, б). Прямоугольные треугольники

C и A

A равны по катету и гипотенузе.

Значит, ∠H

= ∠H

. Возможны две ситу-

ации: точка C

лежит между точками A и H

и точка C лежит между B и H

. В первом случае углы C

CA и A

равны, во втором — углы C

CB и A

AC равны.

Итак, осталось рассмотреть точку пересечения AA

и точку пересечения AA

и CC

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

Точка P

, в которой пересекаются отрезки AA

и CC

лежит на высоте треугольника ABC, выходящей из вер-

шины B. Это (интуитивно очевидное) утверждение можно

доказать так: треугольник AP

C равнобедренный, так как

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

дикуляр к отрезку AC является высотой этого треуголь-

ника, и, значит, он проходит через точку P

. Но этот

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

ника ABC. Значит, точка P

лежит на высоте треуголь-

ника ABC. В силу симметрии все точки на этой высоте

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

Пусть P

— точка пересечения AA

и CC

. Имеем:

∠AP

C = 180

◦

−∠A

AC −∠C

CA =

= 180

◦

−∠A

AC −(60

◦

−∠A

AC) = 120

◦

т. е. отрезок AC виден из точки P

под углом 120

◦

. Гео-

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

которых отрезок AC виден под углом 120

◦

, — это дуга

окружности с концами в точках A и C Нетрудно видеть,

что эта дуга проходит через центр треугольника ABC.

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

видим, что все точки этой дуги удовлетворяют условию

(проверьте).

3. Идея решения: возьмем максимальную полоску (рав-

ную максимальной стороне прямоугольника). Остальные

полоски будем объединять в пары, дающие в сумме мак-

симальную полоску. Если мы заполнили прямоугольник,

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

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

на различные полоски.

Рассмотрим два случая: n 6 1995 и n > 1995.

С л у ч а й n 6 1995. Если n 6 998, то разрежем прямо-

угольник на n полосок длиной 1995. Первую сохраним,

вторую разрежем на две полоски длиной 1 и 1994, тре-

тью — на две полоски длиной 2 и 1993 и т. д. Последняя

полоска 1 ×1995 будет разрезана на части 1 ×(n −1) и

1 ×(1996 −n). У нас получились полоски с длинами:

1, 2, . . . , n −1, 1996 −n, (1996 −n) + 1, . . . , 1994, 1995.

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

Ясно, что первые n −1 полосок различны, остальные по-

лоски тоже различны. Однако, чтобы среди первых n −1

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

лосок, необходимо (и достаточно), чтобы n −1 < 1996 −n.

Рис. 62

Это неравенство выполняется, пото-

му что n 6 998. Такое разрезание для

прямоугольника 5 ×9 изображено на

рис. 62.

Покажем, что при 998 < n 6 1995

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

образом не удастся. Действительно,

самая длинная полоска, которая по-

мещается в нашем прямоугольнике, — 1 ×1995. Значит,

даже если мы используем все 1995 возможных полосок,

их суммарная площадь будет

1 + 2 + 3 + ... + 1994 + 1995 =

1995 · 1996

(см. комментарий), а площадь прямоугольника равна

1995n. Значит, должно выполняться неравенство:

1995n 6

1995 · 1996

но это означает, что n 6 998.

С л у ч а й n > 1995 аналогичен. Разрежем прямоуголь-

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

разрежем на две полоски длиной 1 и n −1 и т. д. Полу-

чатся полоски с длинами

1, 2, . . . , 1994, n −1994, (n −1994) + 1, . . . , n.

Они будут различными, если 1994 < n −1994, т. е. n > 3989.

Чтобы доказать необходимость этого условия, снова срав-

ним площади. Так как суммарная площадь полосок не

превосходит

n(n + 1)

, получаем неравенство

1995n 6

n(n + 1)

Отсюда n > 2 · 1995 −1 = 3989.

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

◦

. Прямоугольник n ×m c n > m можно раз-

резать на полоски различной длины тогда и только тогда, когда

n > 2m −1.

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

◦

. Мы воспользовались формулой 1 + 2 + . .. + n =

n(n + 1)

. Эта фор-

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

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

Тем не менее, приведем элегантное доказательство этой формулы. Обо-

значим 1 + 2 + . .. + n = X и посчитаем сумму всех чисел в таблице:

1 2 3 . .. n −2 n −1 n

n n −1 n −2 . .. 3 2 1

Так как сумма в каждом столбце равна n + 1, а столбцов n, сумма всех

чисел в таблице равна n(n + 1). С другой стороны, сумма в каждой из

строк равна X, так что сумма всех чисел в таблице равна 2X. Итак,

2X = n(n + 1), откуда и следует наше утверждение.

4. П е р в ы й с п о с о б. Из условия следует, что

a + b + c + d = a + b + c +

(a + c)(b + c)

— целое число. Значит, дробь сократима. Поскольку оба

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

сокращения от каждого из них останется число, большее

единицы. Итак, число a + b + c + d является произведени-

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

является простым.

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

нием: если дробь

представляет собой целое число, то можно пред-

ставить z в виде произведения ts так, чтобы x делилось на t, а y

делилось на s. Если Вы разберетесь во втором способе решения, то

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

В т о р о й с п о с о б. Докажем следующее утверждение:

если ab = cd, то найдутся натуральные u, v, w, z такие,

что a = uv, b = wz, c = uw, d = vz. Действительно, разложим

числа a, b и c на простые множители. Так как число c

является делителем произведения ab, все его простые мно-

жители присутствуют среди множителей a и b (причем,

если простой множитель входит в c несколько раз, то он

входит в a и b в сумме по крайней мере столько же раз).

Пусть p

, . . . , p

— все простые делители чисел a и b.

Тогда

a = p

...p

b = p

...p

c = p

...p

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

где некоторые из чисел k

, l

, m

могут быть равны нулю.

Как объяснялось выше, m

6 k

+ l

при i = 1, . . . , n. Зна-

чит, можно представить m

в виде t

+ s

, где t

6 k

, s

6 l

Положим

u = p

...p

w = p

...p

Тогда c = uw. Кроме того, u — делитель числа a, а w —

делитель числа b. Поэтому можно записать a = uv, b = wz

с целыми v и z. Тогда

d =

uvwz

= vz.

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

Итак,

a + b + c + d = uv + wz + uw + vz = (u + z)(v + w).

Оба множителя больше единицы, значит, число a + b + c +

+ d — составное.

Рис. 63

5. П е р в ы й с п о с о б. Сначала из-

ложим идею решения. Заметим, что

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

ники, не важен (в том смысле, что ко-

нечный результат от этого не зависит).

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

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

из них придется разрезать (рис. 63).

Сделаем сначала эти три разреза. В ре-

зультате образуются две тройки оди-

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

этих троек придется разрезать по два

треугольника. Сделаем эти разрезы.

После этого у нас опять образуются че-

тыре одинаковых треугольника!

Теперь изложим эту идею более

строго. Предположим, что после неко-

торого числа разрезаний из четырех

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

попарно различные, и пусть n — наименьшее такое число.

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

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

описанные выше 7 разрезаний. Получим снова 4 одина-

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

n −7 разрезов. Но это противоречит предположению, что

n — минимальное число разрезов, необходимое для того,

чтобы получить разные треугольники.

В т о р о й с п о с о б (выходящий за рамки программы

9-го класса). Пусть гипотенузы исходных треугольников

равны 1, а их катеты — p и q. Тогда все получаемые разре-

заниями треугольники подобны исходному с коэффициен-

том вида p

(m и n — целые неотрицательные числа).

При разрезании такого треугольника получаются два —

подобные исходному с коэффициентами p

m+1

и p

n+1

Теперь задачу можно переформулировать так: на коорди-

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

та стоят 4 фишки. Любую фишку можно заменять на

две соседние (сверху и справа). Докажите, что нельзя

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

ках.

Воспользуемся идеей инварианта (см. факт 2). Запишем

в клетку c координатами (m, n) число 2

−(m+n)

и назовем

весом фишки то число, на котором она стоит. Нетрудно

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

будет меняться.

В начальный момент сумма весов фишек равна 4. Сум-

ма чисел, записанных во всех клетках, тоже равна 4.

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

∞

n=0

∞

m=0

−(n+m)

∞

n=0

−n

∞

m=0

−m

= 2 · 2 = 4.

Предпоследнее равенство следует из формулы суммы бес-

конечной геометрической прогрессии.

Поэтому если фишки стоят в разных клетках, то сумма

их весов меньше 4. Следовательно, переход невозможен.

К о м м е н т а р и й. Похожим образом решается задача про расселе-

ние бактерий М. Концевича:

В вершине положительного квадранта сидит бактерия. Каждую се-

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

в две соседние клетки (сверху и справа). В одной клетке может нахо-

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

диться только одна бактерия. Докажите, что в области x + y 6 5 всегда

останется хотя бы одна бактерия.

6. а) Нам будет удобнее работать с количеством банок,

делящимся на 3. Поэтому введем еще одну «фиктивную»

банку с нулевым весом.

Пусть, сначала, завхоз положит 27 самых легких банок

на левую чашу, а 27 самых тяжелых — на правую. Этим

он убедит всех геологов, что на левой чаше действительно

27 самых легких, а на правой — 27 самых тяжелых. Все

банки разделились на 3 кучки по 27 банок, и про каждую

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

из этой кучки.

Теперь завхоз положит 9 самых легких банок из каж-

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

на правую. При этом геологи видят действия завхоза, а

он не смешивает банки из разных кучек.

Теперь все банки разделились на 9 кучек по 9 банок,

и геологи знают, какие банки в какой кучке. Завхоз по-

ложит по 3 самых легких банки из каждой кучки на

левую чашу и по 3 самых тяжелых — на правую. Банки

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

банок по кучкам. Остается взять по самой легкой банке

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

тяжелые банки в кучках положить на правую.

б) Каждым взвешиванием банки делятся на три груп-

пы — банки на левой чаше, банки на правой чаше и

банки, не участвующие во взвешивании. Самое большее,

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

ния, — это определить, какой набор банок лежит в каждой

группе.

После первого взвешивания в одной из групп будет не

меньше трети всех банок, т. е. не меньше 27 (принцип

Дирихле, см. факт 1); при этом для геологов (кроме зав-

хоза) они будут неразличимы. При втором взвешивании

эта группа также разделится на 3 группы, в одной из

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

логов. При третьем взвешивании из этих 9 банок в одну

из новых групп попадут не меньше трех банок. Поэтому

трех взвешиваний недостаточно.

158 Решения. 1995 год. 10 класс

10 к л а с с

1. а) Покажем сначала, что sin

не может принимать

больше 4 значений. Действительно, если sin = sin , то

= + 2 k либо = − + 2 k (k — целое число). Соот-

ветственно

+ k либо

−

+ k. Этим значениям

соответствуют точки на единичной окружности:

+ ,

−

и только они. Некоторые из этих точек мо-

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

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

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

sin =

√

, тогда точки на окружности, соответствующие

углу

, — это

. Синус принимает следующие

значения в этих точках:

√

, −

и −

√

б) Если sin = 0, то = k (k — целое). Значит, sin

может равняться sin 0 = 0, sin

√

и sin

= −

√

Покажем, что sin

не может принимать больше трех

значений. Можно рассуждать, как в пункте «а». Мы при-

ведем другое доказательство. Пусть sin

= t. Воспользуем-

ся формулой синуса тройного угла:

sin = sin



3 ·



= −4t

+ 3t.

Осталось заметить, что многочлен третьей степени имеет

не более трех корней (см. факт 20).

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

◦

. Известно, что если n нечетно, то sin n

есть многочлен степени n от sin , а cos n есть многочлен степени

n от cos при любом n. См. комментарий к задаче 2 для 11 класса

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

◦

. Если sin n задан, то максимальное число значений, которое

может принимать sin равно n при нечетном n, и 2n при четном n.

Докажите это сами.

При заданном cos n , cos может принимать не более n различных

значений (вне зависимости от четности n).

Решения. 1995 год. 10 класс 159

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

3. Пусть боковые стороны трапеции — это стороны AB

и CD. Обозначим через M и N вторые точки пересечения

прямых AC и BD и окружностей с диаметрами AB, CD

соответственно (рис. 64). Если прямая AC касается окруж-

ности с диаметром AB, то мы полагаем M = A, аналогич-

но поступим, если прямая BD касается соответствующей

окружности.

Рис. 64

По теореме о касательной и секущей квадраты каса-

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

KM·KA и KN · KD. Это верно и в случаях M= A или N= D.

Значит, нам надо доказать, что

KM · KA = KN · KD. (1)

Поскольку ∠AMB опирается на диаметр, ∠KMB = 90

◦

(см. факт 14). Опять же это верно и в случае M = A,

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

ному в точку касания. Обозначим величину угла AKB

через . Из прямоугольного треугольника KMB находим

KM = KB cos . Аналогично, KN = KC cos . Подставляя

полученные формулы в (1), находим, что нам нужно лишь

доказать, что KB · KA = KC · KD. Это известное свойство

трапеции следует из подобия треугольников AKD и CKB.

В а р и а н т р е ш е н и я. Равенство (1) можно доказать

и более геометрически. Для этого докажем, что точки A,

M, N, D лежат на одной окружности.

Так как ∠BMC = 90

◦

и ∠BNC = 90

◦

, точки B, M, N и C

лежат на окружности с диаметром BC, откуда

∠CMN = ∠CBN = ∠BDA

(так как BC kAD).

160 Решения. 1995 год. 10 класс

Но тогда ∠AMN + ∠ NDA = 180

◦

, поэтому точки A, M, N,

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

отрезка секущей на ее внешнюю часть KM · KA = KN · KD.

Однако это решение существенно опирается на рису-

нок: оно не проходит, например, если хотя бы одна из

точек M и N лежит на продолжении диагонали. Эти слу-

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

зоваться ориентированными углами). Сложнее разобраться

со случаями M = A и N = D.

Со случаем M = A можно бороться двумя способами.

Первый способ состоит в том, чтобы правильно интерпре-

тировать все утверждения в случае совпадающих точек.

Например, условие «точки A, M, N и D лежат на одной

окружности» нужно понимать так: прямая AK касается

окружности, проходящей через точки A, N и D.

Второй способ состоит в следующем: так как M = A,

прямые AC и AB перпендикулярны. Прямые AC и CD

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

угольник ABCD был бы параллелограммом, а не трапе-

цией (впрочем, для параллелограмма наше утверждение

очевидно). Ясно, что прямые AB и BD не могут быть

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

точки A и B и точки C и D.

4. Cм. решение задачи 5 для 9 класса.

5. П е р в ы й с п о с о б. Пусть утверждение задачи не

верно. Числа a, b и c можно сократить на их общий

множитель, поэтому будем считать, что НОД(a, b, c) = 1.

Пусть одно из чисел не равно ±1, можно считать, что

это число a. Пусть p — любой простой делитель числа a.

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

число b или p не делит число c. Рассмотрим второй случай

(первый случай аналогичен).

Введем обозначение: k(x) — максимальная степень p в

разложении x на простые множители (см. факт 10). Мож-

но считать, что k(a) > k(b) (мы знаем, что k(c) = 0).

Имеем

c + b

a + c

abc