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

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

Указания 91

2. Найдите сначала трехзначное число, обладающее

нужным свойством.

3. Подсчитайте разными способами число закрашенных

клеток.

4. Докажите, что ∠BAX = ∠YCA.

5. Если 15 городов соединены авиалиниями так, что

можно добраться от любого города до любого другого, то

авиалиний не меньше 14.

6. Рассмотрите остатки от деления Бориного числа

на 12.

9 к л а с с

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

ко частей и сложить второго головастика.

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

ными.

4. Действуйте по аналогии с алгоритмом Евклида.

5. Центр данной окружности и точки A, E, C лежат на

одной окружности.

6. Пусть выключает свет только один из узников.

10 к л а с с

1. Подберите коэффициенты, пользуясь теоремой Виета.

2. Подумайте, четна или нечетна сумма числа сторон

на всех гранях одной части.

3. Если степень P(x) больше единицы, то для достаточ-

но больших x выполняется неравенство |P(x)|> |x|.

4. Перепишите условие задачи, используя векторы и

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

5. Действуйте по индукции, пользуясь следующей лем-

мой. Пусть множество городов M таково, что из каждого

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

Пусть дорога X →Y такова, что X ∈M, Y /∈M. Тогда из Y

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

минуя город X.

6. Рассмотрите функции P

(tg x).

11 к л а с с

1. Перенеся все слагаемые в левую часть и освободив-

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

делится на x −y.

92 Указания

3. Рассмотрите точки, симметричные точке H относи-

тельно прямых AB и AD.

4. Отметьте точку на окружности и напишите около

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

отмеченной точки до этой вишенки и ее номера.

5. Угол между любыми двумя внешними нормалями к

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

6. Упорядочите борцов в каждой деревне по силе и

сравните борцов, имеющих один и тот же номер в разных

деревнях.

7. Докажите, что a −1 — степень двойки.

2004 год

8 к л а с с

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

квадрат с такой стороной может располагаться на клетча-

той бумаге.

3. Прямые, содержащие высоты треугольника, пересе-

каются в одной точке.

4. Пусть курс акций повышался k раз и понижался l

раз. Во сколько раз он изменился?

5. а, б) Рассмотрите правильный семиугольник.

6. Поворачивайте вертикальные доминошки, пока это

возможно. Где после этого окажется пустая клетка? Затем

уложите доминошки «змейкой».

9 к л а с с

1. См. указание к задаче 4 для 8 класса.

3. Угол между любой из сторон бильярда и отрезками

пути шара постоянен.

4. Любой отрезок внутри треугольника не превосходит

наибольшей стороны.

5. Рассмотрите наименьшее неразрешенное число.

6. а) Двумя рубашками можно закодировать масть

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

двух карт.

б) Среди карт, лежащих на нечетных местах, имеется

не менее пяти карт одной масти. Используйте этот факт,

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

Указания 93

10 к л а с с

1. Используйте формулу для суммы членов арифмети-

ческой прогрессии.

3. Ищите черное число в виде суммы двух «сопряжен-

ных» белых чисел.

4. См. указание к задаче 5 для 9 класса.

5. Пусть A

лежит на луче CB. Докажите, что центры

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

A и A

являются вершинами равнобочной трапеции.

11 к л а с с

1. К какому простейшему виду можно привести квад-

ратный трехчлен преобразованием f(x) 7→Af(ax + b)?

2. а) Нетрудно выбрать точки A, B, C, D на указан-

ных прямых, чтобы отрезки AB и CD были параллель-

ны. Сложнее исключить случай параллелограмма. Основ-

ная сложность — исключить случай четырех точек, лежа-

щих на одной прямой. Для этого переведите первые три

прямые аффинным преобразованием в прямые, лежащие

на гиперболоиде x

+ y

−z

= 1 или на параболоиде xy = z.

5. Пусть F — функция с периодом 2 . Число ее нулей

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

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

6. а) Какое расстояние пройдет первый стражник за вре-

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

б) Пусть второй стражник обходит вокруг стены за час.

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

около бойниц в течении часа.

в) Было бы достаточно разбить отрезок [0; 1] на такие

множества A и B, состоящие из отрезков, что если t ∈A,

то {2t} ∈B, а если t ∈B, то {2t} ∈A. К сожалению, это

невозможно, поэтому постройте множества A и B, для

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

2005 год

8 к л а с с

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

3. Используйте факт 14.

94 Указания

4. Если все числа четны, поделите их на 2.

5. Разбейте вначале круг на шесть равных частей ду-

гами окружностей того же радиуса, проходящими через

центр исходного круга.

6. Попробуйте решить задачу, если точек всего 8, и

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

9 к л а с с

1. x

−x

√

2. Если к любому набору чисел, обладающему нужным

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

набор, обладающий нужным нам свойством.

4. Рассмотрите очень длинный и тонкий треугольник.

5. Рассмотрите минимальное число, при повороте на

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

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

APB.

10 к л а с с

1. Из равенства тангенсов не следует равенство углов.

2. Перенесите начало координат в одну из точек, упо-

минающихся в условии задачи.

3. Используйте факт 18.

5. m

−1 делится на 5 для любого m, не делящегося

на 5.

6. а) См. указание к задаче 6 для 8 класса.

11 к л а с с

1. Вариант А. Докажите, что прямая y= bx−a касается

графика функции y = sin x.

2. Пусть a

, a

, . . . , a

— наша прогрессия. Тогда

функция

S(x) = |a

−x |+ |a

−x |+ . . . + |a

−x |

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

4. а) Рассмотрите вписанный четырехугольник; б) Рас-

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

к диагоналям.

6. Угадайте за 2n + 1 попытку одну точку.

РЕШЕНИЯ

1993 год

8 к л а с с

1. а) Согласно признаку делимости на 3 (см. факт 6),

числа x и S(x) дают одинаковые остатки от деления на 3.

Такой же остаток будет и у числа S(S(x)). Значит, сумма

x + S(x) + S(S(x))

делится на 3 (так как это сумма трех чисел с одинако-

выми остатками от деления на 3). Однако, 1993 на 3 не

делится, поэтому решений нет.

б) Ясно, что x < 1993. Нетрудно видеть, что среди

чисел, меньших 1993, наибольшую сумму цифр 27 имеют

числа 1989 и 999. Значит, S(x) 6 27. Далее, S(S(x)) 6

6 S(19) = 10. Наконец, S(S(S(x))) 6 9. Из уравнения сле-

дует, что

x = 1993 −S(x) −S(S(x)) −S(S(S(x))) >

> 1993 −27 −10 −9 = 1947.

Аналогично пункту «а», все числа x, S(x), S(S(x)),

S(S(S(x))) дают одинаковые остатки при делении на 9,

а 1993 дает остаток 4, поэтому число x должно давать

остаток 1 (см. комментарий). Среди чисел от 1947 до 1993

остаток 1 при делении на 9 дают 1954, 1963, 1972, 1981,

1990. Проверив эти числа, убеждаемся, что подходит

только 1963.

К о м м е н т а р и й. Мы использовали такое утверждение: если сум-

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

делении на 9 остаток 4, то каждое из этих чисел дает остаток 1. Это

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

остаток через x. Тогда 4x дает остаток 4 при делении на 9. То есть

4(x −1) = 4x −4 делится на 9, и, значит, x −1 делится на 9. То есть

x = 1, см. факт 7.

2. Пусть

n = a

+ b

+ c

Тогда

= (a

+ b

+ c

)

= a

+ b

+ c

+ 2a

+ 2b

+ 2a

98 Решения. 1993 год. 8 класс

Преобразуем это выражение:

+ b

+ c

+ 2a

+ 2b

+ 2a

= (a

+ b

+ c

+ 2a

−2b

−2a

) + 4b

+ 4a

= (a

+ b

−c

)

+ (2bc)

+ (2ac)

Можно считать, что a > b > c, тогда a

+ b

−c

> 0. Следова-

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

в виде суммы квадратов

трех натуральных чисел.

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

◦

. Попробуйте доказать аналогичное утвержде-

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

◦

. Для суммы двух квадратов утверждение не всегда верно:

+ 1

)

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

чисел, хотя есть аналогичное тождество: (a

+ b

)

= (a

−b

)

+ (2ab)

◦

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

четырех квадратов целых чисел. Это знаменитая теорема Лагранжа.

(Заметим, что квадраты целых чисел — это квадраты натуральных чи-

сел и еще число 0 = 0

◦

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

целых чисел, например, число 7. Оказывается, число не представимо

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

(8k + 7) · 4

◦

. По поводу сумм двух квадратов см. комментарий к задаче 4

для 11 класса олимпиады 1996 г.

◦

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

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

ных, выписывая тождество. Можно задать такой вопрос: при каких k

произведение

+ a

+ .. . + a

)(b

+ b

+ .. . + b

)

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

+ .. . + P

где P

, . .. , P

— многочлены от переменных a

, . .. , a

, b

, . .. , b

Приведем соответствующие формулы при k = 1, 2, 4.

n = 1: a

· b

= (ab)

;

n = 2 (тождество Диофанта):

+ b

)(c

+ d

) = (ac + bd)

+ (ad −bc)

;

n = 4 (тождество Эйлера):

+ b

+ c

+ d

)(a

+ b

+ c

+ d

) =

= (a

−b

−c

−d

)

+ (a

+ c

+ a

−c

)

+ (a

+ a

+ b

−b

)

+ (a

+ a

+ b

−b

)

Существует аналогичное тождество для n = 8. Для n, отличного от

1, 2, 4 и 8, таких тождеств не существует (хотя доказать это очень

Решения. 1993 год. 8 класс 99

не просто)! Чтобы окончательно заинтриговать читателя, скажем, что

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

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

(n = 8) с октавами Кэли.

Прочитать об этом можно в книге [31].

3. П е р в ы й с п о с о б. Будем называть две фишки, из

которых левая — красная, а правая — синяя, инверсией.

Рис. 20

Рассмотрим число всех инверсий (напри-

мер, на рис. 20 число инверсий равно 3).

Оказывается, четность этого показателя

не может измениться (см. факт 23).

Действительно, пусть, например, мы вставили две крас-

ные фишки так, что справа от них будет k синих фишек.

Тогда число инверсий увеличится на 2k, и его четность

не изменится. Аналогично разбираются три других случая

(добавление двух синих фишек, удаление двух красных

и удаление двух синих). Итак, четность числа инверсий

является инвариантом (см. факт 2).

Теперь заметим, что в исходной ситуации число инвер-

сий равно 1, т. е. нечетно, а в желаемой — равно нулю,

т. е. четно. Поэтому перейти к желаемой ситуации невоз-

можно.

К о м м е н т а р и й. Иначе этот инвариант можно описать, как чет-

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

синих.

В т о р о й с п о с о б (выходящий за рамки программы

8-го класса). Рассмотрим прямую (эта прямая не имеет

отношения к прямой, на которой стоят фишки) и две

различных точки A и B на этой прямой. Поставим в со-

ответствие каждому расположению фишек некоторое пре-

образование этой прямой. Это преобразование не будет из-

меняться при разрешенных операциях, т. е. будет инва-

риантом.

Преобразование строится так: мы двигаемся по прямой,

на которой стоят фишки, слева направо. Когда встреча-

ется красная фишка, мы производим симметрию относи-

тельно точки A, а когда встречается синяя фишка — сим-

метрию относительно точки B. Итак, последовательности

фишек соответствует композиция симметрий.

100 Решения. 1993 год. 8 класс

Нетрудно видеть, что каждая операция над фишками

не меняет композицию симметрий. Например, добавление

двух красных фишек соответствует двум одинаковым сим-

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

тождественное преобразование. Остальные случаи (добав-

ление двух синих фишек, удаление двух красных и уда-

ление двух синих фишек) аналогичны.

Итак, эта композиция является инвариантом, в то вре-

мя как начальному и конечному расположению фишек со-

ответствуют разные композиции — параллельные переносы

на векторы 2 и −2 соответственно. Последнее утверждение

можно проверить, введя координаты на прямой.

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

◦

. Эта задача родилась из известной теоремы:

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

ные вершины, пересекаются. Дадим набросок доказательства.

Допустим, что пути не пересекаются. Тогда их можно заменить

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

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

Рис. 21

а другую — в синий. Будем параллельно передвигать

прямую от одной стороны квадрата к другой. Прямая

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

точек, с которым будет происходить то же самое, что

с фишками в задаче (вставкам и удалениям фишек

соответствует прохождение прямой через некоторые

внутренние точки звеньев ломаной, рис. 21).

◦

. Доказанное утверждение тесно связано с те-

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

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

кость на две части. Это интуитивно ясное утвержде-

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

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

даже, как выбрать две точки по разные стороны от кривой.

Н е э л е м е н т а р н ы й к о м м е н т а р и й. Рассмотрим группу, по-

рожденную двумя образующими a и b и соотношениями a

= b

= 1.

Поставим в соответствие красной фишке элемент a, синей — элемент b,

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

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

образующих a и b. Ясно, что элемент группы не меняется при разре-

шенных операциях (в силу соотношений). Более того, из одной после-

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

когда соответствующие элементы группы совпадают.

Можно проверить, что эта группа изоморфна полупрямому произ-

ведению групп Z и Z/2Z. Она некоммутативна, а расположения фишек

из условия задачи соответствуют элементам ab и ba.