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

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

Решения. 2004 год. 11 класс 361

Л е м м а. Пусть f — дифференцируемая функция c пе-

риодом 2 . Тогда число нулей функции f на полуинтер-

вале [0; 2 ) не превосходит числа нулей ее производной

на том же полуинтервале.

Д о к а з а т е л ь с т в о. Воспользуемся теоремой Ролля:

между двумя нулями дифференцируемой функции есть

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

задаче). Пусть x

, x

, ..., x

— нули функции на ука-

занном полуин тервале. По теореме Ролля на каждом из

интервалов (x

; x

), (x

; x

), . . . , (x

N−1

; x

), (x

; x

+ 2 )

есть хотя бы один нуль производной. Однако нуль про-

изводной на последнем интервале (обозначим его через y)

может оказаться вне полуинтервала [0; 2 ). В этом случае

рассмотрим y −2 — это тоже нуль производной, так как

производная периодической функции периодична. Лемма

доказана.

Из леммы следует, что N(F

) > N(F

m+1

). Поэтому до-

статочно доказать, что N(F

) > 2k

для достаточно боль-

шого числа M.

Поскольку

< 1,

< 1, то для достаточно большого

числа M















< 1

(см. факт 27). Выберем такое M вида 4m + 3, тогда





= cos( n)+ A





cos





+ A





cos





Поэтому F





> 1 − > 0 для четных n и F





< −1 +

+ < 0 для нечетных n. Значит, непрерывная функция F

обязательно имеет нуль между любыми соседними точка-

ми x

, где n = 0, 1, ..., 2k

. Поэтому N(F

) > 2k

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

◦

. Периодическую функцию можно представ-

лять себе как функцию на окружности. Тогда утверждение леммы

переформулируется так: число нулей функции на окружности не пре-

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

прозрачным.

◦

. Идея доказательства теоремы Ролля: рассмотрите экстремумы

(максимум и минимум) функции на отрезке, соединяющем точки, где

362 Решения. 2004 год. 11 класс

функция обращается в нуль. Если один из экстремумов достигается

внутри отрезка, то производная обращается в нуль в этой точке. Если

оба экстремума достигаются на концах отрезка, то функция равна

нулю на этом отрезке тождественно.

◦

. Вообще говоря, может оказаться, что функция имеет бесконечно

много нулей на полуинтервале. В этом случае лемму нужно понимать

так: если f имеет бесконечно много нулей на полуинтервале, то и f

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

доказательство остается в силе и в этом случае.

6. а) Предположим, что бойница имеет длину s < 2/3.

За то время, пока второй стражник проходит не занятый

бойницей участок стены (длины 1 −s), первый стражник

пройдет расстояние 2(1 −s) > s. Поэтому найдется такой

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

ходится возле бойницы — противоречие. Значит, s > 2/3.

Рассмотрим такой момент времени, в который первый

стражник находится на 1/3 впереди второго. Пусть бойни-

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

рый имеет длину 2/3. Легко проверить, что тогда условия

задачи выполнены.

б) Пусть суммарная длина бойниц равна s. Без ограни-

чения общности будем считать, что в начальный момент

времени стражники находятся в одной точке, а за 1 час

второй стражник делает ровно один обход вдоль стены.

Чтобы система бойниц была надежной, необходимо, чтобы

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

в течении часа, было не меньше часа. Более того, это

время должно быть больше часа, так как найдется такой

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

находиться возле одной и той же бойницы, содержащей

точку их встречи.

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

возле бойниц s часов (первый стражник пройдет все бой-

ницы дважды, но в два раза быстрее). Итак, 2s > 1, и сле-

довательно s > 1/2.

в) Построим множество A ⊂[0; 1], обладающее следую-

щими свойствами:

1) A есть объединение конечного числ а непересекаю-

щихся отрезков;

2) суммарная длина этих отрезков не превосходит s;

Решения. 2004 год. 11 класс 363

3) если t /∈A, то {2t} ∈A (фигурные скобки обозначают

дробную часть).

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

несложно. Как и раньше, считаем, что в момент времени

t = 0 стражники находились в одной точке, а за отрезок

времени [0; 1] второй стражник делает ровно один обход

вдоль стены. Поставим в соответствие числу t ∈[0; 1]

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

момент t. Пусть бойницы проделаны на участках стены,

соответствующих отрезкам, составляющим множество A.

Тогда их суммарная длина будет меньше s. Так как для

любого t имеем t ∈A или {2t} ∈A, получаем, что в каждый

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

находится возле бойницы.

И д е я п о с т р о е н и я м н о ж е с т в а A: допустим,

что нам удалось разбить отрезок [0; 1] на такие множества

A и B, что если t ∈A, то {2t} ∈B, а если t ∈B, то {2t} ∈A.

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

Представим себе на секунду, что множества A и B состоят

из отрезков (это, конечно, невозможно). Тогда нетрудно

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

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

ющих множество B, а значит, равна 1/2. К сожалению,

таких множеств A и B не существует (см. комментарий).

Тем не менее, можно построить множества A и B, для

которых эти условия выполнены «с точностью до s −

».

Этим мы и займемся.

Выберем натуральное число n таким, чтобы

< s −

Можно считать, что n нечетно. Рассмотрим двоичную за-

пись числа t из полуинтервала [0; 1):

t = 0,a

...

(все a

равны 0 или 1, см. факт 12). Пусть задано неко-

торое натуральное число q. Рассмотрим множество M

чи-

сел t из полуинтервала [0; 1), для которых среди первых

qn знаков после запятой в двоичном разложении t встре-

чается набор 100 ...0

| {z }

n−1 нулей

. Ясно, что M

представляет собой

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

364 Решения. 2004 год. 11 класс

Дополнение [0; 1) \M

содержится в множестве G

тех

чисел t из полуинтервала [0; 1), для которых ни один

из наборов вида

kn+1

kn+2

...a

(k+1)n

(k = 0, 1, . . . , q −1)

не совпадает с набором 100 ...0

| {z }

n−1 нулей

. Суммарная длина полу-

интервалов, составляющих множество G

, равна



−1



Поскольку

−1

< 1, то g

стремится к нулю при неогра-

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

можно взять q настолько большим, что g

n+1

. Можно

считать, что q четно.

Множество M

разобьем на два множества B

и C

, где

— множество таких чисел t, что набор 100 . . . 0

| {z }

n−1 нулей

впервые

встречается в двоичной записи числа t, начиная с нечет-

ного места (т. е. наименьшее k > 0, для которого набор

k+1

...a

k+n−1

совпадает с набором 100 . . . 0

| {z }

n−1 нулей

, нечетно).

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

— множество таких чисел t, что набор

100...0

| {z }

n−1 нулей

впервые встречается, начиная с четного места.

Обозначим суммарную длину полуинтервалов, состав-

ляющих множество B

, через b

, а суммарную длину

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

, — через c

Пусть число t = 0,a

... содержится в B

, тогда чис-

ло

= 0,0a

... содержится в C

(здесь мы используем

то, что n нечетно, а q четно). Кроме того, если набор

...a

n−1

первых цифр числа t

не совпадает с набо-

ром 00...0

| {z }

n−1 нулей

, то число

+ 1

= 0,1a

... также содержит-

ся в C

. Ясно, что

+ 1



так как

+ 1



Решения. 2005 год. 8 класс 365

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



−

n−1



= b

−

Значит, b

< 1 −c

6 1 +

−b

, т. е. b

n+1

Положим A

= B

∪G

. Тогда A

— объединение попарно

непересекающихся полуинтервалов. Искомое множество A

получается из множества A

заменой всех полуинтервалов

на отрезки.

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

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

+ g

n+1

< s,

и свойство 2 доказано. Для доказательства последнего

свойства заметим, что если t /∈A, то t = 0,a

... содер-

жится в множестве C

, т. е. среди первых qn знаков

после запятой встречается набор 100 . . . 0

| {z }

n−1 нулей

, причем он

впервые встречается, начиная с четного места. Тогда {2t} =

= 0,a

..., так что {2t} принадлежит множеству B

⊂A.

К о м м е н т а р и й. Обозначим (x) = {2x}. Тогда можно рассмат-

ривать как отображение единичной окружности в себя. Можно было

бы пытаться решить задачу следующим образом: разобьем окружность

на множества A и B так, что (A) = B и (B) = A. «Приблизим» мно-

жество A объединением отрезков и возьмем это множество отрезков в

качестве бойниц. Нетрудно видеть, что если множества A и B измери-

мы, то мера каждого из них равна 1/2. Однако оказывается, что такие

множества A и B не могут быть измеримыми! Это связано с тем, что

отображение ( (x)) = {4x} является эргодическим. Подробнее об этом

см. в [77].

2005 год

8 к л а с с

1. Для решения задачи достаточно убедиться, что числа

a = 2, b = 20 удовлетворяют нашему уравнению.

Объясним, как найти все целочисленные решения это-

го уравнения (хотя этого и не требовалось для решения

366 Решения. 2005 год. 8 класс

задачи). Разложим левую часть уравнения на множители:

+ a

+ b

+ 1 = a

+ 1) + (b

+ 1) = (a

+ 1)(b

+ 1).

Уравнение примет вид (a

+ 1)(b

+ 1) = 2005. Значит, и

+ 1) и (b

+ 1) являются делителями числа 2005 (см.

факт 5).

Найдем все положительные делители числа 2005. Для

этого разложим это число на простые множители: 2005 =

= 5 · 401 (см. факт 10). Теперь ясно, что все положитель-

ные делители числа 2005 — это 1, 5, 401 и 2005.

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

+ 1 не может быть равно 2005: иначе

= 2004, но 2004 не является полным квадратом. Кроме

того, если a

+ 1 = 1, то b

+ 1 = 2005, что тоже невозможно.

Значит, возможны только случаи

(

+ 1 = 5,

+ 1 = 401

или

(

+ 1 = 401,

+ 1 = 5.

Рис. 180

Решая эти уравнения, находим все

решения исходного уравнения: a =

= ±2, b = ±20 или a = ±20, b = ±2.

2. Пусть разрез проходил верти-

кально (случай горизонтального раз-

реза аналогичен). Проведем во всех

квадратиках 1 ×1 вертикальные от-

резки, соединяющие середины про-

тивоположных сторон. Заметим, что

при сгибании по линиям клеток эти

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

га. Следовательно, при разрезании разрезаются они

и только они. Считая число получающихся при этом ча-

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

К о м м е н т а р и й. Важно было решить задачу для произвольного

складывания, а не рассматривать конкретный пример. В частности, в

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

3. Так как AA

и BB

— высоты, треугольники AA

B, CA

H и CB

H — прямоугольные (рис. 181). Медиана

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

Решения. 2005 год. 8 класс 367

Рис. 181

равна ее половине (см.

факт 14), поэтому XA

AB = XB

и YA

CH =

= YB

. Значит, треугольники

Y и XA

Y равны по

трем сторонам. Следователь-

но, YX — биссектриса угла

. Но в равнобедренном

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

биссек-

триса является высотой,

поэтому прямая XY перпен-

дикулярна прямой A

В а р и а н т р е ш е н и я. Это решение можно изложить

иначе: построим на отрезках AB и CH как на диамет-

рах окружности. Центры этих окружностей — точки X

и Y, причем окружности пересекаются в точках A

и B

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

соединяющая точки пересечения двух окружностей, пер-

пендикулярна линии центров.

4. Пусть это не так, то есть после выкидывания лю-

бых двух соседних чисел оставшиеся числа можно разбить

на две группы с равной суммой. Предположим сначала,

что все числа четны (см. факт 23). Поделим все числа

на два. Заметим, что указанное свойство сохранится по-

сле деления, т. е. опять после выкидывания любых двух

соседних чисел оставшиеся числа можно разбить на две

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

димости все числа набора на 2 несколько раз, можно счи-

тать, что среди всех 2005 чисел есть хотя бы одно не-

четное.

Рассмотрим два случая: сумма всех чисел четна и сум-

ма всех чисел нечетна. В первом случае все 2005 чисел

нечетными быть не могут, т. е. среди них есть как чет-

ные, так и нечетные числа. Тогда среди них можно най-

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

их. Сумма оставшихся чисел будет нечетной, значит, их

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

приходим к противоречию.

368 Решения. 2005 год. 8 класс

Пусть теперь сумма всех 2005 чисел нечетна. Заметим,

что обязательно найдутся два числа одной четности, стоя-

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

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

нечетное число.

Выкинув эти два числа, мы получим 2003 числа, сум-

ма которых нечетна, значит, их нельзя разбить на две

группы с равной суммой — противоречие.

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

◦

. Если в условии задачи заменить натураль-

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

ным — докажите это сами. На самом деле утверждение останется вер-

ным и для вещественных чисел, но доказать это гораздо сложнее.

По этому поводу см. факт 25 и задачу 6 для 9 класса олимпиады

1998 г.

◦

. Хорошо известна похожая задача: в стаде 101 корова. Известно,

что если увести любую корову, то оставшихся можно разделить на

два стада с равной суммарной массой коров. Доказать, что все коровы

имеют одинаковую массу.

5. Разобьем окружность с центром в точке O на шесть

равных частей точками A, B, C, D, E и F. Треугольник

OAB — равносторонний, так как OA = OB, ∠AOB =

360

◦

= 60

◦

. Аналогично, треугольники OBC, OCD, ODE, OEF

и OFA — равносторонние.

Проведем дугу окружности с центром в точке A ра-

диуса AB от точки B до точки O. Аналогично проведем

дуги окружностей с центрами в точках B, C, D, E, F

(рис. 182, а). Таким образом, мы разбили окружность на 6

равных частей. Теперь каждую из этих частей разобьем

на две равные части одним из двух способов, изображен-

ных на рис. 182, б. Получившиеся разрезания изображе-

ны на рис. 182, в. Еще один вариант разрезания изоб-

ражен на рис. 182, г. (Доказательств в этой задаче не

требовалось.)

К о м м е н т а р и й. Данная задача приоткрывает дверь в волшеб-

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

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

проблема. Укажем некоторые направления возможного исследования:

1) Круг разделен на 12 равных частей так, что центр лежит на

границе некоторых, но не всех частей. Верно ли, что части равны

Решения. 2005 год. 8 класс 369

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

нии? Никто не знает!

2) При каких n круг можно разделить на n равных частей так,

чтобы центр лежал на границе некоторых, но не всех частей? (пример

известен лишь при n вида 6k, k > 2; недавно А. Я. Канель-Белов дока-

зал, что при n = 2 такое деление невозможно (см. [84]), больше ничего

не известно).

3) Круг разделен на несколько равных частей. Верно ли, что диа-

метр каждой из частей не меньше радиуса круга? Никто не знает!

(Диаметром фигуры называют наибольшее из расстояний между ее

точками.)

4) Можно ли разделить круг на несколько равных частей так,

чтобы центр круга лежал строго внутри (не на границе) одной из

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

для правильных n-угольников при n > 4.

5) Аналогичные вопросы можно поставить про шар в простран-

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

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

Если Вы смогли решить одну из этих задач или придумали

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

тересно про это узнать: напишите, пожалуйста, Сергею Маркелову

(markelov@mccme.ru).

E F

а)

б)

в) г)

Рис. 182

370 Решения. 2005 год. 8 класс

6. Изложим сначала решение, если точек всего 8, и

можно использовать только три цифры: 0, 1 и 2 (заметим,

что 8 = 2

). Осел должен пометить отрезки как на рис. 183

(16 отрезков на рисунке не изображены, их Осел должен

1 1

Рис. 183

пометить цифрой 2).

Докажем, что Тигр проиграет. Ясно, что в

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

он должен использовать цифру, отличную от

нуля. Рассмотрим верхнюю четверку, одну из

двух верхних вершин Тигр должен пометить

не нулем и одну из двух нижних он должен

пометить не нулем. Если бы он обе эти верши-

ны пометил единицей, то проиграл бы. Значит,

одну из них он вынужден пометить двойкой.

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

шин в нижней четверке Тигр должен пометить

двойкой, но эти вершины соединены ребром, помеченным

двойкой, так что Тигр проиграет.

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

т. е. вместо трех цифр можно использовать все 1 0, а вме-

сто 8 = 2

точек мы используем 1024 = 2

точек.

Итак, выделим из данных точек какие-нибудь 1024.

Докажем, что Осел может так пометить отрезки, что неза-

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

ных 1024 точек найдутся две точки, помеченные той же

цифрой, что и соединяющий их отрезок.

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

пометит нулем отрезки, соединяющие точки из одной па-

ры. Далее, объединим получившиеся пары по две. Полу-

чим 256 четверок. Осел пометит цифрой 1 еще не по-

меченные отрезки, соединяющие точки одной четверки.

После этого объединим получившиеся четверки по две.

Получим 128 восьмерок. Осел пометит цифрой 2 еще не

помеченные отрезки, соединяющие точки из одной вось-

мерки, и так далее. На последнем шаге объединим полу-

чившиеся две группы по 512 точек в одну, и пусть Осел

пометит еще не помеченные отрезки цифрой 9.

Предположим, что теперь Тигр может пометить точки

так, чтобы не нашлось отрезка, помеченного той же циф-

рой, что и оба его конца.