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

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

Решения. 1995 год. 10 класс 161

Число p входит в знаменатель в степени k(a) + k(b). Зна-

чит, числитель делится на p

k(a)+k(b)

. Покажем, что это не

так. Число p входит в a

c в степени 2k(a) > k(a) + k(b), в

a — в степени k(a) + 2k(b) > k(a) + k(b), а в c

b — в степе-

ни k(b) < k(a) + k(b). Значит, a

c + b

a делится на p

k(a)+k(b)

а c

b — не делится на p

k(a)+k(b)

. Поэтому сумма этих чисел

не делится на p

k(a)+k(b)

— противоречие (см. факт 5).

В т о р о й с п о с о б. Введем обозначения: x =

, y =

z =

. Тогда xyz = 1 и

xy + yz + zx =

xy + yz + zx

xyz

— целое число. Рассмотрим многочлен

P(t) = t

−(x + y + z)t

+ (xy + yz + zx)t −xyz.

По доказанному, все коэффициенты этого многочлена

целые. Кроме того, коэффициент при старшем члене t

равен единице. Значит, все рациональные корни этого

многочлена — целые (см. комментарий). Согласно обратной

теореме Виета, x, y и z — корни этого многочлена (см.

факт 20). Значит, x, y и z — целые числа, но xyz = 1,

так что x = ±1, y = ±1, z = ±1. Это равносильно тому, что

|a|= |b|= |c|.

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

Пусть f(x) = a

+ a

x + . .. + a

— многочлен с целыми коэффици-

ентами.

Т е о р е м а. Пусть

— несократимая дробь, которая является

корнем многочлена f(x). Тогда p |a

, q |a

Н а б р о с о к д о к а з а т е л ь с т в а. Докажем первое утверждение.

Условие f

“

”

= 0 можно переписать так:

+ a

n−1

+ .. . + a

= 0. (1)

Пусть l — простое число. В силу факта 10 достаточно доказать, что

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

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

числа a

на простые множители. Пусть это не так, т. е. найдется

такое x, что p делится на l

, а a

не делится на l

. Так как дробь

несократима, q не делится на l, поэтому в левой части равенства (1)

первый член не делится на l

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

(см. факт 5).

162 Решения. 1995 год. 10 класс

С л е д с т в и е. Если a

= 1, то любой рациональный корень много-

члена f (x) является целым.

6. П е р в ы й с п о с о б. Заметим, что результат нажа-

тия нескольких кнопок не зависит от порядка их нажа-

тия. Проведем индукцию по числу лампочек на табло (см.

факт 24). При n = 1 утверждение верно (так как найдется

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

точности с этой лампочкой).

Пусть утверждение доказано для n −1 лампочек. Дока-

жем утверждение для n лампочек. Рассмотрим i-ю лам-

почку. По предположению индукции, мы можем погасить

остальные n −1 лампочек. Обозначим необходимый для

этого набор кнопок через S

. Если погасла и i-я, то ин-

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

при любом i нажатие на кнопки набора S

приводит к

следующей ситуации: горит только i-я лампочка.

Что произойдет, если при некотором состоянии табло

нажать сначала кнопки из набора S

, а потом кнопки

из набора S

? При этом изменится состояние ровно двух

лампочек: лампочек с номерами i и j (подумайте, поче-

му). Итак, мы научились менять состояние у любой пары

лампочек.

По условию найдется кнопка T, соединенная с нечет-

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

ной, соединенной с кнопкой T. Затем нажмем T. Тогда

будет гореть четное число лампочек. Погасим их парами.

В т о р о й с п о с о б (с использованием линейной алге-

бры). Занумеруем лампочки числами от 1 до n. Поставим

в соответствие состоянию табло строчку

x = (x

, . . . , x

где x

= 1, если i-я лампочка горит, и x

= 0 — если не

горит. Такие наборы — это векторы n-мерного векторного

пространства над полем из двух элементов (см. факт 25

и [72], гл. 1 и 2).

Каждой кнопке мы тоже поставим в соответствие век-

тор a = (a

, . . . , a

), где a

= 1, если i-я лампочка соединена

с кнопкой, и a

= 0, если не соединена. Ясно, что нажатие

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

Решения. 1995 год. 11 класс 163

a + x. Таким образом, наша задача состоит в том, чтобы

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

ждают все векторное пространство.

Набору лампочек мы поставим в соответствие линей-

ный функционал:

, . . . , x

) 7→

где сумма берется по всем i таким, что i-я лампочка вхо-

дит в набор.

Все линейные функционалы получаются таким обра-

зом. Функционал обращается в нуль на векторе, соответ-

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

соединена с четным числом лампочек из этого набора.

Значит, условие задачи переводится на язык линейной

алгебры следующим образом: ни один функционал не об-

ращается в нуль на всех кнопках. Но это равносильно

тому, что система векторов, соответствующих кнопкам,

полна! Такую равносильность часто называют альтернати-

вой Фредгольма.

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

что любая кнопка меняет состояние только четного числа лампочек

из этого набора. В условии задачи сказано, что таких инвариантов

нет. Рассмотрим более общую ситуацию: пусть инварианты есть. То-

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

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

ки, очевидно, погасить не удастся.

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

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

то все лампочки можно погасить. Данная задача является частным

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

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

сами).

11 к л а с с

1. Так как модуль суммы не превосходит суммы моду-

лей (см. комментарий), имеем:

|x + y −z|+ |x −y + z|> |(x + y −z) + (x −y + z) |= 2|x |.

Аналогично получаются неравенства

|x −y + z|+ |−x + y + z|> 2|z|,

|−x + y + z|+ |x + y −z|> 2|y|.

164 Решения. 1995 год. 11 класс

Сложив все три неравенства и разделив получившееся

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

К о м м е н т а р и й. Неравенство |x + y |6 |x|+ |y | можно доказать

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

части неравенства неотрицательны, их можно возвести в квадрат, и

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

что

|x + y|

6 (|x |+ |y|)

Пользуясь тем, что для любого a выполняется равенство |a|

= a

раскрывая скобки, приходим к неравенству:

+ 2xy + y

6 x

+ 2|x ||y|+ y

Но это очевидно.

Заметим, также, что неравенство верно и для векторов. Доказа-

тельство сохраняется с небольшими изменениями. На плоскости это

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

2. a) Покрасим ребра нижнего основания по кругу: 1-е

в первый цвет, 2-е во второй, 3-е в третий, 4-е опять

в первый и т. д. (1995 делится на 3, поэтому цепочка

замкнется). Каждое ребро верхнего основания покрасим

Рис. 65

в цвет ребра нижнего основания, на-

ходящегося под ним. Каждое боковое

ребро, выходящее из вершины, где

сходятся два цвета, покрасим в недо-

стающий цвет (рис. 65). Ясно, что

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

все 3 цвета.

б) От противного, пусть призма по-

крашена требуемым образом; тогда в

основании есть 3 ребра всех трех цве-

тов, идущие подряд (иначе основание

раскрашено с периодом 2 и не может быть покрашено

в три цвета). Рассмотрим такую тройку и занумеруем

цвета в ней по часовой стрелке. Несложно проверить, что

раскраска этого участка однозначно определяет раскраску

участка, находящегося над ним, соответствующих боко-

вых ребер и следующих ребер основания (см. рис. 65). Мы

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

имеет цвет 1.

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

основания имеет цвет 2, и т. д. Таким образом, нижняя

Решения. 1995 год. 11 класс 165

грань окажется покрашенной с периодом 3. Но 1996 не

делится на 3 — противоречие.

3. П е р в ы й с п о с о б. Продлим медиану AA

на ее

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

(рис. 66). Напомним, что биссектриса делит основание

Рис. 66

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

циональные сторонам:

Из обобщенной теоремы Фалеса

следует (см. комментарий), что K

делит AD в такой же пропорции:

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

непривычной конфигурации). Значит, точка K делит AD

в том же отношении, что и биссектриса угла ACD (по

свойству биссектрисы треугольника). Из этого следует, что

CK и есть биссектриса! Итак, AA

и CK перпендикуляр-

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

параллельных прямых.

Последнее свойство доказывается так. Пусть R — точка

пересечения этих биссектрис. Тогда

∠RAC + ∠RCA =

(∠BAC + ∠DCA) =

· 180

◦

= 90

◦

В т о р о й с п о с о б. Используем замечательное свой-

ство трапеции (см. комментарий): середины оснований,

Рис. 67

точка пересечения диагоналей и

точка пересечения прямых, содер-

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

на одной прямой.

Продолжим отрезок CK до пе-

ресечения с прямой AB в точке

(рис. 67). Из того, что в тра-

пеции AKA

C середина B

основа-

ния AC, точка пересечения диа-

гоналей R и точка пересечения

166 Решения. 1995 год. 11 класс

продолжений боковых сторон A

лежат на одной пря-

мой, следует, что R принадлежит средней линии A

треугольника ABC. Поэтому CR = RC

. Таким образом, в

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

отрезок AR является медианой и бис-

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

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

◦

. О б о б щ е н н а я т е о р е м а Ф а л е с а.

Пусть на прямой k выбраны точки A

, A

и A

, а на прямой l —

точки B

, B

и B

, причем A

. Тогда

Для доказательства проведем прямую, параллельную прямой l че-

рез точку A

. Пусть она пересекает прямые A

и A

в точках

и C

соответственно. Тогда A

— параллелограмм, поэтому

= B

. Аналоги чно, A

= B

. Остает ся воспользоваться подо-

бием треугольников A

и A

◦

. З а м е ч а т е л ь н о е с в о й с т в о т р а п е ц и и. Пусть M и N —

середины оснований трапеции, P — точка пересечения диагоналей, Q —

точка пересечения продолжений боковых сторон. Замечательное свой-

ство трапеции заключается в том, что эти четыре точки лежат на

одной прямой. Это свойство проще всего доказать с помощью гомоте-

тии. Существует гомотетия с центром P, переводящая одно основание

трапеции в другое. Поэтому точка P лежит на прямой MN. Кроме

того, существует гомотетия с центром Q, переводящая одно основание

трапеции в другое. Поэтому точка Q тоже лежит на прямой MN.

4. Докажем по индукции (см. факт 24), что любой от-

резок можно разбить на белые и черные отрезки так, что

интегралы любого многочлена степени не выше n по чер-

ным и белым отрезкам равны.

Б а з а и н д у к ц и и (n = 0): многочлен степени нуль —

это константа. Интеграл константы по любому отрезку ра-

вен произведению этой константы на длину отрезка. Зна-

чит, достаточно разбить отрезок пополам.

Ш а г и н д у к ц и и. Рассмотрим отрезок [a; b]. Пусть

c — его середина. По предположению индукции, отрезок

[a; c] можно разбить на белые и черные отрезки так, что

интегралы от любого многочлена степени не выше n −1 по

черным и белым отрезкам равны. Обозначим черные от-

резки B

, . . . , B

, а белые отрезки — W

, . . . , W

. Интеграл

функции f(x) по отрезку B

будем обозначать через

]

f(x) dx.

Решения. 1995 год. 11 класс 167

Аналогично обозначим интеграл f(x) по W

. Перенесем

отрезок B

на c вправо и покрасим получившийся отре-

зок в белый цвет. Обозначим его через W

s+i

. Аналогич-

но поступим с отрезком W

: перенесем его на c вправо

и покрасим получившийся отрезок B

r+i

в черный цвет.

Ясно, что отрезки B

, . . . , B

r+s

и W

, . . . , W

r+s

образуют

разбиение отрезка [a; b]. Случаи n = 1 и n = 2 изображены

на рис. 68. Мы утверждаем, что получившееся разбиение

n = 1

a c

n = 2

a c

Рис. 68

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

не выше n. Для доказательства заметим, сначала, что

]

r+i

f(x) dx =

]

f(y + c) dy,

Это равенство следует из замены переменной (см. факт 28):

y = x −c, dy = dx.

Пользуясь тем, что интеграл от разности функций равен

разности интегралов, перепишем равенство в виде:

]

r+i

f(x) dx −

]

f(x) dx =

]

(f(x + c) −f(x)) dx.

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

ков W

и B

s+i

. Складывая все такие равенства, получим:

r+s

i=1

]

f(x) dx −

r+s

i=1

]

f(x) dx =

i=1

]

(f(x + c) −f(x)) dx −

i=1

]

(f(x + c) −f(x)) dx.

Пусть теперь f(x) — многочлен степени не выше n, то-

гда f(x + c) −f(x) — многочлен степени не выше n −1 (см.

факт 22), так что, по предположению индукции, правая

168 Решения. 1995 год. 11 класс

часть последнего равенства равна нулю. Значит, и левая

часть равна нулю, и шаг индукции доказан.

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

◦

. Разобьем отрезок [−1; 1] на отрезки длины

−n−1

. Пометим отрезок знаком «+», если он покрашен в черный цвет,

и знаком «−», если — в белый. Соответствующая последовательность из

плюсов и минусов является n-м членом последовательности Морса:

+, +−, +−−+, +−−+−++−, +−−+−++−−++−+−−+, .. .

(От куска A переходим к куску AA

, где A

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

всех знаков на противоположные.) Можно построить n-й член этой

последовательности так: для каждого k = 0, . .. , 2

−1 взять сумму его

двоичных цифр (см. факт 12) и записать на n-м месте + или − в

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

бинация символов не повторится 3 раза подряд.

◦

. Выражение

f (x) = f(x + c) −f(x)

называется разностной производной функции f с шагом c. Разност-

ное дифференцирование использовали в докомпьютерные времена для

построения таблиц различных функций, например, приближали sin x

многочленом степени n, а затем заполняли таблицу, в которой в k-м

столбце записана k-я разностная производная. Так как n-я производ-

ная — константа, n-й столбец заполнить легко. Если же заполнен k-й

столбец, то нетрудно заполнить и (k −1)-й. Таким образом, используя

лишь операцию сложения, можно заполнить первый столбец, т. е.

получить таблицу синусов.

5. Пример, когда период последовательности A состоит

из одной единицы и 1994 нулей, а B — непериодическая

последовательность из нулей и единиц, в которой все еди-

ницы расположены на расстоянии, не меньшем 1994 друг

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

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

B (см. факт 4).

Докажем, что если любой кусок длины 1995 последо-

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

периодична с периодом длины 1995.

Докажем сначала, что 1995 — длина одного из перио-

дов. Пусть это не так, тогда в последовательности B най-

дется кусок длины 1996, у которого первый и последний

символы не совпадают:

B = . . . x . . . . . . . ..

| {z }

1994 символа

y...,

Решения. 1995 год. 11 класс 169

где x и y — разные символы. Обозначим участок последо-

вательности между x и y через Z. Пусть символ x встреча-

ется в Z ровно k раз. Рассмотрим две последовательности

длины 1995: xZ и Zy. По предположению, каждая из них

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

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

сти A. Поэтому символ x должен встречаться в каждой из

этих последовательностей одинаковое число раз. С другой

стороны, в последовательности xZ он встречается k + 1 раз,

а в последовательности Zy — k раз. Противоречие.

Осталось доказать, что 1995 — длина минимального пе-

риода. Если бы длина периода последовательности B была

меньше, чем 1995, то некоторый кусок последовательно-

сти B длины 1995 распадался бы на несколько одина-

ковых кусков. По условию этот кусок содержится в A.

Ясно, что в этом случае длина (минимального) периода

последовательности A также была бы меньше, чем 1995.

К о м м е н т а р и й. Из доказательства следует, что если n — длина

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

куска длины n −1 находятся на расстоянии, кратном n.

6. Возьмем

n = 3

−2

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

любом натуральном t.

В силу факта 8 достаточно доказать, что n −1 делится

на 2

, т. е. что 3

−1 делится на 2

(поскольку 2

делится

на 2

Докажем по индукции (см. факт 24), что при всех на-

туральных t число 3

−1 дел ится на 2

t+2

. При t = 1 утвер-

ждение очевидно. Пусть оно верно при некотором t. Тогда

для t + 1 имеем:

t+1

−1 = (3

+ 1)(3

−1).

Первый множитель делится на 2, второй — на 2

t+2

. Зна-

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

t+3

, и утверждение дока-

зано.

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

◦

. Малая теорема Ферма утверждает, что если

p — простое число и a не делится на p, то a

p−1

−1 делится на p, см.,

170 Решения. 1996 год. 8 класс

например, [29], гл. 3, § 6. Из этой теоремы следует, что при простом

n 6= 2, 3 число 3

n−1

−2

n−1

делится на n.

◦

. Известно, что множество составных n таких, что 2

n−1

−1 делит-

ся на n, бесконечно.

7. Можно сделать пространственный «крест» из 6 «ка-

рандашей» — длинных тонких параллелепипедов, примы-

кающих снаружи к граням единичного куба (куб нужен

только для объяснения конструкции). Карандаши лежат

по одному на гранях куба симметрично относительно цен-

тра куба, причем центр грани карандаша совпадает с цен-

тром одной из граней куба.

Рис. 69

Каждая пара параллельных ка-

рандашей параллельна одной из

осей координат и загораживает вер-

шины другой пары, поэтому из цен-

тра куба вершин карандашей не

видно (рис. 69).

Остается перекинуть «мосты»

между карандашами и получить

многогранник. При этом образуют-

ся новые вершины, но они будут

находиться рядом с вершинами

карандашей, так что их тоже не

будет видно.

К о м м е н т а р и й. На плоскости такой пример невозможен: для

любого многоугольника из любой точки вне него видна хотя бы од-

на вершина (но, возможно, никакая сторона не видна полностью).

Для многогранника можно гарантировать, что хотя бы одна вершина

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

гранник.

1996 год

8 к л а с с

1. Приведем левую часть к общему знаменателю: a +

+ b

. Аналогично поступим с правой частью. По-

лучим равенство:

+ b