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

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

Решения. 1996 год. 10 класс 181

10 к л а с с

1. П е р в ы й с п о с о б. Можно считать, что a > b (слу-

чай a 6 b аналогичен). Тогда b

6 ab, a

> ab, поэтому

> a

+ b

−ab > b

откуда a > c > b. Значит, первый сомножитель в выраже-

нии (a −c)(b −c) неотрицателен, а второй — неположите-

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

валось доказать.

В т о р о й с п о с о б. Рассмотрим треугольник со сторо-

нами a и b и углом 60

◦

между ними (рис. 76). По теореме

b a

◦

Рис. 76

косинусов, его третья сторона равна

+ b

−2ab cos 60

◦

= c.

Поскольку наибольший угол любого

треугольника не меньше 60

◦

, а наимень-

ший — не больше 60

◦

, угол 60

◦

является

средним по величине в треугольнике.

Из того, что против большего угла тре-

угольника лежит большая сторона, сле-

дует, что либо a 6 c 6 b, либо b 6 c 6 a. Значит, из двух

сомножителей a −c и b −c один неотрицателен, а дру-

гой неположителен. Поэтому их произведение неположи-

тельно.

2. Проведем все прямые, параллельные одной из диаго-

налей квадрата и содержащие более одной из отмеченных

Рис. 77

точек — таких прямых 17. Невы-

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

точки. Их можно вычеркнуть, про-

ведя еще одну прямую — другую

диагональ (рис. 77).

Докажем, что нельзя обойтись

меньшим числом прямых. Действи-

тельно, рассмотрим центры единич-

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

по периметру большого квадрата.

Ясно, что прямая, не параллельная

стороне квадрата, может вычерк-

182 Решения. 1996 год. 10 класс

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

(см. также факт 1).

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

тренних углов, не смежных с ним. Поэтому, рассматривая

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

M, получаем ∠P

MC = ∠P

AC + ∠AP

т. е. ∠AP

M = ∠P

MC −∠P

AC. Складывая все такие ра-

венства, видим, что искомая сумма равна

(∠P

MC + ... + ∠P

n−1

MC) −(∠P

AC + ... + ∠P

n−1

AC).

Пусть n нечетно (случай четного n аналогичен). Симмет-

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

n+1−k

Рис. 78

MC показывает, что ∠P

MC +

+ ∠P

n+1−k

MC = 60

◦

(рис. 78), тогда

слагаемые в первой сумме разбива-

ются на

n −3

пар, в каждой па-

ре сумма равна 60

◦

, кроме того,

двум слагаемым «не хватило» па-

ры: ∠P

MC = 60

◦

, ∠P

n+1

MC = 30

◦

значит, первая сумма равна 30

◦

· n.

Во второй сумме слагаемые разби-

ваются на

n −1

пар с суммой 60

◦

Значит, вторая сумма равна 30

◦

· (n −1). Отсюда немедлен-

но следует утверждение задачи.

К о м м е н т а р и й. Сравните с задачей 4 для 8 класса.

4. Случай m = n = 1 очевиден (первому некуда ходить).

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

m вертикалей и n горизонталей, причем m > n, а ладья,

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

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

более длинные ходы. Докажем правильность этой страте-

гии от противного. Рассмотрим среди досок, для которых

эта стратегия не приводит к выигрышу, доску наимень-

шей площади (см. также факт 24). Для доски 1 ×n утвер-

ждение очевидно, поэтому будем считать, что m > n > 2.

Решения. 1996 год. 10 класс 183

Первый ходит по длинной стороне (горизонтали) до

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

направлении. Рассмотрим 3 случая:

а) Второй пошел на одну клетку. Тогда первый пойдет

по горизонтали до конца, и игра сводится к аналогичной

для доски m ×(n −1) (рис. 79, a). Заметим, что m > 2,

поэтому доска 1 ×1 не получится.

б) Второй пошел до конца. Тогда первый пойдет по

горизонтали до конца. Если m = n = 2, то первый сразу

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

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

(m −1) ×(n −1) (рис. 79, б).

в) Пусть второй пошел на k клеток, k 6= 1, k 6= n −1. То-

гда m > 3. Первый пойдет до конца по горизонтали. Если

второй после этого пойдет вверх, то вся дальнейшая игра

будет происходить, как на доске (m −1) ×k. Доска 1 ×1

не получится, так как (m −1) > 2 (рис. 79, в).

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

происходить, как на доске m ×(n −k).

а) б) в)

Рис. 79

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

чалась ходом позже на меньшей доске, отличной от 1 ×1.

Но, по предположению, на этой доске стратегия верна.

Значит, она верна и на исходной доске. Мы пришли к

противоречию.

5. Приведем пример. Пусть в стране 10 человек, все их

дома располагаются на одной прямой, в порядке возрас-

тания ростов этих людей. Пусть расстояния между между

ними таковы: 1 км, 2 км, 3 км, 4 км, 5 км, 4 км, 3 км,

2 км, 1 км (рис. 80). Тогда все, кроме самого высокого,

184 Решения. 1996 год. 10 класс

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

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

тогда они будут ниже 5 из 9 своих соседей. Остальные

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

сед. С другой стороны, все, кроме самого низкого, могут

играть в баскетбол — для этого пятерым самым высоким

нужно выбирать круг радиуса 100 км, а остальным —

круг, содержащий только одного соседа.

Рис. 80

6. Нетрудно видеть, что (поскольку коэффициенты —

натуральные числа) P(N) > P(M) при N > M > 0. Кроме то-

го, P(N) > 1 при N > 0.

Далее, заметим, что если k |x −y, то k |P(x) −P(y) (см.

комментарий). Положим

A = P(1)P(2)...P(1996).

Тогда P(k) |P(A + k) −P(k) при k = 1, ..., 1996 (так как

P(k) |A). Значит, P(k) |P(A + k). Но P(k) > 1 и P(A + k) >

> P(k). Значит, P(A + k) — составное число при k = 1, . . . ,

1996. Что и требовалось доказать.

К о м м е н т а р и й. Докажем, что если d |x −y и P — многочлен с

целыми коэффициентами, то d |P(x) −P(y).

Заметим сначала, что d |x

−y

для любого натурального n. Это

следует из формулы

−y

= (x −y)(x

n−1

+ x

n−2

y + . .. + y

n−1

Теперь наше утверждение очевидно в случае, когда P(x) = ax

—

одночлен (см. факт 5). Наконец, если утверждение верно для двух

многочленов P

и P

, то оно верно и для их суммы. Остается провести

индукцию (см. факт 24) по числу одночленов в многочлене P(x).

Решения. 1996 год. 11 класс 185

11 к л а с с

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

2. Введем обозначения a =

2 +

√

3, b =

2 −

√

3, x =

= a + b. Тогда ab = 1, так что x = a +

Воспользуемся формулами



a +



= a

+ 5





+ 10



a +





a +



= a

+ 3



a +



Подставляя значение a

из второго равенства в пер-

вое, получаем



a +







+ 5



a +



−3



a +



+ 10



a +



Отсюда, учитывая, что a

+ b

= 4, получаем

= 4 + 5(x

−3x) + 10x,

или

−5x

+ 5x −4 = 0.

К о м м е н т а р и й. Задача, фактически, свелась к тому, чтобы вы-

разить a

через a +

. На самом деле, можно выразить a

через

a +

при любом n:

= P

“

a +

”

Многочлены P

связаны с так называемыми многочленами Чебыше-

ва C

формулой C

(x) =

(2x). Многочлены Чебышева определяются

формулой:

cos(nx) = C

(cos x).

То, что все наши формулы согласованы, следует из формулы cos x =

+ e

−ix

, где i =

√

−1, см. [75]. См. также комментарий к задаче 1

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

3. Решим сначала обратную задачу: возьмем произволь-

ный куб и проведем через его вершины параллельные

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

друга.

186 Решения. 1996 год. 11 класс

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

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

ным, т. е. его вершины имели координаты 0 или 1. Тогда

следующие плоскости содержат вершины куба.

Плоскость Вершина

x + 2y + 4z = 0 (0, 0, 0)

x + 2y + 4z = 1 (1, 0, 0)

x + 2y + 4z = 2 (0, 1, 0)

x + 2y + 4z = 3 (1, 1, 0)

Плоскость Вершина

x + 2y + 4z = 4 (0, 0, 1)

x + 2y + 4z = 5 (1, 0, 1)

x + 2y + 4z = 6 (0, 1, 1)

x + 2y + 4z = 7 (1, 1, 1)

Ясно, что эти плоскости параллельны и расстояния между

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

Теперь преобразованием подобия полученные восемь

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

мы получим из рассматриваемого куба требуемый.

4. П е р в ы й с п о с о б. Заметим прежде всего, что

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

остатки 0 или 1, а при делении на 9 — остатки 0, 1,

4 или 7 (см. комментарий). Поэтому числа вида 4k + 3

и 9k + 3 не представимы в виде суммы квадратов двух

целых чисел.

Для любого натурального числа k рассмотрим число

n = (36k + 2)

+ 4

Число n −1 не представимо в виде суммы двух квадратов,

так как при делении на 4 дает остаток 3, а число n + 1 —

так как при делении на 9 дает остаток 3.

В т о р о й с п о с о б. Возьмем в качестве n число

+ 1 = (3

)

+ 1

Тогда n + 1 дает остаток 2 при делении на 3 и, поэтому,

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

Докажем, что n −1 = 9

не представляется в виде сум-

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

= a

+ b

. Без ограничения общности хотя бы одно из чи-

сел a, b не делится на 3 (иначе сократим равенство на 9).

Тогда и второе число не делится на 3. Но квадрат числа,

не делящегося на 3, дает при делении на 3 остаток 1,

значит a

+ b

не может делиться на 3 — противоречие.

Решения. 1996 год. 11 класс 187

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

◦

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

ный квадрат дает остаток 0 или 1 при делении на 4. Действительно,

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

вид (2k + 1)

= (2k)

+ 2 · 2k + 1 = 4(k

+ k) + 1.

Аналогично доказывается утве рждение про деление на 3. Утвержде-

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

ром остатков с использованием факта 7. Заметим, также, что квадрат

нечетного числа дает остаток 1 при делении на 8.

◦

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

числа n в виде суммы квадратов двух целых чисел: разложим число n

на простые множители (см. факт 10), тогда каждое простое число вида

4k + 3 должно входить в произведение в четной степени [30], § 4—5.

См. также комментарий к задаче 2 для 8 класса олимпиады 1993 г.

5. Обозначим центры окружностей

через O

, а радиусы — через r

и r

соответственно.

Рассмотрим точку D пересечения общей внутренней ка-

сательной к окружностям с отрезком O

. Тогда (см.

факт 17)

Пусть AC — одна из диагоналей указанного четырех-

угольника (рис. 81). Найдем точку S пересечения диаго-

D(= S)

Рис. 81

нали AC и отрезка O

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

соотношения

sin ∠O

. (1)

188 Решения. 1996 год. 11 класс

Проведем окружность с центром в точке X, проходящую

через точки A и C. Прямые AO

и CO

будут касательны-

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

(см. факт 15)

∠O

AS + ∠O

CS =

(

AC +

CA) = ,

значит sin ∠O

AS = sin ∠O

CS. Углы O

SA и O

SC равны

как накрест лежащие. Поэтому из соотношений (1) следу-

ет, что

Поскольку существует единственная точка, делящая

отрезок в данном отношении, точки D и S совпадают.

Аналогичные соображения верны и для второй диагонали.

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

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

линию центров в одной точке. Из этого следует требуемое

утверждение.

К о м м е н т а р и й. Из этой задачи следует такое замечательное

утверждение: если четырехугольник ABCD описан около окружности,

то точка пересечения прямых, соединяющих противоположные точки

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

возьмем в качестве X центр вписанной окружности четырехугольника.

Возьмем в качестве

окружность с центром в точке A, проходящую

через точки касания AB и AD с вписанной окружностью четырехуголь-

ника. Аналогично,

— окружность с центром в точке C. Применяя

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

пересечения прямых, соединяющих противоположные точки касания

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

Аналогично, она лежит на BD.

6. П е р в ы й с п о с о б. Будем выбирать строки «испор-

ченной» нулями таблицы по очереди и следить за суммой

S = S(m) выбранных строк. Первой возьмем «испорчен-

ную» строку, которая получилась из (1, 1, ..., 1). Строка

S(1) будет состоять из 0 и 1 (если в ней только нули,

то уже одна эта строка дает нужное множество). Второй

строкой возьмем «испорченную» строку, полученную из

той, в которой стояли −1 на тех местах, где в S(1)

стоят 1. Тогда S(2) будет стоять из 0 и 1. Пусть k строк

уже выбраны. Если сумма S(k) совпадает с некоторой из

предыдущих сумм S(m), где m < k, то сумма (m + 1)-й,

Решения. 1996 год. 11 класс 189

(m + 2)-й, ..., k-й строк равна нулевой строке, и задача

решена. Если сумма S(k) не совпадает ни с одной из

предыдущих строк, то в качестве (k + 1)-й берем «испор-

ченную» строку, полученную из той, в которой стояли

−1 на тех местах, где в S(k) стоит 1, и 1 на тех местах,

где в S(k) стоит 0. Эта строка еще не была выбрана, так

как для разных сумм S(m) мы выбираем разные строки,

а сумма S(k) раньше не встречалась.

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

встречалась раньше, то задача решена (см. выше), если

нет, — то, в конце концов, все строки будут выбраны.

При этом мы получим 2

различных сумм S(k). Так как

различных наборов из 0 и 1 длины n тоже 2

, то все

строки из 0 и 1 встретятся в качестве сумм S(k). Значит,

на каком-то шаге, S(k) = 0, и нужное множество — первые

k выбранных строк.

В т о р о й с п о с о б. Обозначим строки исходной та-

блицы a

, а строки таблицы, «испорченной» нулями, b

(i = 1, 2, ..., 2

). Построим также таблицу со строками

= a

−2b

. Иными словами, строка c

совпадает с a

в тех

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

ей в остальных. В частности, построенная таблица со-

стоит из ±1. Поэтому для любого i найдется j(i) такое,

что c

= a

j(i)

. Рассмотрим теперь последовательность i

заданную рекуррентным соотношением i

k+1

= j(i

). (Пер-

вый член последовательности выбирается произвольно.)

Поскольку последовательность может принимать лишь

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

собой. Пусть i

= i

для некоторых k < l, причем все члены

последовательности с номерами, меньшими l, различны.

Имеем

+ b

k+1

+ . . . + b

l−1

−c

) +

k+1

−c

k+1

) + ... +

l−1

−c

l−1

) =

−a

k+1

+ a

k+1

−a

k+2

+ . . . + a

l−1

−a

) =

−a

) = 0.

Что и требовалось доказать.

190 Решения. 1997 год. 8 класс

1997 год

8 к л а с с

1. На горизонтали может стоять от одной до восьми

фигур. Так как на разных горизонталях — разное число

фигур, на некоторой горизонтали стоит ровно одна фи-

гура, на некоторой другой — две фигуры, . .., наконец,

некоторая горизонталь заполнена восемью фигурами. Про-

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

щих на них фигур.

Отметим на первой горизонтали ее единственную фигу-

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

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

горизонтали три фигуры, хотя бы одну из них можно

отметить, и так далее. См. также факт 1.

2. Путь по дороге и тропинке (туда и обратно) занимает

16 часов. Значит, если выйти сразу после извержения

первого кратера, то он не будет опасен.

Движение по тропинке (туда и обратно) занимает 8 ча-

сов. Значит, если начать движение по тропинке сразу по-

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

Ване для безопасного подъема достаточно, чтобы к

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

кратер, а спустя 4 часа, к началу движения по тропинке,

перестал извергаться второй кратер.

Найдем такой момент времени. Первый кратер извер-

гается 1-й, 19-й, 37-й часы. Второй кратер извергается

1-й, 11-й, 21-й, 31-й, 41-й часы. Значит, если выйти в

начале 38-го часа, то к началу тропинки Ваня попадет как

раз к концу извержения второго кратера, что и требова-

лось.

К о м м е н т а р и й. Мы решили задачу перебором. На самом де-

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

извергается в часы с номерами 18x + 1, где x — целое число; второй

кратер — в часы с номерами 10y + 1. Нам нужно, чтобы они изверга-

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

10y −18x = 4.

Наименьшее решение в натуральных числах — y = 4, x = 2.