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

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

Решения. 1998 год. 11 класс 231

что эти множители — 1 и 3. Тогда s = 1, l = 2s + 1 = 3.

Теперь нетрудно видеть, что x = y = z = 2.

К о м м е н т а р и й. Нетрудно доказать по индукции, что остаток от

деления на 3 числа 5

равен 1 если z четно, и 2, если z нечетно.

На самом деле остатки от деления числа a

на b (при фиксирован-

ных a и b) образуют периодическую последовательность (факт 4). Это

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

Заметим также, что если b — простое число, то период этой после-

довательности является делителем числа p −1. Это утверждение рав-

носильно малой теореме Ферма, см. комментарий к задаче 6 для 11

класса олимпиады 1995 г.

5. На первый взгляд может показаться, что такая кон-

струкция невозможна: если первая шестеренка вращается

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

часовой и т. д.; следовательно, 61-я должна вращаться по

часовой стрелке, а тогда она не может вращаться согласо-

ванно с первой.

Однако мы работаем в пространстве. И то, по или про-

тив часовой стрелки вращается шестеренка зависит от то-

го, откуда мы на нее смотрим. Требуемая конструкция

изображена на рис. 102.

Рис. 102

232 Решения. 1999 год. 8 класс

Опишем конструкцию на рисунке: шестеренки 13—61

и 1 содержатся в плоскости Oxy; остальные шестерен-

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

сти Oxz. При этом шестеренки 13, 15, 17, ..., 61 враща-

ются по часовой стрелке, если смотреть на плоскость Oxy

сверху, а шестеренки 14, 16, . . . , 60, 1 — против часовой

стрелки. На участке 1—13 этой цепочки происходит «пе-

ремена четности» номеров шестеренок: шестеренки 1 и 13

вращаются в разных направлениях (на плоскости Oxy).

Рис. 103

К о м м е н т а р и й. Искушенный читатель,

конечно, заметил, что эта задача — задача про

лист Мебиуса (рис. 103). Можно было бы на-

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

такое решение было бы трудно аккуратно об-

основать. Феномен «смены четности» связан с

тем, что лист Мебиуса является неориентиру-

емой (или односторонней) поверхностью. См.

[34], § 7, и [25], § 10.

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

1999 год

8 к л а с с

1. Рассмотрим числа

1 −x =

111111

, 1 −y =

222223

, 1 −z =

333334

а также обратные к ним

1 −x

= 111111,

1 −y

= 111111

1 −z

= 111111

Мы видим, что

1 −x

1 −z

1 −y

. Значит, так как числа

1 −x, 1 −y и 1 −z положительны, 1 −x > 1 −z > 1 −y. Сле-

довательно, x < z < y.

2. Решение изображено на рисунках 104, а—в. Однако,

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

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

сутствии строгого обоснования).

Решения. 1999 год. 8 класс 233

Пусть ABCD — произвольный четырехугольник. Заме-

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

сумма которых не меньше 180

◦

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

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

больший 180

◦

, и любой из соседних. Если четырехуголь-

ник выпуклый, то

(∠A + ∠B) + (∠C + ∠D) = 360

◦

Значит, выражение в одной из скобок не меньше 180

◦

Можно считать, что ∠A + ∠B > 180

◦

(другой случай полно-

стью аналогичен). Если сумма углов A и B равна 180

◦

то BC kAD, ABCD — трапеция, и разрезать ее на трапеции

совсем легко — см. рис 104, а.

Пусть ∠A + ∠B > 180

◦

. Рассмотрим прямую l, проходя-

щую через точку B, параллельно стороне AD (рис. 104, б).

Пусть — угол между прямой l и стороной AB. Имеем

= 180

◦

−∠A < ∠B

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

носторонних углах при параллельных прямых). Значит,

прямая l направлена внутрь угла B. Тогда она пересекает

сторону CD в некоторой точке L.

Проведем прямую, параллельную стороне CD и пересе-

кающую отрезки AD и BL, пусть эта прямая пересекает

сторону AD в точке K, а отрезок BL — в точке M. Про-

ведем через точку M прямую, параллельную стороне BC,

до пересечения с отрезком CL в точке N. Мы разреза-

ли наш четырехугольник на трапеции AKMB, KDNM и

CNMB. Случай невыпуклого четырехугольника изображен

на рис. 104, в.

а) б) в)

Рис. 104

234 Решения. 1999 год. 8 класс

3. Если бы вдруг оказалось, что ab = cd, то

+ 2cd + b

= a

+ 2ab + b

= (a + b)

+ 2ab + d

= c

+ 2cd + d

= (c + d)

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

ральных числа a, b, c и d, для которых ab = cd. Или, что

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

лено в виде произведения двух различных множителей

двумя различными способами: n = ab = cd. Пример такого

числа: 6 = 1 · 6 = 2 · 3.

4. Поскольку 300 и 198 делятся на 6, Петя сможет

снять лишь сумму, кратную 6 долларам (см. факт 5). Мак-

симальное число, кратное 6 и не превосходящее 500, — это

498.

Покажем как снять 498 долларов. Произведем следую-

щие операции: 500 −300 = 200, 200 + 198 = 398, 398 −300 =

= 98, 98 + 198 = 296, 296 + 198 = 494. Сумма, лежащая в

банке, уменьшилась на 6 долларов.

Проделав аналогичную процедуру 16 раз, Петя снимет

96 долларов. Затем он может снять 300, положить 198 и

снова снять 300. В результате у него будет 498 долларов.

5. Обозначим через N

точку, симметричную точке N

относительно точки O (рис. 105).

Рис. 105

Треугольники ONC и ON

A равны по

двум сторонам и углу между ними. Кроме

того, угол N

AM — прямой. Действительно,

∠N

AM = ∠N

AO + ∠MAO =

= ∠ACB + ∠BAC = 90

◦

Тогда по теореме Пифагора

+ CN

= AM

+ AN

= MN

Значит, осталось доказать, что MN

= MN. Это следует

из того, что прямоугольные треугольники N

OM и NOM

равны по двум катетам.

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

6. Пусть в турнире участвовало n шахматистов. Тогда

всего в турнире было сыграно n(n −1) партий, и в каж-

дой разыгрывалось 1 очко. Поэтому при равенстве всех

результатов все участники набрали по n −1 очку. Каж-

дый шахматист сыграл белыми фигурами n −1 партию, и

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

из n чисел: 0, . . . , n −1. Предположим, что утверждение

задачи неверно: все выиграли разное число партий белы-

ми. Тогда реализованы все возможные варианты от 0 до

n −1. Рассмотрим двух участников турнира: A, выиграв-

шего n −1 партию белыми фигурами, и B, не выигравшего

ни одной такой партии.

Разберемся, каким мог быть результат партии, которую

A играл против B черными. С одной стороны, A набрал

n −1 очко, играя белыми, так что все свои партии чер-

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

B не выиграл белыми ни одной партии, значит, не мог

выиграть и эту. Мы пришли к противоречию.

9 к л а с с

1. Произведение чисел на доске не меняется. Действи-

тельно,

a + b

1/a + 1/b

a + b

2ab

a + b

= ab.

Поэтому, на 1999-й день произведение будет таким же,

каким и в первый. См. также факт 2.

2. Приведем стратегию второго игрока. Первые 1000

ходов он пропускает. Ход с номером k + 1000 он дела-

ет так, чтобы последние 2k + 1 букв образовывали палин-

дром. Докажем, что он всегда может это сделать.

Для этого проведем индукцию по k (см. факт 24).

При k = 0 это очевидно. Пусть после (k −1) + 1000 ходов

последние 2k −1 букв образуют палиндром. Если припи-

санная первым игроком (1000 + k)-я буква совпадает с

(1000 −k)-й буквой, то второму игроку ничего делать не

нужно.

Если же (1000 + k)-я и (1000 −k)-я буквы различны, то

одна из них не совпадает с буквой, стоящей на 1000-м

месте. Второй игрок меняет ее с 1000-й буквой. При этом

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

палиндром из 2k −1 буквы не разрушится, потому что

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

следние 2k + 1 букв образуют палиндром.

После 1999 ходов все слово будет палиндромом.

3. По теореме об угле между касательной и хордой

∠CBO = ∠BAC (см. факт 15). С другой стороны, по теореме

Рис. 106

о внутренних накрест лежащих

углах при параллельных прямых,

∠BAC = ∠ACD (рис. 106); следова-

тельно, ∠CBO = ∠OCD. Применяя

теперь теорему, обратную к теоре-

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

хордой, убеждаемся, что прямая

CD касается окружности, прохо-

дящей через точки B, O и C.

К о м м е н т а р и й. Рассмотренный в задаче параллелограмм обла-

дает следующим свойством: отношение длины диагонали BD к длине

стороны CD равно

√

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

треугольники BCD и COD подобны. Из этого также следует, что ес-

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

грамм, подобный исходному.

4. Обозначим n = 1000. Рассмотрим два случая.

◦

. k > n. Тогда

1...1

z}|{

2...2

| {z }

−2 . . . 2

|{z}

n+1

= 1 . . . 1

|{z}

2n−k

k−(n+1)

z}|{

2...20...0

|{z}

n+1

Это число заканчивается на n + 1 = 1001 нуль. Но если

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

канчивается на четное число нулей! Значит, это число не

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

◦

. k 6 n. Тогда

1...1

z}|{

2...2

| {z }

−2 . . . 2

|{z}

n+1

= 1 . . . 1

|{z}

2n−k

0...0

|{z}

−2 . . . 2

|{z}

n+1−k

0...0

|{z}

= 10

(1...1

|{z}

2n−k

−2 . . . 2

|{z}

n+1−k

). (1)

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

Это число заканчивается на k нулей. Как было объясне-

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

(в дальнейшем мы будем называть квадраты натуральных

чисел точными квадратами) необходимо, чтобы k было

четно. Обозначим l =

Ясно, что число (1) является точным квадратом тогда

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

A = 1...1

|{z}

2n−2l

−2 . . . 2

|{z}

n+1−2l

Заметим, что

A =

· 9 . . . 9

|{z}

2n−2l

−

· 9 . . . 9

|{z}

n+1−2l

(10

2n−2l

−1 −2(10

n+1−2l

−1))

(см. факт 11). Обозначим B = 9A. Число A является точ-

ным квадратом, тогда и только тогда, когда B = 9A — точ-

ный квадрат. Запишем выражение для B в следующей

форме:

B = 10

2n−2l

−2 · 10

n+1−2l

+ 1 = (10

n−l

)

−2 · 10

n−l

· 10

1−l

+ 1. (2)

При l = 1 правая часть (2) превращается в формулу квад-

рата разности:

B = (10

n−1

)

−2 · 10

n−1

+ 1 = (10

n−1

−1)

Пусть l > 1.

Теперь заметим, что если X = Y

— квадрат натураль-

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

ший X) — это (Y −1)

= Y

−2Y + 1. То есть если число Z

таково, что

−2Y + 1 < Z < Y

то Z не является полным квадратом.

Применим это замечание к числам Y = 10

n−l

и Z = B.

Ясно, что Z < Y

. Кроме того,

Z = (10

n−l

)

−2 · 10

n−l

· 10

1−l

+ 1 > (10

n−l

)

−2 · 10

n−l

+ 1.

Значит, в силу предыдущего замечания, это число не мо-

жет быть точным квадратом, поэтому только l = 1 (и, зна-

чит, только k = 2) удовлетворяет условию.

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

5. Обозначим длины сторон AB, BC и AC через c, a

и b соответственно. Пусть p — полупериметр треугольника.

Будем считать, что R лежит на AC, S — на BC (рис. 107).

Рис. 107

Тогда (см. комментарий)

RQ = |RC −QC|=



−(p −c)



−

a + b −c



c −a

Треугольники PAQ и TRQ подоб-

ны (так как RS kAB), а треуголь-

ник PAQ равнобедренный. Поэтому

RQ = RT. Следовательно,

ST = RS −RT = RS −RQ =

−

c −a

= BS.

Значит, треугольник TSB — равнобедренный, и ∠SBT =

= ∠STB = ∠TBA, так что BT — биссектриса угла B тре-

угольника ABC.

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

ки касания с вписанной окружностью равно p −a, где p — полупери-

метр, a — длина противоположной стороны.

Д о к а з а т е л ь с т в о. Пусть окружность, вписанная в треугольник

ABC, касается сторон AB, BC и AC в точках C

, A

и B

соответ-

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

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

ника равен

2AB

+ 2BA

+ 2A

C = 2AB

+ 2BC.

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

6. Все пункты этой задачи решаются по индукции (см.

факт 24), причем сложность рассуждений резко растет.

Начнем с решения пункта «а». База индукции очевид-

на: один победитель единственного соревнования из дво-

их — это уже половина.

Пусть есть пример 2

спортсменов, упорядоченных по

силе в n видах спорта так, что среди них 2

n−1

возможных

победителей. Обозначим такой пример C

Опишем пример C

n+1

из 2

n+1

спортсменов, упорядочен-

ных по силе в n + 1 виде спорта так, что среди них 2

воз-

можных победителей. Разделим спортсменов на две рав-

ные группы A и A

. Силы спортсменов определим так, что

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

1) в видах спорта с 1-го по n-й спортсмены в каждой

из групп упорядочены, как в примере C

;

2) в (n + 1)-м виде спорта любой спортсмен из A

силь-

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

3) в группе A спортсмены упорядочены по (n+ 1)-му ви-

ду спорта так же, как и по n-му (а в группе A

спортсме-

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

образом).

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

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

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

ции половина спортсменов из этой группы может стать

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

Если провести соревнование по n-му виду спорта — оста-

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

этой группы тоже может стать победителями. По пред-

положению индукции, для половины спортсменов из A

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

они становятся победителями. Однако эта последователь-

ность включает n-й вид спорта, который мы уже сыграли!

Сыграем вместо n-го вида спорта (n + 1)-й, и воспользу-

емся тем, что в группе A спортсмены упорядочены по

(n + 1)-му виду спорта так же, как и по n-му. Итак, поло-

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

и половина спортсменов из группы A

может стать побе-

дителями. Индуктивный переход доказан.

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

рый при любом порядке проведения соревнований выбыва-

ет в этом виде или раньше (независимо от того, каким по

очереди проводится этот вид спорта), причем для разных

видов мы выберем разных спортсменов. Тогда ни один из

них не может стать победителем, и возможных победите-

лей не более, чем 2

−n. Построение индуктивное.

Б а з а и н д у к ц и и: для 1-го вида соревнований — это

самый слабый в 1-м виде.

Ш а г и н д у к ц и и: Пусть уже построено множество

= {a

, . . . , a

} спортсменов такое, что a

выбывает в i-м

виде спорта или раньше.

Из спортсменов, не входящих в множество A

, выберем

самого слабого в (k + 1)-м виде спорта, обозначим его

через a

k+1

. Докажем, что a

k+1

выбывает в (k + 1)-м виде

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

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

Пусть (k + 1)-й вид спорта проводится r-м по порядку, а

из множества A

за первые r −1 соревнований выбыло

w человек. В r-м соревновании выбывает 2

n−r

человек.

Поэтому a

k+1

может пройти в следующий тур только

при выполнении условия 2

n−r

6 k −w (так как лишь k −w

из оставшихся участников могут быть слабее в (k + 1)-м

виде, чем a

k+1

). Но после (k + 1)-го вида спорта должны

пройти соревнования по не менее чем k −w видам спорта

с номерами из множества {1, ..., k} (по предположению

индукции). Поэтому k −w 6 n −r < 2

n−r

. Мы воспользова-

лись неравенством 2

> l, верным для всех целых чисел.

Таким образом, a

k+1

выбывает в (k + 1)-м виде спорта или

раньше, и шаг индукции доказан.

в) Л е м м а. Пусть 2

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

n + 1 виде спорта. При этом соревнование по (n + 1)-му

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

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

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

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

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

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

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

зовать ее для решения пункта «в». Обозначим пример из

этой леммы через E

. База индукции по-прежнему оче-

видна. Для индуктивного перехода повторим рассуждение

пункта «а» с незначительными изменениями.

Пусть есть пример 2

спортсменов, упорядоченных по

силе в n видах спорта так, что среди них 2

−n возмож-

ных победителей, обозначим такой пример D

Опишем пример D

n+1

из 2

n+1

спортсменов. Опять раз-

делим спортсменов на две равные группы A и A

. Силы

спортсменов определим так, что

1) в видах спорта с 1-го по n-й спортсмены в группе A

упорядочены, как в примере D

;

2) в (n + 1)-м виде спорта любой спортсмен из группы

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

наоборот;

3) в группе A спортсмены упорядочены, как в приме-

ре E