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

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

Решения. 2002 год. 9 класс 301

Рис. 148

В прямоугольнике 3 ×3 также есть вечно жи-

вая расстановка (тоже периода 2), см. рис. 148.

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

1 ×1 и 1 ×3 любая расстановка рано или поздно

умрет. Случай 1 ×1 очевиден. Для случая 1 ×3

можно считать (возможно, начиная отсчет со второго ша-

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

в которых есть хотя бы одна живая клетка: , ,

. Проверку этих вариантов мы оставляем читателю.

9 к л а с с

1. Договоримся в случае, когда сержант стоит в строю,

обозначать буквой m количество человек, стоящих в

строю слева от сержанта к нему лицом, а буквой n —

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

лицом.

Пусть сначала сержант встанет в левый край шеренги.

Тогда слева от него никого не будет (m = 0). Если и справа

от сержанта никто не будет стоять к нему лицом (n = 0),

то задача решена. В противном случае (n > 0) пусть сер-

жант идет слева направо от человека к человеку. Если он

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

число m увеличивается на 1, а число n не изменяется.

Если сержант проходит мимо новобранца, стоявшего к

нему лицом, то число n уменьшается на 1, а число m

не изменяется. Если же он проходит мимо новобранца,

повернувшегося кругом, то оба числа m и n остаются без

изменений.

Посмотрим, что происходит с числом m −n. Сначала

оно отрицательно, а в процессе движения сержанта вдоль

строя может изменяться только на единицу. Но когда сер-

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

а значит, число m −n будет неотрицательным. Итак, начав

с отрицательного числа m −n и несколько раз прибав-

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

ное число. Значит, в какой-то момент мы должны были

получить нуль. В этот момент m = n, и с обеих сторон

от сержанта находилось поровну новобранцев, стоящих к

нему лицом.

302 Решения. 2002 год. 9 класс

2. П е р в ы й с п о с о б. По неравенству треугольника

a + b > c. Кроме того, для любых неотрицательных a и b

выполняется неравенство a

−ab + b

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

−ab + b

> a

−2ab + b

= (a −b)

> 0.

Поэтому

(a + b)(a

−ab + b

) > c(a

−ab + b

Отсюда получаем:

+ b

+ 3abc = (a + b)(a

−ab + b

) + 3abc >

> c(a

−ab + b

) + 3abc = c(a

+ 2ab + b

) = c(a + b)

> c

В т о р о й с п о с о б. Пусть d = c −b, тогда d + b= c (d мо-

жет быть отрицательным). По неравенству треугольника

a > d. Получаем:

+ b

+ 3abc > d

+ b

+ 3dbc = d

+ b

+ 3bd(d + b) =

= d

+ 3d

b + 3db

+ b

= (d + b)

= c

К о м м е н т а р и й. Неравенство a

−ab+ b

> 0 выполняется для лю-

бых чисел. Докажите это сами.

3. Отразим симметрично треугольник ABC относитель-

но прямой DE (рис. 149). По свойству вписанных углов

Рис. 149

∠AED = ∠ACD = ∠BCD = ∠BED

(второе равенство верно, пото-

му что CD — биссектриса угла

ACB). Поэтому прямая AE при

этом отражении перейдет в пря-

мую BE, аналогично, прямая

CD при отражении перейдет в

прямую BD. Тогда точка пере-

сечения прямых AE и CD, т. е.

точка I, перейдет при отраже-

нии в точку пересечения прямых BE и BD, т. е. в

точку B. Таким образом, треугольник IFG перейдет при

отражении в треугольник BFG, откуда IF = BF, IG = BG, и

прямая BI перпендикулярна DE. Но луч BI — биссектриса

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

Решения. 2002 год. 9 класс 303

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

FB = BG.

Итак, все стороны четырехугольника BFIG равны, зна-

чит, этот четырехугольник — ромб.

4. Если (x, y) — решение уравнения x

−2y

= 1, то

(−x, y), (x, −y) и (−x, −y) тоже решения. Поэтому будем

искать только неотрицательные решения. Ясно, что x —

нечетное число, x = 2t + 1. Перепишем уравнение в виде

−1 = (x −1)(x + 1)(x

+ 1) = 2t · (2t + 2) · (4t

+ 4t + 2) = 2y

Теперь видно, что y — четное число, y = 2u. Деля обе части

уравнения на 8, получаем уравнение

t(t + 1)(2t(t + 1) + 1) = u

Нетрудно проверить, что числа t, t + 1 и 2t(t + 1) + 1 по-

парно взаимно просты. Действительно, пусть, например,

d |t + 1 и d |2t(t + 1) + 1,

тогда d делит и 2t(t + 1), а, значит, и разность

1 = (2t(t + 1) + 1) −(2t(t + 1))

(см. факт 5). Взаимная простота двух остальных пар до-

казывается аналогично.

Произведение этих взаимно простых чисел — полный

квадрат. Согласно известной теореме (см. комментарий),

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

Итак, t и t + 1 — полные квадраты. Это возможно толь-

ко при t = 0. Действительно, если t =

, t + 1 =

, где

> 0, > 0, то

( − )( + ) = 1,

поэтому − = 1, + = 1, так что = 0, следовательно,

t = 0. Тогда и u = 0. Значит, x = ±1, y = 0.

К о м м е н т а р и й. Приведем подробное доказательство использо-

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

Т е о р е м а. Если ab = d

, a, b и d — натуральные числа, и числа

a и b взаимно просты, то a и b — точные квадраты.

Запишем разложения чисел a, b и d на простые множители:

a = p

.. . p

, b = q

.. . q

, d = r

.. . r

304 Решения. 2002 год. 9 класс

Здесь p

— попарно различные простые числа, q

— попарно раз-

личные простые числа, и r

— попарно различные простые числа (см.

факт 10).

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

не равно

ни одному из чисел q

. Значит,

ab = p

.. . p

.. . q

— разложение числа ab на попарно различные простые множители.

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

= r

.. . r

— разложение числа d

на попарно различные простые множители.

В силу теоремы о единственности разложения, эти разложения мо-

гут отличаться лишь порядком сомножителей. Значит, числа n

— это

некоторые из чисел 2t

. Поэтому все n

четны, но тогда a есть произ-

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

квадратом. Аналогично доказывается, что b является точным квадра-

том. Теорема доказана.

Пусть теперь a, b и c попарно взаимно простые числа, и abc = d

Нетрудно видеть, что числа a и bc взаимно просты (предположите,

что они имеют простой общий делитель p и используйте факт 9).

Применяя нашу теорему к числам a и bc, видим, что каждое из них

является точным квадратом. Аналогично доказывается, что числа b

и c — точные квадраты.

5. См. решение задачи 6 для 8 класса, где данной за-

даче соответствует случай прямоугольников 1 ×n (горящие

лампочки соответствуют живым клеткам).

6. Заметим сначала, что все получающиеся многоуголь-

ники будут выпуклыми. Докажем индукцией по количе-

ству имеющихся частей (см. факт 24) следующее утвер-

ждение: после каждого разрезания найдется часть (мно-

гоугольник) хотя бы с тремя нетупыми углами.

Б а з а и н д у к ц и и. Сначала есть одна часть, и это

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

Ш а г и н д у к ц и и. Пусть на очередном шаге имеется

многоугольник M хотя бы с тремя нетупыми углами, и

мы делаем очередное разрезание.

Если мы режем не многоугольник M, то шаг индукции

очевиден. Пусть мы разрезали M по прямой на две части.

Обозначим точки пересечения этой прямой с многоуголь-

ником M буквами A и B.

Решения. 2002 год. 10 класс 305

Если точка A лежит внутри одной из сторон много-

угольника M, то линия разреза образует с этой стороной

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

не тупой. Если же точка A — вершина многоугольника, то

соответствующий ей угол многоугольника разбивается раз-

резом на два угла, сумма которых меньше 180

◦

(так как

многоугольник M — выпуклый). Значит, тем более один из

них не тупой. Если при этом угол A сам не был тупым,

то, очевидно, оба получившихся угла также не тупые. Та-

ким образом, после разреза к точке A примыкает больше

нетупых углов (по крайней мере, на единицу). Аналогич-

ные рассуждения про второй конец разреза B показывают,

что дополнительный нетупой угол появляется и там.

По предположению индукции многоугольник M имел

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

у двух получившихся многоугольников таких углов в сум-

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

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

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

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

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

хотя бы у одного из них будет не меньше трех нетупых

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

10 к л а с с

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

через , , ( 6 6 ). Так как + + = , имеет место

неравенство 0 < 6

, поэтому 0 < tg 6

√

3. Так как tg —

натуральное число, то он равен 1, =

. Тогда + =

откуда

−1 = tg( + ) =

tg + tg

1 −tg tg

⇒ tg + tg = tg tg −1 ⇒

⇒ (tg −1)(tg −1) = 2.

Число 2 простое, поэтому выражение в одной скобке рав-

но 1, а в другой 2 (случай, когда одно из выражений

равно −1, а другое −2, как легко видеть, невозможен).

Отсюда получаем: tg = 2, tg = 3.

306 Решения. 2002 год. 10 класс

В т о р о й с п о с о б. Нарисуем на клетчатой бумаге

треугольник ABC, как показано на рис. 150. Подсчетом

Рис. 150

клеточек легко убедиться, что

tg ∠BAC = 3, tg ∠ACB = 2. Отметим

теперь на рисунке точки H и D.

Опять-таки из подсчета клеточек

следует, что ADBH — ромб с рав-

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

Поэтому ∠ABC = /4, а tg ∠ABC= 1.

Итак, нарисованный треугольник

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

Покажем, что других значений

тангенсов быть не может. Как бы-

ло доказано (см. первый способ ре-

шения), наименьший из углов треугольника обязательно

равен /4. При этом остальные углы строго больше: если

бы второй угол также равнялся /4, то третий угол был

бы равен −2 ·

, и его тангенс был бы не опреде-

лен. Таким образом, один из тангенсов равен 1, а два

остальных — больше 1 (так как тангенс возрастает на по-

луинтервале [0; /2)).

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

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

чений остальных двух. Значит, кроме варианта 1, 2, 3

осталось рассмотреть вариант 1, m, n, где m > 2, n > 3.

В этом случае пришлось бы увеличить два угла треуголь-

ника ABC, оставив третий без изменений, что невозможно

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

вариант на рисунке — единственный.

2. Умножая неравенство

> a + b + c

на общий знаменатель, получаем равносильное неравенство

bc + ac + ab > (a + b + c)abc.

Теперь докажем вспомогательное неравенство (верное

при всех a, b и c)

(a + b + c)

> 3(ab + bc + ac).

Решения. 2002 год. 10 класс 307

Начнем с известного неравенства (см. комментарий)

+ b

+ c

> ab + bc + ac ⇔

⇔ a

+ b

+ c

+ 2(ab + bc + ac) > 3(ab + bc + ac) ⇔

⇔ (a + b + c)

> 3(ab + bc + ac).

Отсюда легко получить требуемое неравенство:

(a + b + c)

> 3(ab + bc + ac) > 3(a + b + c)abc,

a + b + c > 3abc.

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

сто. Имеем (см. факт 26):

2ab 6 a

+ b

, 2bc 6 b

+ c

, 2ac 6 a

+ c

Достаточно сложить все три неравенства и разделить получившееся

неравенство на два.

3. Пусть площади треугольников равны n, n + 1, n + 2,

n + 3. Тогда площадь четырехугольника ABCD составляет

4n + 6. Нетрудно видеть, что площадь треугольника BCD в

Рис. 151

четыре раза больше площади треуголь-

ника ECF, поэтому эта площадь не

меньше 4n. Значит,

ABD

= S

ABCD

−S

BCD

6 (4n + 6) −4n = 6.

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

ник ECF имеет наименьшую площадь

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

Осталось доказать, что значение 6 является возмож-

ным. Примером служит равнобедренная трапеция с осно-

ваниями AD = 6, BC = 4 и высотой 2 (числа на рис. 151

обозначают площади треугольников).

К о м м е н т а р и й. Нетрудно видеть, что площадь треугольника

ABD всегда равна либо 2, либо 6.

4. Занумеруем всех зрителей номерами их билетов

1, . . . , n. Пусть, для определенности, самое правое место

имеет номер n, а самое левое — номер 1. Мы сведем задачу

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

зрителя n на свое место.

308 Решения. 2002 год. 10 класс

Пусть билетер действует следующим образом. Он пере-

саживает зрителя n вправо, если его правый сосед при

этом не садится на свое место. Если зрителя n не удается

пересадить правее места k, то на (k + 1)-м месте сидит

зритель k. Выберем наибольшее m такое, что зрители с

номерами k, k + 1, . . . , k + m −1 сидят на местах k + 1,

k + 2, . . . , k + m соответственно. Возможны два случая:

k + m < n или k + m = n.

В первом случае на (k + m + 1)-м месте сидит зритель j,

j 6= k + m. Ясно, что j 6= k + m −1, j 6= k + m −2, . . . , j 6= k + 1.

Поэтому можно пересадить зрителя j налево, потом еще

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

зрителем n. В результате билетеру удастся пересадить зри-

теля n на одно место правее, причем все зрители слева

от n сидят на чужих местах. Билетер может повторять

эту процедуру до тех пор, пока не произойдет одно из

двух: зритель n окажется на своем месте или встретится

второй случай (k + m = n).

Во втором случае билетер может рассадить по своим

местам зрителей k, k + 1, . .., n, пересаживая зрителя n

вправо до его места.

Таким образом, несколько зрителей в правом конце ря-

да будут сидеть на своих местах, а остальные — нет. Мы

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

5. а) Остап не мог занять последнее, 2002-е место в

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

числа кандидатов. Поэтому k 6 2001.

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

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

следующем туре получал все голоса выбывшего кандида-

та. Тогда Остап победит в тот момент, когда количество

выбывших кандидатов достигнет половины. Это случится

как раз в 1002-м туре.

Выполним точный подсчет в случае, когда кандидаты

в первом туре набрали 10

, 10

+ 1, . . . , 10

+ 2001 го-

лос. Тогда в 1001-м туре у Остапа еще меньше половины

голосов, а именно: голоса всех кандидатов, занявших по-

следние 1001 место в первом туре. Однако в 1002-м туре

у него уже более половины всех голосов. Действительно,

Решения. 2002 год. 10 класс 309

в 1002-м туре у Остапа

+ (10

+ 1) + . . . + (10

+ 1001) = 1002 · 10

1001 · 1002

= 1002 · 10

+ 1001 · 501 = 1 002 501 501

голосов, а всего избирателей

+ (10

+ 1) + . . . + (10

+ 2001) = 2002 · 10

2001 · 2002

= 2002 · 10

+ 2001 · 1001 = 2 004 003 001.

Нетрудно проверить, что это меньше удвоенного числа го-

лосов Остапа.

б) Предположим, что k > 1. Тех, кто выбыл в первой

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

кандидатов, кроме Остапа, — лидерами. Кандидата, заняв-

шего первое место в первом туре, назовем фаворитом.

Поскольку число аутсайдеров 1000, а лидеров 1001, то

один из лидеров не получал голосов аутсайдеров. В пер-

вом туре (и позже) он имел больше голосов, чем любой

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

не этот лидер). Значит, фаворит тоже имел в первом туре

больше голосов, чем любой аутсайдер. Поэтому фаворит

является лидером.

Максимальное число голосов, которое Остап мог со-

брать к 1001-му туру, — это все голоса аутсайдеров на

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

избирателей Остапа. Любой из лидеров в любом из первой

тысячи туров (а тем более в 1001-м) имеет больше голо-

сов, чем аутсайдер этого тура. Фаворит заведомо имеет

больше, чем имел Остап в первом туре. Поэтому лидеры

и фаворит в сумме имеют в 1001-м туре больше голосов,

чем Остап, и он не может стать победителем.

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

◦

. Д о п о л н и т е л ь н ы й в о п р о с: изменит-

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

делятся между оставшимися?

◦

. З аметим, что в пункте «а» получается очень большой город

(в нем более двух миллиардов избирателей). Интересно понять, как

ответ зависит от количества избирателей. Заметим, что из условия

следует, что в городе не менее, чем

0 + 1 + .. . + 2001 = 2003001

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

бы быть разным.

310 Решения. 2002 год. 10 класс

6. Рассмотрим такую раскраску квадрата: впишем круг

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

жащие вне круга; впишем в полученный круг квадрат

а)

a/2

√

a/2

б)

Рис. 152

со сторонами, параллельными сторо-

нам исходного квадрата. Покрасим в

белый цвет точки круга, лежащие

вне «маленького» квадрата. По тако-

му же правилу раскрасим маленький

квадрат и т. д. (рис. 152, а). Заме-

тим, что мы считаем граничные точки

лежащими «внутри» фигуры. Таким

образом, граница каждого квадрата

покрашена черным, за исключением

четырех точек касания вписанного в

квадрат круга, а граница каждого

круга — белым, за исключением че-

тырех вершин квадрата, вписанного в

этот круг.

Пусть сторона исходного квадра-

та равна a, тогда сторона маленько-

го квадрата равна

√

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

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

(см. факт 27). Поэтому все точки, кро-

ме центра, будут покрашены. Центр

покрасим в черный цвет.

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

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

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

тром в центре квадрата и с коэффициентом

√

). А множе-

ство белых точек квадрата просто совпадает с множеством

белых точек вписанного в него круга (рис. 152, б).

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

◦

. Аналогичная конструкция используется в

доказательстве знаменитой теоремы Кантора—Бернштейна (см., напри-

мер, [71], § 1.5, или [36], § 10).

◦

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

конечного процесса и мало похожи на «фигуры». Оказывается, если

резать фигуры на «плохие» множества, то встречаются разные неожи-

данности: например, шар можно разрезать на части, из которых можно

сложить два шара того же радиуса. По этому поводу см. [36], § 10.