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

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

Решения. 1993 год. 10 класс 111

них, а в том, чтобы построить искомый путь корабля. Для

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

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

750 м, и плыть по границе этого множества (тогда из

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

превосходит 750 м). Проблема состоит в том, что граница

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

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

научного исследования. Мы вынесли его в дополнение Б.

4. Будем изображать числа точками на окружности

единичной длины (числам с одинаковой дробной частью

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

тарий к решению задачи 6 для 10 класса олимпиады 1997 г.).

Тогда последовательности x

= {an + b} соответствует после-

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

n-кратным поворотом на дугу {a}. При этом p

= [2x

Нетрудно видеть, что если x

∈[0; 1/2), т. е. точка x

лежит на верхней полуокружности, то p

= 0; если x

ле-

жит на нижней полуокружности, то p

= 1.

а) Построим последовательности p

, в которых встре-

чаются все слова длины 4, начинающиеся с нуля. Таких

слов восемь. Остальные восемь слов можно получить заме-

ной (a, b) на (a, b+ 1/2). Действительно, при такой замене

точки x

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

так что p

заменится на 1 −p

П р и м е р ы: Рассмотрим a и b, при которых последова-

тельность x

образует правильные фигуры (см. таблицу).

Правильные фигуры a b Нужные слова из p

= [2x

]

восьмиугольник 1/8 0 0000, 0001, 0011, 0111

квадрат 1/4 0 0110

«двуугольник» 1/2 0 0101

треугольник 1/3 0 0010

б) Докажем, что слово 00010 не реализуется ни при

каких a и b. Пусть это слово реализуется. Рассмотрим

три подряд идущих члена последовательности x

, x

n+1

n+2

112 Решения. 1993 год. 10 класс

Если точки x

и x

n+2

диаметрально противоположные,

то следующая точка получается из предыдущей поворотом

n+1

n+2

а)

n+1

n+2

б)

Рис. 31

на 90

◦

, и очевидно, что в последователь-

ности p

не могут встретиться три нуля

подряд.

Если точки x

и x

n+2

не диаметрально

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

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

две ситуации: x

n+1

лежит на большей ду-

ге (как на рис. 31, а), и x

n+1

лежит на

меньшей дуге (как на рис. 31, б).

Пусть x

n+1

лежит на большей дуге,

тогда любые другие точки x

, x

m+1

m+2

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

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

, x

n+1

и x

n+2

по-

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

три такие точки не могут оказаться на

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

слово 000 не встретится — противоречие.

Пусть x

n+1

лежит на меньшей дуге

n+2

. Тогда лю-

бые точки x

, x

m+1

и x

m+2

расположены так же, поэтому

если x

и x

m+2

лежат на верхней полуокружности, то и

точка x

m+1

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

не встретится слово 010.

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

во 00010 не может встретиться.

К о м м е н т а р и й. Если разбить p

на куски, состоящие только из

нулей или тольк о из единиц (причем за куском из нулей идет кусок

из единиц, а за куском из единиц — кусок из нулей), то длины любых

двух таких кусков будут отличаться не больше, чем на 1. Эта задача

относится к символической динамике, о чем рассказано в статье [82].

5. Пусть m — количество растений в хорошем опреде-

лителе. Оценим суммарное количество различий между

всеми парами растений по всем признакам. Количество

пар растений равно

m(m −1)

, и каждая пара различается

не меньше, чем по 51 признаку, поэтому общее число

различий S > 51

m(m −1)

Решения. 1993 год. 10 класс 113

Оценим S другим способом. Пусть m

— количество рас-

тений, обладающих признаком i, тогда число пар расте-

ний, которые i-й признак различает, равно m

(m −m

), и

общее число различий между растениями равно:

S = m

(m −m

) + m

(m −m

) + ... + m

100

(m −m

100

В силу известного неравенства (см. факт 26), m

(m −m

) 6

. Поэтому

S 6 100

= 25m

Значит, 51

m(m −1)

6 S 6 25m

, откуда m 6 51.

Осталось доказать, что m 6= 51. Допустим, что m = 51,

тогда получаем строгое неравенство m

(m −m

) <

(так

как слева стоит целое число, а справа — дробное), и

m(m −1)

6 S < 25m

, откуда m < 51. Противоречие. Зна-

чит, m 6 50.

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

◦

. Напрашивается предположение, что в хоро-

шем определителе может быть описано 50 растений. Однако это не так.

Давайте добавим к описанию растений еще один признак — четность

числа имеющихся у данного растен ия признаков. Получим определи-

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

любые описания различаются по крайней мере по 52 признакам (если

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

числа имеющихся у этих растений признаков различны).

Действуя тем же методом, что и в решении исходной задачи, полу-

чаем: 52

m(m − 1)

6 S 6 101

, откуда m 6 34. Итак, в новом определите-

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

◦

. Эта задача связана с кодами, исправляющими ошибки. Вместо

растений рассматриваются сообщения, а вместо описаний — последова-

тельности из нулей и единиц заданной длины n; минимальное число

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

(в нашей задаче d = 51), а сам определитель называется кодом. Заме-

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

не больше, чем в

d − 1

позициях, то его можно отличить от любого

другого сообщени я в коде. Именно это свойство и понимается под

исправлением ошибок.

Общая задача определения максимального размера (т. е. числа раз-

личных сообщений) кода длины n с кодовым расстоянием d до сих

пор не решена.

114 Решения. 1993 год. 10 класс

Однако в теории кодов известна теорема Плоткина—Левенштейна.

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

стоянием d (2d > n) и утверждает, что при некотором естественном

предположении есть коды соответствующего размера. В условии нашей

задачи n = 100, d = 51, и решение демонстрирует оценку Плоткина для

этих параметров: размер кода не превышает 34. Оказывается, что эта

оценка достижима: можно придумать код из 34 сообщений.

Рис. 32

6. Пусть D и E — остальные вершины

квадрата ABDE и = ∠ACB (рис. 32).

Тогда (по теореме о средней линии тре-

угольника) из 4ACD получаем: CD= 2OM.

Аналогично, CE = 2ON. Поэтому достаточ-

но найти максимум CD + CE = 2(OM+ ON).

П е р в ы й с п о с о б. На стороне BC

треугольника ABC построим внешним об-

разом квадрат CBD

(рис. 33). Тре-

угольники ABD

и DBC равны по двум

сторонам и углу между ними. Значит

CD = AD

В треугольнике ACD

две стороны известны: AC = b,

= a

√

2. Кроме того, ∠ACD

= + 45

◦

. Третья сторона

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

ник вырождается в отрезок. Поэтому

max(CD) = max(AD

) = b + a

√

при = 135

◦

. Аналогично, max(CE) = a + b

√

2 при = 135

◦

√

Рис. 33

Итак, каждая из величин OM,

ON достигает максимума при =

= 135

◦

. Значит, и их сумма макси-

мальна при = 135

◦

max(OM + ON) =

1 +

√

(a + b).

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

∠CAB = , ∠ABC = , c = AB, d =

= CD, e = CE.

По теореме косинусов для тре-

угольника ABC:

= a

+ b

−2ab · cos .

Решения. 1993 год. 11 класс 115

По теореме косинусов для треугольника AEC:

= b

+ c

−2bc · cos (90

◦

+ ) = b

+ c

+ 2bc sin

(мы воспользовались формулой приведения).

Подставим c

из первой формулы во вторую:

= 2b

+ a

−2ab · cos + 2bc · sin .

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

sin =

sin .

Получаем:

= 2b

+ a

+ 2ab · (sin −cos ).

Аналогично получаем: d

= 2a

+ b

+ 2ab · (sin −cos ).

Отсюда следует, что максимум d и e достигается од-

новременно с максимумом выражения sin −cos при

= 135

◦

. Значит, и d + e максимально при = 135

◦

11 к л а с с

1. Если tg ( + ) определен, то

tg ( + ) =

tg + tg

1 −tg · tg

. (1)

Произведение тангенсов связано с p и q следующим обра-

зом:

q =

tg + tg

tg · tg

. (2)

Из (2) получаем, что p и q либо одновременно равны ну-

лю, либо одновременно не равны.

◦

. Если p = 0 и q = 0, то из (1) получаем tg ( + ) = 0.

При этом надо проверить, что знаменатель в (1) не равен

нулю. Действительно:

tg + tg = 0 ⇒ tg = −tg ⇒ 1 −tg · tg = 1 + tg

> 0.

◦

. Если p 6= 0, q 6= 0 и p 6= q, то из (2) получаем tg ·tg =

и из (1) tg ( + ) =

q −p

◦

. Если p 6= 0, q 6= 0 и p = q, то tg ( + ) не определен.

◦

. Если p = 0 или q = 0, но p 6= q, то условие задачи

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

2. Разобьем единичный квадрат на 4 равных квадра-

тика. Квадратики, пересекающиеся с диагональю только

116 Решения. 1993 год. 11 класс

1/2

1/4

1/8

Рис. 34

по вершине, назовем «квадратиками

первого уровня». Каждый из остав-

шихся квадратиков разобьем на 4

квадратика. Квадратики, пересекаю-

щиеся с диагональю по вершине, на-

зовем «квадратиками второго уров-

ня». Снова разобьем каждый из

оставшихся квадратиков на 4 квад-

ратика и т. д. (рис. 34). Проведем

эту операцию 500 раз.

Мы получили 2

квадратиков k-го уровня. Сторона

каждого из таких квадратиков равна 2

−k

. Значит, их сум-

марный периметр равен 4. Значит, суммарный периметр

всех квадратиков всех уровней равен 4 · 500, что больше,

чем 1993.

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

◦

. Формулировку задачи можно усилить. Су-

ществует разбиение квадрата на квадратики такое, что сумма перимет-

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

квадрата, больше 1993.

Идея решения в следующем: возьмем квадратики предыдущего раз-

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

чуть» увеличим, но так, чтобы они имели рациональную длину. (Раци-

ональность нужна для того, чтобы оставшуюся часть квадрата можно

было разбить на равные квадратики.)

◦

. Эта задача возникла на лекции известного математика Н. Н. Лузи-

на, когда он захотел короче доказать теорему Коши (он любил импро-

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

держащаяся в единичном квадрате, может пересечь квадратики разби-

ения только ограниченного суммарного периметра. Будущий академик

А. Н. Колмогоров слушал эту лекцию и вскоре построил контрпример.

3. Случай n = 2 тривиален, так что будем считать, что

n > 3.

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

n попарно непараллельных прямых, — это набор вершин

правильного n-угольника. Докажем, что непараллельных

прямых столько же, сколько осей симметрии.

Поставим в соответствие каждой стороне и каждой

диагонали ее серединный перпендикуляр (это ось симмет-

рии n-угольника). У параллельных сторон и диагоналей

серединные перпендикуляры совпадают. Верно и обратное:

для каждой оси симметрии найдется перпендикулярная

Решения. 1993 год. 11 класс 117

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

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

n-угольник имеет ровно n осей симметрии.

Теперь докажем, что для n > 3 точек, никакие три из

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

различных попарно непараллельных прямых. Легко найти

n −1 прямую: возьмем произвольную точку и рассмотрим

все прямые, через нее проходящие. Труднее найти еще

одну.

Выберем среди данных точек крайнюю. Для этого

рассмотрим их выпуклую оболочку. Иными словами,

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

данные точки, с вершинами в некоторых из этих точек

A B

Рис. 35

(это минимальный выпуклый много-

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

Пусть O — вершина этого выпуклого

многоугольника (рис. 35), A и B — со-

седние с ней вершины. Тогда все лучи,

соединяющие O с остальными точками,

проходят внутри угла AOB. Прямая AB

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

взять в качестве n-й прямой.

К о м м е н т а р и й. Условие общего положения точек нельзя заме-

нить на более слабое: «не все точки лежат на одной прямой». На-

пример, для вершин правильного 2k-угольника и его центра найдутся

лишь 2k попарно непараллельных прямых.

4. Заметим, что если выбрано число k, то после хода в

ящике, в котором было m камней, будет q + r камней, где

q и r — частное и остаток от деления m на k соответствен-

но (см. факт 7).

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

первом ящике лежит 1 камень, во втором — 2 камня и

т. д. вплоть до n-го ящика, в котором лежит n камней

(где n = 460 в пункте «а» и n = 461 в пункте «б»).

◦

. Пусть в ящиках лежат 1, 2, ..., n камней, где

n — некоторое натуральное число. Пусть выбрано чис-

ло k и сделан ход. Пусть f(n, k) — максимальное число

камней в ящике (после хода). Тогда для любого числа

камней 1 6 j 6 f(n, k) найдется ящик, в котором лежит

118 Решения. 1993 год. 11 класс

j камней. Иначе говоря, числа камней в ящиках снова

будут образовывать начальный отрезок натурального ря-

да. Докажем это обратной индукцией по j (см. факт 24).

Пусть найдется ящик с j камнями. Тогда найдется такое

число m (1 6 m 6 n), что j = q + r, где q и r — частное и

остаток от деления m на k. Если r 6= 0, то в ящике, в ко-

тором был m −1 камень, станет j −1 камень. Если r = 0, то

нужно рассмотреть ящик, в котором было m −k камней.

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

◦

. Пусть частное от деления n + 1 на k равно q. Рас-

смотрим ящик, в котором лежит (q −1)k + (k −1) камней.

В нем останется q + k −2 камня. Нетрудно видеть, что это

будет самый большой ящик (впрочем, если n + 2 делится

на k, то будет еще ровно один ящик с таким же числом

камней). Итак,

f(n, k) = q + k −2 =

n + 1

+ k −2. (1)

◦

. Оптимальное значение k (при котором f(n, k) до-

стигает минимума) равно [

√

n + 1] + 1.

Д о к а з а т е л ь с т в о. Имеем

f(n, k) =

n + 1

+ k

−2.

Функция

n + 1

+ x убывает на интервале (0;

√

n + 1) и воз-

растает на интервале (

√

n + 1; n]. Так как [x] — неубы-

вающая функция, f(n, k) достигает минимума либо при

k = [

√

n + 1], либо при k = [

√

n + 1] + 1.

Осталось доказать, что всегда

f(n, [

√

n + 1] + 1) 6 f(n, [

√

n + 1]).

Пусть [

√

n + 1] = s. Тогда

6 n + 1 < (s + 1)

. (2)

В силу (1) достаточно доказать, что

n + 1

s + 1

n + 1

Решения. 1993 год. 11 класс 119

Из (1) следует, что

n + 1

s + 1

6 s, а

n + 1

> s.

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

няться s. Но

n + 1

= s ⇒

n + 1

< s + 1 ⇒

n + 1

s + 1

< s ⇒

n + 1

s + 1

< s.

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

◦

. Пусть

g(n) = f(n, [

√

n + 1] + 1).

Тогда, начиная с ящиков с 1, 2, . . . , n камнями, мы при

оптимальном выборе k (за один ход) получим ящики с 1,

2, ..., g(n) камнями. Осталось убедиться прямым вычис-

лением, что g(g(g(g(g(460))))) = 1, а g(g(g(g(g(461))))) = 2.

Последовательность ходов для n = 460 приведена в та-

блице:

ход 1 2 3 4 5

n 460 40 10 4 2 1

k 22 7 4 3 2

Изложим рассуждение при n = 461 более подробно:

из доказанного следует, что если в ящиках содержатся

все наборы камней от 1 до 461, то после первого хода

останутся, по крайней мере, все наборы от 1 до g(461) =

= f(461, 22) = 41; после второго — все наборы от 1 до

g(41) = 11; затем — от 1 до 5; от 1 до 3; и, наконец,

от 1 до 2. Итак, при n = 461 не всегда можно оставить 1

камень во всех ящиках.

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

◦

. Вместо того чтобы доказывать неравенство

f (n, [

√

n + 1] + 1) 6 f(n, [

√

n + 1]),

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

◦

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

жащий более одного пробела между некоторыми словами. Нужно было

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

бел. При этом применялась следующая операция: выбиралось число k

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

подряд заменялась на один пробел.

120 Решения. 1993 год. 11 класс

−

−1

Рис. 36

5. а) Можно взять, например:

f(x) =











−

−x при x ∈

−1; −



;

x −

при x ∈

−

; 0



;

0 при x = 0;

x +

при x ∈



;

−x при x ∈



; 1

График этой функции изображен на рис. 36.

б) Допустим, что существует такая функция f, опреде-

ленная на интервале (−1; 1) (случай функции, определен-

ной на всей числовой оси, аналогичен).

◦

. График функции f(x) переходит в себя при пово-

ротах на 90

◦

, 180

◦

и 270

◦

. Действительно, пусть (x; y) —

точка на графике. Тогда y = f(x), значит, f(y) = −x. Поэто-

му точка (y; −x) тоже лежит на графике. Но эта точка

как раз получается из точки (x; y) поворотом на 90

◦

по

часовой стрелке. Значит, график переходит в себя при

таком повороте. Но тогда он переходит в себя и при по-

воротах на 180

◦

и 270

◦

. f (0) = 0 и f(x) 6= 0, если x 6= 0. Действительно, если

f(0) = y 6= 0, то точка (0; y) лежит на графике. Тогда по

доказанному и точка (0; −y), которая получается из нее

поворотом на 180

◦

, лежит на графике, что противоречит

определению функции.

Если же f(x) = 0, где x 6= 0, то точка (x; 0) лежит на

графике. Поворачивая эту точку на 90

◦

и 270

◦

, приходим

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

◦

. По условию, график есть объединение конечного

числа точек и интервалов, значит, часть графика, распо-

ложенную в положительном квадранте {x > 0, y > 0}, мож-

но представить в виде:

∪I

∪. . . ∪I

∪P

∪. . . ∪P

При этом можно считать, что разные интервалы I

не

пересекаются, а точки P

различны и не принадлежат