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

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

Решения. 2000 год. 10 класс 271

P(x)

Q(x)

на

P(x + r)

Q(x + r)

для некоторого натурального r, что можно

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

лителе и знаменателе.) Если в таком виде представляется

последовательность {n}, то в таком виде представляет-

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

√

Но из равенства

P(n +

√

Q(n +

√

2 следует, что отношение

старших коэффициентов многочленов P и Q равно

√

что невозможно, так как

√

2 — иррациональное число.

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

6. а) Пусть Гриша назовет два набора карт: свой и на-

бор из трех карт, которых у него нет, и скажет: «У меня

один из этих наборов». При этом Лёша узнает Гришины

карты (так как Гришин набор не пересекается с Лёшиным

набором, а второй названный Гришей набор — обязательно

пересекается).

Теперь возможны две ситуации: если второй из набо-

ров, названных Гришей, не совпадает с Лёшиным, то Лё-

ша должен назвать набор своих карт и набор Гришиных

карт и сказать: «У меня один из этих наборов».

Если второй из наборов, названных Гришей, совпадает

с Лёшиным, то Лёша должен поступить иначе (чтобы Ко-

ля не узнал спрятанной карты): он называет свой набор

и любые три карты, которых у него нет (но не Гришин

набор).

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

же ничего не ясно. Действительно, названо три набора

карт: A, B и C. Гриша сказал: «У меня либо A, либо B»,

Лёша сказал: «У меня либо A, либо C» (наборы B и C

пересекаются по двум картам, а остальные пары набо-

ров не пересекаются). Это означает, что либо у Гриши

набор A, а у Лёши — C, либо у Гриши — B, а у Лёши — A.

Конечно, эти расклады различны, и даже закрытую карту

определить нельзя.

б) Заметим, что предыдущий способ не работает: зная

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

карты числами от 0 до 6. Пусть Гриша и Лёша по очереди

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

272 Решения. 2000 год. 11 класс

на 7 (см. факт 7). Тогда они узн ´ают расклад: каждый из

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

и найти остаток, противоположный этой общей сумме по

модулю 7 (т. е. такой, который при прибавлении к этой

сумме дает число, делящееся на 7). Это и будет номер

закрытой карты. После этого восстановление расклада не

составляет труда. Проверим, что Коля ничего не узнал.

Рассмотрим карту с номером s. Покажем, что она могла

попасть к Грише, если он назвал сумму a. Для этого надо

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

a −s (по модулю 7). Легко видеть (проверьте!), что су-

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

a −s. Одна пара может быть «испорчена» тем, что туда

входит карта с номером s. Еще одна пара может быть

испорчена тем, что туда входит Колина карта, но как

минимум одна пара остается. Ею мы и дополним набор

Гриши. Такие же рассуждения показывают, что любая

карта могла оказаться и у Лёши.

К о м м е н т а р и й. Заметим, что метод пункта «б» не работает в

пункте «а» — Коля узнает закрытую карту.

11 к л а с с

1. Пусть a = 2000m + n, b = 2000n + m, d — наибольший

общий делитель a и b. Тогда d делит также числа

2000a −b = (2000

−1)m и 2000b −a = (2000

−1)n.

Поскольку m и n взаимно просты, то d является также

делителем числа 2000

−1 (см. комментарий). С дру-

гой стороны, при m = 2000

−2000 −1, n = 1, получаем

a = (2000

−1)(2000 −1), b = 2000

−1 = d.

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

m и n взаимно просты, то НОД(dm, dn) = d. Это следует из более

общего утверждения:

НОД(dx, dy) = d НОД(x, y).

Дадим набросок доказательства. Пусть p

, .. ., p

— все простые де-

лители чисел x, y и d. Запишем разложения этих чисел на простые

множители:

x = p

.. . p

y = p

.. . p

d = p

.. . p

Решения. 2000 год. 11 класс 273

(Некоторые из чисел k

, l

и m

могут быть равны нулю. Сравните с

комментарием к задаче 4 для 9 класса олимпиады 1995 г.)

Обозначим через min(p, q) меньшее из чисел p и q. Тогда

НОД(x, y) = p

min(k

)

min(k

)

.. . p

min(k

)

Аналогично,

НОД(dx, dy) = p

min(m

)

min(m

)

.. . p

min(m

)

Остается заметить, что для любого i выполняется равенство

min(m

+ k

, m

+ l

) = m

+ min(k

, l

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

том: для любых целых x и y найдутся такие целые a и b, что

ax + by = НОД(x, y), см. например [30].

2. П е р в ы й с п о с о б. Так как интеграл от разно-

сти функций равен разности интегралов (см. факт 28),

получаем:

]

(|sin 1999x |−|sin 2000x|) dx =

]

|sin 1999x |dx −

]

|sin 2000x |dx. (1)

Мы покажем, что

]

|sin kx |dx = 2

при любом натуральном k. Из этого будет следовать, что

правая часть (1) равна нулю.

Функция |sin kx | периодична с периодом /k. Значит,

]

|sin kx |dx = k

]

|sin kx |dx = k

]

sin kx dx. (2)

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

y = kx (см. факт 28):

]

sin kx dx =

]

sin y

Значит, интеграл (2) равен 2 при любом k, и наше утвер-

ждение доказано.

274 Решения. 2000 год. 11 класс

В т о р о й с п о с о б (набросок). График функции |sin kx|

на отрезке [0; ] состоит из k одинаковых «шапочек»

(рис. 126), которые получаются из графика функции sin x

y = sin |kx|

Рис. 126

на том же отрезке путем сжа-

тия к оси ординат в k раз.

При этом площадь под графи-

ком также уменьшается в k раз.

Как следствие, площадь под k

«шапочками» одинакова при лю-

бом k. Поэтому искомый инте-

грал равен нулю.

3. Пусть X — середина KB (рис. 127, а). Тогда ∠KMX =

∠KMB = ∠KAB = ∠KDC (в предпоследнем равенстве мы

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

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

еся на равные дуги, равны). Ясно, что MX ⊥BD, значит,

KM ⊥CD. При этом ON ⊥CD, так что ON kKM. Аналогич-

но, OM kKN.

а) б)

Рис. 127

Если точки O, K, M, N не лежат на одной прямой,

то OMKN — параллелограмм, и OM = KN. В противном

случае рассмотрим ортогональные проекции отрезков OM

и KN на AC (рис. 127, б). Так как точки O, M и N

проектируются соответственно в середины отрезков AC,

Решения. 2000 год. 11 класс 275

AK и KC, проекции отрезков OM и KN равны

KC. Так

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

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

4. Рассмотрим многочлен P(x) = x

−x

−x −1. Этот мно-

гочлен имеет корень t, больший 1, поскольку P(1) < 0, а

P(2) > 0 (см. комментарий). Возьмем длины палочек рав-

ными t

, t

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

сложить треугольник тогда и только тогда, когда длина

большего из них меньше суммы длин двух оставшихся.

Так как t

= t

+ t + 1 > t

+ t, из этих палочек не удастся

сложить треугольник. После первого отпиливания полу-

чим палочки с длинами t

, t, 1. Так как отношение длин

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

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

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

P(x) непрерывна на отрезке [a; b], причем P(a) < 0, P(b) > 0, то най-

дется такая точка c ∈(a; b), что P(c) = 0.

Мы не будем приводить ни доказательства этой теоремы, ни даже

определения непрерывной функции, отсылая читателя к [75], гл. 4.

Заметим лишь, что любой многочлен непрерывен.

5. а) Пусть N — число игроков, M =

. Игроков,

занявших первые M мест, назовем сильными, а осталь-

ных — слабыми (между участниками с одинаковой суммой

очков места распределяются произвольно). Пусть X —

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

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

собой, равна

M(M −1)

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

больше X. Обозначим сумму очков, набранных сильными,

через S

, а сумму очков, набранных слабыми, — через S

Тогда

M(M −1)

+ X, S

+ S

N(N −1)

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

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

игрока с разным числом очков. Рассмотрим сначала, слу-

чай, когда N — четное. Тогда число слабых игроков равно

276 Решения. 2000 год. 11 класс

числу сильных. Ясно, что в этом случае S

> S

. Значит,

+ S

N(N −1)

откуда

X > S

−

M(M −1)

N(N −1)

−

M(M −1)

Подставляя M = N/2, несложной выкладкой убеждаемся,

что X > N

/8 > N(N −1)/8. Так как общее число партий

равно N(N −1)/2, доля правильных партий больше 1/4.

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

го N. В этом случае можно поступить так: рассмотрим

средний результат сильного игрока

. Ясно, что он боль-

ше среднего результата слабого игрока, а значит, больше

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

N(N −1)/2

То есть S

M(N −1)

. Отсюда

X > S

−

M(M −1)

M(N −M)

N(N −1)

Последнее неравенство нетрудно проверить, подставив

M =

N −1

К о м м е н т а р и й. Доказательство для случая нечетного N прохо-

дит и при четном N.

0 0

1 1

№

игрока

1 2

0 0

0 0 0

1 1

k+1 2k+1

0 0

1 1 1

1 1

k+1

0 0

1 1

0 0 0

2k+1

1 1 1

Рис. 128

б) Рассмотрим сначала

турнир из 2k + 1 игрока, в

котором каждый участник

с номером i 6 k проиграл

участникам с номерами

i + 1, . . . , i + k и выиграл

у остальных, а каждый

участник с номером i > k

выиграл у участников с

номерами i −k, . . ., i −1 и

проиграл остальным. Оче-

видно, что все игроки на-

брали по k очков.

Решения. 2000 год. 11 класс 277

Рассмотрим таблицу турнира (рис. 128). Нетрудно ви-

деть, что в этой таблице над главной диагональю еди-

ницы стоят ровно в

k(k + 1)

клетках из

2k(2k + 1)

. Теперь

«размножим» каждого игрока, заменив его группой из n

игроков, и пусть участники из разных групп играют друг

с другом так же, как соответствующие прежние участни-

ки, а участники из одной группы играют друг с другом

вничью. Получим новую таблицу, в которой по-прежнему

у всех игроков поровну очков.

Исправим эту таблицу так, чтобы суммы очков игроков

перестали быть равными. Для этого будем менять резуль-

таты участников из (k + 1)-й группы: в их встречах про-

тив участников из (k + 1 −i)-й группы заменим in выигры-

шей ничьими, так что сумма очков каждого участника

(k + 1)-й группы уменьшится на i/2, а каждого участника

(k + 1 −i)-й группы увеличится на i/2. Напротив, в пар-

тиях с игроками (k + 1 + i)-й группы заменим ничьими in

проигрышей.

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

группы, второе — из второй группы и т. д. Посчитаем

число неправильных партий.

Все партии, проигранные игроками из группы i 6 k, —

неправильные. Таких партий kn

−in (вспомним, что in

партий с игроками из (k + 1)-й группы сыграны вничью).

Далее, игроки из i-й группы при i > k + 1 проиграли

(2k + 1 −i)n

неправильных партий. Наконец, игроки из

(k + 1)-й группы проиграли kn

−

k(k + 1)n

неправильных

партий (второе слагаемое соответствует неправильным

проигрышам, которые мы заменили на ничьи).

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

i=1

(kn

−in) +

2k+1

i=k+2

(2k + 1 −i)n

+ kn

−

k(k + 1)

n =

+ k

−k(k + 1)n.

При этом общее число партий равно

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

Значит, когда k и n стремятся к бесконечности одновре-

278 Решения. 2001 год. 8 класс

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

, а

число всех партий — как 2k

. Тогда их отношение стре-

мится к

> 0,7 (см. факт 27). Поэтому, если взять доста-

точно большие n и k, это отношение будет больше 70 %.

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

верить, что при n = k = 20 неправильные партии составля-

ют

235 600

335 790

> 0,7 от общего числа партий.

6. Будем помещать между плоскостями правильные

тетраэдры, расстояние между противоположными ребрами

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

Рис. 129

одно из ребер каждого тетра-

эдра лежит в одной из гра-

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

воположное ему — в другой.

Два тетраэдра можно располо-

жить так, чтобы конец «верх-

него» ребра первого совпадал

с серединой «верхнего» ребра

второго, а середина «нижне-

го» ребра первого — с концом

«нижнего» ребра второго, и

при этом как «верхние», так и

«нижние» ребра обоих тетраэдров были перпендикулярны.

Распространив этот процесс на весь слой, получим, что

каждый тетраэдр окружен четырьмя другими (рис. 129);

два из них не позволяют выдвинуть его «вверх», два

остальных — «вниз».

2001 год

8 к л а с с

1. Сначала будет закрашен наружный слой клеток, по-

сле чего останется прямоугольник 98 ×198 клеток. Этот

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

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

ник 96 ×196 клеток, и так далее.

Решения. 2001 год. 8 класс 279

Посмотрим, что произойдет после закраски 49 слоев

(рис. 130). Будут закрашены верхние 49 строк и нижние

49 50 151 152 200

100

Рис. 130

49 строк, значит, незакрашен-

ные клетки будут только в

50-й и 51-й строках. Анало-

гично, будут закрашены ле-

вые 49 столбцов (с номерами

1—49), и правые 49 столбцов

(с номерами 152—200). Итак,

незакрашенными останутся

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

пересечении столбцов с но-

мерами 50—151 и строк с

номерами 50—51 (это прямоугольник 2 ×102). Последней

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

ника, она расположена в 51-й строке и 50-м столбце.

2. Можно, например, ставить точки на окружности че-

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

Рис. 131

только меньшие). В каждый момент полу-

чившаяся фигура будет иметь ось симмет-

рии. Действительно, если число поставлен-

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

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

нюю точку. Если число точек четно, то ось

симметрии — диаметр окружности, проходя-

щий через середину средней дуги.

3. Напишем слова в столбик:

З А Н О З А

З И П У Н Ы

К А З И Н О

К Е Ф А Л Ь

О Т М Е Л Ь

Ш Е Л Е С Т

После всех замен буквы в каждой колонке должны стать

одинаковыми. Число замен будет наименьшим, если в

каждой колонке сохранить наиболее частую букву (любую

из них, если таких букв несколько). Например, в первой

280 Решения. 2001 год. 8 класс

колонке можно оставить буквы З или К. В обоих случаях,

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

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

четыре замены. А вот в третьей колонке все буквы раз-

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

колонках потребуется по четыре замены. Минимальное

число замен во всех колонках равно 4 + 4 + 5 + 4 + 4 + 4 = 25.

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

осмысленные, например, ЗЕЛЕНЬ, КАПЕЛЬ или КАФЕЛЬ.

4. Напомним, что в прямоугольном треугольнике ме-

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

A C

Рис. 132

наоборот, если медиана равна по-

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

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

угольный (см. факт 14).

Медиана ML прямоугольного

треугольника AMC равна поло-

вине гипотенузы AC, т. е.

ML = AL = LC.

По условию, треугольник KLM

равносторонний, так что KL = ML

(рис. 132). Значит, в треугольнике AKC медиана KL равна

половине стороны AC, поэтому угол AKC прямой. Таким

образом, в треугольнике ABC биссектриса AK является

высотой.

Следовательно, треугольник BAC равнобедренный (AB =

= AC) и AK является также медианой: BK = KC. Значит,

MK — медиана прямоугольного треугольника BMC, поэто-

му BC = 2MK = 2KL = AC. Итак, AB = BC = AC, что и тре-

бовалось доказать.

5, 6. Расположим двузначные числа в клетках прямо-

угольника высоты 9 и ширины 10 (по горизонтали откла-

дываем единицы, по вертикали — десятки).

Каждой попытке Гриши соответствует крестик из пя-

ти клеток (рис. 133, а): в центре названное им число,

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

ре на единицу (если названное число содержит цифру 0