ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.04.2024
Просмотров: 48
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Второе решение.
Не умаляя общности, можно считать, что b c, тогда 1 − c
2
1 − b
2
1 − и, следовательно 1
− a
2
1 1
− b
2
1 1
− c
2
.
11 класс. Первое решение. Без ограничения общности можно считать α −
− β 0, γ − τ 0. Положим a =
α + β
2
, b =
α − β
2
, c =
γ + τ
2
, d =
γ − тогда условие задачи перепишется в виде sin ax cos bx = sin cx cos где a > b 0, c > d Наименьший положительный корень левой части — число
π
a
или
π
2b
, а правой или. Если a = c, то cos bx = cos dx и, значит, b = Из этих равенств следует требуемое.
Пусть x
0
=
π
a
. Если, то a = 2d, и из равенства функций sin 2dx cos bx = sin cx cos следует sin dx cos bx = sin cx.
693. Ответ. Существуют.
Мы будем искатьтакие числа в виде m = a
2
, n = b
3
, p = c
2
, q =
= d
3
, где a, b, c, d — натуральные. Тогда условие переформулируется такте+ c) = (d −
− b)(d
2
+ bd + b
2
)
. Зафиксируем такие b и d, что b = d − 1 > 2004. Тогда условиям удовлетворяет пара c =
d
2
+ bd + b
2
− 1 2
, a =
d
2
+ bd + b
2
+ 1 эти числа целые, поскольку b и d разной четности. Кроме того, a > c >
> b
2
> d > b > Замечание. Можно показать, что для любой четверки чисел, удовлетворяющей условию, числа, целые. Ответ. Всегда.
Построим граф, вершины которого соответствуют телефонам, а ребра проводам. Рассмотрим наименьший набор вершин данного графа такой, что среди соединяющих эти вершины ребер присутствуют ребра всех четырех цветов. Удалим из этого набора произвольную вершину. По
708. Ответ · 2002 2
+ 1 = Докажем, что сумма не может бытьменьше. Переставив, если нужно,
столбцы, будем далее считать, что числа впервой строке стоят в неубывающем порядке. Пусть a
i
— е число первой строки. Рассмотрим сумму = (a
1
− 1) + (a
2
− 1) + (a
3
− 1) + (a
4
− 2) + . . . + (a
i
− (i − 2)) + . . .
. . . + (a
2003
− 2001) + (a
2004
− 2001).
719. Пусть, для определенности,
точка D лежит на дуге BC, не содержащей точки A см. рис. Обозначим через H точку пересечения высот треугольника ABC, а через и H
B
— вторые точки пересечения прямых AH и BH с окружностью.
Углы и равны как вписанные, опирающиеся на одну дугу.
Далее, ∠CAA
=
=
∠CBB
= 90
◦
− ∠ACB. Следовательно, прямоугольные треугольники, и имеют по равному острому углу, и поэтому подобны. Кроме того, треугольники и имеют общий катет, и значит равны, отсюда HA
= Так как ∠B
AQ =
∠CAD = ∠CBD = ∠A
BP
, то отрезки AQ и являются соответствующими в подобных треугольниках и следовательно. Построим на высоте точку S такую,
что QS A
B
. Из теоремы Фалеса вытекает, что отношение
A
S
A
H
равно
B
Q
B
H
=
A
P
A
H
A
. По доказанному HA
= H
A
A
, значит, A
S = A
P
, и A
B
— средняя линия треугольника P QS, те. делит пополам сторону P Q.
720. Разобьем всех сидящих за столом на 50 пар соседей и назовем людей в любой паре знакомыми. Тогда достаточно разбитьих на две группы
(по одному представителю от страны в группе) так, чтобы в каждой группе не оказалосьзнакомых. Покажем, как это можно сделать.
Выберем любого представителя страны 1, поместим его в первую группу, второго представителя этой же страны поместим во вторую группу, его знакомого (представителя, скажем, й страны) — снова в первую, второго представителя й страны — во вторую и т. д. Этот процесс завершится, когда очередной знакомый уже распределен это возможно только если этот знакомый — изначальный представитель первой страны, тогда он помещен в первую группу, что от него и требовалось
Не умаляя общности, можно считать, что b c, тогда 1 − c
2
1 − b
2
1 − и, следовательно 1
− a
2
1 1
− b
2
1 1
− c
2
.
УЧЕБНЫЙ ГОД, 9
КЛАСС
397
Заметим, что 1
− a
−
2 1 + a
=
3a
− 1 1
− Таким образом, нужно доказатьнеравенство
3a
− 1 1
− a
2
+
3b
− 1 1
− b
2
+
3c
− 1 1
− c
2
Поскольку сумма числителей равна 0, неравенство будет доказано, если мы заменим знаменатели на равные таким образом, что каждая дробьпри этом не увеличится. Если a b
1 3
c, то заменим все знаменатели на 1 − c
2
, в результате отрицательное слагаемое не изменится, а положительные не увеличатся. Если a
1 3
b c, то заменим все знаменатели на 1 − b
2
, тогда положительное и одно из отрицательных слагаемое только уменьшатся, а второе отрицательное слагаемое останется неизменным. Ответ. Нельзя.
Рассмотрим любой квадрат A размером 200 × 200 клеток. Пустьон будет угловым квадратом некоторого квадрата B размером 200t × клеток, где t — некоторое натуральное число, на которое не делится сумма чисел в квадрате A. Разобьем фигуру B \ A на прямоугольники размером 200(t − 1). В каждом из этих прямоугольников по условию сумма чисел будет делиться на t, в квадрате B — тоже, значит, ив квадрате сумма чисел будет делиться на t, что невозможно в силу выбора Рис. 301
672. Рассмотрим окружности и, построенные на диагоналях AC и
BD
как на диаметрах. Пусть BB
1
,
CC
1
, AA
1
, DD
1
— высоты в треугольниках и AP D, соответственно (точки и лежат на и D
1
— на ω
2
). Тогда точки A, D
1
,
A
1
, D лежат на одной окружности,
поэтому H
1
A
· H
1
A
1
= H
1
D
· те. лежит на радикальной оси и ω
2
. Аналогично, также на ней лежит, следовательно, эта радикальная осьестьпрямая H
1
H
2
. Обозначим через M и N середины диагоналей и BD соответственно. Так как точка X по условию лежит на радикальной оси и ω
2
, то XM
2
−
− CM
2
= XN
2
− DN
2
. Но треугольники XAC и XBD подобны, так как = ∠XBQ, ∠XCQ = ∠XDQ, следовательно эти разности квадратов должны относиться как квадрат коэффициента подобия или рав-
КЛАСС
397
Заметим, что 1
− a
−
2 1 + a
=
3a
− 1 1
− Таким образом, нужно доказатьнеравенство
3a
− 1 1
− a
2
+
3b
− 1 1
− b
2
+
3c
− 1 1
− c
2
Поскольку сумма числителей равна 0, неравенство будет доказано, если мы заменим знаменатели на равные таким образом, что каждая дробьпри этом не увеличится. Если a b
1 3
c, то заменим все знаменатели на 1 − c
2
, в результате отрицательное слагаемое не изменится, а положительные не увеличатся. Если a
1 3
b c, то заменим все знаменатели на 1 − b
2
, тогда положительное и одно из отрицательных слагаемое только уменьшатся, а второе отрицательное слагаемое останется неизменным. Ответ. Нельзя.
Рассмотрим любой квадрат A размером 200 × 200 клеток. Пустьон будет угловым квадратом некоторого квадрата B размером 200t × клеток, где t — некоторое натуральное число, на которое не делится сумма чисел в квадрате A. Разобьем фигуру B \ A на прямоугольники размером 200(t − 1). В каждом из этих прямоугольников по условию сумма чисел будет делиться на t, в квадрате B — тоже, значит, ив квадрате сумма чисел будет делиться на t, что невозможно в силу выбора Рис. 301
672. Рассмотрим окружности и, построенные на диагоналях AC и
BD
как на диаметрах. Пусть BB
1
,
CC
1
, AA
1
, DD
1
— высоты в треугольниках и AP D, соответственно (точки и лежат на и D
1
— на ω
2
). Тогда точки A, D
1
,
A
1
, D лежат на одной окружности,
поэтому H
1
A
· H
1
A
1
= H
1
D
· те. лежит на радикальной оси и ω
2
. Аналогично, также на ней лежит, следовательно, эта радикальная осьестьпрямая H
1
H
2
. Обозначим через M и N середины диагоналей и BD соответственно. Так как точка X по условию лежит на радикальной оси и ω
2
, то XM
2
−
− CM
2
= XN
2
− DN
2
. Но треугольники XAC и XBD подобны, так как = ∠XBQ, ∠XCQ = ∠XDQ, следовательно эти разности квадратов должны относиться как квадрат коэффициента подобия или рав-
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
няться 0. Во втором случае получаем, что ∠AXC = ∠BXD = 90
◦
, но тогда прямые AB и CD будут перпендикулярны (так как одна из них будет получаться из другой поворотной гомотетией с углом и центром что противоречит различности точек и H
2
. Значит, треугольники и BXD будут равны. Но тогда равны будут и треугольники AY C итак как они подобны (по причинам, аналогичным подобию треугольников
AXC
и BXD) и имеют равные соответственные стороны (AC = Значит, степени точки Y относительно окружностей и равны (так как Y M = Y N, MC = ND), поэтому она лежит на той же радикальной оси класс. Возьмем четыре различных числа a, b, c, d ∈ M. Из рациональности чисел d
2
+ и d
2
+ следует рациональность bc − ab, откуда a
2
+
+ ab = a
2
+ bc
− (bc − ab) ∈ Q. Аналогично, b
2
+ ab
∈ Q. Поэтому для произвольных различных a, b ∈ M число q =
a
b
=
a
2
+ ab
b
2
+ ab
∈ Q. Тогда = qb
⇒ a
2
+ ab = b
2
(q
2
+ q) = l
∈ Q, b =
l
q
2
+ q
=
m
k
, m, k ∈ Значит, число b
√
n
, где n = mk, рационально. Тогда c
√
n =
c
b
· b
√
n
∈ для любого c ∈ M.
674. Не умаляя общности, можно считать, что ∠ABO ∠BAO, тогда
S
1
S
2
B
A
D
C
K
L
M
O
P
Q
Рис. и DCOM — равнобокие трапеции (см. рис. 302). Заметим, что касательная к S
2
, поскольку ∠LOD = ∠ABD = ∠OCD; аналогично касательная к S
1
. Тогда ∠KMO = ∠KOL, ∠KLO =
=
∠KOM. Значит, треугольники KOM и KLO подобны. Но тогда подобны и треугольники KOP и KMQ. Отсюда ∠KP O = ∠KQM = π −
− ∠KQO. Значит, четырехугольник KP OQ — вписанный
няться 0. Во втором случае получаем, что ∠AXC = ∠BXD = 90
◦
, но тогда прямые AB и CD будут перпендикулярны (так как одна из них будет получаться из другой поворотной гомотетией с углом и центром что противоречит различности точек и H
2
. Значит, треугольники и BXD будут равны. Но тогда равны будут и треугольники AY C итак как они подобны (по причинам, аналогичным подобию треугольников
AXC
и BXD) и имеют равные соответственные стороны (AC = Значит, степени точки Y относительно окружностей и равны (так как Y M = Y N, MC = ND), поэтому она лежит на той же радикальной оси класс. Возьмем четыре различных числа a, b, c, d ∈ M. Из рациональности чисел d
2
+ и d
2
+ следует рациональность bc − ab, откуда a
2
+
+ ab = a
2
+ bc
− (bc − ab) ∈ Q. Аналогично, b
2
+ ab
∈ Q. Поэтому для произвольных различных a, b ∈ M число q =
a
b
=
a
2
+ ab
b
2
+ ab
∈ Q. Тогда = qb
⇒ a
2
+ ab = b
2
(q
2
+ q) = l
∈ Q, b =
l
q
2
+ q
=
m
k
, m, k ∈ Значит, число b
√
n
, где n = mk, рационально. Тогда c
√
n =
c
b
· b
√
n
∈ для любого c ∈ M.
674. Не умаляя общности, можно считать, что ∠ABO ∠BAO, тогда
S
1
S
2
B
A
D
C
K
L
M
O
P
Q
Рис. и DCOM — равнобокие трапеции (см. рис. 302). Заметим, что касательная к S
2
, поскольку ∠LOD = ∠ABD = ∠OCD; аналогично касательная к S
1
. Тогда ∠KMO = ∠KOL, ∠KLO =
=
∠KOM. Значит, треугольники KOM и KLO подобны. Но тогда подобны и треугольники KOP и KMQ. Отсюда ∠KP O = ∠KQM = π −
− ∠KQO. Значит, четырехугольник KP OQ — вписанный
УЧЕБНЫЙ ГОД, КЛАСС. Первое решение. Рассмотрим ребро l, соединяющее вершины с числами и x
j
. Обозначим через число вершин, из которых нельзя пройти в вершину при удалении ребра l. Аналогично, число вершин,
из которых нельзя пройти в вершину при удалении ребра l, обозначим. Ясно, что 1 k
i
(l), k
j
(l)
n − 1, k
i
(l) + k
j
(l) = n
. Кроме того,
для каждого i сумма
l
k
i
(l)
равна n − 1 (сумма берется по всем ребрам выходящим из x
i
), так как из вершины можно пройти по ребрам дерева в каждую из оставшихся n − 1 вершин единственным несамопересекаю- щимся путем.
Согласно неравенству между средним арифметическими средним геометрическим, для данного ребра l получим 1
x
2
i
+
k
j
(l)
√
n
− 1
x
2
j
2
k
i
(l)k
j
(l)
n
− 1
|x
i
x
j
| Последнее неравенство верно,
так как) + k
j
(l))
2
− (k
i
(l) − k
j
(l))
2 4
n
2
− ((n − 1) − 1)
2 4
= n
− Сложив неравенства (∗) по всем ребрам, получим требуемое неравен- ство.
Второе решение. Будем проводитьоперации, не изменяющие чисел в вершинах и не уменьшающие сумму S чисел на ребрах. Достаточно до- казатьнеравенство по окончании этих операций.
Вначале заменим числа в вершинах на их модули, те. далее считаем,
что x
1
, x
2
, . . . , x
n
Выберем наибольшее из чисел x
i
, пустьэто число x
1
. Если нашлась вершина с числом x
i
, i ≡ 1, из которой выходит ровно одно ребро l, ведущее в вершину x
j
, j = 1, то произведем перестройку удалим ребро и соединим ребром вершины с числами и x
1
. Полученный граф остается деревом, так как количество ребер не изменилосьи по-прежнему из любой вершины можно пройти по ребрам в любую другую. После перестройки сумма S изменяется на x
i
x
1
−x
i
x
j
0. Производим перестройки,
пока это возможно. Поскольку при каждой перестройке число ребер, выходящих из вершины с числом x
1
, увеличивается, через конечное число шагов мы придем к ситуации, когда невозможно сделатьперестройку. В
этой ситуации вершина с числом соединена ребром с каждой из оставшихся вершин. В самом деле, предположим, что некоторая вершина не соединена ребром с вершиной x
1
. Пройдем в нее из по ребрам (не проходя дважды по одному ребру) и продолжим этот путь, пока это возможно. Ясно, что концом этого пути может являться вершина, из которой выходит ровно одно ребро, причем не в вершину с числом x
1
. Но это означает, что можно произвести перестройку, — противоречие
j
. Обозначим через число вершин, из которых нельзя пройти в вершину при удалении ребра l. Аналогично, число вершин,
из которых нельзя пройти в вершину при удалении ребра l, обозначим. Ясно, что 1 k
i
(l), k
j
(l)
n − 1, k
i
(l) + k
j
(l) = n
. Кроме того,
для каждого i сумма
l
k
i
(l)
равна n − 1 (сумма берется по всем ребрам выходящим из x
i
), так как из вершины можно пройти по ребрам дерева в каждую из оставшихся n − 1 вершин единственным несамопересекаю- щимся путем.
Согласно неравенству между средним арифметическими средним геометрическим, для данного ребра l получим 1
x
2
i
+
k
j
(l)
√
n
− 1
x
2
j
2
k
i
(l)k
j
(l)
n
− 1
|x
i
x
j
| Последнее неравенство верно,
так как) + k
j
(l))
2
− (k
i
(l) − k
j
(l))
2 4
n
2
− ((n − 1) − 1)
2 4
= n
− Сложив неравенства (∗) по всем ребрам, получим требуемое неравен- ство.
Второе решение. Будем проводитьоперации, не изменяющие чисел в вершинах и не уменьшающие сумму S чисел на ребрах. Достаточно до- казатьнеравенство по окончании этих операций.
Вначале заменим числа в вершинах на их модули, те. далее считаем,
что x
1
, x
2
, . . . , x
n
Выберем наибольшее из чисел x
i
, пустьэто число x
1
. Если нашлась вершина с числом x
i
, i ≡ 1, из которой выходит ровно одно ребро l, ведущее в вершину x
j
, j = 1, то произведем перестройку удалим ребро и соединим ребром вершины с числами и x
1
. Полученный граф остается деревом, так как количество ребер не изменилосьи по-прежнему из любой вершины можно пройти по ребрам в любую другую. После перестройки сумма S изменяется на x
i
x
1
−x
i
x
j
0. Производим перестройки,
пока это возможно. Поскольку при каждой перестройке число ребер, выходящих из вершины с числом x
1
, увеличивается, через конечное число шагов мы придем к ситуации, когда невозможно сделатьперестройку. В
этой ситуации вершина с числом соединена ребром с каждой из оставшихся вершин. В самом деле, предположим, что некоторая вершина не соединена ребром с вершиной x
1
. Пройдем в нее из по ребрам (не проходя дважды по одному ребру) и продолжим этот путь, пока это возможно. Ясно, что концом этого пути может являться вершина, из которой выходит ровно одно ребро, причем не в вершину с числом x
1
. Но это означает, что можно произвести перестройку, — противоречие
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Таким образом, для конечной ситуации S = x
1
x
2
+ x
1
x
3
+. . .
. . . + Исходное неравенство верно, поскольку 1(x
2 1
+
+ x
2 2
+ . . . + x
2
n
) =
x
2 1
√
n − 1
+
√
n
− 1x
2 2
+
x
2 1
√
n − 1
+
√
n
− 1x
2 3
+. . .
. . . +
x
2 1
√
n − 1
+
√
n
− 1x
2
n
2x
1
x
2
+ 2x
1
x
3
+ . . . + 2x
1
x
n
676. Нам понадобятся две леммы:
Лемма 1. Если два треугольника и T
2
гомотетичны с положительным коэффициентом и треугольник пересекает каждую
прямую, содержащую сторону треугольника T
1
, то T
2
содержит
T
1
.
Д ока за тел ь ст во. Очевидно.
Лемма 2. Для любого конечного множества точек M и треугольника T найдется треугольник T
, гомотетичный T с положительным коэффициентом, содержащий M и содержащий на каждой своей стороне какую-то точку из Доказательство. Рассмотрим какой-то треугольник, положительно гомотетичный T и содержащий M. Если какая-то его сторона не пересекается с M, уменьшим его гомотетией с центром в противоположной этой стороне вершине и добьемся, чтобы сторона пересеклась си треугольник все еще содержал M. Повторяя это для каждой стороны, получим требуемое.
Заметим, что в условии предыдущей леммы любой положительного- мотетичный T треугольник, содержащий M, содержит также и полем- ме 1.
Теперьперейдем к решению задачи. Применим лемму 2 к T и X. Получим треугольник, обозначим его для определенности ABC. На сторонах, AC и AB естьсоответственно три точки x
A
, и из множества, среди которых могут бытьсовпадающие.
Если ABC не превосходит T по размерам, доказательство очевидно закончено. Иначе рассмотрим три треугольника AB
A
C
A
, и, положительно гомотетичные ABC с центрами в его вершинах и равные исходному T . Обозначим подмножества множества X
X
A
= X
\ AB
A
C
A
X
B
= X
\ A
B
BC
B
X
C
= X
\ Докажем еще одну лемму:
Лемма 3. Если какой-то треугольник T
, получающийся из T параллельным переносом, содержит точки и x
B
, то он не может
пересекать множество X
C
. Аналогично для других пар точек и соответствующего им множества
Таким образом, для конечной ситуации S = x
1
x
2
+ x
1
x
3
+. . .
. . . + Исходное неравенство верно, поскольку 1(x
2 1
+
+ x
2 2
+ . . . + x
2
n
) =
x
2 1
√
n − 1
+
√
n
− 1x
2 2
+
x
2 1
√
n − 1
+
√
n
− 1x
2 3
+. . .
. . . +
x
2 1
√
n − 1
+
√
n
− 1x
2
n
2x
1
x
2
+ 2x
1
x
3
+ . . . + 2x
1
x
n
676. Нам понадобятся две леммы:
Лемма 1. Если два треугольника и T
2
гомотетичны с положительным коэффициентом и треугольник пересекает каждую
прямую, содержащую сторону треугольника T
1
, то T
2
содержит
T
1
.
Д ока за тел ь ст во. Очевидно.
Лемма 2. Для любого конечного множества точек M и треугольника T найдется треугольник T
, гомотетичный T с положительным коэффициентом, содержащий M и содержащий на каждой своей стороне какую-то точку из Доказательство. Рассмотрим какой-то треугольник, положительно гомотетичный T и содержащий M. Если какая-то его сторона не пересекается с M, уменьшим его гомотетией с центром в противоположной этой стороне вершине и добьемся, чтобы сторона пересеклась си треугольник все еще содержал M. Повторяя это для каждой стороны, получим требуемое.
Заметим, что в условии предыдущей леммы любой положительного- мотетичный T треугольник, содержащий M, содержит также и полем- ме 1.
Теперьперейдем к решению задачи. Применим лемму 2 к T и X. Получим треугольник, обозначим его для определенности ABC. На сторонах, AC и AB естьсоответственно три точки x
A
, и из множества, среди которых могут бытьсовпадающие.
Если ABC не превосходит T по размерам, доказательство очевидно закончено. Иначе рассмотрим три треугольника AB
A
C
A
, и, положительно гомотетичные ABC с центрами в его вершинах и равные исходному T . Обозначим подмножества множества X
X
A
= X
\ AB
A
C
A
X
B
= X
\ A
B
BC
B
X
C
= X
\ Докажем еще одну лемму:
Лемма 3. Если какой-то треугольник T
, получающийся из T параллельным переносом, содержит точки и x
B
, то он не может
пересекать множество X
C
. Аналогично для других пар точек и соответствующего им множества
УЧЕБНЫЙ ГОД, 10
КЛАСС
401
Д ока за тел ьс т во. Предположим противное. Так как T
содержит
x
A
и x
B
, то одна из этих точек лежит по одну сторону с C относительно, иначе длина стороны больше Тогда можно заметить, что пересекает все прямые сторона значит содержит A
C
B
C
C
. Так как эти треугольники равны, то они совпадают, но тогда не может пересекать X
C
Теперьприменим лемму 2 к треугольнику T и множествам X
A
, X
B
,
X
C
, получим треугольники T
A
, T
B
, T
C
, причем на их сторонах можно выбратьточки {x
AB
, x
AC
, x
A
}, {x
BA
, x
BC
, x
B
}, {x
CA
, x
CB
, x
C
} соответственно (некоторые из них могут совпасть, лежащие в соответствующих множествах X
A
, X
B
, К точкам x
A
, x
B
, x
C
, x
AB
, x
AC
, x
BA
, x
BC
, x
CA
, применим условие задачи. Они содержатся в треугольниках и T
2
, являющихся параллельными переносами T .
Какие-то две из первых трех точек содержатся водном из этих треугольников, без ограничения общности x
A
, x
B
∈ T
1
. Тогда по лемме треугольник не пересекает множество и все три точки x
C
, x
CA
, содержатся в другом треугольнике T
2
. Отсюда следует, что множество содержится в по лемме 1; значит, треугольники и покрывают все множество X.
677. См. решение задачи 669.
678. Условие эквивалентно тому, что начиная с некоторого n число не делится на 5. Докажем это.
Покажем, что найдутся 2 соседних члена последовательности, не делящихся на 5. Предположим противное. Тогда для любого n либо получается из делением на 5, либо получается из делением на. Заметим, что всегда a
k+1
√
5a
k
, поэтому a
n+2
a
n
·
√
5/5 < a
n
. Это означает, что последовательность натуральных чисел a
1
, a
3
, a
5
, . . строго монотонно убывает, — противоречие.
Итак, доказано, что найдутся и a
k+1
, не делящиеся на 5. Докажем,
что также не делится на 5. Также последовательно получим, что, a
k+4
, . . не делятся на 5, откуда следует решение задачи. По условию. Положим a
k
= m
, тогда a
k+1
=
=
√
5m
−α, где 0 < α < 1. Далее, a
k+2
= [
√
5(
√
5m
−α)] = Но поскольку 0 <
√
5α < 3
, получаем, что 5m − 3 a
k+2
< 5m
, те. не делится на 5.
679. Первое решение. В случаете) утверждение задачи очевидно. Пусть BC Пусть R — радиус описанной окружности, и r
A
— соответственно центр и радиус окружности ω
a
КЛАСС
401
Д ока за тел ьс т во. Предположим противное. Так как T
содержит
x
A
и x
B
, то одна из этих точек лежит по одну сторону с C относительно, иначе длина стороны больше Тогда можно заметить, что пересекает все прямые сторона значит содержит A
C
B
C
C
. Так как эти треугольники равны, то они совпадают, но тогда не может пересекать X
C
Теперьприменим лемму 2 к треугольнику T и множествам X
A
, X
B
,
X
C
, получим треугольники T
A
, T
B
, T
C
, причем на их сторонах можно выбратьточки {x
AB
, x
AC
, x
A
}, {x
BA
, x
BC
, x
B
}, {x
CA
, x
CB
, x
C
} соответственно (некоторые из них могут совпасть, лежащие в соответствующих множествах X
A
, X
B
, К точкам x
A
, x
B
, x
C
, x
AB
, x
AC
, x
BA
, x
BC
, x
CA
, применим условие задачи. Они содержатся в треугольниках и T
2
, являющихся параллельными переносами T .
Какие-то две из первых трех точек содержатся водном из этих треугольников, без ограничения общности x
A
, x
B
∈ T
1
. Тогда по лемме треугольник не пересекает множество и все три точки x
C
, x
CA
, содержатся в другом треугольнике T
2
. Отсюда следует, что множество содержится в по лемме 1; значит, треугольники и покрывают все множество X.
677. См. решение задачи 669.
678. Условие эквивалентно тому, что начиная с некоторого n число не делится на 5. Докажем это.
Покажем, что найдутся 2 соседних члена последовательности, не делящихся на 5. Предположим противное. Тогда для любого n либо получается из делением на 5, либо получается из делением на. Заметим, что всегда a
k+1
√
5a
k
, поэтому a
n+2
a
n
·
√
5/5 < a
n
. Это означает, что последовательность натуральных чисел a
1
, a
3
, a
5
, . . строго монотонно убывает, — противоречие.
Итак, доказано, что найдутся и a
k+1
, не делящиеся на 5. Докажем,
что также не делится на 5. Также последовательно получим, что, a
k+4
, . . не делятся на 5, откуда следует решение задачи. По условию. Положим a
k
= m
, тогда a
k+1
=
=
√
5m
−α, где 0 < α < 1. Далее, a
k+2
= [
√
5(
√
5m
−α)] = Но поскольку 0 <
√
5α < 3
, получаем, что 5m − 3 a
k+2
< 5m
, те. не делится на 5.
679. Первое решение. В случаете) утверждение задачи очевидно. Пусть BC Пусть R — радиус описанной окружности, и r
A
— соответственно центр и радиус окружности ω
a
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
A
B
C
N
K
M
O
P
I
I
A
Рис. Поскольку AK = AM, прямая AP является биссектрисой угла, следовательно, P — середина дуги BC см. рис. Заметим, что ∠IBI
A
=
∠ICI
A
= 90
◦
, поскольку BI и CI — внутренние биссектрисы, аи внешние биссектрисы треугольника. Отсюда следует, что четырехугольник вписан в окружность с диаметром II
A
. Центр этой окружности лежит на пересечении серединного перпендикуляра к BC и прямой биссектрисе угла BAC), т. е.
находится в точке P . Поэтому P I = P I
A
= P B = 2R sin
∠BAP . Так как ∠AKI
A
=
∠AP K = 90
◦
, то ∠I
A
KP =
∠BAP , и ввиду теоремы синусов. Отсюда = r
A
⇒ I
A
N = 2P O
. Отрезок P O параллелен так как они оба перпендикулярны BC), проходит через середину P отрезка и равен, поэтому P O — средняя линия треугольника II
A
N
, поэтому O
— середина отрезка Второе решение. Как ив первом решении, предполагаем BC
Обозначим через I
A
, I
B
, соответствующие центры вневписанных окружностей, а через X — середину отрезка MN. Серединные перпендикуляры к отрезками являются биссектрисой угла A и внешней биссектрисой угла C соответственно. Поэтому точки P и X лежат на и соответственно. Как показано в первом решении, точка P
— середина дуги BC описанной окружности треугольника ABC и является серединой II
A
. P X — средняя линия треугольника KMN, поэто-
A
B
C
N
K
M
O
P
I
I
A
Рис. Поскольку AK = AM, прямая AP является биссектрисой угла, следовательно, P — середина дуги BC см. рис. Заметим, что ∠IBI
A
=
∠ICI
A
= 90
◦
, поскольку BI и CI — внутренние биссектрисы, аи внешние биссектрисы треугольника. Отсюда следует, что четырехугольник вписан в окружность с диаметром II
A
. Центр этой окружности лежит на пересечении серединного перпендикуляра к BC и прямой биссектрисе угла BAC), т. е.
находится в точке P . Поэтому P I = P I
A
= P B = 2R sin
∠BAP . Так как ∠AKI
A
=
∠AP K = 90
◦
, то ∠I
A
KP =
∠BAP , и ввиду теоремы синусов. Отсюда = r
A
⇒ I
A
N = 2P O
. Отрезок P O параллелен так как они оба перпендикулярны BC), проходит через середину P отрезка и равен, поэтому P O — средняя линия треугольника II
A
N
, поэтому O
— середина отрезка Второе решение. Как ив первом решении, предполагаем BC
Обозначим через I
A
, I
B
, соответствующие центры вневписанных окружностей, а через X — середину отрезка MN. Серединные перпендикуляры к отрезками являются биссектрисой угла A и внешней биссектрисой угла C соответственно. Поэтому точки P и X лежат на и соответственно. Как показано в первом решении, точка P
— середина дуги BC описанной окружности треугольника ABC и является серединой II
A
. P X — средняя линия треугольника KMN, поэто-
УЧЕБНЫЙ ГОД, 11
КЛАСС
403
му P X KN II
B
, а поскольку середина II
A
, P X — средняя линия треугольника I
B
I
A
I
. Поскольку XN ⊥ I
A
I
B
, точка N лежит на серединном перпендикуляре к аналогично и к I
A
I
C
), откуда NI
B
=
= N I
A
= N I
C
. Тогда N — центр описанной окружности треугольника. Заметим, что он лежит на прямой Эйлера этого треугольника,
которая также проходит через его ортоцентр I и центр окружности девяти точек O.
680. Ответ. Приведем пример, показывающий, что N 209. Разделим таблицу на два прямоугольника 20 × 10 по вертикали. В первом прямоугольнике расставим числа от 1 до 200 по строкам в возрастающем порядке (впервой строке — от 1 до 10, во второй — от 11 доит. д. Во втором расставим также числа от 201 до 400. Тогда максимальная разность между числами в любой строке равна 210 − 1 = 209, а в любом столбце 191 − 1 = Поэтому N Покажем, что N = 209 подходит. Рассмотрим два множества чисел:
от 1 дои от 300 до 400. Отметим все строки и столбцы, в которых есть числа первого множества, красным, а второго — синим. Покажем, что красным отмечено не менее 20 линий (те. строк или столбцов, а синим не менее 21 (тогда какая-то линия будет отмечена и красными синими в ней максимальная разность чисел будет не меньше, чем 300−91 = что и требовалось).
Пустькрасным отмечено i строки столбцов. Тогда все первое множество находится в клетках их пересечения, поэтому ij 91. Отсюда + j
2
√
ij
2
√
91 > 19
. Аналогично, для второго множества сумма числа строки столбцов i + j 2
√
101 > 20
КЛАСС
403
му P X KN II
B
, а поскольку середина II
A
, P X — средняя линия треугольника I
B
I
A
I
. Поскольку XN ⊥ I
A
I
B
, точка N лежит на серединном перпендикуляре к аналогично и к I
A
I
C
), откуда NI
B
=
= N I
A
= N I
C
. Тогда N — центр описанной окружности треугольника. Заметим, что он лежит на прямой Эйлера этого треугольника,
которая также проходит через его ортоцентр I и центр окружности девяти точек O.
680. Ответ. Приведем пример, показывающий, что N 209. Разделим таблицу на два прямоугольника 20 × 10 по вертикали. В первом прямоугольнике расставим числа от 1 до 200 по строкам в возрастающем порядке (впервой строке — от 1 до 10, во второй — от 11 доит. д. Во втором расставим также числа от 201 до 400. Тогда максимальная разность между числами в любой строке равна 210 − 1 = 209, а в любом столбце 191 − 1 = Поэтому N Покажем, что N = 209 подходит. Рассмотрим два множества чисел:
от 1 дои от 300 до 400. Отметим все строки и столбцы, в которых есть числа первого множества, красным, а второго — синим. Покажем, что красным отмечено не менее 20 линий (те. строк или столбцов, а синим не менее 21 (тогда какая-то линия будет отмечена и красными синими в ней максимальная разность чисел будет не меньше, чем 300−91 = что и требовалось).
Пустькрасным отмечено i строки столбцов. Тогда все первое множество находится в клетках их пересечения, поэтому ij 91. Отсюда + j
2
√
ij
2
√
91 > 19
. Аналогично, для второго множества сумма числа строки столбцов i + j 2
√
101 > 20
1 ... 51 52 53 54 55 56 57 58 ... 64
11 класс. Первое решение. Без ограничения общности можно считать α −
− β 0, γ − τ 0. Положим a =
α + β
2
, b =
α − β
2
, c =
γ + τ
2
, d =
γ − тогда условие задачи перепишется в виде sin ax cos bx = sin cx cos где a > b 0, c > d Наименьший положительный корень левой части — число
π
a
или
π
2b
, а правой или. Если a = c, то cos bx = cos dx и, значит, b = Из этих равенств следует требуемое.
Пусть x
0
=
π
a
. Если, то a = 2d, и из равенства функций sin 2dx cos bx = sin cx cos следует sin dx cos bx = sin cx.
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Приравнивая наименьшие положительные корни левой и правой частей,
получаем c = d что невозможно) либо c = 2b. В последнем случае sin bx = sin dx
, так что b = d. Тогда sin ax = sin cx, те. Также ив случае. Наконец, в случае
π
2b
=
π
2d
также получаем b = d и a = Второе решение αx + sin βx = sin γx + sin τ Продифференцируем данное равенство и положим x = 0:
α cos αx + β cos βx = γ cos γx + τ cos τ x
⇒ α + β = γ + Возьмем третью производную и подставим x = 0:
−α
3
cos αx
− β
3
cos βx =
−γ
3
cos γx
− τ
3
cos τ x
⇒ α
3
+ β
3
= γ
3
+ Мы получили систему + β = γ + τ,
α
3
+ β
3
= γ
3
+ τ
3
⇒
%
α
2
− αβ + β
2
= γ
2
− γτ + τ
2
,
α
2
+ 2αβ + β
2
= γ
2
+ 2γτ + τ
2
⇒
⇒
%
αβ = γτ,
α + β = γ + τ
⇒ пары (α, β) и (γ, τ) совпадают, что и требовалось. См. решение задачи 674.
683. Предположим что f = g. Пусть (x) = c
n
x
n
+ c
n−1
x
n−1
+ . . . + c
1
x + и) = d
k
x
k
+ d
k−1
x
k−1
+ . . . + d
1
x + Поскольку 0 c
i
m < b, в b-ичной системе счисления число f(b) будет записываться как c
n
c
n−1
. . . c
1
c
0
. Если все коэффициенты многочлена также меньше b, то из единственности записи числа f(b) = g(b) в b-ичной системе счисления мы можем заключить, что коэффициенты многочленов
f
и g совпадают, а значит, f = g. Пусть i — наименьший номер, для которого d
i
> b
. Тогда d
i
= bq+r
. Рассмотрим вместо многочлена g новый многочлену которого коэффициент заменен на r, а коэффициент на d
i+1
+ q
. Тогда g
1
(b) = не изменится, а g
1
(a) < g(a)
, ибо+ d
i+1
a
i+1
= (bq + r)a
i
+ d
i+1
a
i+1
>
> (aq + r)a
i
+ d
i+1
a
i+1
= ra
i
+ (d
i+1
+ Далее продолжим эту процедуру со следующим номером i. На каждом шаге i увеличивается хотя бы на 1, и всегда не больше n, поэтому не более чем через n шагов процесс остановится и мы придем к некоторому многочлену, у которого все коэффициенты будут целыми неотрицательными и меньшими. Тогда по единственности записи числа f(b) = в b- ичной системе счисления следует, что многочлены f и совпадают, но это невозможно, ибо f(a) = g(a) > g
j
(a)
. Противоречие
Приравнивая наименьшие положительные корни левой и правой частей,
получаем c = d что невозможно) либо c = 2b. В последнем случае sin bx = sin dx
, так что b = d. Тогда sin ax = sin cx, те. Также ив случае. Наконец, в случае
π
2b
=
π
2d
также получаем b = d и a = Второе решение αx + sin βx = sin γx + sin τ Продифференцируем данное равенство и положим x = 0:
α cos αx + β cos βx = γ cos γx + τ cos τ x
⇒ α + β = γ + Возьмем третью производную и подставим x = 0:
−α
3
cos αx
− β
3
cos βx =
−γ
3
cos γx
− τ
3
cos τ x
⇒ α
3
+ β
3
= γ
3
+ Мы получили систему + β = γ + τ,
α
3
+ β
3
= γ
3
+ τ
3
⇒
%
α
2
− αβ + β
2
= γ
2
− γτ + τ
2
,
α
2
+ 2αβ + β
2
= γ
2
+ 2γτ + τ
2
⇒
⇒
%
αβ = γτ,
α + β = γ + τ
⇒ пары (α, β) и (γ, τ) совпадают, что и требовалось. См. решение задачи 674.
683. Предположим что f = g. Пусть (x) = c
n
x
n
+ c
n−1
x
n−1
+ . . . + c
1
x + и) = d
k
x
k
+ d
k−1
x
k−1
+ . . . + d
1
x + Поскольку 0 c
i
m < b, в b-ичной системе счисления число f(b) будет записываться как c
n
c
n−1
. . . c
1
c
0
. Если все коэффициенты многочлена также меньше b, то из единственности записи числа f(b) = g(b) в b-ичной системе счисления мы можем заключить, что коэффициенты многочленов
f
и g совпадают, а значит, f = g. Пусть i — наименьший номер, для которого d
i
> b
. Тогда d
i
= bq+r
. Рассмотрим вместо многочлена g новый многочлену которого коэффициент заменен на r, а коэффициент на d
i+1
+ q
. Тогда g
1
(b) = не изменится, а g
1
(a) < g(a)
, ибо+ d
i+1
a
i+1
= (bq + r)a
i
+ d
i+1
a
i+1
>
> (aq + r)a
i
+ d
i+1
a
i+1
= ra
i
+ (d
i+1
+ Далее продолжим эту процедуру со следующим номером i. На каждом шаге i увеличивается хотя бы на 1, и всегда не больше n, поэтому не более чем через n шагов процесс остановится и мы придем к некоторому многочлену, у которого все коэффициенты будут целыми неотрицательными и меньшими. Тогда по единственности записи числа f(b) = в b- ичной системе счисления следует, что многочлены f и совпадают, но это невозможно, ибо f(a) = g(a) > g
j
(a)
. Противоречие
УЧЕБНЫЙ ГОД, КЛАСС. Назовем палиндромом слово, читающееся одинаково справа налево и слева направо. Докажем индукцией по n, что через n минут слово на любой полоске можно будет разрезатьна два палиндрома (один из которых, возможно, пустой. Тогда, если эти палиндромы переставитьме- стами, получится тоже слово, записанное в обратном порядке.
При n = 0, 1 это, очевидно, верно. Пусть n > 1. Без ограничения общности можно считать, что на первом ходу Боря приписал к своему слову А
слева, те. после первого хода написаны слова Аи АБ. Посадим Антона и Валю в этот момент за полоски, на которых написаны буквы Аи В, и попросим их повторятьдействия Ани и Бори (те. если Аня приписывает к началу Борино слово, то Антон приписывает Валино, и т. п. Получившийся процесс длится n − 1 минуту. Тогда в конце процесса слова Антона и Вали можно разрезатьна два палиндрома каждое, а если в них заменить каждую букву В на последовательность АБ, то получатся слова Ани и Бо- ри.
Докажем, что если к палиндрому из букв Аи В приписатьв конце Аи заменитькаждую букву В на АБ, то получится палиндром. Действительно, пустьперед первой В стояло букв А, между первой и второй — x
1
,
. . . , после последней, й буквы В — букв А. Тогда x
i
= при любом 1 i k. В измененном слове перед первой буквой Б будет x
0
+ букв А, между первой и второй — x
1
+ 1
, . . . , после последней, й буквы
Б — x
k
+ букв А. Поскольку x
i
+ 1 = x
k+1−i
+ 1
, то полученное слово также будет палиндромом.
Пусть, скажем, Антоново слово из букв Аи В разрезается на палиндромы и T . Пусть и T
— слова, полученные заменой В на АБ. Если слово T
непусто, то Аи А — палиндромы, слово начинается с А
(T
А = АT
А), и поэтому T
— тоже палиндром. Тогда Анино слово разрезается на палиндромы Аи. Если же слово пусто, то А палиндром) является требуемым разбиением. Доказательство для
Бориного слова аналогично. В силу рациональности коэффициентов многочлена, можно считать, что он приведенный. Из теоремы Виета следует, что если a, b, c длины сторон треугольника, то 2p = a + b + c = A, ab + bc + ba = B, abc =
= рациональны. Тогда из формулы Герона S
2
= p
· (p
3
− Ap
2
+ Bp
− следует рациональность S
2
. (Действительно, если f(x) = 0 данное кубическое уравнение, то f (p)
, так как f(x) = (x − a)(x − b)(x − Из равенств h
a
=
2S
a
, h
b
=
2S
b
, следует, что h
a
, h
b
, корни уравнения
При n = 0, 1 это, очевидно, верно. Пусть n > 1. Без ограничения общности можно считать, что на первом ходу Боря приписал к своему слову А
слева, те. после первого хода написаны слова Аи АБ. Посадим Антона и Валю в этот момент за полоски, на которых написаны буквы Аи В, и попросим их повторятьдействия Ани и Бори (те. если Аня приписывает к началу Борино слово, то Антон приписывает Валино, и т. п. Получившийся процесс длится n − 1 минуту. Тогда в конце процесса слова Антона и Вали можно разрезатьна два палиндрома каждое, а если в них заменить каждую букву В на последовательность АБ, то получатся слова Ани и Бо- ри.
Докажем, что если к палиндрому из букв Аи В приписатьв конце Аи заменитькаждую букву В на АБ, то получится палиндром. Действительно, пустьперед первой В стояло букв А, между первой и второй — x
1
,
. . . , после последней, й буквы В — букв А. Тогда x
i
= при любом 1 i k. В измененном слове перед первой буквой Б будет x
0
+ букв А, между первой и второй — x
1
+ 1
, . . . , после последней, й буквы
Б — x
k
+ букв А. Поскольку x
i
+ 1 = x
k+1−i
+ 1
, то полученное слово также будет палиндромом.
Пусть, скажем, Антоново слово из букв Аи В разрезается на палиндромы и T . Пусть и T
— слова, полученные заменой В на АБ. Если слово T
непусто, то Аи А — палиндромы, слово начинается с А
(T
А = АT
А), и поэтому T
— тоже палиндром. Тогда Анино слово разрезается на палиндромы Аи. Если же слово пусто, то А палиндром) является требуемым разбиением. Доказательство для
Бориного слова аналогично. В силу рациональности коэффициентов многочлена, можно считать, что он приведенный. Из теоремы Виета следует, что если a, b, c длины сторон треугольника, то 2p = a + b + c = A, ab + bc + ba = B, abc =
= рациональны. Тогда из формулы Герона S
2
= p
· (p
3
− Ap
2
+ Bp
− следует рациональность S
2
. (Действительно, если f(x) = 0 данное кубическое уравнение, то f (p)
, так как f(x) = (x − a)(x − b)(x − Из равенств h
a
=
2S
a
, h
b
=
2S
b
, следует, что h
a
, h
b
, корни уравнения
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
x
2
−
4S
2
b
2
x
2
−
4S
2
c
2
= имеющего рациональные коэффициента в силу тождеств+ c
2
a
2
+ a
2
b
2
) =
4S
2
C
2
(B
2
− 2AC),
16S
4
a
2
b
2
+
16S
4
b
2
c
2
+
+
16S
4
c
2
a
2
=
16(S
2
)
2
C
2
(a
2
+ b
2
+ c
2
) =
16(S
2
)
2
C
2
(A
2
− 2B),
64S
6
a
2
b
2
c
2
=
64(S
2
)
3
C
2
686. См. решение задачи 671.
687. Построим граф, вершины которого соответствуют городам, а ребра дорогам. Выберем в этом графе самый длинный путь S, пустьверши- ны A и B — концы этого пути. Из условия задачи следует, что в путине более 99 вершин. Отметим, что концы пути S — вершины A и B не могут бытьсмежны с вершинами не из S иначе путьможно удлинить).
А в случае, когда вершины A и B смежны и наш путьзамыкается в цикл,
никакая вершина пути S по аналогичным причинам не может бытьсмежна с вершиной не из S.
1) Рассмотрим случай, когда вне более 98 вершин. В этом случае рассмотрим любые две вершины и Y
2
, не входящие в путь S, и концы пути A и B. Среди этих четырех вершин должны бытьпроведены хотя бы два ребра. Так как ни A, ни B не могут бытьсмежны с вершинами не из то концы пути A и B соединены ребром.
Таким образом, путь S замыкается в цикли тогда ни одна из вершин путине смежна с вершиной не из S. Рассмотрим четверку из любых двух вершин и пути S и любых двух вершин и Y
2
, не входящих в S. Так как между этими четырьмя вершинами проведено хотя бы два ребра, то одно из них соединяет и X
2
, а другое — и Y
2
. Таким образом, в рассматриваемом случае все вершины пути S попарно смежны и все вершины не из S также попарно смежны. Отсюда очевидно следует утверждение задачи) Рассмотрим случай, когда вне пути S лежит ровно одна вершина.
Пустьэто вершина D. Если D не смежна ни с одной из вершин пути то рассмотрим D и любые три вершины пути S. Поскольку среди этих четырех вершин проведено хотя бы два ребра, то среди любых трех вершин пути S проведено хотя бы два ребра. Следовательно, для любой вершины из S естьне более одной не смежной с ней вершины пути S. Поскольку вершин пути S нельзя разбить на пары не соединенных ребром, тов должна бытьвершина, смежная со всеми остальными вершинами S. Эта вершина в паре с D удовлетворяет утверждению задачи
x
2
−
4S
2
b
2
x
2
−
4S
2
c
2
= имеющего рациональные коэффициента в силу тождеств+ c
2
a
2
+ a
2
b
2
) =
4S
2
C
2
(B
2
− 2AC),
16S
4
a
2
b
2
+
16S
4
b
2
c
2
+
+
16S
4
c
2
a
2
=
16(S
2
)
2
C
2
(a
2
+ b
2
+ c
2
) =
16(S
2
)
2
C
2
(A
2
− 2B),
64S
6
a
2
b
2
c
2
=
64(S
2
)
3
C
2
686. См. решение задачи 671.
687. Построим граф, вершины которого соответствуют городам, а ребра дорогам. Выберем в этом графе самый длинный путь S, пустьверши- ны A и B — концы этого пути. Из условия задачи следует, что в путине более 99 вершин. Отметим, что концы пути S — вершины A и B не могут бытьсмежны с вершинами не из S иначе путьможно удлинить).
А в случае, когда вершины A и B смежны и наш путьзамыкается в цикл,
никакая вершина пути S по аналогичным причинам не может бытьсмежна с вершиной не из S.
1) Рассмотрим случай, когда вне более 98 вершин. В этом случае рассмотрим любые две вершины и Y
2
, не входящие в путь S, и концы пути A и B. Среди этих четырех вершин должны бытьпроведены хотя бы два ребра. Так как ни A, ни B не могут бытьсмежны с вершинами не из то концы пути A и B соединены ребром.
Таким образом, путь S замыкается в цикли тогда ни одна из вершин путине смежна с вершиной не из S. Рассмотрим четверку из любых двух вершин и пути S и любых двух вершин и Y
2
, не входящих в S. Так как между этими четырьмя вершинами проведено хотя бы два ребра, то одно из них соединяет и X
2
, а другое — и Y
2
. Таким образом, в рассматриваемом случае все вершины пути S попарно смежны и все вершины не из S также попарно смежны. Отсюда очевидно следует утверждение задачи) Рассмотрим случай, когда вне пути S лежит ровно одна вершина.
Пустьэто вершина D. Если D не смежна ни с одной из вершин пути то рассмотрим D и любые три вершины пути S. Поскольку среди этих четырех вершин проведено хотя бы два ребра, то среди любых трех вершин пути S проведено хотя бы два ребра. Следовательно, для любой вершины из S естьне более одной не смежной с ней вершины пути S. Поскольку вершин пути S нельзя разбить на пары не соединенных ребром, тов должна бытьвершина, смежная со всеми остальными вершинами S. Эта вершина в паре с D удовлетворяет утверждению задачи
УЧЕБНЫЙ ГОД, 11
КЛАСС
407
Если концы максимального пути A и B смежны, то, как мы доказали,
вершина D не смежна ни с одной из вершин пути S, а этот случай уже разобран.
Остается рассмотретьпоследний случай, когда концы путине смежны и вершина D смежна хотя бы с одной из вершин пути S. Рассмотрим вершины A, B, D и произвольную четвертую вершину Z естественно, лежащую на пути S). Так как A, B, и D попарно не смежны, то Z смежна хотя бы с двумя вершинами из A, B, и D. Пусть D смежна с вершиной пути S. Одна из соседних с X вершин путине является концом пути.
Можно считать, что это первая вершина Y , лежащая на пути изв по ребрам S. Если Y смежна сто, пройдя от A к X по пути S, далее по ребрами и затем по пути S от Y к B, мы обойдем все вершины нашего графа ровно по одному разу, что невозможно по условию. Если жене смежна сто, как мы доказали, эта вершина смежна и си с B. Тогда пройдем по ребру DX, далее по пути S от X к A, по ребрами и затем по пути S от его конца B до вершины, соседней сна пути S, получился путь, проходящей по каждой вершине нашего графа ровно один раз, которого по условию не существует. Следовательно, и этот случай не возможен.
Таким образом, мы рассмотрели все случаи ив тех из них, которые возможны, убедилисьв справедливости утверждения задачи. Первое решение. Обозначим вершины получающегося тетраэдра, и D
2
. Тогда тетраэдры и A
2
B
2
C
2
D
2
гомоте- тичны, причем эта гомотетия переводит центр вписанной сферы тетраэдра
ABCD
в центр описанной сферы тетраэдра A
2
B
2
C
2
D
2
. Покажем, что она переводит центр вписанной сферы тетраэдра ABCD в центр описанной сферы тетраэдра Заметим, что точка A
2
— радикальный центр трех точек B, C, D и вписанной в тетраэдр ABCD сферы, поскольку является точкой пересечения трех радикальных плоскостей (именно эти плоскости рассматриваются в задаче. В связи с этим точка равноудалена от вершин B, C и. Поэтому, прямая, проходящая через перпендикулярно плоскости, проходит через центр описанной сферы ABCD. Именно эта прямая является образом при гомотетии прямой, проходящей через перпендикулярно. Точка пересечения таких прямых — центр вписанной сферы ABCD — переходит таким образом в центр описанной сферы. Что и требовалось.
Второе решение. Пусть O, O
A
, O
B
, O
C
, O
D
— центры описанных сфер тетраэдров ABCD, BCDI, ACDI, ABDI, ABCI соответственно — центр вписанной в ABCD сферы. Покажем, что O — центр описан
КЛАСС
407
Если концы максимального пути A и B смежны, то, как мы доказали,
вершина D не смежна ни с одной из вершин пути S, а этот случай уже разобран.
Остается рассмотретьпоследний случай, когда концы путине смежны и вершина D смежна хотя бы с одной из вершин пути S. Рассмотрим вершины A, B, D и произвольную четвертую вершину Z естественно, лежащую на пути S). Так как A, B, и D попарно не смежны, то Z смежна хотя бы с двумя вершинами из A, B, и D. Пусть D смежна с вершиной пути S. Одна из соседних с X вершин путине является концом пути.
Можно считать, что это первая вершина Y , лежащая на пути изв по ребрам S. Если Y смежна сто, пройдя от A к X по пути S, далее по ребрами и затем по пути S от Y к B, мы обойдем все вершины нашего графа ровно по одному разу, что невозможно по условию. Если жене смежна сто, как мы доказали, эта вершина смежна и си с B. Тогда пройдем по ребру DX, далее по пути S от X к A, по ребрами и затем по пути S от его конца B до вершины, соседней сна пути S, получился путь, проходящей по каждой вершине нашего графа ровно один раз, которого по условию не существует. Следовательно, и этот случай не возможен.
Таким образом, мы рассмотрели все случаи ив тех из них, которые возможны, убедилисьв справедливости утверждения задачи. Первое решение. Обозначим вершины получающегося тетраэдра, и D
2
. Тогда тетраэдры и A
2
B
2
C
2
D
2
гомоте- тичны, причем эта гомотетия переводит центр вписанной сферы тетраэдра
ABCD
в центр описанной сферы тетраэдра A
2
B
2
C
2
D
2
. Покажем, что она переводит центр вписанной сферы тетраэдра ABCD в центр описанной сферы тетраэдра Заметим, что точка A
2
— радикальный центр трех точек B, C, D и вписанной в тетраэдр ABCD сферы, поскольку является точкой пересечения трех радикальных плоскостей (именно эти плоскости рассматриваются в задаче. В связи с этим точка равноудалена от вершин B, C и. Поэтому, прямая, проходящая через перпендикулярно плоскости, проходит через центр описанной сферы ABCD. Именно эта прямая является образом при гомотетии прямой, проходящей через перпендикулярно. Точка пересечения таких прямых — центр вписанной сферы ABCD — переходит таким образом в центр описанной сферы. Что и требовалось.
Второе решение. Пусть O, O
A
, O
B
, O
C
, O
D
— центры описанных сфер тетраэдров ABCD, BCDI, ACDI, ABDI, ABCI соответственно — центр вписанной в ABCD сферы. Покажем, что O — центр описан
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
ной сферы тетраэдра O
A
O
B
O
C
O
D
. Действительно, отрезки OO
A
, перпендикулярны плоскостям BCD, ACD, ICD соответственно, причем плоскость ICD составляет равные углы с плоскостями и ACD; поэтому равнобедренный, OO
A
= OO
B
. Остальные равенства получаются аналогично. Тогда тетраэдры A
1
B
1
C
1
D
1
и
O
A
O
B
O
C
O
D
гомотетичны.
Отложим от точки вектор, аналогично получаются точки B
2
, C
2
, D
2
. Тогда, поскольку плоскости и параллельны, то плоскость также им параллельна кроме того,
поскольку O
A
O
B
O
C
— серединный перпендикуляр ка расстояние между и вдвое меньше расстояния между I и то A
2
B
2
C
2
— плоскость, данная в условии. Но тогда из равенства OA
2
=
= OO
A
+
IA
1 и аналогичных равенств следует требуемое г класс. Назовем целочисленную точку узлом. Если на каждой вертикальной прямой все узлы одного цвета, то выберем любой узел (пустьон цвета. Проведем через него две перпендикулярные прямые, идущие под углом
45
◦
к вертикали и выберем на этих прямых точки цветов 2 и 3 (это возможно, поскольку существуют вертикали этих цветов. Полученный треугольник будет искомым. Аналогично, если все горизонтали одного цвета.
Пустьестьвертикальv, на которой присутствуют ровно два цвета
(скажем, 1 и 2). Тогда выберем любой узел C цвета 3, узел A на v, находящийся сна одной горизонтали (пустьузел A цвета 1) и узел B цвета на Если же естьвертикальv, на которой встречаются все три цвета, то выберем горизонтальна которой не все точки одного цвета. Пустьточ- ка A их пересечения имеет цвет 1, тогда выберем на h точку B цвета, отличного от 1 (скажем, цвета 2), а на v точку C третьего цвета. Обозначим через O центр вписанной окружности четырехугольника. Поскольку внешняя и внутренняя биссектрисы угла перпендикулярны. Высота треугольника ABK перпендикулярна, поэтому AK
1
OB. Аналогично, BK
1
OA. Следовательно параллелограмм, и точка получается из точки параллельным переносом на вектор. Таким же образом, точка
L
1
получается из точки C параллельным переносом на вектор. Поэтому УЧЕБНЫЙ ГОД, 9
КЛАСС
409
O
A
B
C
D
K
L
M
N
K
1
L
1
M
1
N
1
Рис. Также получаем, что, откуда следует, что параллелограмм. Ответ. За 4005 вопросов.
Занумеруем коробочки (и соответственно шарики в них) числами от дои будем вопрос обозначатьпарой номеров коробочек. Будем называтьнебелые шарики черными.
Покажем, что за 4005 вопросов можно найти два белых шарика. Зададим вопросы (1, 2), (1, 3), . . . , (1, 2004), (2, 3), (2, 4), . . . , (2, 2004). Если все ответы положительны, то первый и второй шарики белые (пусть, например, первый — черный тогда естьеще хотя бы один черный шарик,
который вместе с первым составляет черную пару. Если же хотя бы один ответ отрицателен (скажем, на вопрос, включающий первый шарик, то первый шарик черный тогда белыми являются ровноте шарики, про которые (в паре с черным первым) ответ был положительными в этом случае мы найдем даже все белые, которых хотя бы два.
Пустьсуществует алгоритм, позволяющий гарантированно найти два белых шарика за меньшее число вопросов. Будем отвечать на все вопросы положительно. Тогда максимум после 4004 вопросов игрок сможет указатьна какие-то (для определенности, первую и вторую) коробочки и заявить, что в них шарики белые. При этом какого-то из вопросов вида, или (2, n) (скажем, вопроса (1, k)) задано не будет, ибо таких вопросов всего 4005. Положим теперьв ю и ю коробочку черные шарики
ной сферы тетраэдра O
A
O
B
O
C
O
D
. Действительно, отрезки OO
A
, перпендикулярны плоскостям BCD, ACD, ICD соответственно, причем плоскость ICD составляет равные углы с плоскостями и ACD; поэтому равнобедренный, OO
A
= OO
B
. Остальные равенства получаются аналогично. Тогда тетраэдры A
1
B
1
C
1
D
1
и
O
A
O
B
O
C
O
D
гомотетичны.
Отложим от точки вектор, аналогично получаются точки B
2
, C
2
, D
2
. Тогда, поскольку плоскости и параллельны, то плоскость также им параллельна кроме того,
поскольку O
A
O
B
O
C
— серединный перпендикуляр ка расстояние между и вдвое меньше расстояния между I и то A
2
B
2
C
2
— плоскость, данная в условии. Но тогда из равенства OA
2
=
= OO
A
+
IA
1 и аналогичных равенств следует требуемое г класс. Назовем целочисленную точку узлом. Если на каждой вертикальной прямой все узлы одного цвета, то выберем любой узел (пустьон цвета. Проведем через него две перпендикулярные прямые, идущие под углом
45
◦
к вертикали и выберем на этих прямых точки цветов 2 и 3 (это возможно, поскольку существуют вертикали этих цветов. Полученный треугольник будет искомым. Аналогично, если все горизонтали одного цвета.
Пустьестьвертикальv, на которой присутствуют ровно два цвета
(скажем, 1 и 2). Тогда выберем любой узел C цвета 3, узел A на v, находящийся сна одной горизонтали (пустьузел A цвета 1) и узел B цвета на Если же естьвертикальv, на которой встречаются все три цвета, то выберем горизонтальна которой не все точки одного цвета. Пустьточ- ка A их пересечения имеет цвет 1, тогда выберем на h точку B цвета, отличного от 1 (скажем, цвета 2), а на v точку C третьего цвета. Обозначим через O центр вписанной окружности четырехугольника. Поскольку внешняя и внутренняя биссектрисы угла перпендикулярны. Высота треугольника ABK перпендикулярна, поэтому AK
1
OB. Аналогично, BK
1
OA. Следовательно параллелограмм, и точка получается из точки параллельным переносом на вектор. Таким же образом, точка
L
1
получается из точки C параллельным переносом на вектор. Поэтому УЧЕБНЫЙ ГОД, 9
КЛАСС
409
O
A
B
C
D
K
L
M
N
K
1
L
1
M
1
N
1
Рис. Также получаем, что, откуда следует, что параллелограмм. Ответ. За 4005 вопросов.
Занумеруем коробочки (и соответственно шарики в них) числами от дои будем вопрос обозначатьпарой номеров коробочек. Будем называтьнебелые шарики черными.
Покажем, что за 4005 вопросов можно найти два белых шарика. Зададим вопросы (1, 2), (1, 3), . . . , (1, 2004), (2, 3), (2, 4), . . . , (2, 2004). Если все ответы положительны, то первый и второй шарики белые (пусть, например, первый — черный тогда естьеще хотя бы один черный шарик,
который вместе с первым составляет черную пару. Если же хотя бы один ответ отрицателен (скажем, на вопрос, включающий первый шарик, то первый шарик черный тогда белыми являются ровноте шарики, про которые (в паре с черным первым) ответ был положительными в этом случае мы найдем даже все белые, которых хотя бы два.
Пустьсуществует алгоритм, позволяющий гарантированно найти два белых шарика за меньшее число вопросов. Будем отвечать на все вопросы положительно. Тогда максимум после 4004 вопросов игрок сможет указатьна какие-то (для определенности, первую и вторую) коробочки и заявить, что в них шарики белые. При этом какого-то из вопросов вида, или (2, n) (скажем, вопроса (1, k)) задано не будет, ибо таких вопросов всего 4005. Положим теперьв ю и ю коробочку черные шарики
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
а вовсе остальные — белые. Тогда все наши ответы будут верны, а указанный игроком первый шарик окажется черным. Противоречие. Уменьшим каждое слагаемое следующим образом 1 + x
1
+ x
1
x
2
+
1 1 + x
2
+ x
2
x
3
+ . . . +
1 1 + x
n
+ x
n
x
1
>
>
1 1 + x
1
+ x
1
x
2
+ x
1
x
2
x
3
+ . . . + x
1
x
2
. . . x
n−1
+
+
1 1 + x
2
+ x
2
x
3
+ . . . + x
2
x
3
. . . x
n
+ . . .
. . . +
1 1 + x
n
+ x
n
x
1
+ . . . + x
n
x
1
x
2
. . . x
n−2
.
Домножая числительи знаменательв первом слагаемом на x
n
, во втором — на x
n
x
1
, . . . , в м — на x
n
x
1
x
2
. . . и учитывая, что. . . x
n
= 1
, получаем 1 + x
1
+ x
1
x
2
+
1 1 + x
2
+ x
2
x
3
+ . . . +
1 1 + x
n
+ x
n
x
1
>
>
x
n
x
n
+ x
n
x
1
+ x
n
x
1
x
2
+ . . . + x
1
. . . x
n
+
+
x
n
x
1
x
n
x
1
+ x
n
x
1
x
2
+ . . . + x
n
x
1
. . . x
n−1
+ x
n
+
+
x
n
x
1
x
2
x
n
x
1
x
2
+ x
n
x
1
x
2
x
3
+ . . . + x
n
x
1
. . . x
n−1
+ x
n
+ x
n
x
1
+ . . .
. . . +
x
n
x
1
x
2
. . . x
n−1
x
n
x
1
. . . x
n−1
+ x
n
+ x
n
x
1
+ . . . + x
n
x
1
. . . x
n−2
= 1.
а вовсе остальные — белые. Тогда все наши ответы будут верны, а указанный игроком первый шарик окажется черным. Противоречие. Уменьшим каждое слагаемое следующим образом 1 + x
1
+ x
1
x
2
+
1 1 + x
2
+ x
2
x
3
+ . . . +
1 1 + x
n
+ x
n
x
1
>
>
1 1 + x
1
+ x
1
x
2
+ x
1
x
2
x
3
+ . . . + x
1
x
2
. . . x
n−1
+
+
1 1 + x
2
+ x
2
x
3
+ . . . + x
2
x
3
. . . x
n
+ . . .
. . . +
1 1 + x
n
+ x
n
x
1
+ . . . + x
n
x
1
x
2
. . . x
n−2
.
Домножая числительи знаменательв первом слагаемом на x
n
, во втором — на x
n
x
1
, . . . , в м — на x
n
x
1
x
2
. . . и учитывая, что. . . x
n
= 1
, получаем 1 + x
1
+ x
1
x
2
+
1 1 + x
2
+ x
2
x
3
+ . . . +
1 1 + x
n
+ x
n
x
1
>
>
x
n
x
n
+ x
n
x
1
+ x
n
x
1
x
2
+ . . . + x
1
. . . x
n
+
+
x
n
x
1
x
n
x
1
+ x
n
x
1
x
2
+ . . . + x
n
x
1
. . . x
n−1
+ x
n
+
+
x
n
x
1
x
2
x
n
x
1
x
2
+ x
n
x
1
x
2
x
3
+ . . . + x
n
x
1
. . . x
n−1
+ x
n
+ x
n
x
1
+ . . .
. . . +
x
n
x
1
x
2
. . . x
n−1
x
n
x
1
. . . x
n−1
+ x
n
+ x
n
x
1
+ . . . + x
n
x
1
. . . x
n−2
= 1.
1 ... 52 53 54 55 56 57 58 59 ... 64
693. Ответ. Существуют.
Мы будем искатьтакие числа в виде m = a
2
, n = b
3
, p = c
2
, q =
= d
3
, где a, b, c, d — натуральные. Тогда условие переформулируется такте+ c) = (d −
− b)(d
2
+ bd + b
2
)
. Зафиксируем такие b и d, что b = d − 1 > 2004. Тогда условиям удовлетворяет пара c =
d
2
+ bd + b
2
− 1 2
, a =
d
2
+ bd + b
2
+ 1 эти числа целые, поскольку b и d разной четности. Кроме того, a > c >
> b
2
> d > b > Замечание. Можно показать, что для любой четверки чисел, удовлетворяющей условию, числа, целые. Ответ. Всегда.
Построим граф, вершины которого соответствуют телефонам, а ребра проводам. Рассмотрим наименьший набор вершин данного графа такой, что среди соединяющих эти вершины ребер присутствуют ребра всех четырех цветов. Удалим из этого набора произвольную вершину. По
УЧЕБНЫЙ ГОД, 9
КЛАСС
411
скольку набор был наименьший, среди ребер, соединяющих оставшиеся вершины, присутствуют уже не все цвета. Если среди этих ребер присутствуют ребра ровно трех цветов, то искомый набор найден. В противном случае среди ребер, выходящих из удаленной вершины в другие вершины нашего набора, присутствуют как минимум два цвета, которые исчезнут после удаления этой вершины. Рассмотрим два ребра этих цветов, выходящие из удаленной вершины в другие вершины набора. Тогда ребро,
соединяющее их концы, должно иметьцвет, отличный от цветов этих двух ребер. Таким образом, в графе нашелся треугольник, все ребра которого имеют попарно различные цвета. Это означает, что требуемый набор вершин можно выбратьвсегда.
695. Ответ. 51 хорошая пара.
Пример: сначала расставим числа подряда затем поменяем местами числа 2 и 3, 4 и 5, . . . , 98 и 99. В полученной расстановке, 3, 2, 5, 4, . . . , 99, 98, хорошими парами являются в точности пары, 3)
, (3, 2), (5, 4), (7, 6), . . . , (97, 96), (99, 98), (98, Докажем, что хороших парне менее 51. Заметим, что среди любых двух пересекающихся пар хотя бы одна — хорошая. Действительно, пусть, a
2
, a
3
, a
4
, a
5
— такие подряд идущие числа, что пары (a
2
, и (a
3
, не являются хорошими. Не умаляя общности, можно считать, что a
1
>
> a
2
< a
3
> a
4
< a
5
. С другой стороны, пара (a
3
, не является хорошей, значит, a
1
> a
2
> a
5
, пара (a
2
, не является хорошей, значит a
4
> a
1
. Тогда a
1
> a
2
> a
5
> a
4
> a
1
, что невозможно, значит,
либо пара (a
2
, a
3
)
, либо пара (a
3
, a
4
)
— хорошая. Поэтому хороших пар уже не менее 50, причем ровно 50 их может быть, только если хорошие и нехорошие пары чередуются. Но если рассмотретьчисло 100, то следующая за ним пара — хорошая 100 > (a
k
< a
k+1
) > a
k+2
< a
k+3
. Также хорошей является и пара, предшествующая числу 100, а значит, чередование невозможно. Так как D и E лежат на сторонах, то ∠ABC — наибольший угол треугольника поэтому ∠AOC = 2∠ABC 120
◦
, и точки O и T лежат по разные стороны от AC.
Пустьпрямые ME и MD пересекают AB и BC соответственно в точках и Y см. рис. 305). Из остроугольности очевидно следует, что X и лежат на продолжениях отрезков BA и BC заточки и C соответственно. Заметим, что ∠DXM = 180
◦
− ∠ABE − ∠BEM = 180
◦
− аналогично ∠EY M = 180
◦
− 2∠ABC, поэтому четырехугольник DEY вписанный и ∠BED = ∠BXY Далее, ∠AT M = 2∠ACO так как точки O, M, T , очевидно, лежат на серединном перпендикуляре к AC и T — центр описанной окружности
КЛАСС
411
скольку набор был наименьший, среди ребер, соединяющих оставшиеся вершины, присутствуют уже не все цвета. Если среди этих ребер присутствуют ребра ровно трех цветов, то искомый набор найден. В противном случае среди ребер, выходящих из удаленной вершины в другие вершины нашего набора, присутствуют как минимум два цвета, которые исчезнут после удаления этой вершины. Рассмотрим два ребра этих цветов, выходящие из удаленной вершины в другие вершины набора. Тогда ребро,
соединяющее их концы, должно иметьцвет, отличный от цветов этих двух ребер. Таким образом, в графе нашелся треугольник, все ребра которого имеют попарно различные цвета. Это означает, что требуемый набор вершин можно выбратьвсегда.
695. Ответ. 51 хорошая пара.
Пример: сначала расставим числа подряда затем поменяем местами числа 2 и 3, 4 и 5, . . . , 98 и 99. В полученной расстановке, 3, 2, 5, 4, . . . , 99, 98, хорошими парами являются в точности пары, 3)
, (3, 2), (5, 4), (7, 6), . . . , (97, 96), (99, 98), (98, Докажем, что хороших парне менее 51. Заметим, что среди любых двух пересекающихся пар хотя бы одна — хорошая. Действительно, пусть, a
2
, a
3
, a
4
, a
5
— такие подряд идущие числа, что пары (a
2
, и (a
3
, не являются хорошими. Не умаляя общности, можно считать, что a
1
>
> a
2
< a
3
> a
4
< a
5
. С другой стороны, пара (a
3
, не является хорошей, значит, a
1
> a
2
> a
5
, пара (a
2
, не является хорошей, значит a
4
> a
1
. Тогда a
1
> a
2
> a
5
> a
4
> a
1
, что невозможно, значит,
либо пара (a
2
, a
3
)
, либо пара (a
3
, a
4
)
— хорошая. Поэтому хороших пар уже не менее 50, причем ровно 50 их может быть, только если хорошие и нехорошие пары чередуются. Но если рассмотретьчисло 100, то следующая за ним пара — хорошая 100 > (a
k
< a
k+1
) > a
k+2
< a
k+3
. Также хорошей является и пара, предшествующая числу 100, а значит, чередование невозможно. Так как D и E лежат на сторонах, то ∠ABC — наибольший угол треугольника поэтому ∠AOC = 2∠ABC 120
◦
, и точки O и T лежат по разные стороны от AC.
Пустьпрямые ME и MD пересекают AB и BC соответственно в точках и Y см. рис. 305). Из остроугольности очевидно следует, что X и лежат на продолжениях отрезков BA и BC заточки и C соответственно. Заметим, что ∠DXM = 180
◦
− ∠ABE − ∠BEM = 180
◦
− аналогично ∠EY M = 180
◦
− 2∠ABC, поэтому четырехугольник DEY вписанный и ∠BED = ∠BXY Далее, ∠AT M = 2∠ACO так как точки O, M, T , очевидно, лежат на серединном перпендикуляре к AC и T — центр описанной окружности
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ AOC). Тогда ∠AT M = 2(90
◦
− ∠MOC) = 2(90
◦
− ∠ABC), так как центр описанной окружности ABC. Поэтому ∠AT M = 180
◦
−
− 2∠ABC = ∠AXM, откуда AMT X — вписанный. Так как ∠AMT =
= 90
◦
, то ∠AXT = 90
◦
. Аналогично ∠CY T = 90
◦
. Тогда четырехугольник также вписанный, и ∠T BY = ∠T XY = 90
◦
− ∠BXY . Получаем, что и требовалось класс
A
B
C
M
D
E
O
T
X
Y
Рис. 305
697. См. решение задачи 689.
698. Ответ. За 2003 вопроса.
Занумеруем коробочки (и соответственно шарики в них) числами от дои будем вопрос обозначатьпа- рой номеров коробочек. Будем называть небелые шарики черными.
Покажем, что за 2003 вопроса можно найти белый шарик. Зададим вопросы. Если все ответы положительны, то первый шарик белый (иначе естьеще хотя бы один черный шарики первый вместе с ним составит черную пару. Если же хотя бы один ответ отрицателен, то первый шарик черный тогда белыми являются ровноте шарики, про которые (в паре с черным первым) ответ был положительными в этом случае мы найдем даже все белые.
Пустьсуществует алгоритм, позволяющий гарантированно найти белый шарик за меньшее число вопросов. Будем отвечатьна все вопросы положительно. Тогда максимум после 2002 вопросов игрок сможет ука- затьна какую-то (для определенности, первую) коробочку и заявить, что в ней шарик белый. При этом какого-то из вопросов вида (1, n) (скажем,
вопроса (1, 2)) задано не будет, ибо таких вопросов всего 2003. Положим теперьв ю и ю коробочку черные шарики, а вовсе остальные белые. Тогда все наши ответы будут верны, а указанный игроком шарик окажется черным. Противоречие. Если ABCD — трапеция (скажем, AB CD), то прямые L
L
и
N
N
имеют общую точку пересечения с серединным перпендикуляром к, на котором лежат K, K
, M и M
. Пустьпрямые AB и CD пересекаются в точке E, а прямые BC ив точке F см. рис. 306). Заметим,
что и лежат на биссектрисе угла CF D так как они равноудалены
◦
− ∠MOC) = 2(90
◦
− ∠ABC), так как центр описанной окружности ABC. Поэтому ∠AT M = 180
◦
−
− 2∠ABC = ∠AXM, откуда AMT X — вписанный. Так как ∠AMT =
= 90
◦
, то ∠AXT = 90
◦
. Аналогично ∠CY T = 90
◦
. Тогда четырехугольник также вписанный, и ∠T BY = ∠T XY = 90
◦
− ∠BXY . Получаем, что и требовалось класс
A
B
C
M
D
E
O
T
X
Y
Рис. 305
697. См. решение задачи 689.
698. Ответ. За 2003 вопроса.
Занумеруем коробочки (и соответственно шарики в них) числами от дои будем вопрос обозначатьпа- рой номеров коробочек. Будем называть небелые шарики черными.
Покажем, что за 2003 вопроса можно найти белый шарик. Зададим вопросы. Если все ответы положительны, то первый шарик белый (иначе естьеще хотя бы один черный шарики первый вместе с ним составит черную пару. Если же хотя бы один ответ отрицателен, то первый шарик черный тогда белыми являются ровноте шарики, про которые (в паре с черным первым) ответ был положительными в этом случае мы найдем даже все белые.
Пустьсуществует алгоритм, позволяющий гарантированно найти белый шарик за меньшее число вопросов. Будем отвечатьна все вопросы положительно. Тогда максимум после 2002 вопросов игрок сможет ука- затьна какую-то (для определенности, первую) коробочку и заявить, что в ней шарик белый. При этом какого-то из вопросов вида (1, n) (скажем,
вопроса (1, 2)) задано не будет, ибо таких вопросов всего 2003. Положим теперьв ю и ю коробочку черные шарики, а вовсе остальные белые. Тогда все наши ответы будут верны, а указанный игроком шарик окажется черным. Противоречие. Если ABCD — трапеция (скажем, AB CD), то прямые L
L
и
N
N
имеют общую точку пересечения с серединным перпендикуляром к, на котором лежат K, K
, M и M
. Пустьпрямые AB и CD пересекаются в точке E, а прямые BC ив точке F см. рис. 306). Заметим,
что и лежат на биссектрисе угла CF D так как они равноудалены
УЧЕБНЫЙ ГОД, 10
КЛАСС
413
от прямых BC и AD). Пустьэта биссектриса пересекает AB ив точках и Q соответственно.
A
B
C
D
F
E
K
L
N
M
K
L
N
M
P
Q
Рис. Тогда, так как ABCD — вписанный и F P — биссектриса угла CF то ∠F AP = ∠F CQ и ∠P F A = ∠CF Q ⇒ ∠F P A = ∠F QC ⇒ ∠EP Q =
=
∠EQP , те. биссектриса угла AED является высотой равнобедренного треугольника EP Q; поскольку и лежат на этой биссектрисе, то L
N
. Но биссектриса угла AED перпендикулярна KM, откуда K
M
; аналогично LN L
N
. Прямая KL перпендикулярна биссектрисе угла ABC, а значит, параллельна биссектрисе внешнего угла следовательно, K
L
KL аналогично, L
M
LM). Тогда у треугольников и соответствующие стороны параллельны, а значит,
они гомотетичны. Заметим, что при этой гомотетии K переходит в K
, а в M
, итак как параллельные прямые переходят в параллельные, то прямые KN и MN переходят в и соответственно, значит, переходит в N
; следовательно, четырехугольники KLMN и K
L
M
N
гомотетичны. Получаем, что KK
, LL
, MM, проходят через центр гомотетии, те. через одну точку. См. решение задачи 692.
701. Предположим противное. Полагая m = n = 1, получаем a
1
+
+ a
1
= a
1
, те. Поэтому все остальные члены ненулевые. Пусть p/q
, a
3
= r/s
. Из условия следует, что a
m
k
= ka
m
; поэтому a
2
qr
=
= qr
· p/q = pr = ps · r/s = a
3
ps
, но 2
qr
= 3
ps
. Противоречие. Предположим, что утверждение задачи неверно скажем, из города
X
нельзя добраться до Y по городам республики (X, Y — города рес-
КЛАСС
413
от прямых BC и AD). Пустьэта биссектриса пересекает AB ив точках и Q соответственно.
A
B
C
D
F
E
K
L
N
M
K
L
N
M
P
Q
Рис. Тогда, так как ABCD — вписанный и F P — биссектриса угла CF то ∠F AP = ∠F CQ и ∠P F A = ∠CF Q ⇒ ∠F P A = ∠F QC ⇒ ∠EP Q =
=
∠EQP , те. биссектриса угла AED является высотой равнобедренного треугольника EP Q; поскольку и лежат на этой биссектрисе, то L
N
. Но биссектриса угла AED перпендикулярна KM, откуда K
M
; аналогично LN L
N
. Прямая KL перпендикулярна биссектрисе угла ABC, а значит, параллельна биссектрисе внешнего угла следовательно, K
L
KL аналогично, L
M
LM). Тогда у треугольников и соответствующие стороны параллельны, а значит,
они гомотетичны. Заметим, что при этой гомотетии K переходит в K
, а в M
, итак как параллельные прямые переходят в параллельные, то прямые KN и MN переходят в и соответственно, значит, переходит в N
; следовательно, четырехугольники KLMN и K
L
M
N
гомотетичны. Получаем, что KK
, LL
, MM, проходят через центр гомотетии, те. через одну точку. См. решение задачи 692.
701. Предположим противное. Полагая m = n = 1, получаем a
1
+
+ a
1
= a
1
, те. Поэтому все остальные члены ненулевые. Пусть p/q
, a
3
= r/s
. Из условия следует, что a
m
k
= ka
m
; поэтому a
2
qr
=
= qr
· p/q = pr = ps · r/s = a
3
ps
, но 2
qr
= 3
ps
. Противоречие. Предположим, что утверждение задачи неверно скажем, из города
X
нельзя добраться до Y по городам республики (X, Y — города рес-
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
публики). Обозначим через A множество всех городов республики, до которых можно добраться из X по городам республики (включая сам города через B — множество всех остальных ее городов (оно непусто, так как содержит Y ). Тогда города республики разбилисьна две группы так,
что все дороги между городами группы A и группы B направлены от B к
A
Обозначим количество городов в группах A и B через a и b соответственно. Пустьв A городов не меньше, чем в B, те. В B естьгород Z, из которого выходит не менее − 1 дорог в города из B. Кроме того, из Z выходит a дорог к городам группы A. Всего дорог, выходящих из Z, получается не менее a +
b − 1 2
=
a + (a + b) − 1 2
=
=
a + 667 2
1001 2
> 500
. Противоречие.
Случай, когда в B больше городов, чем в A, рассматривается аналогично путем выбора города изв который входит не менее − 1 дорог из городов из A.
703. Первое решение. Пусть O центр симметрии многоугольника, B, C — вершины T , A
, B
, C
— соответствующие вершины T
; пусть ABC при симметрии относительно O переходит в лежащий в M). Если O = P , утверждение очевидно. Пусть d — луч прямой OP с вершиной вне содержащий O. Тогда d пересекает одну из сторон скажем, Рис. Рассмотрим параллелограмм, лежащий в M.
Прямая
OP
высекает в нем отрезок, симметричный относительно O; тогда отрезок
A
B
пересекается с этой прямой во внутренней точке K параллелограмма
(см. рис. 307). Теперь, поскольку A
B
AB A
0
B
0
, то одна из точек и лежит в этом параллелограмме (или на его границе, иначе A
B
> AB
, что неверно.
Второе решение. Докажем простую лемму если на плоскости дан треугольники точка S, то треугольник XY Z покрывается треугольниками, Действительно, прямые XY , Y Z, ZX разбивают плоскостьна 7 частей (см. рис. 308). Если S лежит в части 1, то XY Z = SXY ∪ SY Z∪
∪ SZX; если S лежит в части 2, то XY Z ⊂ SY Z рассмотрения для частей 3, 4 аналогичны если S лежит в части 5, то XY Z ⊂ SXY ∪
∪ SZX рассмотрения для частей 6, 7 аналогичны
публики). Обозначим через A множество всех городов республики, до которых можно добраться из X по городам республики (включая сам города через B — множество всех остальных ее городов (оно непусто, так как содержит Y ). Тогда города республики разбилисьна две группы так,
что все дороги между городами группы A и группы B направлены от B к
A
Обозначим количество городов в группах A и B через a и b соответственно. Пустьв A городов не меньше, чем в B, те. В B естьгород Z, из которого выходит не менее − 1 дорог в города из B. Кроме того, из Z выходит a дорог к городам группы A. Всего дорог, выходящих из Z, получается не менее a +
b − 1 2
=
a + (a + b) − 1 2
=
=
a + 667 2
1001 2
> 500
. Противоречие.
Случай, когда в B больше городов, чем в A, рассматривается аналогично путем выбора города изв который входит не менее − 1 дорог из городов из A.
703. Первое решение. Пусть O центр симметрии многоугольника, B, C — вершины T , A
, B
, C
— соответствующие вершины T
; пусть ABC при симметрии относительно O переходит в лежащий в M). Если O = P , утверждение очевидно. Пусть d — луч прямой OP с вершиной вне содержащий O. Тогда d пересекает одну из сторон скажем, Рис. Рассмотрим параллелограмм, лежащий в M.
Прямая
OP
высекает в нем отрезок, симметричный относительно O; тогда отрезок
A
B
пересекается с этой прямой во внутренней точке K параллелограмма
(см. рис. 307). Теперь, поскольку A
B
AB A
0
B
0
, то одна из точек и лежит в этом параллелограмме (или на его границе, иначе A
B
> AB
, что неверно.
Второе решение. Докажем простую лемму если на плоскости дан треугольники точка S, то треугольник XY Z покрывается треугольниками, Действительно, прямые XY , Y Z, ZX разбивают плоскостьна 7 частей (см. рис. 308). Если S лежит в части 1, то XY Z = SXY ∪ SY Z∪
∪ SZX; если S лежит в части 2, то XY Z ⊂ SY Z рассмотрения для частей 3, 4 аналогичны если S лежит в части 5, то XY Z ⊂ SXY ∪
∪ SZX рассмотрения для частей 6, 7 аналогичны
УЧЕБНЫЙ ГОД, 10
КЛАСС
415
Перейдем к решению задачи. Обозначим через O центр симметрии многоугольника M, через A, B, C — вершины треугольника T , а через, B
1
, C
1
— середины сторон BC, CA, AB соответственно 2
3 4
5 Рис. Рис. Рассмотрим многоугольник V
A
, являющийся выпуклой оболочкой точек. Заметим, что покрывает AB
1
C
1
. Определим также
V
B
и как выпуклые оболочки четверок O, B, C
1
, и O, C, A
1
, При этом покрывает BA
1
C
1
, покрывает CA
1
B
1
. Кроме того OB
1
C
1
, V
B
⊃ OC
1
A
1
, V
C
⊃ OA
1
B
1
. Отсюда, применяя лемму, получаем, что объединение V многоугольников V
A
, V
B
, покрывает. Итак, V покрывает объединение треугольников AB
1
C
1
,
BA
1
C
1
, CA
1
B
1
, A
1
B
1
C
1
, те покрывает ABC. Это означает, что один из многоугольников V
A
, V
B
, содержит точку P , пусть , для определенности см. рис. Пусть A
— вершина треугольника T
, те. точка, симметричная точке
A
относительно P ; пусть D — точка, симметричная точке A относительно. При гомотетии с центром в точке A и коэффициентом k = 2 точка перейдет в A
, O перейдет в D, перейдет в B, перейдет в C. Следовательно, многоугольник перейдет в выпуклую оболочку U точек D, A,
C
, B, причем точка содержится в U. Так как A, B, C ∈ M и M симметричен относительно O, то D ∈ M. Поскольку M — выпуклый, U ⊂ Значит, A
∈ M, что и требовалось. Ответ. Существует.
Приведем пример такого числа. Пусть n = 13·11 . . . 1 = 144 . . . 43, количество единиц мы подберем позже. Если переставитьединицу и тройку,
то получится число 344 . . . 41 = 31 · 11 . . . 1. При этом, если наше число из одних единиц делится на 13 · 31 = 403, то простыми делителями обоих чисел будут в точности его простые делители. Осталосьпоказать, что существует такое число из хотя бы 1000 единиц
КЛАСС
415
Перейдем к решению задачи. Обозначим через O центр симметрии многоугольника M, через A, B, C — вершины треугольника T , а через, B
1
, C
1
— середины сторон BC, CA, AB соответственно 2
3 4
5 Рис. Рис. Рассмотрим многоугольник V
A
, являющийся выпуклой оболочкой точек. Заметим, что покрывает AB
1
C
1
. Определим также
V
B
и как выпуклые оболочки четверок O, B, C
1
, и O, C, A
1
, При этом покрывает BA
1
C
1
, покрывает CA
1
B
1
. Кроме того OB
1
C
1
, V
B
⊃ OC
1
A
1
, V
C
⊃ OA
1
B
1
. Отсюда, применяя лемму, получаем, что объединение V многоугольников V
A
, V
B
, покрывает. Итак, V покрывает объединение треугольников AB
1
C
1
,
BA
1
C
1
, CA
1
B
1
, A
1
B
1
C
1
, те покрывает ABC. Это означает, что один из многоугольников V
A
, V
B
, содержит точку P , пусть , для определенности см. рис. Пусть A
— вершина треугольника T
, те. точка, симметричная точке
A
относительно P ; пусть D — точка, симметричная точке A относительно. При гомотетии с центром в точке A и коэффициентом k = 2 точка перейдет в A
, O перейдет в D, перейдет в B, перейдет в C. Следовательно, многоугольник перейдет в выпуклую оболочку U точек D, A,
C
, B, причем точка содержится в U. Так как A, B, C ∈ M и M симметричен относительно O, то D ∈ M. Поскольку M — выпуклый, U ⊂ Значит, A
∈ M, что и требовалось. Ответ. Существует.
Приведем пример такого числа. Пусть n = 13·11 . . . 1 = 144 . . . 43, количество единиц мы подберем позже. Если переставитьединицу и тройку,
то получится число 344 . . . 41 = 31 · 11 . . . 1. При этом, если наше число из одних единиц делится на 13 · 31 = 403, то простыми делителями обоих чисел будут в точности его простые делители. Осталосьпоказать, что существует такое число из хотя бы 1000 единиц
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Рассмотрим числа 1, 10 1000
, 10 2000
, . . . , 10 403·1000
. Два из них скажем и 10 1000n
, где m < n) имеют одинаковые остатки отделения на 403. Тогда 10 1000n
− 10 1000m
= 10 1000m
(10 1000(n−m)
− 1) делится на 403, а поскольку 403 и 90 взаимно просты, тона делится и 1000(n−m)
− 1 9
= 11 . . . 1
1000(n−m)
, что и требовалось класс. См. решение задачи 689.
706. Пусть M — середина отрезка I
A
I
B
. Поскольку биссектрисы внутреннего и внешнего углов перпендикулярны, AI
A
⊥AI
B
. В прямоугольном треугольнике середина M гипотенузы равноудалена от вершин, поэтому MA = I
A
I
B
/2
. Аналогично, MB = I
A
I
B
/2
. Тогда центр окружности, описанной около AI
B
I
A
B
, поэтому ∠AI
A
B =
=
∠AMB/2. Заметим, что ∠AI
A
B = (180
◦
− ∠ABC)/2 − ∠BAC/2 =
=
∠ACB/2, поэтому ∠AMB = ∠ACB, и точки A, B, C и M лежат на одной окружности Ω. Поскольку AM = BM, точка M является серединой дуги ACB этой окружности.
A
B
C
I
A
I
B
O
A
O
B
M
P
O
M
I
A
I
B
Рис. Пусть I
A
, I
B
, M
— середины отрезков CI
A
, CI
B
, CM соответственно (см. рис. 310). Точки I
A
, I
B
, являются проекциями соответственно точек O
A
, O
B
, O напрямую здесь O
A
, O
B
, O — центры описанных окружностей треугольников I
A
CP
, I
B
CP
, ABC). Точки O
A
, O
B
, лежат на серединном перпендикуляре l к отрезку CP . Поэтому для решения задачи достаточно доказать, что является серединой отрезка Но это верно, поскольку M — середина I
A
I
B
, а тройка точек I
A
, I
B
, M
Рассмотрим числа 1, 10 1000
, 10 2000
, . . . , 10 403·1000
. Два из них скажем и 10 1000n
, где m < n) имеют одинаковые остатки отделения на 403. Тогда 10 1000n
− 10 1000m
= 10 1000m
(10 1000(n−m)
− 1) делится на 403, а поскольку 403 и 90 взаимно просты, тона делится и 1000(n−m)
− 1 9
= 11 . . . 1
1000(n−m)
, что и требовалось класс. См. решение задачи 689.
706. Пусть M — середина отрезка I
A
I
B
. Поскольку биссектрисы внутреннего и внешнего углов перпендикулярны, AI
A
⊥AI
B
. В прямоугольном треугольнике середина M гипотенузы равноудалена от вершин, поэтому MA = I
A
I
B
/2
. Аналогично, MB = I
A
I
B
/2
. Тогда центр окружности, описанной около AI
B
I
A
B
, поэтому ∠AI
A
B =
=
∠AMB/2. Заметим, что ∠AI
A
B = (180
◦
− ∠ABC)/2 − ∠BAC/2 =
=
∠ACB/2, поэтому ∠AMB = ∠ACB, и точки A, B, C и M лежат на одной окружности Ω. Поскольку AM = BM, точка M является серединой дуги ACB этой окружности.
A
B
C
I
A
I
B
O
A
O
B
M
P
O
M
I
A
I
B
Рис. Пусть I
A
, I
B
, M
— середины отрезков CI
A
, CI
B
, CM соответственно (см. рис. 310). Точки I
A
, I
B
, являются проекциями соответственно точек O
A
, O
B
, O напрямую здесь O
A
, O
B
, O — центры описанных окружностей треугольников I
A
CP
, I
B
CP
, ABC). Точки O
A
, O
B
, лежат на серединном перпендикуляре l к отрезку CP . Поэтому для решения задачи достаточно доказать, что является серединой отрезка Но это верно, поскольку M — середина I
A
I
B
, а тройка точек I
A
, I
B
, M
УЧЕБНЫЙ ГОД, 11
КЛАСС
417
получается из тройки I
A
, I
B
, M путем гомотетии с центром C и коэффициентом. Предположим противное. Рассмотрим многочлены P (x), Q(x), для которых наше утверждение неверно и степень P (x) — наименьшая извоз- можных. Обозначим степени P (x) и Q(x) через n и k соответственно. Заметим, что при домножении многочленов на ненулевые константы условие не меняется, поэтому будем считать P (x) и Q(x) приведенными. Ясно, что > 0
, иначе можно положить S(x) = P (x) = Лемма. n делится на Доказательство. Старшей компонентой T (x, y) многочлена от двух переменных T (x, y) будем называтьсумму всех составляющих его одночленов, сумма степеней при x и y у которых максимальна (так, умно- гочлена x
3
+ 3xy
2
+ x
− старшей компонентой является x
3
+ Заметим, что T
1
(x, y)T
2
(x, y) = T
1
(x, y)
· T
2
(x, y)
. Тогда y
n
= P (x)
− P (y) = R(x, y) · Q(x) − Q(y) = R(x, y)(x
k
− те. многочлен x
n
− делится на x
k
− y
k
. Если n = qk + r — результат деления n нас остатком, то y
n
= x
r
(x
qk
− y
qk
) + y
qk
(x
r
− y
r
) =
= x
r
(x
k
− y
k
)(x
k(q−1)
+ x
k(q−2)
y
k
+ . . . + y
k(q−1)
) + y
qk
(x
r
− поэтому F (x, y) = y
qk
(x
r
− делится на x
k
− y
k
. Однако его степеньпо
x
меньше, чем k, поэтому такое может бытьлишьтогда, когда она равна нулю, те. Лемма доказана.
Рассмотрим многочлены P
1
(x) = P (x)
− и Q(x). Для них условие задачи выполнено P
1
(y) =
=
R(x, y)
− (Q
n/k−1
(x) + Q
n/k−2
(x)Q(y) + . . .
. . . + Q
n/k−1
(y))
(Q(x)
− Кроме того, степеньу меньше, чем степень P (x); поэтому P
1
(x) =
= для некоторого многочлена S
1
(x)
. Тогда, положив S(x) =
= S
1
(x) + x
n/k
, получаем противоречие с выбором P (x), так как P (x) =
= P
1
(x) + Q
n/k
(x) = S(Q(x))
КЛАСС
417
получается из тройки I
A
, I
B
, M путем гомотетии с центром C и коэффициентом. Предположим противное. Рассмотрим многочлены P (x), Q(x), для которых наше утверждение неверно и степень P (x) — наименьшая извоз- можных. Обозначим степени P (x) и Q(x) через n и k соответственно. Заметим, что при домножении многочленов на ненулевые константы условие не меняется, поэтому будем считать P (x) и Q(x) приведенными. Ясно, что > 0
, иначе можно положить S(x) = P (x) = Лемма. n делится на Доказательство. Старшей компонентой T (x, y) многочлена от двух переменных T (x, y) будем называтьсумму всех составляющих его одночленов, сумма степеней при x и y у которых максимальна (так, умно- гочлена x
3
+ 3xy
2
+ x
− старшей компонентой является x
3
+ Заметим, что T
1
(x, y)T
2
(x, y) = T
1
(x, y)
· T
2
(x, y)
. Тогда y
n
= P (x)
− P (y) = R(x, y) · Q(x) − Q(y) = R(x, y)(x
k
− те. многочлен x
n
− делится на x
k
− y
k
. Если n = qk + r — результат деления n нас остатком, то y
n
= x
r
(x
qk
− y
qk
) + y
qk
(x
r
− y
r
) =
= x
r
(x
k
− y
k
)(x
k(q−1)
+ x
k(q−2)
y
k
+ . . . + y
k(q−1)
) + y
qk
(x
r
− поэтому F (x, y) = y
qk
(x
r
− делится на x
k
− y
k
. Однако его степеньпо
x
меньше, чем k, поэтому такое может бытьлишьтогда, когда она равна нулю, те. Лемма доказана.
Рассмотрим многочлены P
1
(x) = P (x)
− и Q(x). Для них условие задачи выполнено P
1
(y) =
=
R(x, y)
− (Q
n/k−1
(x) + Q
n/k−2
(x)Q(y) + . . .
. . . + Q
n/k−1
(y))
(Q(x)
− Кроме того, степеньу меньше, чем степень P (x); поэтому P
1
(x) =
= для некоторого многочлена S
1
(x)
. Тогда, положив S(x) =
= S
1
(x) + x
n/k
, получаем противоречие с выбором P (x), так как P (x) =
= P
1
(x) + Q
n/k
(x) = S(Q(x))
708. Ответ · 2002 2
+ 1 = Докажем, что сумма не может бытьменьше. Переставив, если нужно,
столбцы, будем далее считать, что числа впервой строке стоят в неубывающем порядке. Пусть a
i
— е число первой строки. Рассмотрим сумму = (a
1
− 1) + (a
2
− 1) + (a
3
− 1) + (a
4
− 2) + . . . + (a
i
− (i − 2)) + . . .
. . . + (a
2003
− 2001) + (a
2004
− 2001).
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Заметим, что сумма вычитаемых чисел как раз равна · 2002 2
+ 1
; поэтому достаточно доказать, что S 0. Обозначим е слагаемое в нашей сумме через d
i
. Если в этой сумме нет отрицательных членов, все очевидно. Ясно, что a
2004
2001, a
2
a
1
1, те Пусть d
i
< 0
, те. Тогда в i первых столбцах содержатся только числа от 1 до i, следовательно, там содержатся все такие числа.
Отсюда следует, что a
i
= i
− 3, a
i+1
i + 1, и d
i
+ d
i+1
> 0
. Таким образом, для любого отрицательного сумма его со следующим членом положительна, поэтому, объединив такие слагаемые в пары, получаем сумму неотрицательных слагаемых, что и требовалось.
Осталосьпривести пример таблицы, для которой оценка достигается 1 1 2 3 4 · · ·
k
· · · 1998 1999 2000 2001 2001 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2002 2002 2003 2004 2 3 4 5 6 7 · · · k + 3 · · · 2001 2002 2003 2003 2004 2 3 4 5 6 7 · · · k + 3 · · · 2001 2002 2003 2004 два первых и четыре последних столбца устроены несколько иначе, чем остальные. Пусть A
1
1. Достаточно доказать, что A
n+1
< при любом n Имеем A
n
A
1
A
n
. Перемножая и и раскрывая скобки, видим, что A
1
A
n
= A
n+1
+ S
n
, где S
n
— сумма всех слагаемых полученной суммы, в которых встречается квадрат одного из x
i
. Тогда S
n
> 0
, откуда следует требуемое. Предположим противное. Выберем прямую, неортогональную ни одному из векторов нашего множества. Тогда проекции хотя бы N векторов на нее направлены в одну сторону обозначим их e
1
, . . . , e
N
. Введем на этой прямой направление так, что эти векторы направлены в отрицательную сторону, и выберем N векторов f
1
, . . . , так, что алгебраическая проекция s их суммы максимальна (ясно, что из условия 2) s > 0). При этом, если некоторые из этих векторов совпали с векторами e
i
, то проекции всех векторов, кроме f
1
, . . . , f
N
, направлены в отрицательную сторону тогда мы обозначим через e
i
какие-то N векторов, отличных от f
i
,
i = 1
, . . . , N.
Заметим, что сумма вычитаемых чисел как раз равна · 2002 2
+ 1
; поэтому достаточно доказать, что S 0. Обозначим е слагаемое в нашей сумме через d
i
. Если в этой сумме нет отрицательных членов, все очевидно. Ясно, что a
2004
2001, a
2
a
1
1, те Пусть d
i
< 0
, те. Тогда в i первых столбцах содержатся только числа от 1 до i, следовательно, там содержатся все такие числа.
Отсюда следует, что a
i
= i
− 3, a
i+1
i + 1, и d
i
+ d
i+1
> 0
. Таким образом, для любого отрицательного сумма его со следующим членом положительна, поэтому, объединив такие слагаемые в пары, получаем сумму неотрицательных слагаемых, что и требовалось.
Осталосьпривести пример таблицы, для которой оценка достигается 1 1 2 3 4 · · ·
k
· · · 1998 1999 2000 2001 2001 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2002 2002 2003 2004 2 3 4 5 6 7 · · · k + 3 · · · 2001 2002 2003 2003 2004 2 3 4 5 6 7 · · · k + 3 · · · 2001 2002 2003 2004 два первых и четыре последних столбца устроены несколько иначе, чем остальные. Пусть A
1
1. Достаточно доказать, что A
n+1
< при любом n Имеем A
n
A
1
A
n
. Перемножая и и раскрывая скобки, видим, что A
1
A
n
= A
n+1
+ S
n
, где S
n
— сумма всех слагаемых полученной суммы, в которых встречается квадрат одного из x
i
. Тогда S
n
> 0
, откуда следует требуемое. Предположим противное. Выберем прямую, неортогональную ни одному из векторов нашего множества. Тогда проекции хотя бы N векторов на нее направлены в одну сторону обозначим их e
1
, . . . , e
N
. Введем на этой прямой направление так, что эти векторы направлены в отрицательную сторону, и выберем N векторов f
1
, . . . , так, что алгебраическая проекция s их суммы максимальна (ясно, что из условия 2) s > 0). При этом, если некоторые из этих векторов совпали с векторами e
i
, то проекции всех векторов, кроме f
1
, . . . , f
N
, направлены в отрицательную сторону тогда мы обозначим через e
i
какие-то N векторов, отличных от f
i
,
i = 1
, . . . , N.
УЧЕБНЫЙ ГОД, 11
КЛАСС
419
Для N векторов найдутся векторы a
1
, . . . , a
N такие, что f
1
+. . .
. . . + f
N
=
−(a
1
+ . . . + a
N −1
)
. Хотя бы один из векторов не совпадает ни с одним из a
j
(пустьэто e
1
), при этом алгебраическая проекция суммы+ отрицательна и больше s по модулю. Тогда для векторов a
1
, . . . , a
N −1
, существуют N векторов, сумма которых равна+ . . . + a
N −1
+ e
1
)
, те. алгебраическая проекция суммы которых больше s. Противоречие с выбором векторов f
i
711. Индукция по k. Если k = 0, утверждение тривиально авиалиний нет.
Рассмотрим граф, вершины которого соответствуют городам, а ребра авиалиниям. Пусть E
1
, E
2
, . . . , E
k
— группы ребер, соответствующие авиалиниям первой, второй, . . . , й авиакомпаний. Нетрудно понять, что для любого i ∈ {1, . . . , k} группа E
i
— либо треугольник, либо
ёж
—
несколько ребер с одним концом. Если какая-то группа E
i
— ёж сцен- тром в вершине A, то удалим A и все выходящие из нее ребра. В оставшемся графе ребра принадлежат k − 1 авиакомпании, его вершины мы разобьем на k + 1 группу так, чтобы вершины из одной группы небыли соединены ребром, а вершина A составит (k + ю группу.
Остается рассмотретьслучай, когда все группы E
1
, . . . , E
k
— треугольники. Тогда всего в графе 3k ребер. Разобьем вершины графа на минимальное возможное количество групп так, что никакие две вершины одной группы не смежны (те. не соединены ребром. Пустьэто группы, . . . , B
n
, причем n k + 3. Отметим, что для любых двух групп и существует ребро между вершиной из и вершиной из B
j
, иначе можно объединитьэти две группы в одну. Таким образом, всего в графе хотя бы − ребер. Отметим, что − 1)
2
(k + 3)(k + 2)
2
> 3k
, — противоречие, завершающее решение задачи. Пусть ABCDA
1
B
1
C
1
D
1
— прямоугольный параллелепипед, в котором, причем a b c. Без ограничения общности можно считать, что шестиугольное сечение KLMNP Q расположено так, что K ∈ AD, L ∈ AB, M ∈ BB
1
, N ∈ B
1
C
1
, P ∈ C
1
D
1
,
Q
∈ см. рис. В шестиугольнике пары противоположных сторон параллельны (как прямые пересечения плоскости с парой параллельных плоскостей. Расстояние между параллельными прямыми QK и MN не меньше, чем расстояние между гранями и BCC
1
B
1
, которое равно Аналогично, расстояние между парами параллельных сторон KL и P
, LM и P Q не меньше длины одного из ребер параллелепипеда, и, следовательно, не меньше a.
КЛАСС
419
Для N векторов найдутся векторы a
1
, . . . , a
N такие, что f
1
+. . .
. . . + f
N
=
−(a
1
+ . . . + a
N −1
)
. Хотя бы один из векторов не совпадает ни с одним из a
j
(пустьэто e
1
), при этом алгебраическая проекция суммы+ отрицательна и больше s по модулю. Тогда для векторов a
1
, . . . , a
N −1
, существуют N векторов, сумма которых равна+ . . . + a
N −1
+ e
1
)
, те. алгебраическая проекция суммы которых больше s. Противоречие с выбором векторов f
i
711. Индукция по k. Если k = 0, утверждение тривиально авиалиний нет.
Рассмотрим граф, вершины которого соответствуют городам, а ребра авиалиниям. Пусть E
1
, E
2
, . . . , E
k
— группы ребер, соответствующие авиалиниям первой, второй, . . . , й авиакомпаний. Нетрудно понять, что для любого i ∈ {1, . . . , k} группа E
i
— либо треугольник, либо
ёж
—
несколько ребер с одним концом. Если какая-то группа E
i
— ёж сцен- тром в вершине A, то удалим A и все выходящие из нее ребра. В оставшемся графе ребра принадлежат k − 1 авиакомпании, его вершины мы разобьем на k + 1 группу так, чтобы вершины из одной группы небыли соединены ребром, а вершина A составит (k + ю группу.
Остается рассмотретьслучай, когда все группы E
1
, . . . , E
k
— треугольники. Тогда всего в графе 3k ребер. Разобьем вершины графа на минимальное возможное количество групп так, что никакие две вершины одной группы не смежны (те. не соединены ребром. Пустьэто группы, . . . , B
n
, причем n k + 3. Отметим, что для любых двух групп и существует ребро между вершиной из и вершиной из B
j
, иначе можно объединитьэти две группы в одну. Таким образом, всего в графе хотя бы − ребер. Отметим, что − 1)
2
(k + 3)(k + 2)
2
> 3k
, — противоречие, завершающее решение задачи. Пусть ABCDA
1
B
1
C
1
D
1
— прямоугольный параллелепипед, в котором, причем a b c. Без ограничения общности можно считать, что шестиугольное сечение KLMNP Q расположено так, что K ∈ AD, L ∈ AB, M ∈ BB
1
, N ∈ B
1
C
1
, P ∈ C
1
D
1
,
Q
∈ см. рис. В шестиугольнике пары противоположных сторон параллельны (как прямые пересечения плоскости с парой параллельных плоскостей. Расстояние между параллельными прямыми QK и MN не меньше, чем расстояние между гранями и BCC
1
B
1
, которое равно Аналогично, расстояние между парами параллельных сторон KL и P
, LM и P Q не меньше длины одного из ребер параллелепипеда, и, следовательно, не меньше a.
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
a
b
c
A
B
C
D
A
1
B
1
C
1
D
1
K
P
Q
L
M
N
Рис. Рис. Докажем, что проекция шестиугольника на любую прямую, лежащую в плоскости этого шестиугольника, не меньше, чем a. Поскольку противоположные стороны шестиугольника KLMNP параллельны, его проекция на некоторую прямую l будет совпадатьс проекцией одного из отрезков KN, LP , MQ. Пусть,
для определенности, проекция на l совпадает с отрезком K
N
, где и N
— проекции точек K и N соответственно. Можно предполагать, что K
, N
, P и Q лежат по одну сторону от KN этого можно добиться параллельным сдвигом l). Тогда один из углов K
KN
, N
N K
— не тупой, пусть, например, не тупой
(см. рис. 312). Тогда K
N
= KN sin
∠K
KN
KN sin ∠QKN. Но sin
∠QKN — это расстояние между прямыми QK и MN, поэтому KN sin ∠QKN a.
Пустьшестиугольник KLMNP Q помещен в прямоугольник Π со сторонами, равными d
1
, d
2
. Тогда каждая из сторон d
1
, не меньше, чем длина проекции KLMNP Q на прямые, параллельные сторонам Π. Отсюда по доказанному a, d
2
Заметим, что при проекции на плоскость отрезок LP переходит в отрезок см. рис. 311), поэтому LP AD
1
=
√
b
2
+ c
2
. С
другой стороны, LP содержится в Π, поэтому длина LP не превосходит длины диагонали 1
+ d
2 прямоугольника Π. Получаем, что 1
+ d
2 2
b
2
+ c
2
.
(2)
a
b
c
A
B
C
D
A
1
B
1
C
1
D
1
K
P
Q
L
M
N
Рис. Рис. Докажем, что проекция шестиугольника на любую прямую, лежащую в плоскости этого шестиугольника, не меньше, чем a. Поскольку противоположные стороны шестиугольника KLMNP параллельны, его проекция на некоторую прямую l будет совпадатьс проекцией одного из отрезков KN, LP , MQ. Пусть,
для определенности, проекция на l совпадает с отрезком K
N
, где и N
— проекции точек K и N соответственно. Можно предполагать, что K
, N
, P и Q лежат по одну сторону от KN этого можно добиться параллельным сдвигом l). Тогда один из углов K
KN
, N
N K
— не тупой, пусть, например, не тупой
(см. рис. 312). Тогда K
N
= KN sin
∠K
KN
KN sin ∠QKN. Но sin
∠QKN — это расстояние между прямыми QK и MN, поэтому KN sin ∠QKN a.
Пустьшестиугольник KLMNP Q помещен в прямоугольник Π со сторонами, равными d
1
, d
2
. Тогда каждая из сторон d
1
, не меньше, чем длина проекции KLMNP Q на прямые, параллельные сторонам Π. Отсюда по доказанному a, d
2
Заметим, что при проекции на плоскость отрезок LP переходит в отрезок см. рис. 311), поэтому LP AD
1
=
√
b
2
+ c
2
. С
другой стороны, LP содержится в Π, поэтому длина LP не превосходит длины диагонали 1
+ d
2 прямоугольника Π. Получаем, что 1
+ d
2 2
b
2
+ c
2
.
(2)
УЧЕБНЫЙ ГОД, 9
КЛАСС
421
Если бы каждая из сторон d
1
, была меньше b, то мы получили бы противоречие неравенству (2). Поэтому одна из сторон d
1
, не меньше, другая сторона не меньше a в силу (1). Следовательно, в Π можно по- меститьпрямоугольник со сторонами a, b, равный грани ABCD.
2004–2005 г класс
A
B
C
D
Q
P
A
Рис. 313
713. Построим биссектрису угла и рассмотрим точку A
, симметричную относительно этой биссектрисы. Так как CP = то построенная биссектриса является серединным перпендикуляром к отрезку P Q. Значит, четырехугольник равнобо- кая трапеция или прямоугольник,
следовательно, лежит на описанной окружности AP Q при любом положении точек P и удовлетворяющем условию. Ответ. Верно.
Предположим, что Олег не сможет выбратьдве требуемые клетки. Заменим все числа на их остатки при делении на 4. Тогда в таблице стоит по чисел 0, 1, 2 и 3. Разобьем таблицу на 121 табличку 2 × 2. В каждой такой табличке может стоятьне более одного нуля и не более одной двойки. Но так как количество табличек равно количеству нулей и количеству двоек, тов каждой табличке стоит ровно один нольи ровно одна двойка.
Заметим, что в каждой табличке два оставшихся числа оба должны быть либо единицами, либо тройками. Но тогда количество единиц четно, однако их 121 — противоречие. Преобразуем условие 1
a
1
− 1
> S
⇐⇒ a
2 1
> (a
1
+ a
2
+ a
3
)(a
1
− 1) ⇐⇒
⇐⇒ a
1
+ a
2
+ a
3
> a
1
(a
2
+ a
3
)
⇐⇒
1
a
2
+ a
3
>
a
1
a
1
+ a
2
+ Сложив это неравенство с двумя аналогичными, получаем+ a
2
+
1
a
2
+ a
3
+
1
a
3
+ a
1
>
a
1
+ a
2
+ a
3
a
1
+ a
2
+ a
3
= что и требовалось
КЛАСС
421
Если бы каждая из сторон d
1
, была меньше b, то мы получили бы противоречие неравенству (2). Поэтому одна из сторон d
1
, не меньше, другая сторона не меньше a в силу (1). Следовательно, в Π можно по- меститьпрямоугольник со сторонами a, b, равный грани ABCD.
2004–2005 г класс
A
B
C
D
Q
P
A
Рис. 313
713. Построим биссектрису угла и рассмотрим точку A
, симметричную относительно этой биссектрисы. Так как CP = то построенная биссектриса является серединным перпендикуляром к отрезку P Q. Значит, четырехугольник равнобо- кая трапеция или прямоугольник,
следовательно, лежит на описанной окружности AP Q при любом положении точек P и удовлетворяющем условию. Ответ. Верно.
Предположим, что Олег не сможет выбратьдве требуемые клетки. Заменим все числа на их остатки при делении на 4. Тогда в таблице стоит по чисел 0, 1, 2 и 3. Разобьем таблицу на 121 табличку 2 × 2. В каждой такой табличке может стоятьне более одного нуля и не более одной двойки. Но так как количество табличек равно количеству нулей и количеству двоек, тов каждой табличке стоит ровно один нольи ровно одна двойка.
Заметим, что в каждой табличке два оставшихся числа оба должны быть либо единицами, либо тройками. Но тогда количество единиц четно, однако их 121 — противоречие. Преобразуем условие 1
a
1
− 1
> S
⇐⇒ a
2 1
> (a
1
+ a
2
+ a
3
)(a
1
− 1) ⇐⇒
⇐⇒ a
1
+ a
2
+ a
3
> a
1
(a
2
+ a
3
)
⇐⇒
1
a
2
+ a
3
>
a
1
a
1
+ a
2
+ Сложив это неравенство с двумя аналогичными, получаем+ a
2
+
1
a
2
+ a
3
+
1
a
3
+ a
1
>
a
1
+ a
2
+ a
3
a
1
+ a
2
+ a
3
= что и требовалось
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Ответ. Может.
Лемма. Пусть за x рублей Вася смог выложить в нужном порядке на стол некоторые N −1 карточку, где N 3
k
. Тогда он сможет
добавить к выложенным карточкам еще одну, потратив при этом
еще не более k рублей, те. затратив всего не более x + k рублей.
Д ока за тел ьс т во леммы проведем индукцией по числу k. База = очевидна. Пустьдля всех N лемма доказана. Первый рубль
Вася потратит на то, чтобы правильно выложить на стол ю карточку и карточки A и B, уже лежащие на местах
N
3
и
2N
3
. Тогда я карточка попадет в одну из трех частей, на которые другие две карточки разбивают уже выложенную на стол последовательность. Но карточки A и B разбивают лежащую на столе последовательность из N − 1 карточки на куски размером не более чем по 3
k−1
−1 карточек, а значит Васе осталосьопре- делитьместо карточки с номером N средине более чем 3
k−1
− 1 карточек,
потратив не более чем k−1 рубль, а это можно сделать по предположению индукции. Таким образом, лемма доказана.
Теперь, используя лемму, подсчитаем Васины затраты на выкладывание всех 365 карточек. На выкладывание первых трех карточек Вася потратит рубль. На добавление к ним карточек с номерами от 4 до 9 всего карточек) Вася потратит не более 2 рублей на каждую карточку. На карточки с 10 по 27 не более 3 рублей на каждую, с 28 по 81 не более рублей, с 82 по 243 не более 5 рублей и наконец на карточки с номерами от 244 доне более 6 рублей на каждую. Итого, Вася сможет выложить все карточки на стол в нужном порядке, потратив не более чем 1 + 6 · 2 +
+ 18
· 3 + 54 · 4 + 162 · 5 + 122 · 6 = 1845 < 2000 рублей. Таким образом,
Вася сможет потратитьне более 2000 рублей. Первое решение. Утверждение верно, если все числа — рациональны. Пусть наше множество содержит иррациональное число a. Тогда каждое из остальных чисел имеет вид либо p − a, либо, где p — рационально. Покажем, что чисел вида p − a не больше двух. Пусть b
1
= p
1
− a,
b
2
= p
2
− a, b
3
= p
3
− a, тогда b
1
+ b
2
= (p
1
+ p
2
)
− 2a — не рационально,
значит, b
1
·b
2
= p
1
p
2
−a(p
1
+p
2
)+a
2
, а также b
1
·b
3
, b
2
·b
3
— рациональны.
Отсюда A
3
= a
2
−a(p
1
+ p
2
)
, A
2
= a
2
−a(p
1
+ p
3
)
, A
1
= a
2
−a(p
2
+ рациональны, значит, A
3
−A
2
= a(p
3
−p
2
)
— рационально, что возможно только прите противоречие.
Значит, чисел второго вида больше двух, пусть c
1
=
q
1
a
, c
2
=
q
2
a
, c
3
=
=
q
3
a
— такие числа. Сумма c
1
+ c
2
=
q
1
+ может бытьрациональной только при q
2
=
−q
1
. Но q
3
= q
2
, значит, сумма c
1
+ c
3
=
q
1
+ q
3
a
—
Лемма. Пусть за x рублей Вася смог выложить в нужном порядке на стол некоторые N −1 карточку, где N 3
k
. Тогда он сможет
добавить к выложенным карточкам еще одну, потратив при этом
еще не более k рублей, те. затратив всего не более x + k рублей.
Д ока за тел ьс т во леммы проведем индукцией по числу k. База = очевидна. Пустьдля всех N лемма доказана. Первый рубль
Вася потратит на то, чтобы правильно выложить на стол ю карточку и карточки A и B, уже лежащие на местах
N
3
и
2N
3
. Тогда я карточка попадет в одну из трех частей, на которые другие две карточки разбивают уже выложенную на стол последовательность. Но карточки A и B разбивают лежащую на столе последовательность из N − 1 карточки на куски размером не более чем по 3
k−1
−1 карточек, а значит Васе осталосьопре- делитьместо карточки с номером N средине более чем 3
k−1
− 1 карточек,
потратив не более чем k−1 рубль, а это можно сделать по предположению индукции. Таким образом, лемма доказана.
Теперь, используя лемму, подсчитаем Васины затраты на выкладывание всех 365 карточек. На выкладывание первых трех карточек Вася потратит рубль. На добавление к ним карточек с номерами от 4 до 9 всего карточек) Вася потратит не более 2 рублей на каждую карточку. На карточки с 10 по 27 не более 3 рублей на каждую, с 28 по 81 не более рублей, с 82 по 243 не более 5 рублей и наконец на карточки с номерами от 244 доне более 6 рублей на каждую. Итого, Вася сможет выложить все карточки на стол в нужном порядке, потратив не более чем 1 + 6 · 2 +
+ 18
· 3 + 54 · 4 + 162 · 5 + 122 · 6 = 1845 < 2000 рублей. Таким образом,
Вася сможет потратитьне более 2000 рублей. Первое решение. Утверждение верно, если все числа — рациональны. Пусть наше множество содержит иррациональное число a. Тогда каждое из остальных чисел имеет вид либо p − a, либо, где p — рационально. Покажем, что чисел вида p − a не больше двух. Пусть b
1
= p
1
− a,
b
2
= p
2
− a, b
3
= p
3
− a, тогда b
1
+ b
2
= (p
1
+ p
2
)
− 2a — не рационально,
значит, b
1
·b
2
= p
1
p
2
−a(p
1
+p
2
)+a
2
, а также b
1
·b
3
, b
2
·b
3
— рациональны.
Отсюда A
3
= a
2
−a(p
1
+ p
2
)
, A
2
= a
2
−a(p
1
+ p
3
)
, A
1
= a
2
−a(p
2
+ рациональны, значит, A
3
−A
2
= a(p
3
−p
2
)
— рационально, что возможно только прите противоречие.
Значит, чисел второго вида больше двух, пусть c
1
=
q
1
a
, c
2
=
q
2
a
, c
3
=
=
q
3
a
— такие числа. Сумма c
1
+ c
2
=
q
1
+ может бытьрациональной только при q
2
=
−q
1
. Но q
3
= q
2
, значит, сумма c
1
+ c
3
=
q
1
+ q
3
a
—
УЧЕБНЫЙ ГОД, 9
КЛАСС
423
иррациональна. Тогда число c
1
· c
3
=
q
1
q
3
a
2
— рационально, откуда a
2
—
рационально.
Второе решение. Рассмотрим произвольные 6 чисел из нашего набора. Поставим этим 6 числам в соответствие граф следующим образом у него шестьвершин, соответствующих нашим шести числам вершины соединены синим ребром, если сумма соответствующих чисел рациональна,
и соединены красным ребром, если произведение соответствующих чисел рационально. Хорошо известно, что в таком графе найдется одноцветный треугольник. Рассмотрим каждый из этих случаев. Нашелся синий треугольник, те. нашлись три числа x, y, z такие,
что x + y, x + z, y + z рациональны. Но тогда, например, (x + y) + (x +
+ z)
− (y + z) = 2x рационально. То есть числа x, y, z рациональны. Тогда рассмотрим любое из оставшихся чисел t. Из рациональности любого из чисел xt и x + t следует рациональность числа t все числа по условию отличны от нуля. То естьвсе числа набора рациональны. Нашелся красный треугольник. То естьнашлисьтри числа x, y, такие, что xy, xz, yz рациональны. Но тогда, например, число рационально. То есть числа x
2
, y
2
, рациональны. Если хотя бы одно из чисел x, y, z рационально, то аналогично предыдущему случаю получаем рациональность всех чисел набора. Пусть теперь x = m
√
a
, где
a
рационально, m = ±1. Так как xy = m√ay = b — рационально, то =
b
m
√
a
=
b
√
a
ma
= c
√
a
, где c = m — рационально. Тогда рассмотрим любое из оставшихся чисел t. Если xt или yt — рационально, то аналогично предыдущему t = d
√
a
, где d — рационально, те рационально.
Если же x + t и y + t — рациональны, то (y + t) − (x + t) = (m − c)
√
a
— рационально. Но (x + t) − (y + t) = (m − c)
√
a
— иррационально.
Противоречие.
То естьмы получили, что либо все числа набора рациональны, либо квадраты всех чисел набора рациональны, что и требовалось.
Замечание. Утверждение задачи верно при любом n 5.
718. Ответ. Если x
1
x
2
— корни уравнения, то x
1
, x
2
∈ N и x
1
+ x
2
= S(A)
,
x
1
x
2
= S(B)
, поэтому (x
1
+ 1)(x
2
+ 1) = S(B) + S(A) + 1 = 1 + 2 + 4
+. . .
. . . + 2 2005
+ 1 = 2 2006
. Значит, x
1
+ 1 = 2
k
, x
2
+ 1 = 2 2006−k
, где k может приниматьзначения 1, 2, . . . , Наоборот, пусть x
1
, x
2
— числа такого вида, тогда они являются корнями уравнения x
2
−px+q = 0, где p = 2
k
+ 2 2006−k
−2, q = 2 Но число p имеет единственное разложение в сумму различных степеней двойки (двоичное разложение, ив этом разложении степени двойки не
КЛАСС
423
иррациональна. Тогда число c
1
· c
3
=
q
1
q
3
a
2
— рационально, откуда a
2
—
рационально.
Второе решение. Рассмотрим произвольные 6 чисел из нашего набора. Поставим этим 6 числам в соответствие граф следующим образом у него шестьвершин, соответствующих нашим шести числам вершины соединены синим ребром, если сумма соответствующих чисел рациональна,
и соединены красным ребром, если произведение соответствующих чисел рационально. Хорошо известно, что в таком графе найдется одноцветный треугольник. Рассмотрим каждый из этих случаев. Нашелся синий треугольник, те. нашлись три числа x, y, z такие,
что x + y, x + z, y + z рациональны. Но тогда, например, (x + y) + (x +
+ z)
− (y + z) = 2x рационально. То есть числа x, y, z рациональны. Тогда рассмотрим любое из оставшихся чисел t. Из рациональности любого из чисел xt и x + t следует рациональность числа t все числа по условию отличны от нуля. То естьвсе числа набора рациональны. Нашелся красный треугольник. То естьнашлисьтри числа x, y, такие, что xy, xz, yz рациональны. Но тогда, например, число рационально. То есть числа x
2
, y
2
, рациональны. Если хотя бы одно из чисел x, y, z рационально, то аналогично предыдущему случаю получаем рациональность всех чисел набора. Пусть теперь x = m
√
a
, где
a
рационально, m = ±1. Так как xy = m√ay = b — рационально, то =
b
m
√
a
=
b
√
a
ma
= c
√
a
, где c = m — рационально. Тогда рассмотрим любое из оставшихся чисел t. Если xt или yt — рационально, то аналогично предыдущему t = d
√
a
, где d — рационально, те рационально.
Если же x + t и y + t — рациональны, то (y + t) − (x + t) = (m − c)
√
a
— рационально. Но (x + t) − (y + t) = (m − c)
√
a
— иррационально.
Противоречие.
То естьмы получили, что либо все числа набора рациональны, либо квадраты всех чисел набора рациональны, что и требовалось.
Замечание. Утверждение задачи верно при любом n 5.
718. Ответ. Если x
1
x
2
— корни уравнения, то x
1
, x
2
∈ N и x
1
+ x
2
= S(A)
,
x
1
x
2
= S(B)
, поэтому (x
1
+ 1)(x
2
+ 1) = S(B) + S(A) + 1 = 1 + 2 + 4
+. . .
. . . + 2 2005
+ 1 = 2 2006
. Значит, x
1
+ 1 = 2
k
, x
2
+ 1 = 2 2006−k
, где k может приниматьзначения 1, 2, . . . , Наоборот, пусть x
1
, x
2
— числа такого вида, тогда они являются корнями уравнения x
2
−px+q = 0, где p = 2
k
+ 2 2006−k
−2, q = 2 Но число p имеет единственное разложение в сумму различных степеней двойки (двоичное разложение, ив этом разложении степени двойки не
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
превосходят 2 2005
, а двоичное разложение q содержит 1 на тех местах, где у числа p — нули, так как p + q = 2 2005
− 1. Итак, для каждого k такого, что 1 k 1003, существует единственное разбиение (A, B), дающее указанные корни и Рис. 314
превосходят 2 2005
, а двоичное разложение q содержит 1 на тех местах, где у числа p — нули, так как p + q = 2 2005
− 1. Итак, для каждого k такого, что 1 k 1003, существует единственное разбиение (A, B), дающее указанные корни и Рис. 314
1 ... 54 55 56 57 58 59 60 61 ... 64
719. Пусть, для определенности,
точка D лежит на дуге BC, не содержащей точки A см. рис. Обозначим через H точку пересечения высот треугольника ABC, а через и H
B
— вторые точки пересечения прямых AH и BH с окружностью.
Углы и равны как вписанные, опирающиеся на одну дугу.
Далее, ∠CAA
=
=
∠CBB
= 90
◦
− ∠ACB. Следовательно, прямоугольные треугольники, и имеют по равному острому углу, и поэтому подобны. Кроме того, треугольники и имеют общий катет, и значит равны, отсюда HA
= Так как ∠B
AQ =
∠CAD = ∠CBD = ∠A
BP
, то отрезки AQ и являются соответствующими в подобных треугольниках и следовательно. Построим на высоте точку S такую,
что QS A
B
. Из теоремы Фалеса вытекает, что отношение
A
S
A
H
равно
B
Q
B
H
=
A
P
A
H
A
. По доказанному HA
= H
A
A
, значит, A
S = A
P
, и A
B
— средняя линия треугольника P QS, те. делит пополам сторону P Q.
720. Разобьем всех сидящих за столом на 50 пар соседей и назовем людей в любой паре знакомыми. Тогда достаточно разбитьих на две группы
(по одному представителю от страны в группе) так, чтобы в каждой группе не оказалосьзнакомых. Покажем, как это можно сделать.
Выберем любого представителя страны 1, поместим его в первую группу, второго представителя этой же страны поместим во вторую группу, его знакомого (представителя, скажем, й страны) — снова в первую, второго представителя й страны — во вторую и т. д. Этот процесс завершится, когда очередной знакомый уже распределен это возможно только если этот знакомый — изначальный представитель первой страны, тогда он помещен в первую группу, что от него и требовалось
УЧЕБНЫЙ ГОД, 10
КЛАСС
425
Если еще осталисьнераспределенные люди, осталосьповторитьпро- цесс, начиная с любого нераспределенного человека класс. Ответ. 11.
1 =
4
− 2 4
− 2
,
3 =
8
− 2 4
− 2
,
5 =
16
− 1 4
− 1
=
2 5
− 2 2
3
− 2
,
7 =
16
− 2 4
− 2
,
9 = 2 3
+ 1 =
2 6
− 1 2
3
− 1
=
2 7
− 2 2
4
− 2
,
2 = 2
· 1 =
2 3
− 2 2
2 2
− 2
,
. . . ,
10 = 2
· 5 =
2 6
− 2 2
2 3
− Предположим, что 11 =
2
a
− 2
b
2
c
− 2
d
. Не уменьшая общности, положим > b
, c > d. Обозначим m = a − b, n = c − d, k = b − d. Получаем 1) = 2
k
(2
m
− Так как в левой части целое нечетное число, то k = 0. Заметим, что n = не подходит. Если же m > n > 1, то 2
m
− 1 и 2
n
− 1 дают остаток 3 при делении на 4. Значит, левая и правая части дают соответственно остатки и 3 при делении на 4. Противоречие.
Замечание. Можно прийти к противоречию по другому. Из алгоритма
Евклида следует, что 2
m
− 1 делится на 2
n
− 1 без остатка, тогда и только тогда, когда m делится на n. Значит, надо доказать, что 11 = 1 + 2
n
+
+ 2 2n
+ . . .
. Но последнее очевидно, поскольку 11 неравно ни одному из чисел 1 + 2, 1 + 2 + 4, 1 + 4, 1 + 8.
722. Пустьв верхней строке стоят числа a
1
, a
2
, . . . , a
n
. Переставим столбцы так, что a
1
a
2
. . . a
n
. Тогда в нижней строке стоят соответственно b
1
= 1
− a
1
, b
2
= 1
− a
2
, . . . , b
n
= 1
− a
n
; ясно, что b
2
. . . b
n
. Если a
1
+ a
2
+ . . . + a
n
n + 1 4
, то вычеркнем все числа нижней строки. Иначе найдем минимальный номер k такой, что a
1
+
+a
2
+ . . . +a
k
>
n + 1 4
, вычеркнем в верхней строке числа a
k
, a
k+1
, . . . , а в нижней — b
1
, b
2
, . . . , b
k−1
. По выбору k имеем a
1
+ . . . + a
k−1
n + 1 Остается доказать, что b
k
+ b
k+1
+ . . . + b
n
n + 1 Поскольку a
k
a
1
+ . . . + a
k
k
>
n + 1 4k
, имеем+ b
k+1
+ . . . + b
n
(n + 1 − k)b
k
= (n + 1
− k)(1 − a
k
) <
< (n + 1
− k)
1
−
n + 1 4k
=
5 4
(n + 1)
−
(n + 1)
2
+ (2k)
2 4k
5 4
(n + 1)
−
2(n + 1)(2k)
4k
=
n + 1 4
.
КЛАСС
425
Если еще осталисьнераспределенные люди, осталосьповторитьпро- цесс, начиная с любого нераспределенного человека класс. Ответ. 11.
1 =
4
− 2 4
− 2
,
3 =
8
− 2 4
− 2
,
5 =
16
− 1 4
− 1
=
2 5
− 2 2
3
− 2
,
7 =
16
− 2 4
− 2
,
9 = 2 3
+ 1 =
2 6
− 1 2
3
− 1
=
2 7
− 2 2
4
− 2
,
2 = 2
· 1 =
2 3
− 2 2
2 2
− 2
,
. . . ,
10 = 2
· 5 =
2 6
− 2 2
2 3
− Предположим, что 11 =
2
a
− 2
b
2
c
− 2
d
. Не уменьшая общности, положим > b
, c > d. Обозначим m = a − b, n = c − d, k = b − d. Получаем 1) = 2
k
(2
m
− Так как в левой части целое нечетное число, то k = 0. Заметим, что n = не подходит. Если же m > n > 1, то 2
m
− 1 и 2
n
− 1 дают остаток 3 при делении на 4. Значит, левая и правая части дают соответственно остатки и 3 при делении на 4. Противоречие.
Замечание. Можно прийти к противоречию по другому. Из алгоритма
Евклида следует, что 2
m
− 1 делится на 2
n
− 1 без остатка, тогда и только тогда, когда m делится на n. Значит, надо доказать, что 11 = 1 + 2
n
+
+ 2 2n
+ . . .
. Но последнее очевидно, поскольку 11 неравно ни одному из чисел 1 + 2, 1 + 2 + 4, 1 + 4, 1 + 8.
722. Пустьв верхней строке стоят числа a
1
, a
2
, . . . , a
n
. Переставим столбцы так, что a
1
a
2
. . . a
n
. Тогда в нижней строке стоят соответственно b
1
= 1
− a
1
, b
2
= 1
− a
2
, . . . , b
n
= 1
− a
n
; ясно, что b
2
. . . b
n
. Если a
1
+ a
2
+ . . . + a
n
n + 1 4
, то вычеркнем все числа нижней строки. Иначе найдем минимальный номер k такой, что a
1
+
+a
2
+ . . . +a
k
>
n + 1 4
, вычеркнем в верхней строке числа a
k
, a
k+1
, . . . , а в нижней — b
1
, b
2
, . . . , b
k−1
. По выбору k имеем a
1
+ . . . + a
k−1
n + 1 Остается доказать, что b
k
+ b
k+1
+ . . . + b
n
n + 1 Поскольку a
k
a
1
+ . . . + a
k
k
>
n + 1 4k
, имеем+ b
k+1
+ . . . + b
n
(n + 1 − k)b
k
= (n + 1
− k)(1 − a
k
) <
< (n + 1
− k)
1
−
n + 1 4k
=
5 4
(n + 1)
−
(n + 1)
2
+ (2k)
2 4k
5 4
(n + 1)
−
2(n + 1)(2k)
4k
=
n + 1 4
.
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Ответ. За 1003 вопроса.
Пустьбыло задано N вопросов. Ясно, что каждая карточка участвует хотя бы водном вопросе, иначе число на ней мы неопределим. Пустьесть
k
карточек, участвующих ровно водном вопросе. Тогда водном вопросе не может встретиться двух таких карточек. Действительно, если бы две таких карточки участвовали водном вопросе, то, поменяв местами числа на этих карточках, мы не изменим ответов на вопросы поэтому невозможно установить, какое число на которой из них написано. Следовательно N. Остальные карточки участвовали хотя бы в двух вопросах. Теперь, просуммировав для каждой карточки количество вопросов, в которых она участвовала, получим утроенное количество вопросов. Поэтому k+2(2005−k) = 4010−k 4010−N, откуда 2N 2005, N Приведем способ узнатьчисла за 1003 вопроса. Отложим одну карточку, а остальные разобьем на 334 группы по 6 карточек. В каждой группе занумеруем карточки числами от 1 дои зададим три вопроса (1, 2, 3),
(3, 4, и (5, 6, 1). Тогда числа на карточках 1, 3, 5 встречаются в двух ответах (для разных карточек — в разных парах) и поэтому однозначно определяются, а числа на карточках 2, 4, 6 — оставшиеся числа в каждом из ответов. Так за 6
× 3 = 1002 вопроса мы узнаем числа на 2004 карточках. Осталосьспроситьпро отложенную карточку вместе с любыми двумя уже известными. Пусть B
0
, C
0
— середины сторон AC, AB соответственно, третья вневписанная окружность, P и Q — точки пересечения и Положим AB = c, BC = a, CA = b. Обозначим через I
A
, I
B
, I
C
, центры окружностей ω
A
, ω
B
, ω
C
, ω
B
, соответственно. Обозначим через D, E, F точки касания ω
A
, ω
B
, и сторон BC, CA, AB; через, F
— точки касания ω
B
, и сторон CA, AB; через X, Y — точки касания и продолжений сторон AB, BC соответственно (см. рис. Известно, что AD делит пополам периметр треугольника ABC это следует из того, что CD =
a + c − b
2
). Поэтому достаточно показать, что) A лежит на P Q; (2) AD⊥I
B
I
C
1) Ясно, что E и симметричны относительно B
0
. Следовательно CE =
b + c − a
2
. Аналогично, AF
=
b + c − a
2
. Получаем, что касательные к и ω
C
, проведенные из точки A, равны. Поэтому A лежит на радикальной оси P Q окружностей и ω
C
2) Из симметрии следует, что AI
B
CI
B
— параллелограмм, поэтому =
−−→
AI
B
. Аналогично, AI
C
BI
C
— параллелограмм, поэтому. Построим такую точку T , что BI
C
T C
— параллелограмм. Получаем УЧЕБНЫЙ ГОД, 10
КЛАСС
427
A
B
C
I
A
I
B
I
C
D
E
F
B
0
C
0
I
B
I
C
X
Y
E
F
P
Q
T
Рис. Так как и являются внутренней и внешней биссектрисами угла BAC, то AI
A
⊥I
B
I
C
. Аналогично, BI
B
⊥I
C
I
A
, CI
C
⊥I
A
I
B
. Следовательно. Это означает, что I
A
BC
∼ I
A
I
B
I
C
. Заметим, что и I
A
A
— соответствующие высоты в подобных треугольниках и I
A
I
B
I
C
. Отсюда следует, что
I
A
D
I
A
A
=
BC
I
B
I
C
Рассмотрим треугольники и ADI
A
. Имеем I
B
T
I
B
I
C
⊥I
A
A
,
I
C
T
BC⊥I
A
D
,
I
C
T
I
B
T
=
BC
I
B
I
C
=
I
A
D
I
A
A
. Отсюда следует, что треугольники
I
B
I
C
T
и подобны, и их соответствующие стороны перпендикулярны. Итак, Замечание. Вместо части (2) можно доказать, что D лежит наследующим образом.
Пусть ω — вписанная окружностьтреугольника ABC. Нетрудно видеть, что ω касается AB и AC соответственно в точках F
, E
. Обозначим через I центр ω, через D
— точку касания ω и BC. Обозначим через r,
Пустьбыло задано N вопросов. Ясно, что каждая карточка участвует хотя бы водном вопросе, иначе число на ней мы неопределим. Пустьесть
k
карточек, участвующих ровно водном вопросе. Тогда водном вопросе не может встретиться двух таких карточек. Действительно, если бы две таких карточки участвовали водном вопросе, то, поменяв местами числа на этих карточках, мы не изменим ответов на вопросы поэтому невозможно установить, какое число на которой из них написано. Следовательно N. Остальные карточки участвовали хотя бы в двух вопросах. Теперь, просуммировав для каждой карточки количество вопросов, в которых она участвовала, получим утроенное количество вопросов. Поэтому k+2(2005−k) = 4010−k 4010−N, откуда 2N 2005, N Приведем способ узнатьчисла за 1003 вопроса. Отложим одну карточку, а остальные разобьем на 334 группы по 6 карточек. В каждой группе занумеруем карточки числами от 1 дои зададим три вопроса (1, 2, 3),
(3, 4, и (5, 6, 1). Тогда числа на карточках 1, 3, 5 встречаются в двух ответах (для разных карточек — в разных парах) и поэтому однозначно определяются, а числа на карточках 2, 4, 6 — оставшиеся числа в каждом из ответов. Так за 6
× 3 = 1002 вопроса мы узнаем числа на 2004 карточках. Осталосьспроситьпро отложенную карточку вместе с любыми двумя уже известными. Пусть B
0
, C
0
— середины сторон AC, AB соответственно, третья вневписанная окружность, P и Q — точки пересечения и Положим AB = c, BC = a, CA = b. Обозначим через I
A
, I
B
, I
C
, центры окружностей ω
A
, ω
B
, ω
C
, ω
B
, соответственно. Обозначим через D, E, F точки касания ω
A
, ω
B
, и сторон BC, CA, AB; через, F
— точки касания ω
B
, и сторон CA, AB; через X, Y — точки касания и продолжений сторон AB, BC соответственно (см. рис. Известно, что AD делит пополам периметр треугольника ABC это следует из того, что CD =
a + c − b
2
). Поэтому достаточно показать, что) A лежит на P Q; (2) AD⊥I
B
I
C
1) Ясно, что E и симметричны относительно B
0
. Следовательно CE =
b + c − a
2
. Аналогично, AF
=
b + c − a
2
. Получаем, что касательные к и ω
C
, проведенные из точки A, равны. Поэтому A лежит на радикальной оси P Q окружностей и ω
C
2) Из симметрии следует, что AI
B
CI
B
— параллелограмм, поэтому =
−−→
AI
B
. Аналогично, AI
C
BI
C
— параллелограмм, поэтому. Построим такую точку T , что BI
C
T C
— параллелограмм. Получаем УЧЕБНЫЙ ГОД, 10
КЛАСС
427
A
B
C
I
A
I
B
I
C
D
E
F
B
0
C
0
I
B
I
C
X
Y
E
F
P
Q
T
Рис. Так как и являются внутренней и внешней биссектрисами угла BAC, то AI
A
⊥I
B
I
C
. Аналогично, BI
B
⊥I
C
I
A
, CI
C
⊥I
A
I
B
. Следовательно. Это означает, что I
A
BC
∼ I
A
I
B
I
C
. Заметим, что и I
A
A
— соответствующие высоты в подобных треугольниках и I
A
I
B
I
C
. Отсюда следует, что
I
A
D
I
A
A
=
BC
I
B
I
C
Рассмотрим треугольники и ADI
A
. Имеем I
B
T
I
B
I
C
⊥I
A
A
,
I
C
T
BC⊥I
A
D
,
I
C
T
I
B
T
=
BC
I
B
I
C
=
I
A
D
I
A
A
. Отсюда следует, что треугольники
I
B
I
C
T
и подобны, и их соответствующие стороны перпендикулярны. Итак, Замечание. Вместо части (2) можно доказать, что D лежит наследующим образом.
Пусть ω — вписанная окружностьтреугольника ABC. Нетрудно видеть, что ω касается AB и AC соответственно в точках F
, E
. Обозначим через I центр ω, через D
— точку касания ω и BC. Обозначим через r,
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ, соответственно радиусы окружностей ω, ω
B
, ω
C
. В окружности проведем диаметр см. рис. Рис. Гомотетия с центром A, переводящая в ω, переводит D в S. Поэтому, достаточно доказать, что S ∈ P Гомотетия с центром и коэффициентом
r
B
r
переводит ω в ω
B
. Обозначим через образ точки S при этой гомотетии. Также, обозначим через образ точки S при гомотетии с центром F
, переводящей ω в Достаточно показать, что E
S
·SS
B
= F
S
·SS
C
. Заметим, что E
S
·SS
B
=
= E
S
·(E
S
B
−E
S) = E
S
·(
r
B
r
E
S
−E
S) =
r
B
− r
r
E
S
2
. Аналогично SS
C
=
r
C
− r
r
F
S
2
. Чтобы завершитьрешение, установим, что r)E
S
2
= (r
C
− Четырехугольник вписанный, поэтому ∠SE
F
=
∠SD
F
=
=
π
2
− Аналогично, ∠SF
E
=
∠C
2
. По теореме синусов
E
S
F
S
=
sin
∠C
2
sin
∠B
2
.
(2)
Четырехугольник вписанный, поэтому =
∠B
2
. Аналогично, ∠II
B
I
C
=
∠C
2
. Заметим, что
B
, ω
C
. В окружности проведем диаметр см. рис. Рис. Гомотетия с центром A, переводящая в ω, переводит D в S. Поэтому, достаточно доказать, что S ∈ P Гомотетия с центром и коэффициентом
r
B
r
переводит ω в ω
B
. Обозначим через образ точки S при этой гомотетии. Также, обозначим через образ точки S при гомотетии с центром F
, переводящей ω в Достаточно показать, что E
S
·SS
B
= F
S
·SS
C
. Заметим, что E
S
·SS
B
=
= E
S
·(E
S
B
−E
S) = E
S
·(
r
B
r
E
S
−E
S) =
r
B
− r
r
E
S
2
. Аналогично SS
C
=
r
C
− r
r
F
S
2
. Чтобы завершитьрешение, установим, что r)E
S
2
= (r
C
− Четырехугольник вписанный, поэтому ∠SE
F
=
∠SD
F
=
=
π
2
− Аналогично, ∠SF
E
=
∠C
2
. По теореме синусов
E
S
F
S
=
sin
∠C
2
sin
∠B
2
.
(2)
Четырехугольник вписанный, поэтому =
∠B
2
. Аналогично, ∠II
B
I
C
=
∠C
2
. Заметим, что
УЧЕБНЫЙ ГОД, КЛАСС =
ID
sin ∠B
2
=
r
sin ∠B
2
, и также I
B
B =
r
B
sin ∠B
2
. Получаем I
B
I = I
B
B
−
− IB =
r
B
− r
sin ∠B
2
. Аналогично, I
C
I =
r
C
− r
sin ∠C
2
. Из теоремы синусов r
sin ∠B
2
r
C
− r
sin Из (2) и (3) получаем (1).
725. Ответ. Заметим, что если в строке a ладей, тов ней есть (a − 1) пара ладей,
которые бьют друг друга. Но тогда количество пар ладей, бьющих друг друга по горизонтали, не меньше, чем число ладей минус число горизонталей, те. не меньше 8. Аналогично, количество пар ладей, бьющих друг друга по вертикали, не меньше Пример для 16 ладей получается, если, например, расставитьпо 8 ладей на главных диагоналях. См. решение задачи 719.
727. Далее в решении латинские буквы обозначают целые числа.
Лемма 1. Если a = НОД(t + 1, t
2
− t + 1), то a = 1 либо a = Доказательство. Поделив с остатком t
2
− t + 1 на t + 1, получаем t + 1 = (t − 2)(t + 1) + 3. Из полученного равенства видим, что если общий делитель t
2
− t + 1 и t + 1, то d — делительчисла Аналогично, из равенства t
4
−t
3
+t
2
−t+1 = (t
3
−2t
2
+3t
−4)(t+1)+5
выводится
Лемма 2. Если b = НОД(t + 1, t
4
− t
3
+ t
2
− t + 1), то b = 1 либо = Имеем t
3
+ 1 = (t + 1)(t
2
− t + 1) = 2x
2
, где t = y
5
. Так как число t + 1 всегда нечетно, то из леммы 1 следует, что либо t + 1 = 2u
2
,
t
2
− t + 1 = v
2
, либо t + 1 = 6u
2
, t
2
− t + 1 = 3v
2
. Далее, при x > имеем t > 1, отсюда (t − 1)
2
< t
2
− t + 1 < t
2
, и равенство t
2
− t + 1 =
= выполняться не может. Получаем t + 1 = y
5
+ 1 = 6u
2
. С другой стороны, (y
5
+ 1)
− (y
3
+ 1) = y
3
(y
− 1)(y + 1) делится на произведение 1)y(y + 1), и поэтому делится на 3. Таким образом, y
3
+ делится назначит Далее, положим z = y
3
= 3m
− 1, тогда z
5
+ 1 = (z + 1)(z
4
− z
3
+
+ z
2
− z + 1) = 2x
2
. Если z
4
− z
3
+ z
2
− z + 1 делится на 5, то все доказано. В противном случае из леммы 2 следует, что сомножители в левой части равенства взаимно просты. Поскольку z
4
− z
3
+ z
2
− z + нечетно, получаем, что z + 1 = 2u
2
, z
4
− z
3
+ z
2
− z + 1 = v
2
. Но так как
ID
sin ∠B
2
=
r
sin ∠B
2
, и также I
B
B =
r
B
sin ∠B
2
. Получаем I
B
I = I
B
B
−
− IB =
r
B
− r
sin ∠B
2
. Аналогично, I
C
I =
r
C
− r
sin ∠C
2
. Из теоремы синусов r
sin ∠B
2
r
C
− r
sin Из (2) и (3) получаем (1).
725. Ответ. Заметим, что если в строке a ладей, тов ней есть (a − 1) пара ладей,
которые бьют друг друга. Но тогда количество пар ладей, бьющих друг друга по горизонтали, не меньше, чем число ладей минус число горизонталей, те. не меньше 8. Аналогично, количество пар ладей, бьющих друг друга по вертикали, не меньше Пример для 16 ладей получается, если, например, расставитьпо 8 ладей на главных диагоналях. См. решение задачи 719.
727. Далее в решении латинские буквы обозначают целые числа.
Лемма 1. Если a = НОД(t + 1, t
2
− t + 1), то a = 1 либо a = Доказательство. Поделив с остатком t
2
− t + 1 на t + 1, получаем t + 1 = (t − 2)(t + 1) + 3. Из полученного равенства видим, что если общий делитель t
2
− t + 1 и t + 1, то d — делительчисла Аналогично, из равенства t
4
−t
3
+t
2
−t+1 = (t
3
−2t
2
+3t
−4)(t+1)+5
выводится
Лемма 2. Если b = НОД(t + 1, t
4
− t
3
+ t
2
− t + 1), то b = 1 либо = Имеем t
3
+ 1 = (t + 1)(t
2
− t + 1) = 2x
2
, где t = y
5
. Так как число t + 1 всегда нечетно, то из леммы 1 следует, что либо t + 1 = 2u
2
,
t
2
− t + 1 = v
2
, либо t + 1 = 6u
2
, t
2
− t + 1 = 3v
2
. Далее, при x > имеем t > 1, отсюда (t − 1)
2
< t
2
− t + 1 < t
2
, и равенство t
2
− t + 1 =
= выполняться не может. Получаем t + 1 = y
5
+ 1 = 6u
2
. С другой стороны, (y
5
+ 1)
− (y
3
+ 1) = y
3
(y
− 1)(y + 1) делится на произведение 1)y(y + 1), и поэтому делится на 3. Таким образом, y
3
+ делится назначит Далее, положим z = y
3
= 3m
− 1, тогда z
5
+ 1 = (z + 1)(z
4
− z
3
+
+ z
2
− z + 1) = 2x
2
. Если z
4
− z
3
+ z
2
− z + 1 делится на 5, то все доказано. В противном случае из леммы 2 следует, что сомножители в левой части равенства взаимно просты. Поскольку z
4
− z
3
+ z
2
− z + нечетно, получаем, что z + 1 = 2u
2
, z
4
− z
3
+ z
2
− z + 1 = v
2
. Но так как
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ = 3m
− 1, то число в левой части последнего равенства при делении надает остаток 2, а число в правой части — остаток 0 или 1 — противоречие. Идея решения состоит в следующем. Если соединитьцентры соседних черных клеток отрезками, то объединение проведенных отрезков разбивает плоскостьна области. Из четности степеней вершин следует,
что области можно покраситьв два цвета (желтый и синий) так, чтобы области, граничащие по отрезку, имели разные цвета. Далее, покрасим зеленым в синих областях клетки счетной абсциссой, а в желтых — с нечетной. Остальные клетки покрасим красным.
Проведем формальные рассуждения. Введем координаты так, чтобы центры клеток были целочисленными, и будем считать, что окрашены не клетки, а их центры. Вначале окрасим все белые точки
в полоску, т. е.
так, чтобы зеленые точки имели четную абсциссу, а красные — нечетную.
Пустьграф Γ имеет в качестве вершин множество V всех черных точек, а в качестве ребер — множество всех отрезков E, соединяющих соседние черные точки. Заметим, что степенькаждой вершины в Γ четна.
Начнем движение по ребрам из какой-то вершины. Войдя в вершину по некоторому ребру, мы сможем выйти по другому ребру, поэтому когда- нибудьпридем в вершину, в которой уже были. Тем самым, в графе найден простой цикл C. Ребра C ограничивают на плоскости многоугольник. Изменим цвету всех красных и зеленых точек, лежащих внутри цикла C. Далее, перейдем к рассмотрению графа Γ
, получаемого из Γ удалением всех ребер цикла C. В графе Γ
степенькаждой вершины четна, поэтому снова найдем простой цикл, произведем перекрашивание, удалим ребра цикла, и т. д. Действуем так до тех пор, пока в соответствующем графе естьребра.
Докажем, что полученная в конце этого процесса раскраска удовлетворяет условию.
Если у черной точки P четыре белых соседа, то при каждом перекрашивании они находилисьлибо все внутри многоугольника, либо все вне, а значит перекрашивалисьодинаковое число раз. Тогда у P по два красных и зеленых соседа, поскольку так было в начальной раскраске.
Пустьу черной точки P два белых соседа K и L, и два черных соседа
M
и Пусть K и L лежат водной горизонтали или водной вертикали. Тогда
K
и L находилисьв разных частях плоскости относительно цикла только при перекрашивании точек внутри цикла, содержащего путь MP N. Таким образом, количество перекрашиваний точек K и L отличается на Так как в начальной раскраске K и L одноцветны, тов конечной — раз- ноцветны.
− 1, то число в левой части последнего равенства при делении надает остаток 2, а число в правой части — остаток 0 или 1 — противоречие. Идея решения состоит в следующем. Если соединитьцентры соседних черных клеток отрезками, то объединение проведенных отрезков разбивает плоскостьна области. Из четности степеней вершин следует,
что области можно покраситьв два цвета (желтый и синий) так, чтобы области, граничащие по отрезку, имели разные цвета. Далее, покрасим зеленым в синих областях клетки счетной абсциссой, а в желтых — с нечетной. Остальные клетки покрасим красным.
Проведем формальные рассуждения. Введем координаты так, чтобы центры клеток были целочисленными, и будем считать, что окрашены не клетки, а их центры. Вначале окрасим все белые точки
в полоску, т. е.
так, чтобы зеленые точки имели четную абсциссу, а красные — нечетную.
Пустьграф Γ имеет в качестве вершин множество V всех черных точек, а в качестве ребер — множество всех отрезков E, соединяющих соседние черные точки. Заметим, что степенькаждой вершины в Γ четна.
Начнем движение по ребрам из какой-то вершины. Войдя в вершину по некоторому ребру, мы сможем выйти по другому ребру, поэтому когда- нибудьпридем в вершину, в которой уже были. Тем самым, в графе найден простой цикл C. Ребра C ограничивают на плоскости многоугольник. Изменим цвету всех красных и зеленых точек, лежащих внутри цикла C. Далее, перейдем к рассмотрению графа Γ
, получаемого из Γ удалением всех ребер цикла C. В графе Γ
степенькаждой вершины четна, поэтому снова найдем простой цикл, произведем перекрашивание, удалим ребра цикла, и т. д. Действуем так до тех пор, пока в соответствующем графе естьребра.
Докажем, что полученная в конце этого процесса раскраска удовлетворяет условию.
Если у черной точки P четыре белых соседа, то при каждом перекрашивании они находилисьлибо все внутри многоугольника, либо все вне, а значит перекрашивалисьодинаковое число раз. Тогда у P по два красных и зеленых соседа, поскольку так было в начальной раскраске.
Пустьу черной точки P два белых соседа K и L, и два черных соседа
M
и Пусть K и L лежат водной горизонтали или водной вертикали. Тогда
K
и L находилисьв разных частях плоскости относительно цикла только при перекрашивании точек внутри цикла, содержащего путь MP N. Таким образом, количество перекрашиваний точек K и L отличается на Так как в начальной раскраске K и L одноцветны, тов конечной — раз- ноцветны.
УЧЕБНЫЙ ГОД, 11
КЛАСС
431
Если же K и L — соседи по диагонали, то при каждом перекрашивании они находилисьлибо обе внутри многоугольника, либо обе — вне, и значит одна из них зеленая, другая — красная, как это было вначале класс. Ответ. Положим f(x) = |x − a
1
| + . . . + |x − a
50
| − |x − b
1
| − . . . − |x −
− b
50
| и перепишем исходное уравнение в виде f(x) = 0. Пусть c
1
<
< c
2
< . . . < c
100
— все числа из множества {a
1
, . . . , a
50
, b
1
, . . . , упорядоченные по возрастанию. На каждом из 101 промежутка [−∞, c
1
]
,
[c
1
, c
2
]
, . . . , [c
99
, c
100
]
, [c
100
, +
∞), функция f(x) линейна. Заметим, что на первом и последнем из этих промежутков f(x) = m = (a
1
+ . . . + a
50
)
−
− (b
1
+ . . . + и f(x) = −m соответственно, при этом m = 0, так как количество корней конечно.
Пойдем по числовой оси слева направо. Вначале угловой коэффициент функции f(x) равен 0. Всякий раз, когда мы проходим одну из точек, он за счет смены знака при раскрытии соответствующего модуля изменяется на ±2. Таким образом, он всегда равен четному целому числу и не может поменятьзнак, не обратившисьперед этим в 0. Значит,
угловые коэффициенты на любых двух соседних промежутках либо оба неотрицательны, либо оба неположительны, те. функция f(x) на объединении этих промежутков либо неубывающая, либо невозрастающая.
Стало быть, если число ее корней конечно, тона каждом из 50 отрезков, c
3
], . . . , [c
97
, c
99
], [c
99
, она имеет не более одного корня. Кроме того, на крайних интервалах значения имеют разные знаки, ив каждом корне знак функции меняется. Следовательно, количество корней нечетно и не превышает Нетрудно проверить, что если роль будут игратьчисла 1, 4, 5, 8,
. . . , 97, 100, а роль b
i
— числа 2, 3, 6, 7, . . . , 94, 95, 98, 99 1
10
, то уравнение (x) = будет иметьровно 49 корней. См. решение задачи 723.
КЛАСС
431
Если же K и L — соседи по диагонали, то при каждом перекрашивании они находилисьлибо обе внутри многоугольника, либо обе — вне, и значит одна из них зеленая, другая — красная, как это было вначале класс. Ответ. Положим f(x) = |x − a
1
| + . . . + |x − a
50
| − |x − b
1
| − . . . − |x −
− b
50
| и перепишем исходное уравнение в виде f(x) = 0. Пусть c
1
<
< c
2
< . . . < c
100
— все числа из множества {a
1
, . . . , a
50
, b
1
, . . . , упорядоченные по возрастанию. На каждом из 101 промежутка [−∞, c
1
]
,
[c
1
, c
2
]
, . . . , [c
99
, c
100
]
, [c
100
, +
∞), функция f(x) линейна. Заметим, что на первом и последнем из этих промежутков f(x) = m = (a
1
+ . . . + a
50
)
−
− (b
1
+ . . . + и f(x) = −m соответственно, при этом m = 0, так как количество корней конечно.
Пойдем по числовой оси слева направо. Вначале угловой коэффициент функции f(x) равен 0. Всякий раз, когда мы проходим одну из точек, он за счет смены знака при раскрытии соответствующего модуля изменяется на ±2. Таким образом, он всегда равен четному целому числу и не может поменятьзнак, не обратившисьперед этим в 0. Значит,
угловые коэффициенты на любых двух соседних промежутках либо оба неотрицательны, либо оба неположительны, те. функция f(x) на объединении этих промежутков либо неубывающая, либо невозрастающая.
Стало быть, если число ее корней конечно, тона каждом из 50 отрезков, c
3
], . . . , [c
97
, c
99
], [c
99
, она имеет не более одного корня. Кроме того, на крайних интервалах значения имеют разные знаки, ив каждом корне знак функции меняется. Следовательно, количество корней нечетно и не превышает Нетрудно проверить, что если роль будут игратьчисла 1, 4, 5, 8,
. . . , 97, 100, а роль b
i
— числа 2, 3, 6, 7, . . . , 94, 95, 98, 99 1
10
, то уравнение (x) = будет иметьровно 49 корней. См. решение задачи 723.
