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

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

Решения. 2001 год. 11 класс 291

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

, прямая LI

так-

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

утверждение задачи.

4. Предположим, что такой многочлен Q(x) существует.

Пусть Q(x) = a

+ a

n−1

+ . . . + a

x + a

, где a

, a

, . . .

..., a

— целые неотрицательные числа, a

6= 0, n > 2.

Если a

= 0, то Q(x) = x(a

n−1

+ a

n−1

n−2

+ . . . + a

), сле-

довательно, при простом p число Q(p) делится на p, при-

чем Q(p) > p (здесь используется то, что степень Q не мень-

ше 2), поэтому Q(p) — число составное. Допустим, a

> 2.

Обозначим через p некоторый простой делитель чис-

ла a

. Тогда Q(p) = (a

n−1

+ a

n−1

n−2

+ . . . + a

)p+ a

делит-

ся на p, причем Q(p) > p; значит, Q(p) — число составное.

Таким образом, имеется единственная возможность: a

= 1.

Если для любого простого p число Q(p) простое, то и

число Q(Q(p)) является простым при любом простом p.

Значит, свободный член многочлена Q(Q(x)) должен рав-

няться 1. Однако, поскольку Q(0) = a

= 1, Q(Q(0)) = Q(1) =

= a

+ a

n−1

+ . . . + a

+ 1 > 1. Мы получили противоречие, за-

вершающее доказательство.

5. Положим N = 2001 и опишем построение расположе-

ния N выпуклых многогранников, из которых никакие

три не пересекаются и любые два касаются.

Рассмотрим бесконечный круговой конус, вершина O

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

вдоль оси Oz. На окружности, являющейся сечением ко-

нуса плоскостью z = 1, возьмем точки A

, A

, ..., A

—

вершины правильного N-угольника. Обозначим через B

, . . . , B

середины меньших дуг A

, A

, . . . , A

соответственно. Через C(t) обозначим круг, являющийся

сечением конуса плоскостью z = t, через O

— центр этого

круга, через A

, B

— точки пересечения образующих OA

с кругом C(t), где t > 0, 1 6 i 6 N. Здесь и далее мы

будем считать нумерацию точек A

циклической, т. е.,

например, A

N+1

= A

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

Л е м м а. Пусть выпуклый многоугольник M лежит

внутри круга C(t

), t

> 0. Рассмотрим бесконечную вверх

292 Решения. 2001 год. 11 класс

«призму» P, основанием которой служит многоугольник

M, а боковое «ребро» параллельно прямой OB

для неко-

торого i. Многоугольник (равный M), который получа-

ется при пересечении призмы P и круга C(t), обозна-

чим M(t) (таким образом, M(t

) совпадает с M). Тогда

найдется такое положительное T > t

, что при всех t> T

многоугольник M(t) будет содержаться внутри сегмента

(t) = A

i+1

круга C(t).

Д о к а з а т е л ь с т в о. Многоугольник M(t) является

образом M при параллельном переносе на вектор, парал-

лельный образующей OB

. Поэтому многоугольник M(t)

содержится внутри круга, равного кругу C(t

), который

C(t

)

C(t)

i+1

Рис. 142

касается круга C(t) в точ-

ке B

. Расстояние от точки

до прямой A

i+1

прямо

пропорционально длине обра-

зующей OB

; следовательно,

найдется такое T, что при

всех t > T это расстояние боль-

ше диаметра окружности C(t

)

(рис. 142). Это и означает,

что многоугольник M(t) по-

падает внутрь сегмента S

(t)

круга C(t). Лемма доказана.

Переходим к индуктивному построению требуемого рас-

положения (см. факт 24). При каждом n (1 6 n 6 N) мы

построим положительные числа t

< t

< . .. < t

, выпуклые

многоугольники M

, M

, . . . , M

, лежащие внутри кру-

гов C(t

), C(t

), . . . , C(t

), бесконечные «призмы» P

, ..., P

с основаниями M

, M

, ..., M

и боковыми

«ребрами», параллельными OB

, OB

, ..., OB

соответ-

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

три не имеют общих точек.

Выберем t

> 0. Возьмем выпуклый многоугольник M

внутри круга C(t

). Рассмотрим бесконечную вверх «приз-

му» P

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

, а

боковое «ребро» параллельно прямой OB

Пусть для некоторого n (1 6 n < N) уже определены

положительные числа t

, t

, . . . , t

n−1

, выпуклые много-

угольники M

, M

, . . . , M

n−1

и «призмы» P

, P

, . . .

Решения. 2001 год. 11 класс 293

..., P

n−1

. Согласно лемме существует такое число t

> t

n−1

что многоугольник M

) содержится внутри сегмента

) круга C(t

), многоугольник M

) содержится

внутри сегмента S

) круга C(t

), ..., многоуголь-

ник M

n−1

) содержится внутри сегмента S

n−1

) кру-

га C(t

). Сдвинем каждую из прямых A

i+1

(1 6 i 6 n −1)

в направлении вектора O

, пока она не совпадет с

прямой l

), касающейся многоугольника M

). Теперь

построим выпуклый многоугольник M

, который содер-

жится в круге C(t

), касается каждого многоугольника

) и лежит по разные с ним стороны от прямой

): возьмем для каждого i одну из точек касания

многоугольника M

) и прямой l

); при n > 3 эти

точки являются вершинами выпуклого (n −1)-угольника,

который мы и выберем в качестве M

; при n = 2, 3 надо

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

вверх «призму» P

, основанием которой является много-

угольник M

, а боковое «ребро» параллельно прямой OB

Построение будет закончено, когда мы получим призмы

, P

, . .., P

. Наконец, «срежем» призмы плоскостью

z = T, где T > t

Докажем, что полученные (обычные) призмы удовле-

творяют условию задачи. Для этого достаточно показать,

что призма P

пересекается с призмой P

, i < n, только в

плоскости круга C(t

). Пусть, напротив, найдется общая

точка R ∈C(t) двух призм, где t > t

. Через точку R про-

ведем прямые, параллельные OB

и OB

; обозначим их

точки пересечения с плоскостью круга C(t

) через R

соответственно. Тогда точка R

должна принадлежать

многоугольнику M

), а точка R

должна принадлежать

многоугольнику M

). Ненулевые векторы R

и B

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

= −(t −t

)OB

и RR

= −(t −t

)OB

Однако это невозможно, поскольку точки R

и B

лежат

по одну сторону от прямой l

), а точки R

и B

— по

другую. Противоречие завершает доказательство.

6. а) Текущее состояние описанной в задаче системы

определяется количеством шариков в каждой коробочке

294 Решения. 2001 год. 11 класс

и указанием коробочки, с которой нужно начинать рас-

кладывать шарики в следующий раз. Поэтому возможных

состояний системы конечное число. Из каждого состояния

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

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

зная состояние системы в настоящий момент, можно

однозначно определить состо яние системы перед послед-

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

раскладывание должно было закончиться на выделен-

ной коробочке; поэтому, чтобы восстановить предыдущее

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

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

по шарику из каждой коробочки, пока это возможно.

Когда же мы встретим пустую коробочку, мы положим

в нее все собранные шарики и объявим ее отмеченной.

(Фактически мы дали описание операции, обратной к

ходу, описанному в условии задачи.) Если обозначить

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

из одного состояния в другое — стрелкой, соединяющей

соответствующие точки (т. е. построить ориентированный

граф состояний системы, см. факт 3), то из каждой

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

точку будет входить ровно одна стрелка. Начнем дви-

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

Получаем последовательность состояний A

, A

, . . . По-

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

в последовательности {A

} возникнет повторение. Пусть,

например, A

= A

, где k < n. Поскольку в точку A

вхо-

дит ровно одна стрелка, из равенства A

= A

следуют

равенства A

k−1

= A

n−1

, . . . , A

= A

n−k+1

. Тем самым, через

n −k ходов мы вернулись в состояние A

б) В отличие от задачи «а» теперь состояние системы

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

бочкам. В каждый момент возможно несколько ходов, а

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

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

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

в решении пункта «а». В терминах графа состояний си-

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

же стрелок, сколько в нее входит.

Решения. 2002 год. 8 класс 295

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

Л е м м а 1. При любом начальном состоянии можно

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

перед заданной коробочке X.

Д о к а з а т е л ь с т в о. Если при каждой операции

брать шарики из непустой коробочки, ближайшей к X

при движении против часовой стрелки, то либо число

шариков в X увеличится, либо количество шариков в X

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

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

Лемма доказана.

Л е м м а 2. Если из состояния A можно попасть в

состояние B, то из состояния B можно попасть в со-

стояние A.

Д о к а з а т е л ь с т в о. Заметим, что если из A в C ве-

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

стрелкам. Действительно, пройдем по стрелке из A в C, а

далее будем действовать как в пункте «а», т. е. на каждом

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

в которую попал последний шарик на предыдущем ходе.

Тогда, согласно утверждению пункта «а», повторится на-

чальная ситуация — мы попадем в состояние A. Поэтому

если можно попасть из A в B (за несколько ходов), то

можно попасть из B в A. Лемма доказана.

Пусть A и B — произвольные состояния. Обозначим че-

рез K состояние, при котором все шарики собраны в коро-

бочке X. Согласно лемме 1, можно попасть из A в K. Из

лемм 1 и 2 следует, что можно попасть из K в B. Значит,

можно попасть из A в B.

2002 год

8 к л а с с

1. Пусть число супружеских пар на острове равно N

(замужем N женщин, женаты N мужчин). По условию N

замужних женщин составляют 3/5 всех женщин острова,

значит, на острове 5N/3 женщин. Аналогично, женатые

мужчины составляют 2/3 всех мужчин острова, значит,

на острове 3N/2 мужчин.

296 Решения. 2002 год. 8 класс

Поэтому всего на острове

N +

N =

N жителей, а в

браке состоит 2N жителей. Итак, искомая доля равна

19N/6

2. Заметим, что A

6 99

= 9801 < 9999. Поэтому сумма

цифр числа A

меньше, чем 9 · 4 = 36. Так как она равна

квадрату суммы цифр числа A, то сумма цифр числа A

меньше, чем

√

36 = 6.

Но если сумма цифр меньше, чем 6, то она меньше

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

которых сумма цифр не больше 5 — таких чисел 15: 10,

11, 12, 13, 14, 20, 21, 22, 23, 30, 31, 32, 40, 41, 50.

Нетрудно проверить, что условию задачи удовлетворяют

только девять чисел, указанных в ответе.

К о м м е н т а р и й. Возникает естественный вопрос: а как найти

все (не только двузначные) числа, удовлетворяющие условию задачи?

Простого ответа на этот вопрос автору неизвестно. Можно доказать

(попробуйте это сделать), что любое число A, квадрат суммы цифр ко-

торого равен сумме цифр числа A

, обладает следующими свойствами:

— в его десятичной записи могут встречаться только цифры 0, 1,

2 и 3;

— тройки не могут стоять рядом друг с другом и с двойками.

К сожалению, эти условия не являются достаточными: например,

222

= 49284,

но сумма цифр числа 49284 равна 27 и не совпадает с 6

Рис. 143

3. Пусть E — точка касания второй

окружности с общей касательной, O —

центр первой окружности (рис. 143).

Треугольник AOD равнобедренный (по-

тому что AO и OD — радиусы первой

окружности), поэтому ∠ODA = ∠OAD.

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

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

ку касания. Значит, отрезки OD и

AE перпендикулярны общей касатель-

ной DE. Поэтому OD kAE, так что по

теореме о внутренних накрест лежащих

Решения. 2002 год. 8 класс 297

углах при параллельных прямых ∠DAE = ∠ODA. Итак,

∠DAE = ∠OAD.

Теперь мы видим, что 4DEA = 4DCA по двум сторо-

нам и углу между ними. Действительно, ∠DAE = ∠OAD,

EA = AC (радиусы!), AD — общая сторона. Значит, ∠DCA =

= ∠DEA = 90

◦

, т. е. прямые DC и AB перпендикулярны.

4. Заметим, что от перестановки горизонталей доски

ничего не изменяется. Иными словами, если некоторая

позиция является проигрышной для первого, и мы раз-

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

позиция тоже будет проигрышной для первого (а если

она была выигрышной для первого, то она останется вы-

игрышной). Это следует из того, что при такой переста-

новке числа шашек на вертикалях не меняются.

От перестановки вертикалей тоже ничего не меняется.

Пусть первый поставил на доску первую шашку. Пере-

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

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

ки. Далее второй игрок должен делать ходы симметрично

ходам первого игрока относительно центра доски. Тогда

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

первый не сможет занять центральную клетку.

Легко проверить, что второй всегда сможет сделать

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

второго расстановка шашек симметрична относительно

центра доски. Значит, на средней горизонтали стоит

либо 0, либо 2 шашки (напомним, что центр не может

быть занят!). Если там стоит 0 шашек, то первый может

сделать ход на среднюю горизонталь (но не в центр!).

Ясно, что второй сможет ответить симметричным ходом.

На среднюю вертикаль первый пойти не может. Оста-

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

ку, не лежащую ни на средней горизонтали, ни на сред-

ней вертикали. Его ход не изменяет количества шашек

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

клетку, поэтому второй может поставить туда шашку.

К о м м е н т а р и й. Игра всегда заканчивается либо после 129, ли-

бо после 130 ходов. Действительно, пусть сделано не более 128 хо-

дов. Тогда по принципу Дирихле (см. факт 1) либо найдется пустая

298 Решения. 2002 год. 8 класс

горизонталь, либо две горизонтали с одной шашкой. В первом случае

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

вертикали, на которой стоит не более одной шашки. Во втором случае

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

пересечение с каждой из этих двух горизонталей. Ясно, что хотя бы

одна из этих двух клеток пуста, и в нее можно поставить шашку.

130-й ход можно сделать не всегда: после 129 ходов есть одна вер-

тикаль с одной шашкой, и одна горизонталь с одной шашкой (осталь-

ные вертикали и горизонтали содержат по две шашки). Казалось бы,

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

может уже стоять — и в этом случае выиграет первый.

После 128-го хода возможны четыре ситуации: 1) свободная гори-

зонталь и свободная вертикаль; 2) две вертикали с одной фишкой и

свободная горизонталь; 3) две горизонтали с одной фишкой и свобод-

ная вертикаль; 4) две вертикали с одной фишкой и две горизонтали

Рис. 144

с одной фишкой. Нетрудно видеть, что при стратегии,

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

и последняя ситуации. Во второй ситуации всегда

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

рим клетки A, B, C и D на пересечении вертикалей

с одной фишкой и горизонталей с одной фишкой

(рис. 144). В некоторых из них уже могут стоять

фишки. Например, если в A фишка стоит, а в D —

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

при нашей стратегии это невозможно: либо все клет-

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

ные по диагонали (A и D или B и C). Нетрудно видеть, что в каждом

из этих вариантов второй сможет сделать 130-й ход (и выиграть).

5. П е р в ы й с п о с о б. Проведем в треугольнике AMB

медианы AF и BG и обозначим через N точку их пересе-

Рис. 145

чения (рис. 145). Известно, что точка

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

шении 1 : 2. Поэтому

MF =

MB = ME,

так как M — точка пересечения ме-

диан треугольника ABC. В пунк-

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

AME и AMF равны, так что AF = AE.

В пункте «б» основание перпендику-

ляра, опущенного из вершины A на

прямую BE, лежит на луче MB, зна-

чит, AF < AE.

Решения. 2002 год. 8 класс 299

Рис. 146

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

Пусть P — основание перпендикуляра. Так

как P лежит на луче MB и M — середина

отрезка EF, получаем PF < PE. По теореме

Пифагора

AF =

+ PF

+ PE

= AE.

Итак, в любом случае AF 6 AE.

Значит,

AN =

AF 6

AE =

(так как N — точка пересечения

медиан треугольника ABM).

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

BN 6

BC. Используя неравенство

треугольника для треугольника

ANB, получаем:

AC + BC > 3(AN + BN) > 3AB.

В т о р о й с п о с о б. Проведем

медиану CK и продолжим ее на

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

точку F такую, что KF = CK (рис. 146). Четырехугольник

ACBF — параллелограмм. Из треугольника ACF имеем:

AC + AF > FC = 2CK, значит, AC + BC > 2CK.

Построим на стороне AB как на диаметре окружность.

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

этой окружности (см. факт 14). Значит, MK > AK =

AB.

Но CK = 3MK, так как медианы делятся точкой пересече-

ния в отношении 1 : 2. Поэтому

AC + BC > 2CK = 6MK > 3AB.

6. Рассмотрим сначала случай прямоугольника 1 ×n.

При n = 2 и n > 4 вечно живые расстановки в прямоуголь-

нике 1 ×n существуют: каждая из расстановок на рис. 147

имеет период 2, т. е. каждую вторую минуту возвращает-

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

ветствуют различным остаткам от деления числа n на 4

300 Решения. 2002 год. 8 класс

(см. факт 7). Выделенная часть является повторя-

ющейся, т. е., чтобы получить картинку для большего n,

достаточно увеличить количество таких частей (символ

соответствует живой клетке, символ — мертвой).

n = 2 n = 4k n = 4k + 2

n = 4k + 1 n = 4k + 3

Рис. 147

Заметим, что при n = 4k + 1 имеется одна «вечно мерт-

вая» клетка, а при остальных n каждая клетка последо-

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

Пусть для некоторого n в прямоугольнике 1 ×n суще-

ствует вечно живая расстановка. Тогда такая расстановка

существует и во всех прямоугольниках m ×n.

Строится она так: берем вечно живую расстановку в

прямоугольнике 1 ×n и копируем ее во все строки пря-

моугольника m ×n. Тогда в нем столбцы будут эволюцио-

нировать так же, как клетки в соответствующем столбце

прямоугольника 1 ×n. Действительно, все клетки живого

столбца умирают, как и соответствующая клетка прямо-

угольника 1 ×n. У каждой клетки мертвого столбца сосе-

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

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

чит, и количеству живых соседей у соответствующей клет-

ки в «полоске» 1 ×n. Значит, мертвый столбец оживает в

том и только том случае, когда оживает соответствующая

клетка в полоске.

Поскольку в полоске всегда остается хотя бы одна жи-

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

ника m ×n тоже всегда остается хотя бы один живой стол-

бец.

Мы можем счи тать, что m 6 n (иначе повернем прямо-

угольник на 90

◦

). Если n > 4 или n = 2, то, по доказанно-

му, вечно живая расстановка найдется. Остается рассмот-

реть прямоугольники 1 ×1, 1 ×3 и 3 ×3.