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

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

Решения. 1994 год. 9 класс 131

Рис. 49

То есть достаточно доказать,

что

. (1)

Применяя теорему об угле

между касательной и хордой,

видим, что треугольники AMB

и NAB подобны (рис. 49). Зна-

чит,

, и

Перемножая эти равенства, по-

лучаем равенство (1).

К о м м е н т а р и й. Если центр одной из окружностей расположен

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

центр каждой из окружностей находится внутри другой окружности,

то получается третья картинка. В этих случаях, в первом доказатель-

стве вместо равенства углов ABQ и MAN, нужно доказать, что эти

углы составляют в сумме 180

◦

. Второй способ решения остается без

изменений. Читатель может самостоятельно провести эти рассуждения.

5. Пусть x — вычеркнутая цифра, a — часть числа слева

от x, c — часть числа справа от x, тогда число имеет вид

axc, см. факт 11. Пусть цифра x стоит на (n + 1)-м месте

(считая справа). Тогда

axc = a · 10

n+1

+ x · 10

+ c.

После вычеркивания цифры x получится число ac = a · 10

+ c. Рассмотрим отношение исходного числа к полученно-

му

r =

a · 10

n+1

+ x · 10

+ c

a · 10

+ c

, где c < 10

. (2)

Вычитая 10 из обеих частей равенства (2), и производя

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

r −10 =

x · 10

−9c

a · 10

+ c

6 9.

Обозначим l = r −10. Умножая последнее равенство на зна-

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

(x −la) · 10

= (l + 9)c. (3)

132 Решения. 1994 год. 9 класс

Если l 6 0, то левая часть последнего равенства положи-

тельна, значит, l + 9 > 0. Итак,

−8 6 l 6 9.

Ясно также, что l 6= 0 (иначе десятичная запись числа c

оканчивается нулем).

Л е м м а. a — цифра (иными словами, a < 10).

Д о к а з а т е л ь с т в о. Рассмотрим два случая: l > 0 и

l < 0.

Пусть l > 0. Из равенства (3) следует, что x −la > 0, зна-

чит,

a <

6 9.

Пусть l < 0, тогда

x −la =

(l + 9)c

9 · 10

= 9,

откуда −la < 9, так что a < 9. Лемма доказана.

Из леммы следует, что десятичная запись числа axc со-

стоит из n + 2 цифр. Поэтому, чтобы найти максимальное

исходное число, нужно найти максимальное n.

Число c по условию не оканчивается нулем, поэтому

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

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

◦

. Пусть разложение числа c не содержит двоек. Рас-

смотрим правую часть равенства (3). Так как 1 6 l + 9 6 18,

число l + 9 может делиться на 4-ю степень двойки (l + 9 =

= 16), но не может делиться на 5-ю (2

= 32 > 18). Поэтому

n 6 4. Пусть n = 4, тогда l + 9 = 16, и равенство (3) перепи-

шется в виде

(x −7a) · 5

= c.

Поскольку x — это цифра, то a = 1, x = 8 или x = 9. При

x = 9 число c оканчивается нулем, и потому не подходит.

При x = 8 получаем c = 625 и ответ

axc = 180625.

◦

. Пусть число c не содержит пятерок. Число l + 9 де-

лится на степень пятерки не выше первой, поэтому n 6 1,

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

Решения. 1994 год. 9 класс 133

а)

б)

в)

г)

Рис. 50

6. В задаче «б» легко привести при-

мер «непродолжаемой» расстановки де-

вяти кораблей (рис. 50, а).

В задаче «а» есть «подводный ка-

мень»: казалось бы достаточно доказать,

что найдется место последнему однокле-

точному кораблю. Но, на самом деле,

нужно доказать, что в процессе расста-

новки найдется место каждому очеред-

ному кораблю.

Корабль 1 ×4 поставить можно. До-

кажем, что очередной корабль 1 ×3 по-

местится. Для этого отметим 8 вспомо-

гательных кораблей 1 ×3, параллельных

друг другу, с интервалом две клетки

(рис. 50, б). Каждый из поставленных

кораблей может задеть (пересечь или

коснуться) не больше двух отмеченных,

поэтому останется незадетым отмечен-

ный корабль, на место которого можно

поставить очередной корабль 1 ×3.

Пусть уже расставлены следующие

корабли: 1 ×4, два 1 ×3 и меньше трех

1 ×2. Докажем, что еще один корабль

1 ×2 поместится. Для этого отметим 12

вспомогательных кораблей 1 ×2, парал-

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

клетки (рис. 50, в). Каждый постав-

ленный корабль может задеть не боль-

ше двух отмеченных, поэтому останется

незадетым отмеченный корабль.

Аналогично поместится очередной од-

ноклеточный корабль. Отметим 16 вспо-

могательных кораблей 1 ×1 с интерва-

лом две клетки (рис. 50, г). Постав-

ленные корабли задевают не больше 15

отмеченных.

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

вых кораблей, например, 1 ×4, которые заведомо поместятся.

134 Решения. 1994 год. 10 класс

10 к л а с с

1. Похожая задача была в 8-м классе (задача 2). Там

приведены более подробные решения.

П е р в ы й с п о с о б. Пусть x и y — искомые числа,

тогда можно составить уравнение: 3 · x · y = 10

x + y (см.

факт 11), 3y = 10

. Поскольку

— чис ло в преде-

лах от 0 до 10, имеем 10

< 3y < 10

+ 10, следовательно

3333333

< y < 3333336

. Теперь можно либо рассмотреть

три варианта: y = 3333334, y = 3333335 и y = 3333336, либо

заметить, что

3333336

1000000

< 4,

значит, 10

+ 1 6 3y < 10

+ 4. Лишь одно число в этом

интервале делится на 3 — это 10

+ 2. Тогда 3y = 10

+ 2,

y = 3333334, x = 1666667.

В т о р о й с п о с о б. 10

x = (3x −1)y. Поскольку x и

(3x −1) не имеют общих делителей, то 3x −1 — делитель

(см. факты 9 и 5). Но 3x −1 > 3 · 10

−1, поэтому

либо 3x −1 = 5 · 10

, либо 3x −1 = 10

. Подходит только

3x −1 = 5 · 10

, откуда x = 1666667. Из первого уравнения

получаем: y = 3333334.

2. а) Если 0 6 x

6 1, то 0 6 x

n+1

6 1. Действительно,

0 6 x

6 1 ⇒ −1 6 1 −2x

6 1 ⇒

⇒ 0 6 |1 −2x

|6 1 ⇒ 0 6 x

n+1

6 1.

Если x

рациональное, то x

n+1

рациональное, причем

со знаменателем не большим чем у x

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

пусть x

— несократимая дробь. Тогда

n+1

= 1 −



−2p



−|q

−2p

Если эта дробь несократима, то ее знаменатель такой же,

как и у x

, если она сократима, то после сокращения

знаменатель уменьшится.

Итак, все члены последовательности — рациональные

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

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

Решения. 1994 год. 10 класс 135

заданной величины q, — конечное число. Поэтому какие-то

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

последовательность будет периодической.

б) П е р в ы й с п о с о б. Раскрывая модуль в x

n+1

= 1 −

−|1 −2x

|, получим либо x

n+1

= 2x

, либо x

n+1

= 2 −2x

Поэтому x

n+1

= a

+ 2b

, где a

— целое число, b

= ±1.

Аналогично, x

n+2

= a

+ 4b

. Продолжая этот процесс,

получим, что

n+k

= a

+ 2

где a

— целое число, b

= ±1.

Допустим, что x

n+k

= x

. Тогда x

— решение линейного

уравнения с целыми коэффициентами a

+ 2

= x

Это уравнение имеет единственное решение, так как

= ±2

6= 1. Это решение рационально, так что x

—

рациональное число. Но тогда x

n−1

— рациональное число,

n−2

— рациональное число и т. д. Значит, x

— тоже

рациональное число.

В т о р о й с п о с о б. Запишем число x

в двоичной си-

стеме счисления (см. факт 12):

= 0,a

...

Если a

= 0, то двоичная запись числа x

n+1

получается из

двоичной записи числа x

сдвигом (проверьте!):

n+1

= 0,a

...

Если же a

= 1, то двоичная запись числа x

n+1

получается

из двоичной записи числа x

сдвигом с заменой всех еди-

ниц на нули, а нулей — на единицы (назовем это инверси-

ей). Докажем, что если x

периодична, то a

тоже пери-

одична. Если x

n+k

= x

и между ними произошло четное

число инверсий, то a

n+k

= a

. Если между x

и x

n+k

про-

изошло нечетное число инверсий, то a

n+2k

= 1 −a

n+k

= a

В обоих случаях a

периодична. Но число, двоичная за-

пись которого периодична, — рационально (см. факт 13).

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

◦

. Заметим, что функция y = f(x) = 1 −|1 −2x |

линейна на каждом из отрезков [0; 1/2] и [1/2; 1]:

y =

(

2x при 0 6 x 6 1/2,

2 −2x при 1/2 6 x 6 1.

136 Решения. 1994 год. 10 класс

Аналогично, функция

y = f

(x) = f(f . .. f(x) .. .)

| {z }

n раз

переводящая x

в x

, линейна на каждом из отрезков

;

k + 1

. Гра-

фики функций y = f(x), y = f

(x), y = f

(x) показаны на (рис. 51).

y = f(x)

y = f

(x)

y = f

(x)

Рис. 51

◦

. Для каждого T = 2, 3, .. . существует по крайней мере одна

точка с периодом T — это, например, абсцисса последней точки

пересечения отрезка y = x, 0 6 x 6 1, с графиком функции y = f

(x),

= 2

/(2

+ 1).

Подумайте над вопросом: сколько существует периодических тра-

екторий для каждого периода T (или, что почти то же самое, — точек

x, для которых x = f

(x), причем x 6= f

(x), если k < T)?

◦

. Задача возникла из символической динамики. Функция f(x) =

= 1 −|1 −2x | называется «палаточным отображением».

3. П е р в ы й с п о с о б. Назовем депутатов врагами,

если один другого бил. Индукцией по n (см. факт 24)

докажем следующее утверждение: если в парламенте

M > 3n −2 депутатов, и каждый дал пощечину ровно

одному коллеге, то можно составить парламентскую

комиссию из n человек, в которой нет врагов. При

n = 665 из этого будет следовать утверждение задачи, так

как 1994 > 1993 = 3 · 665 −2.

Б а з а и н д у к ц и и (n = 1) очевидна.

Ш а г и н д у к ц и и: Так как число депутатов равно

числу пощечин (равно M), по принципу Дирихле (см.

факт 1) найдется депутат, получивший не более одной

пощечины. У него не более двух врагов (его враги — тот,

кто его бил и тот, кого он бил). Отправим этого депутата в

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

из парламента. В парламенте осталось M −3 > 3(n −1) −2

Решения. 1994 год. 10 класс 137

депутатов. По предположению индукции, из них можно

создать комиссию из n −1 депутатов, не бивших друг

друга. Вместе с уже выбранным депутатом они составят

комиссию из n депутатов. Ясно, что в этой комиссии

никто никого не бил.

В т о р о й с п о с о б. Рассмотрим ориентированный

граф Г (см. факт 3), вершины которого — депутаты, а

ребра — пощечины (т. е. ребро, ведущее от одного депутата

к другому, означает, что первый депутат дал второму

пощечину).

Ориентированным деревом будем называть граф следу-

ющего вида: имеется одна вершина уровня 1 (корень), в

нее ведут стрелки из вершин уровня 2, в вершины уров-

ня 2 — стрелки из вершин уровня 3, причем из каждой

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

вершин некоторого уровня k.

Мы утверждаем, что компоненты связности графа Г

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

вершинам которого «подвешены» (попарно непересекаю-

щиеся) ориентированные деревья (рис. 52). Действительно,

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

ребрам (в направлении стрелок), пока не придем в верши-

ну, в которой мы уже были. Это обязательно произойдет,

так как вершин конечное число (1994). Значит, в каждой

компоненте графа есть цикл.

Возьмем любую вершину цикла. В нее входит стрелка

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

вершин. Назовем эти другие вершины вершинами уров-

ня 2. В них могут входить стрелки из вершин, которые

мы назовем вершинами уровня 3, и т. д.

1 1

2 1 2

Рис. 52

138 Решения. 1994 год. 10 класс

Теперь раскрасим граф в 3 цвета так, чтобы концы

любого ребра были разного цвета. В цикле четной длины

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

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

остальных — через одного.

С деревьями поступим так. Пусть, например, корень

покрашен в 1-й цвет. Тогда вершины второго уровня по-

красим во 2-й цвет, 3-го уровня — снова в 1-й и т. д.

Понятно, что граф Г будет раскрашен не более чем в 3

цвета.

Ясно, что вершин некоторого цвета не меньше трети,

т. е. не меньше, чем 667. Достаточно создать комиссию

из депутатов этого цвета.

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

◦

. Если бы все циклы содержали четное число

депутатов, то хватило бы двух цветов (третий цвет нужен для циклов

нечетной длины).

◦

. Приведите пример ситуации, когда комиссию из 668 депутатов

создать не удастся.

◦

. Более общий факт состоит в следующем. Пусть каждый депутат

дал своим коллегам ровно k пощечин. Тогда найдется «приличная»

комиссия, содержащая не менее, чем

2k + 1

депутатов. Идея решения

та же: у наименее битого депутата не больше 2k врагов (k из них бил

он и не более k били его). Отправим его в комиссию, а его врагов

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

4. Попробуем угадать, чему равна длина отрезка AK.

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

Рис. 53

ся к C, тогда вторая окруж-

ность сжимается в точку, а

отрезок AK превращается в

отрезок касательной к пер-

вой окружности. Легко ви-

деть, что в этом случае AK =

AB + AC −BC

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

эта формула верна всегда (а не

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

Обозначим точки касания,

как показано на рис. 53.

Заметим, что AB

= AP, AC

= AQ, KM = KP, KN = KQ

(это отрезки касательных, проведенных из одной точки).

Решения. 1994 год. 10 класс 139

Кроме того, MN = EF — отрезки общих касательных к

окружностям (см. факт 17). Преобразуем наш гипотетиче-

ский ответ (удвоенный), учитывая эти равенства:

AB + AC −BC = AB

+ AC

−EF = AB

+ AC

−MN =

= AP + AQ −MN = AP + AQ −(MK + KN) =

= (AP −KP) + (AQ −KQ) = 2AK.

Значит,

AK =

AB + AC −BC

Задача решена.

5. П е р в ы й с п о с о б. а) Примером служит много-

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

0,3S

Рис. 54

(залов), соединенных тонкими изо-

гнутыми коридорами (рис. 54). Дока-

жем, что такая конструкция дает ре-

шение, т. е. никакая хорда не делит

многоугольник на две равновеликие

части.

Пусть S — площадь многоуголь-

ника, 0,3S — площадь одного за-

ла (0,1S — суммарная площадь всех

коридоров). Если хорда пересекает

только коридор, то по одну сторону

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

площадь больше половины площади многоугольника. Ес-

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

«перекрестка» трех коридоров, а тогда опять в одной ча-

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

б) Идея состоит в том, чтобы двигать хорду по контуру

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

шей части увеличивается.

Выберем направление хорды, не параллельное сторонам

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

правление вертикальным. Тогда хорда может проходить

не более чем через одну вершину многоугольника. Если

ни одна внутренняя точка хорды не является вершиной

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

2 части, в противном случае — ровно на 3.

140 Решения. 1994 год. 10 класс

Если площадь меньшей части больше или равна S/3, то

задача решена. В противном случае, будем двигать хорду

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

щадь меньшей части многоугольника растет. При движе-

нии хорда может «натолкнуться» на внутреннюю вершину

(но не на 2 вершины сразу).

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

площадь наименьшей части изменяется непрерывно (см.

а)

б)

Рис. 55

комментарий к решению задачи 4 для

11 класса олимпиады 2000 г.). Если в

какой-то момент она достигнет S/3, то

задача решена. В противном случае, хор-

да натолкнется на внутреннюю верши-

ну. В этом месте могут сходиться или

расходиться два коридора (рис. 55, а),

тогда хорда, выходя из коридора, скач-

ком увеличится или, входя в коридор,

скачком уменьшится (или «перепрыгнет»

в другую часть многоугольника, как на

рис. 55, б). Что произойдет с площадями?

Из трех образовавшихся частей много-

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

площадь больше S/3. Направим верти-

кальную хорду в наибольшую часть, то-

гда две меньшие части объединятся. Если

их площадь станет больше или равна S/3,

то задача решена. В противном случае

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

следующую вершину, и т. д.

Мы утверждаем, что этот процесс рано или поздно за-

вершится, т. е. площадь меньшей части достигнет S/3.

Действительно, площадь меньшей части все время растет,

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

внутреннюю вершину. Но внутренних вершин — конечное

число, значит, процесс завершится. См. также факт 2.

В т о р о й с п о с о б (набросок). б) Любой многоуголь-

ник можно разбить на треугольники диагоналями, лежа-

щими внутри него (триангулировать). Рассмотрим такую

триангуляцию. Каждая из диагоналей триангуляции раз-

бивает многоугольник на две части. Пусть AB — та из