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

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

Решения. 1999 год. 11 класс 251

квадрате. Выполним гомотетию с центром в левой ниж-

ней вершине большого квадрата и коэффициентом 2.

Рис. 113

Тогда выбранная клетка перейдет в

квадрат со стороной 2

−n

. Нетрудно

видеть, что это будет одна из клеток,

получившихся при разбиении квад-

рата на 4

квадратов со стороной

−n

По предположению индукции куз-

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

прыгнет теперь к левой нижней вер-

шине квадрата, то попадет в нужную

клетку.

К о м м е н т а р и й. Сравните с задачей 5 для 10 класса и с зада-

чей 7 для 11 класса.

5. Цвета, в которые покрашен граф, занумеруем числа-

ми от 1 до k. Те вершины цвета 2, которые не соседствуют

ни с какими вершинами цвета 1, перекрасим в цвет 1.

Новая раскраска будет правильной, поэтому в ней k цве-

тов. Значит, какие-то вершины цвета 2 не перекрашены и

потому соседствуют с вершинами цвета 1. Затем, вершины

цвета 3, которые не соседствуют с вершинами цвета 2, не

перекрашенными в цвет 1, перекрасим в цвет 2, и т. д.

вплоть до последнего цвета. На каждом шаге получается

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

каждого цвета останется неперекрашенной.

После этого рассмотрим какую-либо вершину цвета k.

Она не перекрашена, и потому соседствует с вершиной

цвета k −1. Эта вершина тоже не перекрашена, так как

иначе ее первоначальный цвет был бы k, и она вначале

соседствовала бы с вершиной того же цвета, что невоз-

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

с вершиной цвета k −2, и т. д. Продолжая этот процесс,

построим путь длины k из вершин k цветов, которые не

были перекрашены.

К о м м е н т а р и й. Заметим, что мы доказали более сильное утвер-

ждение: найдется путь, вдоль которого встречаются вершины всех k

цветов по одному разу в заданном порядке.

252 Решения. 1999 год. 11 класс

6. П е р в ы й с п о с о б. Пусть p — простой делитель

числа l. Поскольку n

= (1 + n

)

−1, то n

делится на

(1 + n

)

−1 (см. факт 8). Но, в силу бинома Ньютона (см.

комментарий),

(1 + n

)

−1 = n

· p + n

p(p −1)

+ n

· r,

где r — неотрицательное целое число. Разделив это выра-

жение на n

, получим, что n

делится на

p + n

p(p −1)

+ n

· r.

Если n не делится на p, то это выражение взаимно просто

с n, и n

не может на него делиться (см. факт 5). Значит,

p — делитель числа n (см. факт 9). Тогда

1 + n

p −1

· r

— натуральное число, большее единицы. Если k > 1 или p

нечетно, то второе слагаемое делится на n (третье слага-

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

с n, так что n

не может на нее делиться. Полученное

противоречие показывает, что k = 1 и p = 2. Поэтому 2 —

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

вид 2

(см. факт 10).

Воспользуемся снова биномом Ньютона:

= (1 + n

)

−1 = (1 + n)

−1 = ln +

l(l −1)

+ . . . + n

В правой части все члены, начиная со второго, делятся

на n

. Из этого, поскольку m > 1, следует, что l делится

на n. Значит, n, как и l, является степенью двойки.

Так как 2 |l, (1 + n)

−1 делится на (1 + n)

−1 = n(n+ 2).

Так как n

представляет собой степень двойки, n + 2 так-

же является степенью двойки. Таким образом, n и n + 2 —

степени двойки, следовательно, n = 2.

Если l > 4, то (1 + n)

−1 делится на (1 + n)

−1= 80, и не

может быть степенью двойки. Значит, l = 2, откуда m = 3.

И д е я д р у г о г о с п о с о б а. Так как 1 + n

делится

на 1 + n

, то (при n 6= 1) m делится на k (см. факт 8).

Поэтому, заменяя n

на n, а m/k на m, сводим все к

случаю k = 1.

Решения. 1999 год. 11 класс 253

Пусть n делится на p

, но не на p

t+1

, где p — простое

число (t > 0). Пусть p

— наибольшая степень p, которая

делит l. Теперь запишем бином Ньютона:

ln + C

+ . . . + n

= n

Пусть p 6= 2 или t > 1. Можно показать, что правая часть

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

t+s+1

. Полу-

ченное противоречие показывает, что n = 2.

К о м м е н т а р и й. Хорошо известны формулы для (a + b)

(a + b)

. Оказывается, что существует аналогичная формула для (a + b)

при любом n. Чтобы выписать эту формулу, нам понадобится понятие

числа сочетаний. Числом сочетаний из n элементов по k (обознача-

ется C

, читается «це из эн по ка») называется количество способов

выбрать k предметов из n различных предметов. При этом выборки,

отличающиеся порядком предметов, считаются одинаковыми. Иначе

говоря, C

— это число k-элементных подмножеств в n-элементном

множестве.

Справедлива формула

k!(n − k)!

n(n − 1)(n − 2) . . . (n − k + 1)

k(k − 1) · . . . · 2 · 1

Теперь мы можем привести формулу бинома Ньютона:

(a + b)

k=0

n−k

= a

+ C

n−1

b + C

n−2

+ .. . + C

n−2

+ C

n−1

+ b

7. Рассмотрим окружность длины 1 как отрезок [0; 1] с

отождествленными концами (см. комментарий к решению

задачи 6 для 10 класса олимпиады 1997 г.). Тогда дроб-

ную часть f

числа lg(2

) = m · lg 2 можно рассматривать

как точку этой окружности. Рассмотрим на окружности

точки

0, lg 2, ..., lg 9

и 9 полуинтервалов, на которые они разбивают окруж-

ность. Обозначим эти полуинтервалы I

= [0; lg 2), ...

..., I

= [lg 9; 0).

Первая цифра числа 2

равна s тогда и только тогда,

когда f

попадает на интервал I

. Например, если 2

начинается с 7, то

7 · 10

6 2

< 8 · 10

254 Решения. 1999 год. 11 класс

для некоторого натурального l. Дробная часть числа m·lg2

равна m · lg 2 −l, и она находится между lg 7 и lg 8.

Предположим, что первые цифры чисел 2

повторяют-

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

· lg 2 и

n+k

· lg 2 попадают в один и тот же полуинтервал I

для

любого n > n

, где n

— длина предпериода (см. факт 4).

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

лов — первый, и его длина равна lg 2 < 1/3.

◦

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

положительных чисел A и B; эти дробные части различны

и не являются диаметрально противоположными точками

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

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

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

дробные части чисел 2A и 2B, равна 2x.

◦

. Пусть теперь дробные части чисел A и B лежат

в одном интервале I

; рассмотрим пары 2A и 2B, 4A и

4B и т. д. Из сказанного выше следует, что длина мень-

шей дуги, соединяющей дробные части пары, удваивается

до тех пор, пока она не станет больше, либо равна 1/2.

Значит, на некотором шаге одна из дуг, соединяющих

дробные части пары, станет больше 1/3, но меньше 2/3.

Тогда эти дробные части принадлежат разным интервалам

окружности.

◦

. Рассмотрим числа A = 2

lg 2 и B = 2

lg 2. Эти

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

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

как число lg 2 иррационально (см. ниже). Значит, к этим

числам можно применить пункт 2

◦

, и мы получаем про-

тиворечие с предположением о периодичности.

Иррациональность числа lg 2 можно доказать от про-

тивного: если lg 2 = p/q, то 2

= 10

, что, очевидно, невоз-

можно.

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

◦

. Фактически мы доказали, что если не яв-

ляется рациональной степенью десятки, то последовательность первых

цифр чисел

непериодична.

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

первых цифр

периодична и не является рациональной степенью

десятки.

Решения. 2000 год. 8 класс 255

Например, пусть

lg = 0,101001000100001. ..

(число нулей между последовательными единицами увеличивается).

Эта дробь не является периодической, так что не является ра-

циональной степенью десятки (см. факт 13). С другой стороны,

{10

log } < 0,11 < lg 2 при любом n. Значит, первая цифра числа

при всех n равна 1!

◦

. Задачи 4 для 11 класса и 5 для 10 класса являются задача-

ми про сжимающие отображения отрезка в себя (см. комментарии к

задаче для 10 класса). Данная задача есть задача о растягивающих

отображениях.

2000 год

8 к л а с с

1. Перенесем 2000x в правую часть, а y

— в левую.

Получим:

−y

= 2000x −2000y.

Разложим левую часть по формуле разности квадратов:

(x −y)(x + y) = 2000(x −y).

Так как x 6= y, можно сократить на x −y. Отсюда x + y =

= 2000.

2. Идея решения задачи: Партия Любителей Математи-

ки (ПЛМ) получит наибольшее количество мест в парла-

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

шедшие (т. е. набравшие не более 5 % голосов) партии,

максимально.

Если 10 партий наберут ровно по 5 % голосов, а две,

включая Партию любителей математики (ПЛМ), — по

25 %, то в парламент пройдут только две партии. Каждая

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

Докажем, что большее число мест ПЛМ получить не

может. Если бы в парламент не прошли 11 партий, то

они вместе набрали бы не более 55 % голосов, но 55 % +

+ 25 % < 100 %. Значит, не прошли в парламент максимум

10 партий, и они набрали в сумме не более 50 % голосов.

256 Решения. 2000 год. 8 класс

Поэтому партии, прошедшие в парламент, набрали не ме-

нее 50 % голосов. Так как ПЛМ набрала 25 % голосов,

она получила не более половины мест в парламенте, т. е.

не более 50 мест.

3. Пусть m > n. Продолжим боковые стороны трапеции

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

Рис. 114

ся треугольника на m равных частей.

Через точки деления проведем пря-

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

ника (рис. 114). Получится разбие-

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

треугольники. Верхнее основание тра-

пеции является одной из проведенных

линий, так как его длина выражает-

ся целым числом сантиметров. Таким

образом, мы получили разбиение тра-

пеции на равные треугольники.

4. Обозначим CM = a (рис. 115). Пусть K — точка, сим-

метричная M относительно точки A. Тогда KM = MB =

= ME = 2a. Поэтому треугольник KBE прямоугольный (см.

K M

a a a a

Рис. 115

факт 14): KB ⊥BE.

Четырехугольник DKBM — парал-

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

делятся в точке пересечения попо-

лам. Значит, DM kKB. Следователь-

но, DM ⊥BE.

5. Будем кодировать расположе-

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

цифр столько, сколько в колоде карт.

Это число строится по следующему

правилу: на k-м месте справа стоит 1,

если k-я карта снизу лежит рубашкой вверх, и 2, если эта

карта лежит рубашкой вниз. Например, колода, в которой

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

сятичная запись которого состоит из одних двоек.

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

это число уменьшается. Действительно, сравним полу-

Решения. 2000 год. 8 класс 257

ченное число с предыдущим. Среди всех цифр, которые

изменились, выберем самую левую, т. е. найдем самый

старший изменившийся разряд. Очевидно, в этом разряде

цифра 2 сменилась на 1. Но это означает, что число

уменьшилось.

Поскольку количество n-значных чисел из единиц и

двоек конечно, число не может уменьшаться «до бесконеч-

ности» — в конце концов мы получим число, состоящее из

одних единиц, что соответствует расположению всех карт

рубашкой вверх. См. также факт 2.

6. На рис. 116 приведено расположение 16 коней,

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

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

в черный и белый цвета, как показано на рис. 116.

Рис. 116

Рис. 117

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

женных на черных клетках, равно ко-

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

лых клетках. Действительно, если соеди-

нить отрезками бьющих друг друга коней,

то каждый отрезок будет соединять бе-

лую клетку с черной. С другой стороны,

из каждой клетки выходит два отрезка.

Значит, число отрезков равно удвоенному

числу коней, стоящих на белых клетках,

и удвоенному числу коней, стоящих на

черных клетках. Поэтому число коней,

стоящих на белых клетках, равно числу

коней, стоящих на черных клетках.

Белых клеток всего 12, а черных — 13.

Значит, если число пустых белых клеток

равно n, то число пустых черных клеток

равно n + 1, и нам достаточно доказать,

что n > 4 (тогда по крайней мере 4 + (4 + 1) = 9 клеток

пусты).

При любом оптимальном расположении коней цен-

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

клеток, которые бьет конь, стоящий на центральном поле,

ровно шесть пустых белых. Отсюда n > 6, и число коней

не превосходит 25 −6 −(6 + 1) = 12.

258 Решения. 2000 год. 9 класс

Рассмотрим клетку, обозначенную на рисунке 117 циф-

рой 1. Если на этой клетке стоит конь, то 4 из 6 черных

клеток, которые она бьет, пусты. По доказанному цен-

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

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

считать, что эта клетка пуста. Аналогично, можно счи-

тать, что клетки 2, 3 и 4 пусты. Но тогда n > 4, что и

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

9 к л а с с

1. Умножим обе части уравнения на (x + 1) −(x −1) = 2.

Тогда оно преобразуется к виду

(x + 1)

−(x −1)

= 0. (1)

Это следует из формулы

−b

= (a −b)(a

n−1

+ a

n−2

b + ... + ab

n−2

+ b

n−1

примененной к a = x + 1, b = x −1, n = 64.

Уравнение (1) легко решается:

(x + 1)

= (x −1)

⇔ |x + 1|= |x −1|,

поскольку x + 1 6= x −1, получаем x + 1 = −(x −1), откуда

x = 0.

2. Разобьем данные 23 числа на семь групп из стоящих

подряд чисел: три группы по пять чисел и четыре группы

по два числа (в каком порядке эти группы расположены —

неважно). Каждую группу заключим в скобки, а между

группами расставим знаки умножения. Если расставить

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

ций в группе из двух чисел делился на 2, а в группе из

пяти чисел — на 5, то все выражение будет делиться на

· 5

= 2000.

Покажем, что такая расстановка знаков в группах су-

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

двух чисел. Если числа в группе из двух чисел разной

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

жения, если одинаковой четности — сложения. Результат,

очевидно, будет делиться на 2 (см. факт 23).

Решения. 2000 год. 9 класс 259

Теперь рассмотрим группу чисел a

, a

, иду-

щих именно в таком порядке. Выпишем остатки от деле-

ния на 5 следующих пяти сумм (см. факт 7):

, a

Если один из остатков равен 0, то соответствующая сумма

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

жения между числами, входящими в эту сумму, саму сум-

му (если требуется) заключить в скобки, а все оставшиеся

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

умножения. Если же ни один из остатков нулю не равен,

то, согласно принципу Дирихле (см. факт 1), среди них

найдутся два одинаковых остатка (так как сумм — пять,

а ненулевых остатков — всего четыре). Пусть, например,

суммы a

+ . . . + a

и a

+ . . . + a

(i < j) дают одинаковые

остатки при делении на 5. Тогда их разность, представ-

ляющая собой сумму подряд стоящих чисел a

i+1

+ . . . + a

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

заключаем эту сумму в скобки, а оставшиеся позиции

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

(1 + 2 + 3 + 4) · 3 = 30, 2 · (1 + 4) · 7 · 1 = 70.

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

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

К о м м е н т а р и й. Следующая задача является классической:

в строку выписаны n целых чисел, тогда одно из них или сумма

нескольких подряд идущих делится на n.

| {z }

Рис. 118

3. 1

◦

. Пусть O — центр окруж-

ности в условии задачи. Дока-

жем, что для точки C выполняет-

ся равенство OC

= 2R

−OA

, где

O — центр данной окружности,

R — ее радиус. Введем обозначе-

ния, как показано на рис. 118.

Отрезок OC является гипотену-

зой в прямоугольном треугольни-

ке с катетами x и y; по теореме

260 Решения. 2000 год. 9 класс

Пифагора получаем:

= x

+ y

= (x

+ t

) + (y

+ z

) −(z

+ t

) = 2R

−OA

+ t

= y

+ z

= R

, z

+ t

= OA

по теореме Пифагора).

Отсюда следует, что расстояние от точки C до точки O

постоянно и равно

√

−OA

, значит, искомым ГМТ яв-

ляется окружность с центром O и радиусом

√

−OA

| {z }

Рис. 119

◦

. Обратно, пусть точка C

такова, что OC

= 2R

−OA

Докажем, что найдется прямо-

угольник ABCD, вершины B и

D которого лежат на исходной

окружности.

Построим окружность на

отрезке AC как на диамет-

ре (рис. 119). Она пересе-

чет исходную окружность в

двух точках. Обозначим одну

из этих точек через B. То-

гда ∠ABC = 90

◦

(см. факт 14).

Достроим прямоугольный тре-

угольник ABC до прямоуголь-

ника ABCD. Нам достаточно доказать, что точка D лежит

на окружности. В обозначениях рисунка

= y

+ z

= (x

+ y

) + (z

+ t

) −(x

+ t

) =

= OC

+ OA

−R

= (2R

−OA

) + OA

−R

= R

что и требовалось доказать.

4. Пусть у Лёши есть много доминошек 1 ×2. Если он

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

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

z t

x y

Рис. 120

крывались ровно по одной клетке

(рис. 120, слева), то, вычтя из сум-

мы чисел под одной доминошкой (x + y)

сумму чисел под другой (y + z), он узна-

ет разность x −z чисел, накрытых ровно

одной доминошкой (эти числа записаны

в клетках одного цвета). Пусть Лёша положит третью до-

миношку так, чтобы одна ее половина накрывала число z,