ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.04.2024
Просмотров: 50
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
599. ПустьокружностьS
1
вторично пересекает CD в точке F . Будем счи- татьдля определенности, что E лежит между D и F возможно, F = E). Из равенства DA
2
= DF
· DE следует DF
· DE, а, значит, и окружность проходит через точку F (см.
рис. 276). Теперь, поскольку CA·CM =
= CE
·CF = CB·CN, получаем, откуда CMN ∼ CBA,
∠CMN = ∠CBA, ∠CNM = Проведем касательную кв точке и отметим на ней две точки P итак, чтобы P оказалосьпо одну сторону сот прямой AC, а Q — по другую. Очевидно, ∠P MA = Но тогда ∠QMC = ∠P MA = ∠CAB = ∠CNM, а это означает, что окружность, проходящая через C и M и касающаяся S
1
, проходит и через
613. Доказываемое неравенство можно переписатьв виде sin
2n
x + (2
n
− 2) sin
n
x cos
n
x + cos
2n
x
Возведем тождество sin
2
x + cos
2
x = в степень n, получим = sin
2n
x + cos
2n
x + n(sin
2
x cos
2n−2
x + cos
2
x sin
2n−2
x)+
+C
2
n
(sin
4
x cos
2n−4
x + cos
4
x sin
2n−4
x) + . . .
sin
2n
x + cos
2n
x + (2
n
− 2) sin
n
x поскольку каждая скобка не меньше чем 2 sin
n
x cos
n
x
, а сумма коэффициентов равна 2 2
614. Предположим, что совершенное число равно 7n, где n не кратно. Тогда все натуральные делители числа 7n включая его самого) можно разбитьна пары d и 7d, где d не делится на 7. Следовательно, сумма всех делителей числа 7n она равна 14n) делится на 8. Отсюда n кратно 4. Далее заметим, что числа, и 1 будут различными делителями числа 7n, их сумма равна 7n + 1 > 7n, откуда следует, что число 7n не может бытьсовершенным. Противоречие.
α
α
α
α
A
B
C
D
l
1
l
2
M
P
K
L
N
Q
O
Рис. 279
615. Пустьдля определенности O лежит на продолжении отрезка AB заточку см. рис. Обозначим P , Q точки пересечения KL с окружностью точки касания сторон BC и AD
c ω. Проведем касательные l
1
, кв точках P , Обозначим через α угол между касательной или) и хордой P При гомотетии с центром O, переводящей окружность в ω, касательная BC в точке K перейдет в l
2
; при гомотетии, переводящей окружность в ω, прямая AD перейдет в l
1
. Отсюда l
2
, AD и, следовательно, ∠LKC =
=
∠KLD = α. ∠BMN = ∠ANM как углы между касательной и хордой. Отсюда получаем, что четырехугольник равнобокая трапеция и = ∠MND = α. Итак, хорды P Q и окружности ω параллельны и стягивают равные дуги величиной 2α. Отсюда следует, что средняя линия нашей трапеции проходит через центр ω. Носе- редина KM совпадает с серединой BC точки касания стороны треуголь-
630. Достаточно доказать, что сумма S горизонтальных проекций векторов, соединяющих центры клеток с большим числом с центрами клеток с меньшим числом, равна нулю. Аналогичными рассуждениями доказы-
2001–2002 г класс. Ответ. Нельзя.
Числа от 1 до 2001 могут располагаться не более, чем в 2001 строке и столбце. Значит, найдутся строка и столбец, все числа в которых не меньше 2002. Но тогда произведение любых двух чисел из такой строки
(столбца) больше 2002 2
, те. для клетки, расположенной на пересечении таких строки и столбца, условие задачи не выполняется.
A
B
C
O
O
1
O
2
M
Рис. 289
642. ∠AO
1
O
2
— внешний для треугольника Поэтому 2
∠AOB +
1 2
∠OAB = 90
◦
−
−
1 2
∠OBA =
1 Далее, пусть M — некоторая точка на продолжении отрезка OA заточку внешний для треугольника Отсюда ∠AO
2
O
1
=
∠MAO
2
−
− ∠AOO
2
=
1 2
∠MAC −
1 2
∠AOC =
=
1 2
∠ACO.
Второе решение. Как ив первом решении, можно считать, что в нашем множестве найдутся точки A, B, C, не лежащие на одной прямой.
Докажем, что tg ∠BAC — либо рациональное число, либо не существует.
Рассмотрим координаты этих точек в системе, соответствующей тройке, B, C. Если x
A
= случай x
A
= аналогичен, то tg ∠BAC =
=
±
x
C
− x
A
y
C
− рационален (или не существует. Если же x
B
= и x
C
=
= x
A
, то числа p =
y
B
− y
A
x
B
− и q =
y
C
− y
A
x
C
− рациональны. Но p = tg α,
q = tg β
, где α и β — углы, образуемые лучами AB и AC с положительным направлением оси Ox, поэтому из формулы tg ∠CAB = tg(β − α) =
=
p − q
1 + следует рациональность tg ∠BAC или тангенс не существует,
если pq = −1). Аналогично, рациональными являются тангенсы углов всех треугольников с вершинами в данных точках. Рассмотрим систему координат с центром A и единичным вектором по оси Ax, равным
−−→
AB
Для любой точки D нашего множества tg ∠DAB и tg ∠DBA рациональны, поэтому уравнения прямых AD и BD имеют рациональные коэффициенты. Тогда и точка D имеет рациональные координаты. Изменив масштаб, мы получим целочисленные координаты у всех точек. Первое решение. Достаточно доказатьэто неравенство при 0 <
< x при x оно очевидно, при x получается заменой =
π
2
− x). При k 2 имеем cos
k
x
− sin
k
x = (cos
k
x
− sin
k
x)(sin
2
x + cos
2
x) =
= (cos
k+2
x
− sin
k+2
x) + sin
2
x cos
2
x(cos
k−2
x
− sin
k−2
x)
cos
k+2
x
− Поэтому неравенство сводится к случаю n = m + 1, за исключением n =
= 3
. Кроме того sin
n
x
cos
n−1
x
− sin
n−1
x
cos
k
x
− sin
k
x
cos
k−1
x
− при n k > 1. Действительно, приведя к общему знаменателю, получаем неравенство sin
k−1
x cos
k−1
x(cos
n−k
x
− sin
n−k
x)(cos x
− sin x) которое очевидно. Поэтому неравенство сводится к случаями. Докажем их sin
3
x = (cos x
− sin x)(1 + sin x cos x)
3 2
(cos x
− sin поскольку cos x sin x =
1 2
sin 2x
1 2
;
cos
2
x
− sin
2
x = (cos x
− sin x)(cos x + sin x)
3 2
(cos x
− sin ибо sin x + cos x =
√
2 sin
x +
π
4
3 2
1
вторично пересекает CD в точке F . Будем счи- татьдля определенности, что E лежит между D и F возможно, F = E). Из равенства DA
2
= DF
· DE следует DF
· DE, а, значит, и окружность проходит через точку F (см.
рис. 276). Теперь, поскольку CA·CM =
= CE
·CF = CB·CN, получаем, откуда CMN ∼ CBA,
∠CMN = ∠CBA, ∠CNM = Проведем касательную кв точке и отметим на ней две точки P итак, чтобы P оказалосьпо одну сторону сот прямой AC, а Q — по другую. Очевидно, ∠P MA = Но тогда ∠QMC = ∠P MA = ∠CAB = ∠CNM, а это означает, что окружность, проходящая через C и M и касающаяся S
1
, проходит и через
УЧЕБНЫЙ ГОД, КЛАСС. Аналогично показывается, что окружность, проходящая через C и и касающаяся S
2
, проходит и через M.
600. Положим для удобства изложения при n =
= 1, 2, . . . , 100
. Заметим, что при описанной процедуре числа остаются взаимно простыми в совокупности.
Лемма. Пусть a
1
, a
2
, . . . , и d — натуральные числа. Тогда
существует натуральное число k такое, что НОД(a
1
+ kd, a
i
)
для любого i =2, 3, . . . , Доказательство. Существует некоторое число,
кратное
a
2
a
3
. . . a
n
, — скажем, la
2
a
3
. . . a
n
, которое больше a
1
. Тогда среди тех k, для которых a
1
+ kd > la
2
a
3
. . . a
n
, существует наименьшее число. Положим a
1
= a
1
+ k
0
d
. Тогда 0 < a
1
−la
2
a
3
. . . a
n
d, и наибольший общий делитель и каждого из не превосходит d. Лемма доказана.
ПустьтеперьM > 1 — наибольший из попарных общих делителей чисел a
i
. Докажем, что с помощью операций, описанных в условии, мы сможем заменитьисходный набор чисел на набор, в котором все попарные общие делители меньше M. Действительно, так как числа a
1
, a
2
,
. . . , взаимно простыв совокупности, найдутся два соседних числа
a
i
и a
i+1
, первое из которых делится на M, а второе — нет. Тогда d =
=
НОД(a
i−1
, a
i+1
) < M
. Применяя лемму, прибавим к такое кратное, чтобы наибольшие общие делители с каждым из остальных чисел стали не больше d. В полученном наборе по-прежнему все попарные наибольшие делители не превосходят M, а чисел, кратных M, меньше, чем в исходном. Повторяя при необходимости эту операцию, мы добьемся, что останется ровно одно число, кратное M, и тогда, очевидно, все попарные наибольшие общие делители станут меньше Итак, если наибольший из попарных общих делителей чисел набора больше 1, его можно уменьшить. Поэтому его можно уменьшить до 1, что и требовалось класс. Ответ 1001
−2 3
− Уберем первое слагаемое — оно равно 0 — и вместо суммы остальных слагаемых рассмотрим сумму 3
+
2 2
3
+
2 3
3
+ . . . +
2 1000 Это — сумма геометрической прогрессии, иона равна 1001
−2 3
. Теперьза- меним все ее слагаемые целыми частями. Заметим, что ни одно из этих слагаемых не является целым, а сумма любых двух последовательных слагаемых — целое число (потому что 3
=
3·2
k
3
= 2
k
). Ясно, что
2
, проходит и через M.
600. Положим для удобства изложения при n =
= 1, 2, . . . , 100
. Заметим, что при описанной процедуре числа остаются взаимно простыми в совокупности.
Лемма. Пусть a
1
, a
2
, . . . , и d — натуральные числа. Тогда
существует натуральное число k такое, что НОД(a
1
+ kd, a
i
)
для любого i =2, 3, . . . , Доказательство. Существует некоторое число,
кратное
a
2
a
3
. . . a
n
, — скажем, la
2
a
3
. . . a
n
, которое больше a
1
. Тогда среди тех k, для которых a
1
+ kd > la
2
a
3
. . . a
n
, существует наименьшее число. Положим a
1
= a
1
+ k
0
d
. Тогда 0 < a
1
−la
2
a
3
. . . a
n
d, и наибольший общий делитель и каждого из не превосходит d. Лемма доказана.
ПустьтеперьM > 1 — наибольший из попарных общих делителей чисел a
i
. Докажем, что с помощью операций, описанных в условии, мы сможем заменитьисходный набор чисел на набор, в котором все попарные общие делители меньше M. Действительно, так как числа a
1
, a
2
,
. . . , взаимно простыв совокупности, найдутся два соседних числа
a
i
и a
i+1
, первое из которых делится на M, а второе — нет. Тогда d =
=
НОД(a
i−1
, a
i+1
) < M
. Применяя лемму, прибавим к такое кратное, чтобы наибольшие общие делители с каждым из остальных чисел стали не больше d. В полученном наборе по-прежнему все попарные наибольшие делители не превосходят M, а чисел, кратных M, меньше, чем в исходном. Повторяя при необходимости эту операцию, мы добьемся, что останется ровно одно число, кратное M, и тогда, очевидно, все попарные наибольшие общие делители станут меньше Итак, если наибольший из попарных общих делителей чисел набора больше 1, его можно уменьшить. Поэтому его можно уменьшить до 1, что и требовалось класс. Ответ 1001
−2 3
− Уберем первое слагаемое — оно равно 0 — и вместо суммы остальных слагаемых рассмотрим сумму 3
+
2 2
3
+
2 3
3
+ . . . +
2 1000 Это — сумма геометрической прогрессии, иона равна 1001
−2 3
. Теперьза- меним все ее слагаемые целыми частями. Заметим, что ни одно из этих слагаемых не является целым, а сумма любых двух последовательных слагаемых — целое число (потому что 3
=
3·2
k
3
= 2
k
). Ясно, что
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
если сумма двух нецелых чисел — целое число, то сумма их целых частей меньше суммы самих чисел на 1 ([α + β] = [[α] + {α} + [β] + {β}] = [α] +
+ [β] + [
{α} + {β}] = [α] + [β] + [1] = [α] + [β] + Поэтому при замене каждых двух последовательных членов нашей геометрической прогрессии целыми частями сумма уменьшается на 1, атак как в сумме всего 1000 слагаемых, то при замене целыми частями их всех она уменьшится на 500.
602. Пусть t
i
= x
13
i
− При −1 < x
i
0 имеем t
i
0; если же 0 <
< x
i
< то t
i
< Неравенство, которое нужно доказать, перепишем в виде Без ограничения общности можно считать, что y
1
> поскольку+ c)t
i
=
y
i
t
i
+ c
t
i
=
y
i
t
i
).
Пустьчисло k таково, что x
k
0, x
k+1
> 0
. Тогда t
1
, . . . , t
k
0,
t
k+1
, . . . , t
n
< 0
. Оценим сумму
t
i
y
i
следующим образом y
k
k
i=1
t
i
+ y
k+1
n
j=k+1
t
j
< y
k+1
n
i=1
t
i
= Неравенство доказано. Пусть H — ортоцентр ABC, а M — середина стороны AC. Выберем на отрезках AH и CH точки S и T такие, что P S ⊥ AB и T Q ⊥
⊥ BC см. рис. 277). Обозначим через K точку пересечения перпендикуляров и QT . Поскольку ∠BP K = ∠BQK = 90
◦
, то четырехугольник вписанный. Покажем, что точки K и R совпадают.
A
B
C
H
M
R
S
T
A
1
Q
C
1
P
Рис. Треугольник P BQ равнобедренный, ибо ∠HP B =
=
∠HQB. Поэтому точка K лежит на биссектрисе угла B. Докажем,
что она также лежит и на прямой. Действительно, пары (P, Q) и, T )
— пары соответственных точек в подобных треугольниках и CA
1
H
, поэтому
HS
HT
=
HA
HC
,
откуда ST AC. Поэтому середина отрезка ST лежит на прямой. Поскольку HSKT — параллелограмм, то точка K лежит на прямой HM. Отсюда точка K является
если сумма двух нецелых чисел — целое число, то сумма их целых частей меньше суммы самих чисел на 1 ([α + β] = [[α] + {α} + [β] + {β}] = [α] +
+ [β] + [
{α} + {β}] = [α] + [β] + [1] = [α] + [β] + Поэтому при замене каждых двух последовательных членов нашей геометрической прогрессии целыми частями сумма уменьшается на 1, атак как в сумме всего 1000 слагаемых, то при замене целыми частями их всех она уменьшится на 500.
602. Пусть t
i
= x
13
i
− При −1 < x
i
0 имеем t
i
0; если же 0 <
< x
i
< то t
i
< Неравенство, которое нужно доказать, перепишем в виде Без ограничения общности можно считать, что y
1
> поскольку+ c)t
i
=
y
i
t
i
+ c
t
i
=
y
i
t
i
).
Пустьчисло k таково, что x
k
0, x
k+1
> 0
. Тогда t
1
, . . . , t
k
0,
t
k+1
, . . . , t
n
< 0
. Оценим сумму
t
i
y
i
следующим образом y
k
k
i=1
t
i
+ y
k+1
n
j=k+1
t
j
< y
k+1
n
i=1
t
i
= Неравенство доказано. Пусть H — ортоцентр ABC, а M — середина стороны AC. Выберем на отрезках AH и CH точки S и T такие, что P S ⊥ AB и T Q ⊥
⊥ BC см. рис. 277). Обозначим через K точку пересечения перпендикуляров и QT . Поскольку ∠BP K = ∠BQK = 90
◦
, то четырехугольник вписанный. Покажем, что точки K и R совпадают.
A
B
C
H
M
R
S
T
A
1
Q
C
1
P
Рис. Треугольник P BQ равнобедренный, ибо ∠HP B =
=
∠HQB. Поэтому точка K лежит на биссектрисе угла B. Докажем,
что она также лежит и на прямой. Действительно, пары (P, Q) и, T )
— пары соответственных точек в подобных треугольниках и CA
1
H
, поэтому
HS
HT
=
HA
HC
,
откуда ST AC. Поэтому середина отрезка ST лежит на прямой. Поскольку HSKT — параллелограмм, то точка K лежит на прямой HM. Отсюда точка K является
УЧЕБНЫЙ ГОД, 10
КЛАСС
365
точкой пересечения прямой HM с биссектрисой угла B. Таким образом точки K и R совпадают. Ответ. Нельзя.
Пустьу нас естьгири A, B, C, D, E. Всего имеется 5! = 120 различных способов упорядочивания весов этих гирь. А при условии m(A) <
< m(B) < существует различных способов упорядочи- вания весов. Поэтому если на какой-то вопрос получен отрицательный ответ, то этот вопрос может исключитьне более 20 вариантов. Следовательно, первые пять вопросов могут исключить не более 20 · 5 = 100 вариантов. Каждый из следующих четырех вопросов может исключить(при одном из двух возможных вариантов ответа) не более половины из оставшихся вариантов. То естьпосле го вопроса может остаться не менее вариантов, после гоне менее 5 вариантов, после гоне менее и, наконец, после го вопроса может остаться по крайней мере 2 варианта. Таким образом, мы показали, что при любой последовательности из девяти задаваемых вопросов найдется последовательность ответов, которой удовлетворяют по крайней мере два варианта упорядочивания весов гирь. Ответ. Пример множества из 7 элементов {−3, −2, −1, 0, 1, 2, Докажем, что при m 8 множество из m чисел A = {a
1
, a
2
, . . . , требуемым свойством не обладает. Не ограничивая общности можно считать, что a
1
> a
2
> a
3
> . . . > и a
4
> ясно, что умножение на наше свойство не меняет. Тогда a
1
+ a
2
> a
1
+ a
3
> a
1
+ a
4
> a
1
, тени одна из сумм a
1
+ a
2
, a
1
+ и a
1
+ множеству A не принадлежит.
Кроме того, суммы a
2
+ и a
2
+ не могут одновременно принадлежать, поскольку a
2
+ a
3
> a
2
, a
2
+ a
4
> и a
2
+ a
3
= a
2
+ a
4
. Получается, что по крайней мере для одной из троек (a
1
, a
2
, и (a
1
, a
2
, сумма любых двух ее элементов множеству A не принадлежит. Предположим, что совершенное число равно 3n, где n не кратно. Тогда все натуральные делители числа 3n включая его самого) можно разбитьна пары d и 3d, где d не делится на 3. Следовательно, сумма всех делителей числа 3n она равна 6n) делится на 4. Отсюда n кратно 2. Далее заметим, что числа, и 1 будут различными делителями числа их сумма равна 3n + 1 > 3n, откуда следует, что число 3n не может быть совершенным. Противоречие. Рассмотрим случай, когда точки Q и лежат по разные стороны от прямой BK, а точки P и лежат по разные стороны от прямой см. рис. 278; остальные случаи рассматриваются аналогично. Прямые
QK
и P M пересекаются в точке N, так как точки Q и P являются об
КЛАСС
365
точкой пересечения прямой HM с биссектрисой угла B. Таким образом точки K и R совпадают. Ответ. Нельзя.
Пустьу нас естьгири A, B, C, D, E. Всего имеется 5! = 120 различных способов упорядочивания весов этих гирь. А при условии m(A) <
< m(B) < существует различных способов упорядочи- вания весов. Поэтому если на какой-то вопрос получен отрицательный ответ, то этот вопрос может исключитьне более 20 вариантов. Следовательно, первые пять вопросов могут исключить не более 20 · 5 = 100 вариантов. Каждый из следующих четырех вопросов может исключить(при одном из двух возможных вариантов ответа) не более половины из оставшихся вариантов. То естьпосле го вопроса может остаться не менее вариантов, после гоне менее 5 вариантов, после гоне менее и, наконец, после го вопроса может остаться по крайней мере 2 варианта. Таким образом, мы показали, что при любой последовательности из девяти задаваемых вопросов найдется последовательность ответов, которой удовлетворяют по крайней мере два варианта упорядочивания весов гирь. Ответ. Пример множества из 7 элементов {−3, −2, −1, 0, 1, 2, Докажем, что при m 8 множество из m чисел A = {a
1
, a
2
, . . . , требуемым свойством не обладает. Не ограничивая общности можно считать, что a
1
> a
2
> a
3
> . . . > и a
4
> ясно, что умножение на наше свойство не меняет. Тогда a
1
+ a
2
> a
1
+ a
3
> a
1
+ a
4
> a
1
, тени одна из сумм a
1
+ a
2
, a
1
+ и a
1
+ множеству A не принадлежит.
Кроме того, суммы a
2
+ и a
2
+ не могут одновременно принадлежать, поскольку a
2
+ a
3
> a
2
, a
2
+ a
4
> и a
2
+ a
3
= a
2
+ a
4
. Получается, что по крайней мере для одной из троек (a
1
, a
2
, и (a
1
, a
2
, сумма любых двух ее элементов множеству A не принадлежит. Предположим, что совершенное число равно 3n, где n не кратно. Тогда все натуральные делители числа 3n включая его самого) можно разбитьна пары d и 3d, где d не делится на 3. Следовательно, сумма всех делителей числа 3n она равна 6n) делится на 4. Отсюда n кратно 2. Далее заметим, что числа, и 1 будут различными делителями числа их сумма равна 3n + 1 > 3n, откуда следует, что число 3n не может быть совершенным. Противоречие. Рассмотрим случай, когда точки Q и лежат по разные стороны от прямой BK, а точки P и лежат по разные стороны от прямой см. рис. 278; остальные случаи рассматриваются аналогично. Прямые
QK
и P M пересекаются в точке N, так как точки Q и P являются об
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
разами точек K и M при гомотетии с центром N касательная в точке переходит в параллельную ей касательную сточкой касания в середине дуги AB; второе утверждение аналогично. Значит, ∠KQB + ∠MP B =
= π
. Кроме того, ∠KB
1
B +
∠KQB = π и ∠MB
1
B +
∠MP B = Следовательно, ∠KB
1
B +
∠MB
1
B = π
, те. точка лежит на прямой. Далее, ∠BQB
1
=
∠BKB
1
=
∠KNM = ∠B
1
M B =
∠B
1
P B
. А
поскольку ∠QBP + ∠QNP = π, то получаем, что в четырехугольнике два противоположных угла равны, а сумма двух смежных равна, следовательно, BP B
1
Q
— параллелограмм.
A
B
C
N
Q
P
K
M
B
1
Рис. 278
608. Докажем утверждение задачи индукцией по количеству цветов База для n = 2. Рассмотрим самый левый квадрат K. Если он первого цвета, то все квадраты второго цвета имеют с ним общую точку, следовательно, каждый квадрат второго цвета содержит одну из двух правых вершин квадрата K, следовательно, все квадраты второй системы можно прибитьдвумя гвоздями.
Индуктивный переход. Пусть мы доказали утверждение задачи для n цветов, докажем для (n + го цвета. Рассмотрим все квадраты и выберем из них самый левый квадрат K. Пустьон покрашен в (n + 1)- ый цвет. Все квадраты, пересекающие K, содержат одну из двух его правых вершин, следовательно, их можно прибитьдвумя гвоздями. Уберем со стола все квадраты (n + го цвета и квадраты других цветов, пересекающие. Осталиськвадраты n различных цветов. Если теперьвыбрать
n
квадратов разных цветов, то среди них найдутся два пересекающихся
(иначе добавим квадрат K и получим n + 1 попарно не пересекающихся квадратов разных цветов, что противоречит условию задачи. Таким образом, по индуктивному предположению, можно выбратьодин из цветов и прибить 2n − 2 гвоздями все оставшиеся на столе квадраты этого цвета.
Убранные квадраты цвета i пересекают самый левый квадрат K, следовательно, эти квадраты можно прибить, забив два гвоздя в правые вершины квадрата K.
разами точек K и M при гомотетии с центром N касательная в точке переходит в параллельную ей касательную сточкой касания в середине дуги AB; второе утверждение аналогично. Значит, ∠KQB + ∠MP B =
= π
. Кроме того, ∠KB
1
B +
∠KQB = π и ∠MB
1
B +
∠MP B = Следовательно, ∠KB
1
B +
∠MB
1
B = π
, те. точка лежит на прямой. Далее, ∠BQB
1
=
∠BKB
1
=
∠KNM = ∠B
1
M B =
∠B
1
P B
. А
поскольку ∠QBP + ∠QNP = π, то получаем, что в четырехугольнике два противоположных угла равны, а сумма двух смежных равна, следовательно, BP B
1
Q
— параллелограмм.
A
B
C
N
Q
P
K
M
B
1
Рис. 278
608. Докажем утверждение задачи индукцией по количеству цветов База для n = 2. Рассмотрим самый левый квадрат K. Если он первого цвета, то все квадраты второго цвета имеют с ним общую точку, следовательно, каждый квадрат второго цвета содержит одну из двух правых вершин квадрата K, следовательно, все квадраты второй системы можно прибитьдвумя гвоздями.
Индуктивный переход. Пусть мы доказали утверждение задачи для n цветов, докажем для (n + го цвета. Рассмотрим все квадраты и выберем из них самый левый квадрат K. Пустьон покрашен в (n + 1)- ый цвет. Все квадраты, пересекающие K, содержат одну из двух его правых вершин, следовательно, их можно прибитьдвумя гвоздями. Уберем со стола все квадраты (n + го цвета и квадраты других цветов, пересекающие. Осталиськвадраты n различных цветов. Если теперьвыбрать
n
квадратов разных цветов, то среди них найдутся два пересекающихся
(иначе добавим квадрат K и получим n + 1 попарно не пересекающихся квадратов разных цветов, что противоречит условию задачи. Таким образом, по индуктивному предположению, можно выбратьодин из цветов и прибить 2n − 2 гвоздями все оставшиеся на столе квадраты этого цвета.
Убранные квадраты цвета i пересекают самый левый квадрат K, следовательно, эти квадраты можно прибить, забив два гвоздя в правые вершины квадрата K.
УЧЕБНЫЙ ГОД, КЛАСС класс. Положив x = y = −z, получаем f(2x) + f(0) + f(0) откуда f(2x) С другой стороны, положив x = z = −y, получаем f(0) + f(0) +
+ f (2x)
3f(2x), откуда f(2x) f(0). Итак, f(0) f(2x) те. Легко проверить, что при любом C ∈ R функция (x)
≡ C удовлетворяет неравенству. Предъявим такое разбиение.
Выделим в е множество i 99) все четные числа, дающие при делении на 99 остаток 1, а в сотое множество — все нечетные числа. Очевидно, что среди любых чисел a, b и c, удовлетворяющих уравнению a + 99b = c, четное количество нечетных. Если среди них два нечетных, то они из одного
(сотого) множества, иначе — a и c из одного множества, так как они четные и дают одинаковые остатки отделения на 99.
611. Будем говорить
в
вместо
внутри или на границе
Предположим противное. Рассмотрим пятиугольник минимальной площади S, для которого не выполняется утверждение задачи (так как площадьлюбого пятиугольника с вершинами в целых точках — число полуцелое, то такой найдется. Покажем, что все целые точки в треугольнике, кроме A, лежат на C
1
D
1
. В самом деле, если в нем естьдру- гая целая точка K, то площадьвыпуклого пятиугольника KBCDE меньше, а
внутренний
пятиугольник в KBCDE лежит в пятиугольнике, что, очевидно, невозможно.
Через ρ(M, P Q) будем обозначатьрасстояние от точки M до прямой Выберем из треугольников ABC, BCD, CDE, DEA и
EAB
треугольник наименьшей площади. Пусть это ABC. Тогда, BC)
ρ(D, BC) и ρ(C, AB) ρ(E, AB). Рассмотрим точку O такую, что ABCO — параллелограмм (очевидно, эта точка целая. Тогда, BC) = ρ(A, и ρ(O, AB) = ρ(C, AB) ρ(B
1
, AB)
, поэтому точка лежит в треугольнике AB
1
C
. Тогда из доказанного в предыдущем абзаце следует, что она лежит в пятиугольнике A
1
B
1
C
1
D
1
E
1
, чего немо- жет быть. Противоречие. Первое решение. Для 1 i j n обозначим через [i, j] отрезок натурального ряда от i до j. Пусть, j) =
a
i
+ a
i+1
+
· · · + a
j
j
− i + Заметим, что из S(i, j) > α и S(j + 1, l) > α следует S(i, l) > Выделим в отрезке [1, n] несколько отрезков [p
i
, последующему принципу й отрезок начинается с минимального числа p такого, что превосходит α и не лежит в ранее построенных отрезках (если такого нет
+ f (2x)
3f(2x), откуда f(2x) f(0). Итак, f(0) f(2x) те. Легко проверить, что при любом C ∈ R функция (x)
≡ C удовлетворяет неравенству. Предъявим такое разбиение.
Выделим в е множество i 99) все четные числа, дающие при делении на 99 остаток 1, а в сотое множество — все нечетные числа. Очевидно, что среди любых чисел a, b и c, удовлетворяющих уравнению a + 99b = c, четное количество нечетных. Если среди них два нечетных, то они из одного
(сотого) множества, иначе — a и c из одного множества, так как они четные и дают одинаковые остатки отделения на 99.
611. Будем говорить
в
вместо
внутри или на границе
Предположим противное. Рассмотрим пятиугольник минимальной площади S, для которого не выполняется утверждение задачи (так как площадьлюбого пятиугольника с вершинами в целых точках — число полуцелое, то такой найдется. Покажем, что все целые точки в треугольнике, кроме A, лежат на C
1
D
1
. В самом деле, если в нем естьдру- гая целая точка K, то площадьвыпуклого пятиугольника KBCDE меньше, а
внутренний
пятиугольник в KBCDE лежит в пятиугольнике, что, очевидно, невозможно.
Через ρ(M, P Q) будем обозначатьрасстояние от точки M до прямой Выберем из треугольников ABC, BCD, CDE, DEA и
EAB
треугольник наименьшей площади. Пусть это ABC. Тогда, BC)
ρ(D, BC) и ρ(C, AB) ρ(E, AB). Рассмотрим точку O такую, что ABCO — параллелограмм (очевидно, эта точка целая. Тогда, BC) = ρ(A, и ρ(O, AB) = ρ(C, AB) ρ(B
1
, AB)
, поэтому точка лежит в треугольнике AB
1
C
. Тогда из доказанного в предыдущем абзаце следует, что она лежит в пятиугольнике A
1
B
1
C
1
D
1
E
1
, чего немо- жет быть. Противоречие. Первое решение. Для 1 i j n обозначим через [i, j] отрезок натурального ряда от i до j. Пусть, j) =
a
i
+ a
i+1
+
· · · + a
j
j
− i + Заметим, что из S(i, j) > α и S(j + 1, l) > α следует S(i, l) > Выделим в отрезке [1, n] несколько отрезков [p
i
, последующему принципу й отрезок начинается с минимального числа p такого, что превосходит α и не лежит в ранее построенных отрезках (если такого нет
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
то построение закончено заканчивается он таким максимальным q, что при любом j из [p
i
, среднее чисел от до превосходит α. По построению+ Назовем натуральное число k хорошим, если m
k
> α
. Докажем, что все хорошие числа лежат в построенных отрезках. Предположим противное и рассмотрим минимальное хорошее k, для которого это не так. Поскольку, то найдется l k, для которого S(l, k) > α. Так как любое число вне построенных отрезков не превосходит α, то отрезок [l, пересекается с каким-то отрезком [p
j
, q
j
]
. Пусть [p
i
, q
i
]
— самый правый отрезок, лежащий левее k. Если k > q
i
+ 1
, то S(q
i
+ 2, k)
α, откуда, q
i
+ 1) > α
, что противоречит выбору k. Поэтому k = q
i
+ 1
. Из принципа выбора отрезков следует, что l = иначе получаем противоречие с выбором q
i
). Если l > p
i
, то S(p
i
, l
− 1) > α, откуда S(p
i
, q
i
+ 1) > α
, чего не может быть. Если же l < p
i
, то из S(p
i
, q
i
+ 1)
α следует S(l, p
i
−
− 1) > α, те хорошее число, не принадлежащее ни одному из отрезков [p
j
, и меньшее, что противоречит сделанному предположению. Таким образом, все хорошие k лежат в построенных отрезках.
Получается, что количество хороших чисел не превосходит+ 1)
. Учитывая, что по построению отрезков [p
i
, q
i
]
a
k
k∈[p
i
,q
i
]
a
k
> α
·
(q
i
− p
i
+ мы получаем утверждение задачи.
Второе решение.
Пусть b
i
=
a
1
+
· · · + Ясно, что b
2
. . . b
n
. Тогда+ a
k−m+2
+
· · · + a
k
m
=
b
k
− b
l
k
− Рассмотрим на координатной плоскости точки B
0
(0, 0)
, B
1
(1, b
1
)
,
B
2
(2, b
2
)
,. . . , B
n
(n, b
n
)
. Тогда отношение b
l
k
− будет равно тангенсу угла наклона прямой B
l
B
k
. Значит, условие m
k
> будет равносильно тому, что прямая, проходящая через с углом наклона arctg α эту прямую назовем l
k
) будет проходитьвыше хотя бы одной из точек при l < k такую точку будем называть хорошей. Выражение+ a
2
+
· · · + будет равно b
n
/α
, и это будет расстояние между точкой (n, 0) и точкой пересечения с осью абсцисс.
Докажем индукцией по количеству точек n, что это расстояние больше числа хороших точек. База очевидна. Если точка нехорошая, то выбросим ее, при этом число хороших точек не изменится, а отрезок уменьшится (так как b
n−1
b
n
). Если же она хорошая, то пусть B
k
— ближай-
то построение закончено заканчивается он таким максимальным q, что при любом j из [p
i
, среднее чисел от до превосходит α. По построению+ Назовем натуральное число k хорошим, если m
k
> α
. Докажем, что все хорошие числа лежат в построенных отрезках. Предположим противное и рассмотрим минимальное хорошее k, для которого это не так. Поскольку, то найдется l k, для которого S(l, k) > α. Так как любое число вне построенных отрезков не превосходит α, то отрезок [l, пересекается с каким-то отрезком [p
j
, q
j
]
. Пусть [p
i
, q
i
]
— самый правый отрезок, лежащий левее k. Если k > q
i
+ 1
, то S(q
i
+ 2, k)
α, откуда, q
i
+ 1) > α
, что противоречит выбору k. Поэтому k = q
i
+ 1
. Из принципа выбора отрезков следует, что l = иначе получаем противоречие с выбором q
i
). Если l > p
i
, то S(p
i
, l
− 1) > α, откуда S(p
i
, q
i
+ 1) > α
, чего не может быть. Если же l < p
i
, то из S(p
i
, q
i
+ 1)
α следует S(l, p
i
−
− 1) > α, те хорошее число, не принадлежащее ни одному из отрезков [p
j
, и меньшее, что противоречит сделанному предположению. Таким образом, все хорошие k лежат в построенных отрезках.
Получается, что количество хороших чисел не превосходит+ 1)
. Учитывая, что по построению отрезков [p
i
, q
i
]
a
k
k∈[p
i
,q
i
]
a
k
> α
·
(q
i
− p
i
+ мы получаем утверждение задачи.
Второе решение.
Пусть b
i
=
a
1
+
· · · + Ясно, что b
2
. . . b
n
. Тогда+ a
k−m+2
+
· · · + a
k
m
=
b
k
− b
l
k
− Рассмотрим на координатной плоскости точки B
0
(0, 0)
, B
1
(1, b
1
)
,
B
2
(2, b
2
)
,. . . , B
n
(n, b
n
)
. Тогда отношение b
l
k
− будет равно тангенсу угла наклона прямой B
l
B
k
. Значит, условие m
k
> будет равносильно тому, что прямая, проходящая через с углом наклона arctg α эту прямую назовем l
k
) будет проходитьвыше хотя бы одной из точек при l < k такую точку будем называть хорошей. Выражение+ a
2
+
· · · + будет равно b
n
/α
, и это будет расстояние между точкой (n, 0) и точкой пересечения с осью абсцисс.
Докажем индукцией по количеству точек n, что это расстояние больше числа хороших точек. База очевидна. Если точка нехорошая, то выбросим ее, при этом число хороших точек не изменится, а отрезок уменьшится (так как b
n−1
b
n
). Если же она хорошая, то пусть B
k
— ближай-
УЧЕБНЫЙ ГОД, 11
КЛАСС
369
шая (по оси абсцисс) точка, лежащая под l
n
. Тогда выбросим все точки от
B
k+1
до они все хорошие, количество хороших точек уменьшится на k, а отрезок — больше, чем на n − k.
КЛАСС
369
шая (по оси абсцисс) точка, лежащая под l
n
. Тогда выбросим все точки от
B
k+1
до они все хорошие, количество хороших точек уменьшится на k, а отрезок — больше, чем на n − k.
613. Доказываемое неравенство можно переписатьв виде sin
2n
x + (2
n
− 2) sin
n
x cos
n
x + cos
2n
x
Возведем тождество sin
2
x + cos
2
x = в степень n, получим = sin
2n
x + cos
2n
x + n(sin
2
x cos
2n−2
x + cos
2
x sin
2n−2
x)+
+C
2
n
(sin
4
x cos
2n−4
x + cos
4
x sin
2n−4
x) + . . .
sin
2n
x + cos
2n
x + (2
n
− 2) sin
n
x поскольку каждая скобка не меньше чем 2 sin
n
x cos
n
x
, а сумма коэффициентов равна 2 2
614. Предположим, что совершенное число равно 7n, где n не кратно. Тогда все натуральные делители числа 7n включая его самого) можно разбитьна пары d и 7d, где d не делится на 7. Следовательно, сумма всех делителей числа 7n она равна 14n) делится на 8. Отсюда n кратно 4. Далее заметим, что числа, и 1 будут различными делителями числа 7n, их сумма равна 7n + 1 > 7n, откуда следует, что число 7n не может бытьсовершенным. Противоречие.
α
α
α
α
A
B
C
D
l
1
l
2
M
P
K
L
N
Q
O
Рис. 279
615. Пустьдля определенности O лежит на продолжении отрезка AB заточку см. рис. Обозначим P , Q точки пересечения KL с окружностью точки касания сторон BC и AD
c ω. Проведем касательные l
1
, кв точках P , Обозначим через α угол между касательной или) и хордой P При гомотетии с центром O, переводящей окружность в ω, касательная BC в точке K перейдет в l
2
; при гомотетии, переводящей окружность в ω, прямая AD перейдет в l
1
. Отсюда l
2
, AD и, следовательно, ∠LKC =
=
∠KLD = α. ∠BMN = ∠ANM как углы между касательной и хордой. Отсюда получаем, что четырехугольник равнобокая трапеция и = ∠MND = α. Итак, хорды P Q и окружности ω параллельны и стягивают равные дуги величиной 2α. Отсюда следует, что средняя линия нашей трапеции проходит через центр ω. Носе- редина KM совпадает с серединой BC точки касания стороны треуголь-
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
ника со вписанной и вневписанной окружностью, как известно, симметричны относительно середины стороны, и также середина LN совпадает с серединой AD.
616. Предположим противное пустьсреди четырех клеток на пересечении любых двух строки любых двух столбцов естьдве клетки одинакового цвета. Для удобства будем нумероватьцвета числами от 1 до 4. Назовем горизонтальной вертикальной) парой две клетки разного цвета, лежащие водной строке (одном столбце. Назовем горизонтальным
(вертикальным) совпадением две клетки одинакового цвета, лежащие водной строке (одном столбце. Разделим пары на 6 типов по цветам входящих в них клеток {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, Рассмотрим две произвольные строчки. Докажем, что существует не менее 25 вертикальных совпадений, лежащих в этих строчках. Из сделанного предположения следует, что любые две вертикальных пары с клетками в этих строчках должны иметьобщий цвет. Легко заметить, что тогда в двух рассматриваемых строчках могут бытьвертикальные пары не более,
чем трех типов, причем возможны только два принципиально различных случая все пары содержат один и тот же цвет (скажем, 1) или естьпары типов {1, 2}, {1, 3} и {2, 3} или точно также с другой тройкой цветов).
Рассмотрим эти два случая.
Если все пары в наших двух строчках содержат клетку цвета 1, то всего парне более, чем клеток цвета 1 в обеих строчках, те, не более Значит, в рассматриваемых двух строчках не менее 50 совпадений.
Пустьестьпары типов {1, 2}, {1, 3} и {2, 3}. В этом случае все клетки цвета 4 в наших строчках совпадают, и таким образом естьне менее 25
совпадений.
Итак, мы доказали, что в любой паре строчек не менее 25 вертикальных совпадений, аналогичный результат верен и для любой пары столбцов. Таким образом, всего в нашем квадрате естьне менее 2 ·
99·100 2
· 25 =
= 25
· 99 · 100 совпадений. Но так как в любой строке ив любом столбце по 25 клеток каждого цвета, количество совпадений равно 200 ·
25·24 2
· 4 =
= 24
· 100 2
. Учитывая, что 25 · 99 > 24 · 100, мы приходим к противоречию.
Следовательно, есть две строки и два столбца, все клетки на пересечении которых окрашены в разные цвета г класс. Ответ. Эти суммы одинаковы
ника со вписанной и вневписанной окружностью, как известно, симметричны относительно середины стороны, и также середина LN совпадает с серединой AD.
616. Предположим противное пустьсреди четырех клеток на пересечении любых двух строки любых двух столбцов естьдве клетки одинакового цвета. Для удобства будем нумероватьцвета числами от 1 до 4. Назовем горизонтальной вертикальной) парой две клетки разного цвета, лежащие водной строке (одном столбце. Назовем горизонтальным
(вертикальным) совпадением две клетки одинакового цвета, лежащие водной строке (одном столбце. Разделим пары на 6 типов по цветам входящих в них клеток {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, Рассмотрим две произвольные строчки. Докажем, что существует не менее 25 вертикальных совпадений, лежащих в этих строчках. Из сделанного предположения следует, что любые две вертикальных пары с клетками в этих строчках должны иметьобщий цвет. Легко заметить, что тогда в двух рассматриваемых строчках могут бытьвертикальные пары не более,
чем трех типов, причем возможны только два принципиально различных случая все пары содержат один и тот же цвет (скажем, 1) или естьпары типов {1, 2}, {1, 3} и {2, 3} или точно также с другой тройкой цветов).
Рассмотрим эти два случая.
Если все пары в наших двух строчках содержат клетку цвета 1, то всего парне более, чем клеток цвета 1 в обеих строчках, те, не более Значит, в рассматриваемых двух строчках не менее 50 совпадений.
Пустьестьпары типов {1, 2}, {1, 3} и {2, 3}. В этом случае все клетки цвета 4 в наших строчках совпадают, и таким образом естьне менее 25
совпадений.
Итак, мы доказали, что в любой паре строчек не менее 25 вертикальных совпадений, аналогичный результат верен и для любой пары столбцов. Таким образом, всего в нашем квадрате естьне менее 2 ·
99·100 2
· 25 =
= 25
· 99 · 100 совпадений. Но так как в любой строке ив любом столбце по 25 клеток каждого цвета, количество совпадений равно 200 ·
25·24 2
· 4 =
= 24
· 100 2
. Учитывая, что 25 · 99 > 24 · 100, мы приходим к противоречию.
Следовательно, есть две строки и два столбца, все клетки на пересечении которых окрашены в разные цвета г класс. Ответ. Эти суммы одинаковы
УЧЕБНЫЙ ГОД, 9
КЛАСС
371
Разобьем числа от дона две группы A
n
=
{n
2
, n
2
+
+ 1, . . . , n
2
+ n
} и B
n
=
{n
2
+ n + 1, n
2
+ n + 2, . . . , n
2
+ 2n
}. Для чисел группы ближайшим квадратом является n
2
, для ближайшим является (n + 1)
2
— квадрат другой четности. Суммы чисел в группах и обозначим и соответственно. Но из равенства S(B
n
)
−
− S(A
n
) =
(n
2
+ n + 1)
− (n
2
+ 1)
+
(n
2
+ n + 2)
− (n
2
+ 2)
+. . .
. . . +
(n
2
+ 2n)
− (n
2
+ n)
− n
2
= n
· n − n
2
= следует, что суммы чисел в группах и равны. Осталосьзаметить, что все множество чисел от 1 до 999 999 разбивается на непересекающиеся пары и B
1
, и B
2
, . . . , и B
999
618. Из условия следует, что Q(x) = (x − x
1
)(x
− x
2
)
, где x
2
− x
1
> итак как P (x
1
) = Q(x
1
) = 0
,
P (x
2
) = Q(x
2
) = 0
. Предположим, что P (x)− Q(x) 0, те при всех x. Это выполняется только в том случае, когда x
2
+ Ax + (B
− 1) = (x − x
1
)(x
− x
2
)
, так как в точках = и x = не будет происходитьперемена знака многочлена P (x) −
− Q(x) только при четной кратности корней x = и x = x
2
. Значит =
−(x
1
+ x
2
)
, B − 1 = x
1
x
2
, Поэтому дискриминант трехчлена x
2
+
+ Ax + есть D = (x
1
+ x
2
)
2
− 4(x
1
x
2
+ 1) = (x
1
− x
2
)
2
− 4 > 0. Но тогда P (x) = (x− x
1
)(x
− x
2
)(x
− x
3
)(x
− корни и не совпадают си, так как и x
4
— корни трехчлена x
2
+ Ax + B
, аи нет кроме того, x
3
= x
4
, так как D = 0). Таким образом, P (x) не может иметьв качестве промежутка отрицательных значений ровно интервал I =
= (x
1
; x
2
)
. Противоречие. Значит, неравенство P (x) − Q(x) 0 при некоторых x нарушается. Пусть M — середина стороны CD, а L — середина стороны Достроим параллелограмм ABCD до треугольника так, чтобы отрезок AC был средней линией треугольника см. рис. 280). Для этого через точку D проведем прямую, параллельную AC и обозначим через и точки пересечения этой прямой с продолжениями сторон и BA соответственно. Тогда четырехугольники и будут параллелограммами. Точки A, M и будут лежатьна одной прямой, ибо в параллелограмме диагонали делятся точкой пересечения на равные части. Следовательно, в треугольнике угол K — прямой, поскольку точка M равноудалена от точек A, и K. Аналогично устанавливаем,
что ∠CKC
1
= 90
◦
. Таким образом 90
◦
− Отрезки CN и параллельны, ибо CN — средняя линия в треугольнике. Аналогично параллельны отрезки AN и KC
1
. Следовательно ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
A
B
C
D
A
1
C
1
M
L
K
N
Рис. 280
∠NCK = ∠CKA
1
=
∠C
1
KA =
∠NAK.
620. Уберем вершину данного многоугольника A
1
A
2
. . . Назовем средними диагоналями многоугольника A
1
A
2
. . . отрезки, соединяющие вершины, номера которых отличаются на 999 или Рассмотрим все средние диагонали, их ровно 1999 штук. Заметим, что любые две из них пересекаются, из каждой вершины выходит ровно две средние диагонали. Поскольку 1999 > 2 · 999, то найдутся три одноцветные средние диагонали, они попарно пересекаются в трех разных точках.
Эти точки пересечения и являются вершинами искомого треугольника. Ответили Рассмотрим любые четыре подряд идущие монеты. Докажем, что среди них ровно одна трехкопеечная. Предположим противное. Если среди этих монет не оказалосьни одной трехкопеечной, то однокопеечные и двухкопеечные монеты чередуются, что невозможно. Двух трехкопеечных монет тоже не может быть, поскольку между ними должно быть хотя бы три монеты. Таким образом, среди первых 2000 монет ровно 500 трехкопеечных. Следовательно, всего трехкопеечных монет может быть 501 или. Оба ответа возможны, например . . . и 2131213121312 . . .21312.
622. Докажем, что в этой компании есть n + 1 попарно знакомый человек. Очевидно, что естьдвое знакомых, и если есть попарно знакомых
(где k n), то по условию найдется отличный от них человек, знакомый
КЛАСС
371
Разобьем числа от дона две группы A
n
=
{n
2
, n
2
+
+ 1, . . . , n
2
+ n
} и B
n
=
{n
2
+ n + 1, n
2
+ n + 2, . . . , n
2
+ 2n
}. Для чисел группы ближайшим квадратом является n
2
, для ближайшим является (n + 1)
2
— квадрат другой четности. Суммы чисел в группах и обозначим и соответственно. Но из равенства S(B
n
)
−
− S(A
n
) =
(n
2
+ n + 1)
− (n
2
+ 1)
+
(n
2
+ n + 2)
− (n
2
+ 2)
+. . .
. . . +
(n
2
+ 2n)
− (n
2
+ n)
− n
2
= n
· n − n
2
= следует, что суммы чисел в группах и равны. Осталосьзаметить, что все множество чисел от 1 до 999 999 разбивается на непересекающиеся пары и B
1
, и B
2
, . . . , и B
999
618. Из условия следует, что Q(x) = (x − x
1
)(x
− x
2
)
, где x
2
− x
1
> итак как P (x
1
) = Q(x
1
) = 0
,
P (x
2
) = Q(x
2
) = 0
. Предположим, что P (x)− Q(x) 0, те при всех x. Это выполняется только в том случае, когда x
2
+ Ax + (B
− 1) = (x − x
1
)(x
− x
2
)
, так как в точках = и x = не будет происходитьперемена знака многочлена P (x) −
− Q(x) только при четной кратности корней x = и x = x
2
. Значит =
−(x
1
+ x
2
)
, B − 1 = x
1
x
2
, Поэтому дискриминант трехчлена x
2
+
+ Ax + есть D = (x
1
+ x
2
)
2
− 4(x
1
x
2
+ 1) = (x
1
− x
2
)
2
− 4 > 0. Но тогда P (x) = (x− x
1
)(x
− x
2
)(x
− x
3
)(x
− корни и не совпадают си, так как и x
4
— корни трехчлена x
2
+ Ax + B
, аи нет кроме того, x
3
= x
4
, так как D = 0). Таким образом, P (x) не может иметьв качестве промежутка отрицательных значений ровно интервал I =
= (x
1
; x
2
)
. Противоречие. Значит, неравенство P (x) − Q(x) 0 при некоторых x нарушается. Пусть M — середина стороны CD, а L — середина стороны Достроим параллелограмм ABCD до треугольника так, чтобы отрезок AC был средней линией треугольника см. рис. 280). Для этого через точку D проведем прямую, параллельную AC и обозначим через и точки пересечения этой прямой с продолжениями сторон и BA соответственно. Тогда четырехугольники и будут параллелограммами. Точки A, M и будут лежатьна одной прямой, ибо в параллелограмме диагонали делятся точкой пересечения на равные части. Следовательно, в треугольнике угол K — прямой, поскольку точка M равноудалена от точек A, и K. Аналогично устанавливаем,
что ∠CKC
1
= 90
◦
. Таким образом 90
◦
− Отрезки CN и параллельны, ибо CN — средняя линия в треугольнике. Аналогично параллельны отрезки AN и KC
1
. Следовательно ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
A
B
C
D
A
1
C
1
M
L
K
N
Рис. 280
∠NCK = ∠CKA
1
=
∠C
1
KA =
∠NAK.
620. Уберем вершину данного многоугольника A
1
A
2
. . . Назовем средними диагоналями многоугольника A
1
A
2
. . . отрезки, соединяющие вершины, номера которых отличаются на 999 или Рассмотрим все средние диагонали, их ровно 1999 штук. Заметим, что любые две из них пересекаются, из каждой вершины выходит ровно две средние диагонали. Поскольку 1999 > 2 · 999, то найдутся три одноцветные средние диагонали, они попарно пересекаются в трех разных точках.
Эти точки пересечения и являются вершинами искомого треугольника. Ответили Рассмотрим любые четыре подряд идущие монеты. Докажем, что среди них ровно одна трехкопеечная. Предположим противное. Если среди этих монет не оказалосьни одной трехкопеечной, то однокопеечные и двухкопеечные монеты чередуются, что невозможно. Двух трехкопеечных монет тоже не может быть, поскольку между ними должно быть хотя бы три монеты. Таким образом, среди первых 2000 монет ровно 500 трехкопеечных. Следовательно, всего трехкопеечных монет может быть 501 или. Оба ответа возможны, например . . . и 2131213121312 . . .21312.
622. Докажем, что в этой компании есть n + 1 попарно знакомый человек. Очевидно, что естьдвое знакомых, и если есть попарно знакомых
(где k n), то по условию найдется отличный от них человек, знакомый
УЧЕБНЫЙ ГОД, 9
КЛАСС
373
со всеми этими k людьми. Отсюда следует, что найдутся n + 1 попарно знакомых человек A
1
, . . . Рассмотрим остальных n человек. По условию, существует отличный от них человек A
i
, знающий их всех. Но тогда знаком со всеми.
A
B
C
O
N
P
K
Q
M
P
1
K
1
Q
1
M
1
Рис. 281
623. Пусть P и Q — середины сторон AB и соответственно, P
1
, K
1
,
Q
1
, M
1
— проекции точек, K, Q, M на сторону
AC
(см. рис. 281). Тогда и, по условию, поэтому, следовательно, если точка ближе к вершине B, чем точка P , то точка Q ближе к B, чем точка Из условия следует, что OP ⊥ AB, OQ ⊥ BC ⇒ ∠P OQ = π − Поэтому утверждение задачи равносильно равенству ∠KOM = ∠P тес учетом установленного расположения точек, подобию прямоугольных треугольников OP K и Пусть ∠BAC = α, ∠BCA = γ. Тогда P K = P
1
K
1
: cos α
, QM =
= Q
1
M
1
: cos γ
. Но P
1
Q
1
= K
1
M
1
⇒ P
1
K
1
= Q
1
M
1
⇒ P K : QM =
= cos γ : cos С другой стороны, ∠AOB = 2γ ⇒ ∠BOP = γ ⇒ OP = R cos где R — радиус описанной окружности. Аналогично OQ = R cos α ⇒
⇒ OP : OQ = cos γ : cos α = P K : QM и, значит, OP K ∼ OQM.
624. Ответ. n = p
m
, где p — простое число, m ∈ Предположим, что n не является степенью простого числа. Пусть p наименьший простой делитель числа n. Представим n в виде p
m
· k, где
p
не делится на k. По условию число l = p + k − 1 является делителем. Покажем, что l взаимно просто с k. Предположим противное. Если
НОД(l, k) > 1, то НОД(p−1, k) = НОД(l−k, k) = НОД(l, k) > 1. Таким образом, число k имеет какой-то делитель d, 2 d p − 1. Противоречие с выбором числа p. Следовательно, p + k − 1 = p
α
. Ясно, что α 2, ибо > 1
. Таким образом, числа и k — взаимно простые делители числа те делительчисла n. При этом p
2
+ k
− 1 взаимно просто с k, поскольку в противном случае k имеет общий делительс p
2
− 1 =
= 2(p
−1)·
p + 1 2
, что снова противоречит выбору числа p. Следовательно+ k
−1 = p
β
, где β 3. Но тогда p
β
= p
2
+ k
−1 = p
2
+ (p + k
−1)−p =
КЛАСС
373
со всеми этими k людьми. Отсюда следует, что найдутся n + 1 попарно знакомых человек A
1
, . . . Рассмотрим остальных n человек. По условию, существует отличный от них человек A
i
, знающий их всех. Но тогда знаком со всеми.
A
B
C
O
N
P
K
Q
M
P
1
K
1
Q
1
M
1
Рис. 281
623. Пусть P и Q — середины сторон AB и соответственно, P
1
, K
1
,
Q
1
, M
1
— проекции точек, K, Q, M на сторону
AC
(см. рис. 281). Тогда и, по условию, поэтому, следовательно, если точка ближе к вершине B, чем точка P , то точка Q ближе к B, чем точка Из условия следует, что OP ⊥ AB, OQ ⊥ BC ⇒ ∠P OQ = π − Поэтому утверждение задачи равносильно равенству ∠KOM = ∠P тес учетом установленного расположения точек, подобию прямоугольных треугольников OP K и Пусть ∠BAC = α, ∠BCA = γ. Тогда P K = P
1
K
1
: cos α
, QM =
= Q
1
M
1
: cos γ
. Но P
1
Q
1
= K
1
M
1
⇒ P
1
K
1
= Q
1
M
1
⇒ P K : QM =
= cos γ : cos С другой стороны, ∠AOB = 2γ ⇒ ∠BOP = γ ⇒ OP = R cos где R — радиус описанной окружности. Аналогично OQ = R cos α ⇒
⇒ OP : OQ = cos γ : cos α = P K : QM и, значит, OP K ∼ OQM.
624. Ответ. n = p
m
, где p — простое число, m ∈ Предположим, что n не является степенью простого числа. Пусть p наименьший простой делитель числа n. Представим n в виде p
m
· k, где
p
не делится на k. По условию число l = p + k − 1 является делителем. Покажем, что l взаимно просто с k. Предположим противное. Если
НОД(l, k) > 1, то НОД(p−1, k) = НОД(l−k, k) = НОД(l, k) > 1. Таким образом, число k имеет какой-то делитель d, 2 d p − 1. Противоречие с выбором числа p. Следовательно, p + k − 1 = p
α
. Ясно, что α 2, ибо > 1
. Таким образом, числа и k — взаимно простые делители числа те делительчисла n. При этом p
2
+ k
− 1 взаимно просто с k, поскольку в противном случае k имеет общий делительс p
2
− 1 =
= 2(p
−1)·
p + 1 2
, что снова противоречит выбору числа p. Следовательно+ k
−1 = p
β
, где β 3. Но тогда p
β
= p
2
+ k
−1 = p
2
+ (p + k
−1)−p =
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ p(p+p
α−1
−1), что не делится на p
2
. Противоречие, следовательно, k =
= 1
. Нетрудно убедиться, что полученные числа удовлетворяют условию класс. См. решение задачи 617.
626. Лемма. Пусть множества A и B на прямой являются объединениями m и n отрезков соответственно. Тогда A ∩ B — объединение не более m + n − 1 отрезков.
Д ока за тел ь ст во. Ясно, что A ∩ B — тоже объединение отрезков.
Пустьих количество равно k. Концы отрезков A ∩ B являются концами отрезков A или B. Следовательно, рассматривая концы отрезков A ∩ получаем 2m + Но при этом самый левый конец отрезка из всех концов A или B либо не принадлежит A∩B, либо входит ив концы A ив концы B. Значит, правую часть (∗) можно уменьшить на 1. Аналогично, рассматривая самый правый конец A или B, мы уменьшаем правую часть (∗) еще на 1. Тогда 2m + 2n − те Лемма доказана.
Теперьрешим задачу пересекая последовательно с A
2
, A
3
,
. . . , A
100
, мы увидим, что количество отрезков в пересечении будет небо- лее 100 + 100 − 1 = 199, 199 + 100 − 1 = 298, . . . , 9802 + 100 − 1 = что и требовалосьдоказать.
A
B
M
N
K
P
Ω
ω
ω
1
l
Рис. 282
627. Обозначим внешнюю окружность через Ω, внутреннюю — ω, описанную окружностьтреугольника BKM — их радиусы — R, r и r
1
соответственно.
Пустьотрезок BN пересекает ω в точке см. рис. 282). Рассмотрим гомотетию с центром в точке N, переводящую внутреннюю окружностьво внешнюю. Тогда H(P ) = B, H(AB) = l, где касательная к Ω, параллельная те. проходящая через точку M. Следовательно, те. точки N, лежат на одной прямой. Тогда, по теореме синусов α
2R sin α
=
r
1
R
, где α = ∠BMN. Кроме того
α−1
−1), что не делится на p
2
. Противоречие, следовательно, k =
= 1
. Нетрудно убедиться, что полученные числа удовлетворяют условию класс. См. решение задачи 617.
626. Лемма. Пусть множества A и B на прямой являются объединениями m и n отрезков соответственно. Тогда A ∩ B — объединение не более m + n − 1 отрезков.
Д ока за тел ь ст во. Ясно, что A ∩ B — тоже объединение отрезков.
Пустьих количество равно k. Концы отрезков A ∩ B являются концами отрезков A или B. Следовательно, рассматривая концы отрезков A ∩ получаем 2m + Но при этом самый левый конец отрезка из всех концов A или B либо не принадлежит A∩B, либо входит ив концы A ив концы B. Значит, правую часть (∗) можно уменьшить на 1. Аналогично, рассматривая самый правый конец A или B, мы уменьшаем правую часть (∗) еще на 1. Тогда 2m + 2n − те Лемма доказана.
Теперьрешим задачу пересекая последовательно с A
2
, A
3
,
. . . , A
100
, мы увидим, что количество отрезков в пересечении будет небо- лее 100 + 100 − 1 = 199, 199 + 100 − 1 = 298, . . . , 9802 + 100 − 1 = что и требовалосьдоказать.
A
B
M
N
K
P
Ω
ω
ω
1
l
Рис. 282
627. Обозначим внешнюю окружность через Ω, внутреннюю — ω, описанную окружностьтреугольника BKM — их радиусы — R, r и r
1
соответственно.
Пустьотрезок BN пересекает ω в точке см. рис. 282). Рассмотрим гомотетию с центром в точке N, переводящую внутреннюю окружностьво внешнюю. Тогда H(P ) = B, H(AB) = l, где касательная к Ω, параллельная те. проходящая через точку M. Следовательно, те. точки N, лежат на одной прямой. Тогда, по теореме синусов α
2R sin α
=
r
1
R
, где α = ∠BMN. Кроме того
УЧЕБНЫЙ ГОД, КЛАСС P
BN
=
r
R
. Далее, BK
2
= BP
· BN поэтому 1
−
N P
BN
= 1
−
r
R
. Отсюда следует, что отношение
r
1
R
постоянно.
628. Построим граф, вершины которого соответствуют городам, а ребра дорогам. В этом графе между любыми двумя вершинами естьедин- ственный путь, следовательно, в нем нет циклов (такой граф называется
деревом). По условию, в этом графе есть вершин, из которых выходит ровно одно ребро (такие вершины называются висячими) — пусть это вершины A
1
, A
2
, . . . , A
100
. Для каждой пары висячих вершин и существует единственный путьмежду ними, назовем количество ребер на этом пути расстоянием между этими вершинами и будем обозначатьче- рез d(A
i
, A
j
)
. Из конечности числа способов разбитьэти 100 вершин на пар следует, что при одном из способов достигается максимум суммы расстояний между вершинами в парах. Соединим пары вершин при этом разбиении 50 новыми ребрами (остальные ребра будем называть старыми. Мы докажем, что после этого даже при удалении любого ребра сохраняется связность графа (те, возможностьиз любой вершины по- пастьв любую другую).
Предположим противное, пустьпри удалении ребра между вершинами и C граф распался на две части, которые не связаны между собой.
Нетрудно заметить, что удаленное ребро было старым, водной из полученных частей находится вершина B, а в другой — вершина C. Очевидно,
в каждой части должна бытьвершина, из которой выходит ровно одно старое ребро, и каждое новое ребро соединяет две вершины из одной части.
Но тогда водной из частей должно бытьновое ребро, соединяющее вершины и A
j
, а в другой — соединяющее вершины и A
m
. Однако в этом случае нетрудно проверить, что, A
j
) + d(A
k
, A
m
) < d(A
i
, A
k
) + d(A
j
, что противоречит максимальности суммы расстояний в выбранных парах.
Следовательно, при удалении ребра BC возможностьпопастьиз любой вершины в любую другую должна сохраниться. По условию P (x) = (x − x
1
)(x
− x
2
)(x
− x
3
)
, следовательно (Q(x)) = (Q(x)
−x
1
)(Q(x)
−x
2
)(Q(x)
−x
3
)
, где Q(x)−x
i
= 0, i = 1, 2, те. Перемножив полученные неравенства x
i
>
1 4
, получаем P (2001) = (2001 − x
1
)(2001
− x
2
)(2001
− x
3
) >
>
1 64
BN
=
r
R
. Далее, BK
2
= BP
· BN поэтому 1
−
N P
BN
= 1
−
r
R
. Отсюда следует, что отношение
r
1
R
постоянно.
628. Построим граф, вершины которого соответствуют городам, а ребра дорогам. В этом графе между любыми двумя вершинами естьедин- ственный путь, следовательно, в нем нет циклов (такой граф называется
деревом). По условию, в этом графе есть вершин, из которых выходит ровно одно ребро (такие вершины называются висячими) — пусть это вершины A
1
, A
2
, . . . , A
100
. Для каждой пары висячих вершин и существует единственный путьмежду ними, назовем количество ребер на этом пути расстоянием между этими вершинами и будем обозначатьче- рез d(A
i
, A
j
)
. Из конечности числа способов разбитьэти 100 вершин на пар следует, что при одном из способов достигается максимум суммы расстояний между вершинами в парах. Соединим пары вершин при этом разбиении 50 новыми ребрами (остальные ребра будем называть старыми. Мы докажем, что после этого даже при удалении любого ребра сохраняется связность графа (те, возможностьиз любой вершины по- пастьв любую другую).
Предположим противное, пустьпри удалении ребра между вершинами и C граф распался на две части, которые не связаны между собой.
Нетрудно заметить, что удаленное ребро было старым, водной из полученных частей находится вершина B, а в другой — вершина C. Очевидно,
в каждой части должна бытьвершина, из которой выходит ровно одно старое ребро, и каждое новое ребро соединяет две вершины из одной части.
Но тогда водной из частей должно бытьновое ребро, соединяющее вершины и A
j
, а в другой — соединяющее вершины и A
m
. Однако в этом случае нетрудно проверить, что, A
j
) + d(A
k
, A
m
) < d(A
i
, A
k
) + d(A
j
, что противоречит максимальности суммы расстояний в выбранных парах.
Следовательно, при удалении ребра BC возможностьпопастьиз любой вершины в любую другую должна сохраниться. По условию P (x) = (x − x
1
)(x
− x
2
)(x
− x
3
)
, следовательно (Q(x)) = (Q(x)
−x
1
)(Q(x)
−x
2
)(Q(x)
−x
3
)
, где Q(x)−x
i
= 0, i = 1, 2, те. Перемножив полученные неравенства x
i
>
1 4
, получаем P (2001) = (2001 − x
1
)(2001
− x
2
)(2001
− x
3
) >
>
1 64
1 ... 47 48 49 50 51 52 53 54 ... 64
630. Достаточно доказать, что сумма S горизонтальных проекций векторов, соединяющих центры клеток с большим числом с центрами клеток с меньшим числом, равна нулю. Аналогичными рассуждениями доказы-
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
вается, что сумма вертикальных проекций векторов также равна нулю, откуда следует утверждение задачи.
Примем длину стороны клетки за 1, за положительное направление горизонтальной оси выберем направление слева направо. Будем переме- щатьчисла внутри строк (при этом в одну клетку могут попадатьнесколь- ко чисел) и следитьза изменением суммы S проекций векторов. Заметим вначале, что сумма чисел в столбце магического квадрата составляет от суммы всех чисел, те. она равна. В клетку с числом k входит k и выходит k − 1 векторов. Следовательно, если мы передвинем на клетку влево, то сумма S меняется на (k − 1) − (n
2
− k) = 2k − 1 −
−n
2
. Последовательно передвинем n чисел a
1
, a
2
, . . . , a
n
, которые стояли водном столбце, на одну клетку влево. При этом сумма S меняется на 1 − n
2
) + (2a
2
− 1 − n
2
) + . . . + (2a
n
− 1 − n
2
) = 2(a
1
+ a
2
+. . .
. . . +a
n
)
−n−n
3
= n(n
2
+1)
−n−n
3
= 0
. Таким образом, последовательно переместив числа каждого столбца в самый левый столбец, получим, что сумма S не изменилась. Нов конце сумма S стала равна нулю, поскольку проекции всех векторов стали нулевые. Значит ив начале S = 0.
631. Пустьокружность, проходящая через H, A
1
, B
1
, пересекает второй раз прямую CH в точке C
1
. Достаточно доказать, что совпадает с
C
1
A
B
C
A
1
B
1
C
1
H
F
Рис. Рассмотрим точку F , диаметрально противоположную точке
H
(см. рис. 283). Углы и HC
1
F
— прямые, так как опираются на диаметр. Поэтому Отсюда следует равенство площадей S
BF C
=
= в треугольниках BF и основание общее, а высоты равны, аналогично S
CF A
= и S
AF B
= Заметим, что точка F лежит внутри треугольника ABC: поскольку и лежат на высотах, а не на их продолжениях, точка F лежит внутри угла ACB; если бы при этом F лежала вне треугольника ABC, то сумма площадей S
AF C
+ S
BF C
= S
AB
1
C
+ была бы больше площади треугольника ABC в противоречие с условием таком образом, лежит на высоте, а не на ее продолжении. Ввиду равенств S = S
AF B
+ S
BF C
+
+S
CF A
= получаем, что S
AC
1
B
= S
AC
1
B
, откуда следует совпадение точек и C
1
632. Ответ. n = p
k
, p — простое, или n = 12.
вается, что сумма вертикальных проекций векторов также равна нулю, откуда следует утверждение задачи.
Примем длину стороны клетки за 1, за положительное направление горизонтальной оси выберем направление слева направо. Будем переме- щатьчисла внутри строк (при этом в одну клетку могут попадатьнесколь- ко чисел) и следитьза изменением суммы S проекций векторов. Заметим вначале, что сумма чисел в столбце магического квадрата составляет от суммы всех чисел, те. она равна. В клетку с числом k входит k и выходит k − 1 векторов. Следовательно, если мы передвинем на клетку влево, то сумма S меняется на (k − 1) − (n
2
− k) = 2k − 1 −
−n
2
. Последовательно передвинем n чисел a
1
, a
2
, . . . , a
n
, которые стояли водном столбце, на одну клетку влево. При этом сумма S меняется на 1 − n
2
) + (2a
2
− 1 − n
2
) + . . . + (2a
n
− 1 − n
2
) = 2(a
1
+ a
2
+. . .
. . . +a
n
)
−n−n
3
= n(n
2
+1)
−n−n
3
= 0
. Таким образом, последовательно переместив числа каждого столбца в самый левый столбец, получим, что сумма S не изменилась. Нов конце сумма S стала равна нулю, поскольку проекции всех векторов стали нулевые. Значит ив начале S = 0.
631. Пустьокружность, проходящая через H, A
1
, B
1
, пересекает второй раз прямую CH в точке C
1
. Достаточно доказать, что совпадает с
C
1
A
B
C
A
1
B
1
C
1
H
F
Рис. Рассмотрим точку F , диаметрально противоположную точке
H
(см. рис. 283). Углы и HC
1
F
— прямые, так как опираются на диаметр. Поэтому Отсюда следует равенство площадей S
BF C
=
= в треугольниках BF и основание общее, а высоты равны, аналогично S
CF A
= и S
AF B
= Заметим, что точка F лежит внутри треугольника ABC: поскольку и лежат на высотах, а не на их продолжениях, точка F лежит внутри угла ACB; если бы при этом F лежала вне треугольника ABC, то сумма площадей S
AF C
+ S
BF C
= S
AB
1
C
+ была бы больше площади треугольника ABC в противоречие с условием таком образом, лежит на высоте, а не на ее продолжении. Ввиду равенств S = S
AF B
+ S
BF C
+
+S
CF A
= получаем, что S
AC
1
B
= S
AC
1
B
, откуда следует совпадение точек и C
1
632. Ответ. n = p
k
, p — простое, или n = 12.
УЧЕБНЫЙ ГОД, 11
КЛАСС
377
Легко видеть, что указанные в ответе числа удовлетворяют условию задачи. Покажем, что других чисел, удовлетворяющих условию, не суще- ствует.
Случай нечетного n рассмотрен в задаче 624. Пусть n четно и не является степенью двойки представим его в виде n = 2
m
· k, где m 1, а > 1
— нечетное число. Заметим, что k + 2 − 1 = k + 1 — делитель Поскольку НОД(k + 1, k) = 1, k + 1 = 2
α
, α > 1. Поэтому 2 2
+ k
− 1 =
= k + 3
— тоже делитель n. Заметим, что k + 3 = (k + 1) + 2 = 2
α
+ не делится на 2 2
. Кроме того, НОД(k + 3, k) = НОД(3, k) 3. Из этого заключаем, что k + 3 2 · 3 = 6, и k 3. Значит, n = 2
m
· 3. Ноне подходит m 3 также не подходит, так как в этом случае мы получили бы, что 2 3
+ 3
− 1 = 10 — также делитель n.
11 класс. Ответ. 97 средних чисел.
Заметим, что если число k = m является средним, то число k = 100 −
− m также является средним. Поэтому если число k = 1 не является средним, то число k = 99 также не является средними количество средних чисел не больше 97 (k = 100). Если же число k = 1 является средним,
то вес одной из гирек равен S и, следовательно, только k = 99 также является средним числом. Значит, количество средних чисел не превосходит
97.
Приведем пример набора из 100 гирек с весами a
1
, . . . , для которого все числа от 2 до 98 (всего 97 чисел) — средние. Пусть a
1
= a
2
= 1
,
a
n+2
= a
n
+ a
n+1
, n = 1, 2, . . . , 97, — последовательные числа Фибоначчи и S = a
1
+ a
2
+ . . . + a
98
. Выберем a
100
= S
− a
99
. Тогда суммарный вес всех гирек равен 2S ив тоже время, a
100
+ a
99
= a
100
+ a
98
+ a
97
=
= a
100
+ a
98
+ a
96
+ a
95
= a
100
+ a
98
+ a
96
+ a
94
+ a
93
= . . . = a
100
+
+ a
98
+ a
96
+ a
94
+ a
92
+ a
90
+ . . . + a
6
+ a
4
+ a
2
+ a
1
= S
. Следовательно,
средними являются числа 2, 3, 4, . . . , 51. Но тогда средними будут и числа 2 = 98, 100 − 3 = 97, . . . , 100 − 48 = 52, те. все числа от 2 до 98 средние. См. решение задачи 627.
635. Для каждой из прямых, пересекающих все многоугольники набора, проведем параллельную ей прямую через центр O некоторой окружности. Обозначим через множество точек пересечения этих прямых с S. Определим аналогично для набора множество S
2
⊂ Покажем, что S
1
∪ S
2
= S
. Спроектируем многоугольники наборов
P
1
и на произвольную прямую l см. рис. 284). Из условия следует
КЛАСС
377
Легко видеть, что указанные в ответе числа удовлетворяют условию задачи. Покажем, что других чисел, удовлетворяющих условию, не суще- ствует.
Случай нечетного n рассмотрен в задаче 624. Пусть n четно и не является степенью двойки представим его в виде n = 2
m
· k, где m 1, а > 1
— нечетное число. Заметим, что k + 2 − 1 = k + 1 — делитель Поскольку НОД(k + 1, k) = 1, k + 1 = 2
α
, α > 1. Поэтому 2 2
+ k
− 1 =
= k + 3
— тоже делитель n. Заметим, что k + 3 = (k + 1) + 2 = 2
α
+ не делится на 2 2
. Кроме того, НОД(k + 3, k) = НОД(3, k) 3. Из этого заключаем, что k + 3 2 · 3 = 6, и k 3. Значит, n = 2
m
· 3. Ноне подходит m 3 также не подходит, так как в этом случае мы получили бы, что 2 3
+ 3
− 1 = 10 — также делитель n.
11 класс. Ответ. 97 средних чисел.
Заметим, что если число k = m является средним, то число k = 100 −
− m также является средним. Поэтому если число k = 1 не является средним, то число k = 99 также не является средними количество средних чисел не больше 97 (k = 100). Если же число k = 1 является средним,
то вес одной из гирек равен S и, следовательно, только k = 99 также является средним числом. Значит, количество средних чисел не превосходит
97.
Приведем пример набора из 100 гирек с весами a
1
, . . . , для которого все числа от 2 до 98 (всего 97 чисел) — средние. Пусть a
1
= a
2
= 1
,
a
n+2
= a
n
+ a
n+1
, n = 1, 2, . . . , 97, — последовательные числа Фибоначчи и S = a
1
+ a
2
+ . . . + a
98
. Выберем a
100
= S
− a
99
. Тогда суммарный вес всех гирек равен 2S ив тоже время, a
100
+ a
99
= a
100
+ a
98
+ a
97
=
= a
100
+ a
98
+ a
96
+ a
95
= a
100
+ a
98
+ a
96
+ a
94
+ a
93
= . . . = a
100
+
+ a
98
+ a
96
+ a
94
+ a
92
+ a
90
+ . . . + a
6
+ a
4
+ a
2
+ a
1
= S
. Следовательно,
средними являются числа 2, 3, 4, . . . , 51. Но тогда средними будут и числа 2 = 98, 100 − 3 = 97, . . . , 100 − 48 = 52, те. все числа от 2 до 98 средние. См. решение задачи 627.
635. Для каждой из прямых, пересекающих все многоугольники набора, проведем параллельную ей прямую через центр O некоторой окружности. Обозначим через множество точек пересечения этих прямых с S. Определим аналогично для набора множество S
2
⊂ Покажем, что S
1
∪ S
2
= S
. Спроектируем многоугольники наборов
P
1
и на произвольную прямую l см. рис. 284). Из условия следует
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
что при этом получатся два набора отрезков и таких, что любые два отрезка из разных наборов имеют общую точку.
Возьмем отрезок I, левый конец A которого является среди полученных отрезков самым правым. Пусть, например, I принадлежит P
1
, тогда все отрезки содержат точку A. Следовательно, прямая m, проходящая через точку A перпендикулярно l, пересекает все многоугольники набора. В силу произвольности выбора прямой l получаем, что S
1
∪ S
2
= Рис. Рис. Очевидно, все отрезки в имеют общую точку и все отрезки в имеют общую точку тогда и только тогда, когда точки окружности S, имеющие направление m, принадлежат как S
1
, таки Но если все отрезки из имеют общую точку и все отрезки из имеют общую точку, то любые два отрезка из имеют общую точку. Тогда все отрезки из P
1
∪ имеют общую точку.
Следовательно, прямая, проходящая через эту точку перпендикулярно, пересекает все многоугольники наборов и P
2
. Таким образом, утверждение задачи доказано, если S
1
∩ S
2
= Покажем, что S
1
∩ S
2
= ∅. В самом деле, легко видеть, что множества и состоят из конечного числа замкнутых дуг окружности (например, если число элементов вне больше n, то дуг не больше так как конец каждой дуги соответствует непересекающимся многоугольникам см. рис. 285). Так как в каждом множестве естьпара непересе- кающихся многоугольников, то, отделяя эти многоугольники прямой, мы видим, что S
1
= S и S
2
= Если S
1
∩ S
2
=
∅, то S
1
∪ состоит из попарно непересекающихся замкнутых дуг. Возьмем конец одной дуги, тогда между ними ближайшим концом дуги почасовой стрелке нет точек S
1
∪ S
2
, что противоречит тому,
что S
1
∪ S
2
= S
636. Ответ. При n участниках
что при этом получатся два набора отрезков и таких, что любые два отрезка из разных наборов имеют общую точку.
Возьмем отрезок I, левый конец A которого является среди полученных отрезков самым правым. Пусть, например, I принадлежит P
1
, тогда все отрезки содержат точку A. Следовательно, прямая m, проходящая через точку A перпендикулярно l, пересекает все многоугольники набора. В силу произвольности выбора прямой l получаем, что S
1
∪ S
2
= Рис. Рис. Очевидно, все отрезки в имеют общую точку и все отрезки в имеют общую точку тогда и только тогда, когда точки окружности S, имеющие направление m, принадлежат как S
1
, таки Но если все отрезки из имеют общую точку и все отрезки из имеют общую точку, то любые два отрезка из имеют общую точку. Тогда все отрезки из P
1
∪ имеют общую точку.
Следовательно, прямая, проходящая через эту точку перпендикулярно, пересекает все многоугольники наборов и P
2
. Таким образом, утверждение задачи доказано, если S
1
∩ S
2
= Покажем, что S
1
∩ S
2
= ∅. В самом деле, легко видеть, что множества и состоят из конечного числа замкнутых дуг окружности (например, если число элементов вне больше n, то дуг не больше так как конец каждой дуги соответствует непересекающимся многоугольникам см. рис. 285). Так как в каждом множестве естьпара непересе- кающихся многоугольников, то, отделяя эти многоугольники прямой, мы видим, что S
1
= S и S
2
= Если S
1
∩ S
2
=
∅, то S
1
∪ состоит из попарно непересекающихся замкнутых дуг. Возьмем конец одной дуги, тогда между ними ближайшим концом дуги почасовой стрелке нет точек S
1
∪ S
2
, что противоречит тому,
что S
1
∪ S
2
= S
636. Ответ. При n участниках
УЧЕБНЫЙ ГОД, 11
КЛАСС
379
Докажем, что при n участниках такое распределение баллов может существовать. Пример очевиден — пусть й участник ответит только на один й вопрос. Тогда, назначив стоимостьвопросов a
1
, a
2
, . . . , a
n
, где, a
2
, . . . , a
n
} = {1, 2, . . . , n}, жюри поставит го участника на место + 1
− a
k
Теперьдокажем от противного, что не могло быть + 1 участников или более. Представим себе, что мы клонировали каждого участника, т. е.
у нас естьнеограниченное количество участников каждого из n + 1 типов. Докажем, что если мы сможем составитьиз них две команды, разные по составу (хотя бы для одного типа число участников этого типа впервой команде неравно числу участников этого типа во второй команде, но имеющих одинаковые результаты (те. на каждый вопрос впервой команде ответило столько же человек, сколько во второй, то мы придем к противоречию.
Во-первых, можно считать, что участники каждого типа присутствуют не более, чем водной команде если в обеих командах естьпо участнику одного типа, удалим их, составы команд останутся разными, а результаты одинаковыми.
Пусть, без ограничения общности, впервой команде участников не меньше, чем во второй. Тогда нельзя назначить баллы за вопросы так,
чтобы места всех участников первой команды были выше, чем места участников второй команды, ибо сумма баллов участников первой команды всегда равна сумме баллов участников второй команды.
Осталосьдоказать, что такие две команды найдутся. Для этого запишем систему линейных уравнений, е уравнение которой гласит, что разностьчисла участников первой и второй команды, ответивших на й вопрос естьноль; й переменной здесьбудет число участников го типа в команде (впервой, если переменная положительна, во второй, — если отрицательна. Это система из n однородных уравнений с n + 1 переменной. Как известно, она имеет ненулевое решение, причем, поскольку все коэффициенты рациональны (а они нули или единицы, существует рациональное ненулевое решение. Поскольку уравнения однородны, решение можно домножитьна константу. Домножим так, чтобы значения всех переменных стали целыми. Требуемые команды найдены. Первое решение. Без ограничения общности можно считать, что (x) < при x ∈ (x
1
, x
2
)
, g(x) < 0 при x ∈ (x
3
, x
4
)
, где x
2
< x
3
. Рассмотрим касательную к графику y = αf(x) в точке и касательную к графику y = βg(x) в точке x
3
. Подберем положительные α итак, чтобы модули угловых коэффициентов этих касательных стали равными. Пусть касательная кв точке имеет вид y = ax+b
1
, касательная к βg(x)
КЛАСС
379
Докажем, что при n участниках такое распределение баллов может существовать. Пример очевиден — пусть й участник ответит только на один й вопрос. Тогда, назначив стоимостьвопросов a
1
, a
2
, . . . , a
n
, где, a
2
, . . . , a
n
} = {1, 2, . . . , n}, жюри поставит го участника на место + 1
− a
k
Теперьдокажем от противного, что не могло быть + 1 участников или более. Представим себе, что мы клонировали каждого участника, т. е.
у нас естьнеограниченное количество участников каждого из n + 1 типов. Докажем, что если мы сможем составитьиз них две команды, разные по составу (хотя бы для одного типа число участников этого типа впервой команде неравно числу участников этого типа во второй команде, но имеющих одинаковые результаты (те. на каждый вопрос впервой команде ответило столько же человек, сколько во второй, то мы придем к противоречию.
Во-первых, можно считать, что участники каждого типа присутствуют не более, чем водной команде если в обеих командах естьпо участнику одного типа, удалим их, составы команд останутся разными, а результаты одинаковыми.
Пусть, без ограничения общности, впервой команде участников не меньше, чем во второй. Тогда нельзя назначить баллы за вопросы так,
чтобы места всех участников первой команды были выше, чем места участников второй команды, ибо сумма баллов участников первой команды всегда равна сумме баллов участников второй команды.
Осталосьдоказать, что такие две команды найдутся. Для этого запишем систему линейных уравнений, е уравнение которой гласит, что разностьчисла участников первой и второй команды, ответивших на й вопрос естьноль; й переменной здесьбудет число участников го типа в команде (впервой, если переменная положительна, во второй, — если отрицательна. Это система из n однородных уравнений с n + 1 переменной. Как известно, она имеет ненулевое решение, причем, поскольку все коэффициенты рациональны (а они нули или единицы, существует рациональное ненулевое решение. Поскольку уравнения однородны, решение можно домножитьна константу. Домножим так, чтобы значения всех переменных стали целыми. Требуемые команды найдены. Первое решение. Без ограничения общности можно считать, что (x) < при x ∈ (x
1
, x
2
)
, g(x) < 0 при x ∈ (x
3
, x
4
)
, где x
2
< x
3
. Рассмотрим касательную к графику y = αf(x) в точке и касательную к графику y = βg(x) в точке x
3
. Подберем положительные α итак, чтобы модули угловых коэффициентов этих касательных стали равными. Пусть касательная кв точке имеет вид y = ax+b
1
, касательная к βg(x)
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
в точке имеет вид y = −ax + b
2
, a > 0. Эти касательные пересекаются в точке с ординатой y
0
> 0
. Парабола, ветви которой направлены вверх,
лежит выше касательной. Поэтому αf(x) + βg(x) > ax + b
1
− ax + b
2
=
= b
1
+ b
2
= 2y
0
> 0
, что и требовалосьдоказать.
Второе решение. Пустьграфики пересекаются в точке P (x
0
, Тогда f(x) = y
0
+ (x
− x
)(x
− x
0
)
, g(x) = y
0
+ (x
− x
)(x
− x
0
)
, причем,
если x
0
< x
0
, то x
0
< x
. Действительно, если, скажем, x
< x
< тона интервале (x
, выполнено f(x) < g(x), ив точках, в которых
g(x)
отрицательно, f(x) также отрицательно, что невозможно. Поэтому) = αf (x) + βg(x) = (α + β)y
0
+ (x
− x
0
)[(α + β)x
− (αx
+ βx
)] =
= (α + β)y
0
+ (α + β)(x
− x
0
)
2
(α + β)y
0
> 0
, если выбрать α и β так,
чтобы (α + β)x
0
= αx
+ βx
, те. Это можно сделать, так как x
< x
0
< x
638. Пусть d — наибольший общий делитель чисел a и b, те, где и взаимно просты. Тогда da
1
b
1
(a
1
+ делится на 1
+ a
1
b
1
+ b
2 1
= m
. Число a
1
+ взаимно просто с числами ив противном случае и имеют общий делитель, поэтому из равенств = a
1
(a
1
+ b
1
) + b
2 1
= b
1
(a
1
+ b
1
) + a
2 следует, что m взаимно просто с числами a
1
, и a
1
+ b
1
, поэтому d делится на m. Но тогда d m > следовательно d
3
> ab
. Поэтому |a − b| d >
3
√
ab
, что и требовалось доказать. Построим граф, вершины которого соответствуют городам, а ребра дорогам. В задаче требуется покраситьвершины этого графа в цветов так, что никакие две вершины одного цвета не соединены ребром
(такая раскраска называется правильной).
Рассмотрим вершину A наибольшей степени, пусть из этой вершины выходит s ребер (s < 2000). Обозначим через V множество из s вершин,
соединенных с A, пусть W — множество из 2000 − s оставшихся вершин.
Рассмотрим два случая) Пустьв множестве W естьдве соединенные ребром вершины B и Тогда рассмотрим множество U, состоящее из вершины A и всех вершин множества W , кроме C. В этом множестве 2000 − s вершин и любая не входящая в U вершина соединена ребром с одной из вершин множества либо с вершиной A, либо с B). Следовательно, 2000 − s Остается заметить, что из каждой вершины выходит не более s ребер,
следовательно, эти вершины можно по очереди покрасить в s + 1 цвет так, чтобы никакие две вершины одного цвета небыли соединены ребром
(вершину нельзя красить в цвета ее соседей, которых не более, чем s, а в нашем распоряжении s + 1 цвет. Неравенство s + 1 = 2001 − (2000 −
− s) 2001 − k завершает доказательство задачи в этом случае
в точке имеет вид y = −ax + b
2
, a > 0. Эти касательные пересекаются в точке с ординатой y
0
> 0
. Парабола, ветви которой направлены вверх,
лежит выше касательной. Поэтому αf(x) + βg(x) > ax + b
1
− ax + b
2
=
= b
1
+ b
2
= 2y
0
> 0
, что и требовалосьдоказать.
Второе решение. Пустьграфики пересекаются в точке P (x
0
, Тогда f(x) = y
0
+ (x
− x
)(x
− x
0
)
, g(x) = y
0
+ (x
− x
)(x
− x
0
)
, причем,
если x
0
< x
0
, то x
0
< x
. Действительно, если, скажем, x
< x
< тона интервале (x
, выполнено f(x) < g(x), ив точках, в которых
g(x)
отрицательно, f(x) также отрицательно, что невозможно. Поэтому) = αf (x) + βg(x) = (α + β)y
0
+ (x
− x
0
)[(α + β)x
− (αx
+ βx
)] =
= (α + β)y
0
+ (α + β)(x
− x
0
)
2
(α + β)y
0
> 0
, если выбрать α и β так,
чтобы (α + β)x
0
= αx
+ βx
, те. Это можно сделать, так как x
< x
0
< x
638. Пусть d — наибольший общий делитель чисел a и b, те, где и взаимно просты. Тогда da
1
b
1
(a
1
+ делится на 1
+ a
1
b
1
+ b
2 1
= m
. Число a
1
+ взаимно просто с числами ив противном случае и имеют общий делитель, поэтому из равенств = a
1
(a
1
+ b
1
) + b
2 1
= b
1
(a
1
+ b
1
) + a
2 следует, что m взаимно просто с числами a
1
, и a
1
+ b
1
, поэтому d делится на m. Но тогда d m > следовательно d
3
> ab
. Поэтому |a − b| d >
3
√
ab
, что и требовалось доказать. Построим граф, вершины которого соответствуют городам, а ребра дорогам. В задаче требуется покраситьвершины этого графа в цветов так, что никакие две вершины одного цвета не соединены ребром
(такая раскраска называется правильной).
Рассмотрим вершину A наибольшей степени, пусть из этой вершины выходит s ребер (s < 2000). Обозначим через V множество из s вершин,
соединенных с A, пусть W — множество из 2000 − s оставшихся вершин.
Рассмотрим два случая) Пустьв множестве W естьдве соединенные ребром вершины B и Тогда рассмотрим множество U, состоящее из вершины A и всех вершин множества W , кроме C. В этом множестве 2000 − s вершин и любая не входящая в U вершина соединена ребром с одной из вершин множества либо с вершиной A, либо с B). Следовательно, 2000 − s Остается заметить, что из каждой вершины выходит не более s ребер,
следовательно, эти вершины можно по очереди покрасить в s + 1 цвет так, чтобы никакие две вершины одного цвета небыли соединены ребром
(вершину нельзя красить в цвета ее соседей, которых не более, чем s, а в нашем распоряжении s + 1 цвет. Неравенство s + 1 = 2001 − (2000 −
− s) 2001 − k завершает доказательство задачи в этом случае
УЧЕБНЫЙ ГОД, КЛАСС 2) Пустьникакие две вершины множества W не соединены ребром.
Покрасим все эти вершины в цвет 1, в этот же цвет можно покраситьвер- шину A она не соединена ребром ни с одной вершиной из W ). Заметим,
что в этом случае вершины из множества W должны бытьсоединены с вершинами из множества V так как из каждой вершины выходит хотя бы одно ребро. Это означает, что среди вершин множества V естьдве не соединенные ребром (иначе в этом множестве естьвершина, из которой выходит более s ребер — к s − 1 остальным вершинам множества V , к вершине A и к вершинам множества W ). Так как среди s вершин множества естьдве не соединенные ребром, вершины этого множества можно покраситьв s−1 цвет. Таким образом, все вершины оказалисьраскраше- ны в s цветов и никакие две вершины не соединены ребром. Так как все вершин из множества V соединены ребром с вершиной A, то 2001−s следовательно, s = 2001 − (2001 − s) 2001 − k, что и требовалосьдо- казать.
S
A
B
C
O
1
A
1
B
1
C
1
γ
ω
Рис. 286
640. Пусть ω — сфера из условия задачи сфера, описанная около тетраэдра. Эти сферы пересекаются по окружности, описанной около треугольника
A
1
B
1
C
1
(см. рис. Выберем на γ произвольно точку пусть K — вторая точка пересечения луча
SK
1
со сферой ω. Рассмотрим сечение сфер
ω
и плоскостью α = Пусть l — касательная к сечению сферы плоскостью α, проведенная в точке см. рис. 287). Тогда ∠1 = ∠2 и ∠2 = π − ∠A
1
K
1
K =
∠3, следовательно = ∠3 и, значит, AK l. Поэтому если β — плоскость, касающаяся в точке S, то AK β. Поэтому лучи, проведенные из точки S и пересекающие окружность γ, вторично пересекают сферу ω в точках, лежащих водной плоскости τ. Точки A, B и C лежат в этой плоскости, следовательно проходит через точку O
1
— центр сферы ω.
Теперьрассмотрим множество плоскостей, касающихся ω в точках,
принадлежащих γ. Они касаются некоторого конуса с вершиной в точке и образующими OA
1
, OB
1
, OC
1
). Проведем плоскостьчерез точки, и S. В сечении получатся две пересекающиеся окружности (см.
рис. 288), при этом =
∠SQ
1
Q = так как O
1
∈ P Q. Но и OQ
1
— касательные к окружности с центром, поэтому
Покрасим все эти вершины в цвет 1, в этот же цвет можно покраситьвер- шину A она не соединена ребром ни с одной вершиной из W ). Заметим,
что в этом случае вершины из множества W должны бытьсоединены с вершинами из множества V так как из каждой вершины выходит хотя бы одно ребро. Это означает, что среди вершин множества V естьдве не соединенные ребром (иначе в этом множестве естьвершина, из которой выходит более s ребер — к s − 1 остальным вершинам множества V , к вершине A и к вершинам множества W ). Так как среди s вершин множества естьдве не соединенные ребром, вершины этого множества можно покраситьв s−1 цвет. Таким образом, все вершины оказалисьраскраше- ны в s цветов и никакие две вершины не соединены ребром. Так как все вершин из множества V соединены ребром с вершиной A, то 2001−s следовательно, s = 2001 − (2001 − s) 2001 − k, что и требовалосьдо- казать.
S
A
B
C
O
1
A
1
B
1
C
1
γ
ω
Рис. 286
640. Пусть ω — сфера из условия задачи сфера, описанная около тетраэдра. Эти сферы пересекаются по окружности, описанной около треугольника
A
1
B
1
C
1
(см. рис. Выберем на γ произвольно точку пусть K — вторая точка пересечения луча
SK
1
со сферой ω. Рассмотрим сечение сфер
ω
и плоскостью α = Пусть l — касательная к сечению сферы плоскостью α, проведенная в точке см. рис. 287). Тогда ∠1 = ∠2 и ∠2 = π − ∠A
1
K
1
K =
∠3, следовательно = ∠3 и, значит, AK l. Поэтому если β — плоскость, касающаяся в точке S, то AK β. Поэтому лучи, проведенные из точки S и пересекающие окружность γ, вторично пересекают сферу ω в точках, лежащих водной плоскости τ. Точки A, B и C лежат в этой плоскости, следовательно проходит через точку O
1
— центр сферы ω.
Теперьрассмотрим множество плоскостей, касающихся ω в точках,
принадлежащих γ. Они касаются некоторого конуса с вершиной в точке и образующими OA
1
, OB
1
, OC
1
). Проведем плоскостьчерез точки, и S. В сечении получатся две пересекающиеся окружности (см.
рис. 288), при этом =
∠SQ
1
Q = так как O
1
∈ P Q. Но и OQ
1
— касательные к окружности с центром, поэтому
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Рис. Рис. 288
∠SP те равнобедренный и ∠Q
1
OP
1
= 180
◦
− 2 · ∠OQ
1
P
1
=
= 2(90
◦
− ∠SP P
1
) = 2
· ∠Q
1
SP
1
. Отсюда и из равенства OP
1
= следует, что O — центр окружности, описанной около SP
1
Q
1
. Но тогда = OP
1
= OA
1
= OB
1
= OC
1
, те центр сферы ω
1
∠SP те равнобедренный и ∠Q
1
OP
1
= 180
◦
− 2 · ∠OQ
1
P
1
=
= 2(90
◦
− ∠SP P
1
) = 2
· ∠Q
1
SP
1
. Отсюда и из равенства OP
1
= следует, что O — центр окружности, описанной около SP
1
Q
1
. Но тогда = OP
1
= OA
1
= OB
1
= OC
1
, те центр сферы ω
1
1 ... 48 49 50 51 52 53 54 55 ... 64
2001–2002 г класс. Ответ. Нельзя.
Числа от 1 до 2001 могут располагаться не более, чем в 2001 строке и столбце. Значит, найдутся строка и столбец, все числа в которых не меньше 2002. Но тогда произведение любых двух чисел из такой строки
(столбца) больше 2002 2
, те. для клетки, расположенной на пересечении таких строки и столбца, условие задачи не выполняется.
A
B
C
O
O
1
O
2
M
Рис. 289
642. ∠AO
1
O
2
— внешний для треугольника Поэтому 2
∠AOB +
1 2
∠OAB = 90
◦
−
−
1 2
∠OBA =
1 Далее, пусть M — некоторая точка на продолжении отрезка OA заточку внешний для треугольника Отсюда ∠AO
2
O
1
=
∠MAO
2
−
− ∠AOO
2
=
1 2
∠MAC −
1 2
∠AOC =
=
1 2
∠ACO.
УЧЕБНЫЙ ГОД, 9
КЛАСС
383
Таким образом, из равенства O
1
A = следует равенство углов
AO
1
O
2
и AO
2
O
1
, а значит, и углов ABC и Тем самым, треугольник ABC — равнобедренный, AB = AC.
643. Рассмотрим три синих точки A, B, C и не синюю D. Тогда S
ABD
+ S
ACD
+ S
BCD
. Просуммируем это неравенство по всем таким четверкам. При этом каждый
синий
треугольник считается раза каждый
сине-сине-несиний
— 4 раза. Таким образом, сумма площадей
синих
треугольников хотя бы в 3 раза меньше суммы площадей. Итого сумма площадей
синих
треугольни- ков составляет не более четверти сумм площадей треугольников, хотя бы две вершины которых — синие. Аналогичное неравенство получим для двух других цветов. Так как рассмотренные группы не пересекаются, то и сумма площадей одноцветных треугольников составляет не более четверти суммы площадей всех треугольников. Ответ. Перейдем к графу, в котором головы — вершины, шеи — ребра, а удар по шеям, выходящим из головы A назовем инвертированием вершины. Тогда если естьвершина X степени не больше 10, то достаточно инвер- тироватьее соседей, иона отделится, те. эта вершина не будет соединена с остальными вершинами графа. Если естьвершина, соединенная со всеми вершинами, за исключением n (n 9), то нужно инвертироватьсна- чала эту вершину, а затем те n вершин, с которыми она вначале не была соединена, и тогда эта вершина отделится. Если же для каждой вершины естьхотя бы 11 вершин, соединенных с ней, и хотя бы 10, не соединенных с ней, то всего вершин не меньше 22, и ребер не меньше · 11 2
> Приведем пример гидры, которую нельзя разрубить за 9 ударов две группы по 10 голов и 100 шей, соединяющих все пары голов из разных групп. Заметим, что
состояние ребра
между вершинами A и B не изменилось (те. оно осталось, если было вначале, и не появилось, — иначе)
тогда и только тогда, когда вершины A и B отрубали в сумме четное число раз. Поэтому порядок отрубания вершин неважен, и бессмысленно отру- батьвершину два раза.
Пустьпо нашей гидре нанесено не более 9 ударов. Тогда в каждой группе осталосьпо неотрубленной голове, и поэтому естьшея из одной группы в другую более того, все неотрубленные головы образуют связное множество. С другой стороны, каждая неотрубленная голова связана со всеми отрубленными в своей группе. Поэтому, если в каждой части отрублено хотя бы по голове, то гидра осталасьсвязной. Если же все отрубленные головы водной части, то гидра тоже осталасьсвязной: любая
КЛАСС
383
Таким образом, из равенства O
1
A = следует равенство углов
AO
1
O
2
и AO
2
O
1
, а значит, и углов ABC и Тем самым, треугольник ABC — равнобедренный, AB = AC.
643. Рассмотрим три синих точки A, B, C и не синюю D. Тогда S
ABD
+ S
ACD
+ S
BCD
. Просуммируем это неравенство по всем таким четверкам. При этом каждый
синий
треугольник считается раза каждый
сине-сине-несиний
— 4 раза. Таким образом, сумма площадей
синих
треугольников хотя бы в 3 раза меньше суммы площадей. Итого сумма площадей
синих
треугольни- ков составляет не более четверти сумм площадей треугольников, хотя бы две вершины которых — синие. Аналогичное неравенство получим для двух других цветов. Так как рассмотренные группы не пересекаются, то и сумма площадей одноцветных треугольников составляет не более четверти суммы площадей всех треугольников. Ответ. Перейдем к графу, в котором головы — вершины, шеи — ребра, а удар по шеям, выходящим из головы A назовем инвертированием вершины. Тогда если естьвершина X степени не больше 10, то достаточно инвер- тироватьее соседей, иона отделится, те. эта вершина не будет соединена с остальными вершинами графа. Если естьвершина, соединенная со всеми вершинами, за исключением n (n 9), то нужно инвертироватьсна- чала эту вершину, а затем те n вершин, с которыми она вначале не была соединена, и тогда эта вершина отделится. Если же для каждой вершины естьхотя бы 11 вершин, соединенных с ней, и хотя бы 10, не соединенных с ней, то всего вершин не меньше 22, и ребер не меньше · 11 2
> Приведем пример гидры, которую нельзя разрубить за 9 ударов две группы по 10 голов и 100 шей, соединяющих все пары голов из разных групп. Заметим, что
состояние ребра
между вершинами A и B не изменилось (те. оно осталось, если было вначале, и не появилось, — иначе)
тогда и только тогда, когда вершины A и B отрубали в сумме четное число раз. Поэтому порядок отрубания вершин неважен, и бессмысленно отру- батьвершину два раза.
Пустьпо нашей гидре нанесено не более 9 ударов. Тогда в каждой группе осталосьпо неотрубленной голове, и поэтому естьшея из одной группы в другую более того, все неотрубленные головы образуют связное множество. С другой стороны, каждая неотрубленная голова связана со всеми отрубленными в своей группе. Поэтому, если в каждой части отрублено хотя бы по голове, то гидра осталасьсвязной. Если же все отрубленные головы водной части, то гидра тоже осталасьсвязной: любая
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
неотрубленная голова в этой части связана со всей другой частью и со всеми отрубленными. Рассмотрим семьпар ладей, стоящих в соседних столбцах. Разности их координат по вертикали лежат на отрезке [1, 7], поэтому либо две из них совпадают (и тогда расстояния в соответствующих парах тоже совпадают, либо среди них естьвсе числа от 1 до 7. В частности, естьдве ладьи, отстоящие друг от друга на 2 по вертикали и на 1 по горизонтали
(пара A). Аналогично, либо найдутся две пары в соседних строках с равным расстоянием, либо естьдве ладьи, отстоящие друг от друга на 1 по вертикали и на 2 по горизонтали (пара B). Тогда расстояния в парах A и
B
совпадают, асами эти пары различны. Ответ. n = k − Построим пример, показывающий, что при n k это невозможно.
Пустькарты (сверху вниз) первоначально лежат так сначала все нечетные (в произвольном порядке, потом четные, причем верхняя из них карта 2n. Тогда первые k ходов однозначно определены — нечетные карты перекладываются на свободные позиции следующий ход, если n > невозможен, а если n = k, то можно лишьпереложитькарту 2n−1 обратно в изначальную стопку, что бессмысленно, ибо мы вернулись к предыдущей позиции. Поэтому эту стопку переложитьнельзя.
Пусть n < k. Покажем, как можно организоватьпроцесс перекладывания. Разобьем все карты на пары (1, 2), . . . , (2n − 1, 2n) и сопоставим каждой паре по незанятой ячейке (хотя бы одна ячейка не сопоставлена никакой паре назовем ее свободной. Теперькаждую карту сверху красной ячейки попытаемся положитьв
ее
ячейку. Это может не получиться, только если эта карта имеет номера карта 2i − 1 уже лежит в ячейке но тогда можно переместитькарту 2i в свободную ячейку, сверху положитькарту 2i − 1, сопоставитьэтой ячейке нашу пару, а прежнюю сопоставленную назватьсвободной. Таким образом, в результате мы получим карты, разложенные в ячейки по парам. Теперь, используя свободную ячейку, легко собратьих в колоду в правильном порядке. Построим такие точки K и L, лежащие внутри угла AOC, что треугольники и BMO, а также CLO и BNO соответственно равны (см.
рис. 290). Тогда KO = OM, LO = ON и ∠KOL = ∠AOC − ∠MOB −
− ∠BON = ∠MON, поэтому треугольники KOL и MON равны, следовательно. Тогда периметр треугольника BMN равен BM +
+ M N + N B = AK + KL + LC
В других исходных конфигурациях задачи решение проходит аналогично, но треугольники, возможно, нужно откладывать в другую сторону
(см. рис. 291, рис. 292, рис. 293).
неотрубленная голова в этой части связана со всей другой частью и со всеми отрубленными. Рассмотрим семьпар ладей, стоящих в соседних столбцах. Разности их координат по вертикали лежат на отрезке [1, 7], поэтому либо две из них совпадают (и тогда расстояния в соответствующих парах тоже совпадают, либо среди них естьвсе числа от 1 до 7. В частности, естьдве ладьи, отстоящие друг от друга на 2 по вертикали и на 1 по горизонтали
(пара A). Аналогично, либо найдутся две пары в соседних строках с равным расстоянием, либо естьдве ладьи, отстоящие друг от друга на 1 по вертикали и на 2 по горизонтали (пара B). Тогда расстояния в парах A и
B
совпадают, асами эти пары различны. Ответ. n = k − Построим пример, показывающий, что при n k это невозможно.
Пустькарты (сверху вниз) первоначально лежат так сначала все нечетные (в произвольном порядке, потом четные, причем верхняя из них карта 2n. Тогда первые k ходов однозначно определены — нечетные карты перекладываются на свободные позиции следующий ход, если n > невозможен, а если n = k, то можно лишьпереложитькарту 2n−1 обратно в изначальную стопку, что бессмысленно, ибо мы вернулись к предыдущей позиции. Поэтому эту стопку переложитьнельзя.
Пусть n < k. Покажем, как можно организоватьпроцесс перекладывания. Разобьем все карты на пары (1, 2), . . . , (2n − 1, 2n) и сопоставим каждой паре по незанятой ячейке (хотя бы одна ячейка не сопоставлена никакой паре назовем ее свободной. Теперькаждую карту сверху красной ячейки попытаемся положитьв
ее
ячейку. Это может не получиться, только если эта карта имеет номера карта 2i − 1 уже лежит в ячейке но тогда можно переместитькарту 2i в свободную ячейку, сверху положитькарту 2i − 1, сопоставитьэтой ячейке нашу пару, а прежнюю сопоставленную назватьсвободной. Таким образом, в результате мы получим карты, разложенные в ячейки по парам. Теперь, используя свободную ячейку, легко собратьих в колоду в правильном порядке. Построим такие точки K и L, лежащие внутри угла AOC, что треугольники и BMO, а также CLO и BNO соответственно равны (см.
рис. 290). Тогда KO = OM, LO = ON и ∠KOL = ∠AOC − ∠MOB −
− ∠BON = ∠MON, поэтому треугольники KOL и MON равны, следовательно. Тогда периметр треугольника BMN равен BM +
+ M N + N B = AK + KL + LC
В других исходных конфигурациях задачи решение проходит аналогично, но треугольники, возможно, нужно откладывать в другую сторону
(см. рис. 291, рис. 292, рис. 293).
УЧЕБНЫЙ ГОД, КЛАСС Рис. Рис. Рис. Рис. 293
648. Заметим, что среди выбранных чисел найдутся числа a и b, имеющие одинаковые остатки отделения на 2 2n
. Докажем, что они — искомые.
Предположим, что a
2
... b. Тогда и (a − b)
2
= a
2
− 2ab + b
2
... b. Пусть = p
· 2 2n
+ r
, b = q · 2 2n
+ r
. Тогда (p − q)
2
· 2 4n
... b, но поскольку нечетное, то (p − q)
2
...b, откуда |p−q| > и max(a, b) = max(p, q) · 2 2n
+
+ r > 2 3n
, что невозможно по условию класс. Из условия следует, что R и один из многочленов P и Q — третьей степени. Пусть, например, R и Q — третьей степени, P — второй. Поменяв, если это нужно, знаки многочленов на противоположные, можно считать, что коэффициенты при у R и Q положительны. Тогда из равенства, где R + Q — третьей степени,
следует, что R − Q — первой степени, те (коэффициент при у P
2
положителен).
Тогда P ... x − x
1
, поэтому и R + Q ... x − x
1
, итак как R − Q ... x − тот. е. R = (x − x
1
)R
1
, Q = (x − x
1
)Q
1
, где и Q
1
— квадратичные функции с положительными коэффициентами при. Пусть P = a(x − x
1
)(x
− x
2
)
. Из равенства x
2
)
2
= (R
1
+ Q
1
)(R
1
− Q
1
)
648. Заметим, что среди выбранных чисел найдутся числа a и b, имеющие одинаковые остатки отделения на 2 2n
. Докажем, что они — искомые.
Предположим, что a
2
... b. Тогда и (a − b)
2
= a
2
− 2ab + b
2
... b. Пусть = p
· 2 2n
+ r
, b = q · 2 2n
+ r
. Тогда (p − q)
2
· 2 4n
... b, но поскольку нечетное, то (p − q)
2
...b, откуда |p−q| > и max(a, b) = max(p, q) · 2 2n
+
+ r > 2 3n
, что невозможно по условию класс. Из условия следует, что R и один из многочленов P и Q — третьей степени. Пусть, например, R и Q — третьей степени, P — второй. Поменяв, если это нужно, знаки многочленов на противоположные, можно считать, что коэффициенты при у R и Q положительны. Тогда из равенства, где R + Q — третьей степени,
следует, что R − Q — первой степени, те (коэффициент при у P
2
положителен).
Тогда P ... x − x
1
, поэтому и R + Q ... x − x
1
, итак как R − Q ... x − тот. е. R = (x − x
1
)R
1
, Q = (x − x
1
)Q
1
, где и Q
1
— квадратичные функции с положительными коэффициентами при. Пусть P = a(x − x
1
)(x
− x
2
)
. Из равенства x
2
)
2
= (R
1
+ Q
1
)(R
1
− Q
1
)
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
следует, что R
1
− Q
1
= t = const > 0
. Значит, R
1
= Q
1
+ t
, поэтому x
2
)
2
= (2Q
1
+ t)
· те трехчлен, имеющий два действительных корня. Тогда Q имеет три действительных корня.
A
B
C
D
M
K
Рис. 294
650. Запишем MB
2
= M A
· MD =
=
1 2
M D
2
, KA
2
= KB
· KC =
1 Отсюда, используя теорему синусов,
получаем:
1
√
2
=
AK
KC
=
sin ∠ACK
sin ∠CAK
,
1
√
2
=
=
BM
MD
=
sin ∠BDM
sin ∠DBM
. Но sin ∠ACK =
= sin
∠BDM, поскольку ABCD — вписанный четырехугольник. Следовательно = sin ∠DBM. Это означает, что имеются следующие две возможности) ∠CAK = ∠DBM. В этом случае треугольники CAK и BDM подобны по двум углам. Кроме того, AB является общей медианой к соответственным сторонам этих треугольников. Значит, треугольники CAK и
DBM
подобны с коэффициентом подобия 1, те. эти треугольники равны.
Следовательно, AD = MD/2 = KC/2 = BC. Таким образом, ABCD вписанная трапеция, AB CD.
2) ∠CAK + ∠DBM = 180
◦
. По теореме об угле между касательной и хордой ∠CAK = ∠CDA, ∠DBM = ∠DCB. Значит, ∠CDA + ∠DCB =
= 180
◦
, откуда следует, что AD BC.
651. Пусть x — наибольшее целое число, квадрат которого не превосходит. Так как n — целое, n−x
2
2x 2
√
n
. Пусть,
далее, y — наименьшее натуральное число, квадрат которого больше n −
−x
2
: (y−1)
2
n−x
2
< y
2
. Тогда y = (y−1)+1
√
n
− x
2
+1
2
√
n+
+ 1 =
√
2 4
√
n + 1
. Ясно, что m = x
2
+ y
2
> n
, те представимо в виде суммы двух квадратов и m − n > С другой стороны n = x
2
+ y
2
− n = y
2
− (n − x
2
)
y
2
− (y − 1)
2
=
= 2y
− 1 2
√
2 4
√
n + 1.
Осталосьзаметить, что при n > 10 000 2
√
2 4
√
n + 1 < 3 4
√
n.
652. Построим граф, вершины которого соответствуют городам, а ребра дорогам, существовавшим в стране до начала всех преобразований.
По условию, над этим графом несколько раз подряд проделывается следующая операция удаляются все ребра некоторого простого цикла, а все вершины этого цикла соединяются с новой вершиной. Докажем, что в гра-
следует, что R
1
− Q
1
= t = const > 0
. Значит, R
1
= Q
1
+ t
, поэтому x
2
)
2
= (2Q
1
+ t)
· те трехчлен, имеющий два действительных корня. Тогда Q имеет три действительных корня.
A
B
C
D
M
K
Рис. 294
650. Запишем MB
2
= M A
· MD =
=
1 2
M D
2
, KA
2
= KB
· KC =
1 Отсюда, используя теорему синусов,
получаем:
1
√
2
=
AK
KC
=
sin ∠ACK
sin ∠CAK
,
1
√
2
=
=
BM
MD
=
sin ∠BDM
sin ∠DBM
. Но sin ∠ACK =
= sin
∠BDM, поскольку ABCD — вписанный четырехугольник. Следовательно = sin ∠DBM. Это означает, что имеются следующие две возможности) ∠CAK = ∠DBM. В этом случае треугольники CAK и BDM подобны по двум углам. Кроме того, AB является общей медианой к соответственным сторонам этих треугольников. Значит, треугольники CAK и
DBM
подобны с коэффициентом подобия 1, те. эти треугольники равны.
Следовательно, AD = MD/2 = KC/2 = BC. Таким образом, ABCD вписанная трапеция, AB CD.
2) ∠CAK + ∠DBM = 180
◦
. По теореме об угле между касательной и хордой ∠CAK = ∠CDA, ∠DBM = ∠DCB. Значит, ∠CDA + ∠DCB =
= 180
◦
, откуда следует, что AD BC.
651. Пусть x — наибольшее целое число, квадрат которого не превосходит. Так как n — целое, n−x
2
2x 2
√
n
. Пусть,
далее, y — наименьшее натуральное число, квадрат которого больше n −
−x
2
: (y−1)
2
n−x
2
< y
2
. Тогда y = (y−1)+1
√
n
− x
2
+1
2
√
n+
+ 1 =
√
2 4
√
n + 1
. Ясно, что m = x
2
+ y
2
> n
, те представимо в виде суммы двух квадратов и m − n > С другой стороны n = x
2
+ y
2
− n = y
2
− (n − x
2
)
y
2
− (y − 1)
2
=
= 2y
− 1 2
√
2 4
√
n + 1.
Осталосьзаметить, что при n > 10 000 2
√
2 4
√
n + 1 < 3 4
√
n.
652. Построим граф, вершины которого соответствуют городам, а ребра дорогам, существовавшим в стране до начала всех преобразований.
По условию, над этим графом несколько раз подряд проделывается следующая операция удаляются все ребра некоторого простого цикла, а все вершины этого цикла соединяются с новой вершиной. Докажем, что в гра-
УЧЕБНЫЙ ГОД, 10
КЛАСС
387
фе, получившемся после окончания всех преобразований, все вершины исходного графа будут иметьстепень1. Поскольку таких вершин ровно, это даст нам полное решение задачи.
Рассмотрим произвольную вершину v, принадлежащую исходному графу. По условию, при удалении этой вершины (и всех выходящих из нее ребер) из исходного графа образуется связный граф. Докажем, что это свойство сохраняется после применения к графу описанной в условии операции.
Рассмотрим произвольный граф G и вершину u этого графа, при удалении которой образуется связный граф. Пустьпосле применения к графу описанной в условии операции образовался граф G
. Рассмотрим произвольный путь в графе G, не проходящий через u. В графе некоторые ребра этого пути могут бытьудалены, но их концы должны быть соединены с новой вершиной (обозначим ее w). Таким образом, заменив минимальный участок пути, содержащий все удаленные ребра, на пару ребер, соединяющих концы этого участка с вершиной w, мы получим путьв графе G
, имеющий те же концы и не проходящий через u. Это означает,
что если мы удалим из графа вершину u, то для любых двух вершин получившегося графа мы можем найти соединяющий их путь. Для старых
(отличных от w) вершин этот путьполучается описанным выше способом из пути, соединяющего их в графе, образовавшемся при удалении u из графа, а вершина w должна бытьсоединена ребром хотя бы с одной из старых вершин, которая соединена путями со всеми остальными вершинами данного графа. Таким образом, при удалении вершины u из графа также образуется связный граф.
Из доказанного следует, что после всех преобразований при удалении из получившегося графа вершины v образуется связный граф. Тогда, если степеньвершины v в получившемся графе больше 1, то между двумя соединенными с v вершинами естьне проходящий через v путь. Этот путь вместе с вершиной v и двумя выходящими из нее ребрами образует в получившемся графе простой цикл, что по условию невозможно. Таким образом, степеньвершины v в этом графе равна 1.
653. Рассмотрим равенство (a + b + c)
2
= 9
. Тогда + bc + ca =
9
− a
2
− b
2
− c
2 Следовательно, нужно доказать, что + 2
√
b + 2
√
c + a
2
+ b
2
+ c
2
Для этого заметим, что 2
√
a + a
2
3a. Действительно, согласно неравенству между средним арифметическими средним геометрическим, 2
√
a +
КЛАСС
387
фе, получившемся после окончания всех преобразований, все вершины исходного графа будут иметьстепень1. Поскольку таких вершин ровно, это даст нам полное решение задачи.
Рассмотрим произвольную вершину v, принадлежащую исходному графу. По условию, при удалении этой вершины (и всех выходящих из нее ребер) из исходного графа образуется связный граф. Докажем, что это свойство сохраняется после применения к графу описанной в условии операции.
Рассмотрим произвольный граф G и вершину u этого графа, при удалении которой образуется связный граф. Пустьпосле применения к графу описанной в условии операции образовался граф G
. Рассмотрим произвольный путь в графе G, не проходящий через u. В графе некоторые ребра этого пути могут бытьудалены, но их концы должны быть соединены с новой вершиной (обозначим ее w). Таким образом, заменив минимальный участок пути, содержащий все удаленные ребра, на пару ребер, соединяющих концы этого участка с вершиной w, мы получим путьв графе G
, имеющий те же концы и не проходящий через u. Это означает,
что если мы удалим из графа вершину u, то для любых двух вершин получившегося графа мы можем найти соединяющий их путь. Для старых
(отличных от w) вершин этот путьполучается описанным выше способом из пути, соединяющего их в графе, образовавшемся при удалении u из графа, а вершина w должна бытьсоединена ребром хотя бы с одной из старых вершин, которая соединена путями со всеми остальными вершинами данного графа. Таким образом, при удалении вершины u из графа также образуется связный граф.
Из доказанного следует, что после всех преобразований при удалении из получившегося графа вершины v образуется связный граф. Тогда, если степеньвершины v в получившемся графе больше 1, то между двумя соединенными с v вершинами естьне проходящий через v путь. Этот путь вместе с вершиной v и двумя выходящими из нее ребрами образует в получившемся графе простой цикл, что по условию невозможно. Таким образом, степеньвершины v в этом графе равна 1.
653. Рассмотрим равенство (a + b + c)
2
= 9
. Тогда + bc + ca =
9
− a
2
− b
2
− c
2 Следовательно, нужно доказать, что + 2
√
b + 2
√
c + a
2
+ b
2
+ c
2
Для этого заметим, что 2
√
a + a
2
3a. Действительно, согласно неравенству между средним арифметическими средним геометрическим, 2
√
a +
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ+ a
2
=
√
a +
√
a + a
2
3 3
√
a
3
= 3a
. Тогда 2
√
a + 2
√
b + 2
√
a + a
2
+ b
2
+
+ c
2
3(a + b + c) = 9.
654. См. решение задачи 646.
655. Пусть A
1
, и C
1
— точки касания вписанной окружности с соответствующими сторонами ABC см. рис. 295). Проведем через прямую a
1
, параллельную биссектрисе угла A. Так как равнобедренный, то биссектриса угла A перпендикулярна B
1
C
1
, поэтому проведенная через прямая, будучи перпендикулярной B
1
C
1
, является высотой Рис. Рис. Пусть A
0
, и C
0
— середины соответствующих сторон ABC (см.
рис. 296). Так как ABC и A
0
B
0
C
0
гомотетичны с коэффициентом −
1 то биссектрисы углов A и параллельны. Обозначим точку пересечения биссектрис через Как известно, точки и равноудалены от середины своей стороны
(то же верно для точек и B
, и Рассмотрим симметрию относительно точки S. При этой симметрии прямая a
1
, перейдет впрямую. Таким образом, при этой симметрии каждая из высот перейдет в одну из прямых a, b и c, следовательно,
эти прямые пересекутся в точке, симметричной ортоцентру относительно центра S окружности, вписанной в серединный треугольник. Предположим противное. Заметим, что через любую точку пересечения двух прямых проходит красная прямая. Рассмотрим синюю прямую пусть A, B — две наиболее удаленные друг от друга точки пересечения
l
с красными прямыми, m и n — красные прямые, проходящие через A и C — точка пересечения m и n. Тогда через C проходит синяя прямая, которая пересекает l в какой-то точке D отрезка AB, иначе A и B — не наиболее удаленные (см. рис. Рассмотрим все четверки прямых l
, m
, n
, p
, расположенных как l,
m
, n, p (l
, p
— одного цвета m
, n
— другого m
, n
, пересекаются водной точке точка пересечения и лежит между точками пересечения сии рассмотрим среди них такую, в которой прямые l
, m
, n
обра-
2
=
√
a +
√
a + a
2
3 3
√
a
3
= 3a
. Тогда 2
√
a + 2
√
b + 2
√
a + a
2
+ b
2
+
+ c
2
3(a + b + c) = 9.
654. См. решение задачи 646.
655. Пусть A
1
, и C
1
— точки касания вписанной окружности с соответствующими сторонами ABC см. рис. 295). Проведем через прямую a
1
, параллельную биссектрисе угла A. Так как равнобедренный, то биссектриса угла A перпендикулярна B
1
C
1
, поэтому проведенная через прямая, будучи перпендикулярной B
1
C
1
, является высотой Рис. Рис. Пусть A
0
, и C
0
— середины соответствующих сторон ABC (см.
рис. 296). Так как ABC и A
0
B
0
C
0
гомотетичны с коэффициентом −
1 то биссектрисы углов A и параллельны. Обозначим точку пересечения биссектрис через Как известно, точки и равноудалены от середины своей стороны
(то же верно для точек и B
, и Рассмотрим симметрию относительно точки S. При этой симметрии прямая a
1
, перейдет впрямую. Таким образом, при этой симметрии каждая из высот перейдет в одну из прямых a, b и c, следовательно,
эти прямые пересекутся в точке, симметричной ортоцентру относительно центра S окружности, вписанной в серединный треугольник. Предположим противное. Заметим, что через любую точку пересечения двух прямых проходит красная прямая. Рассмотрим синюю прямую пусть A, B — две наиболее удаленные друг от друга точки пересечения
l
с красными прямыми, m и n — красные прямые, проходящие через A и C — точка пересечения m и n. Тогда через C проходит синяя прямая, которая пересекает l в какой-то точке D отрезка AB, иначе A и B — не наиболее удаленные (см. рис. Рассмотрим все четверки прямых l
, m
, n
, p
, расположенных как l,
m
, n, p (l
, p
— одного цвета m
, n
— другого m
, n
, пересекаются водной точке точка пересечения и лежит между точками пересечения сии рассмотрим среди них такую, в которой прямые l
, m
, n
обра-
УЧЕБНЫЙ ГОД, 11
КЛАСС
389
A
B
C
D
l
p
n
m
A
B
C
D
l
q
p
m
n
Рис. Рис. 298
зуют треугольник наименьшей площади (см. рис. 298). Тогда через точку
D
проходит прямая q
, одноцветная с m
. Она пересекает либо отрезок, либо пусть, для определенности, B
C
). Тогда прямые n
, l
,
p
, образуют конфигурацию с треугольником меньшей площади. Про- тиворечие.
Замечание. Найти хотя бы одну пару прямых l, m, n, p можно бы было и по-другому: взятькакую-нибудьчетверку прямых l, m, n, p нужных цветов (так, чтобы m, n, p пересекалисьв одной точке) и проективным преобразованием добиться того, чтобы точка D пересечения p и l лежала между A и B.
11 класс. См. решение задачи 649.
658. Первое решение. Рассмотрим любые 3 точки A, B и C, не лежащие на одной прямой (если все точки будут лежатьна одной прямой, то утверждение задачи очевидно. Пусть T
1
— система координат, в которой эти точки имеют целые координаты. Рассмотрим любую из оставшихся точек, назовем ее D. Пусть T
2
— система координат, в которой точки B,
C
, D имеют целые координаты. Поскольку квадрат длины отрезка BC в
T
1
и будет целым, то отношение квадратов единиц измерения и T
2
— рациональное число. Но скалярное произведение векторов (в T
2
— целое, значит, в оно рационально, поскольку произведение длин этих векторов в будет рационально относиться к произведению их длин в T
2
, а косинус угла не изменится. Аналогично, (
−−→
BA,
−−→
BD)
рационально.
Пусть
−−→
BC
в T
1
— это (x, y),
−−→
BA
— это (z, t),
−−→
BD
— это (p, q). Тогда px +
+qy = и pz +qt = n — рациональны, откуда p =
mt − ny
xt − yz
, q =
nx − mz
xt − yz
— рациональные числа (поскольку xt−yz = 0, так как A, B, C не лежали на одной прямой. Следовательно, точка D в имеет рациональные координаты. Тогда, выбрав другую единицу измерения, можно координаты всех точек сделатьцелыми.
КЛАСС
389
A
B
C
D
l
p
n
m
A
B
C
D
l
q
p
m
n
Рис. Рис. 298
зуют треугольник наименьшей площади (см. рис. 298). Тогда через точку
D
проходит прямая q
, одноцветная с m
. Она пересекает либо отрезок, либо пусть, для определенности, B
C
). Тогда прямые n
, l
,
p
, образуют конфигурацию с треугольником меньшей площади. Про- тиворечие.
Замечание. Найти хотя бы одну пару прямых l, m, n, p можно бы было и по-другому: взятькакую-нибудьчетверку прямых l, m, n, p нужных цветов (так, чтобы m, n, p пересекалисьв одной точке) и проективным преобразованием добиться того, чтобы точка D пересечения p и l лежала между A и B.
11 класс. См. решение задачи 649.
658. Первое решение. Рассмотрим любые 3 точки A, B и C, не лежащие на одной прямой (если все точки будут лежатьна одной прямой, то утверждение задачи очевидно. Пусть T
1
— система координат, в которой эти точки имеют целые координаты. Рассмотрим любую из оставшихся точек, назовем ее D. Пусть T
2
— система координат, в которой точки B,
C
, D имеют целые координаты. Поскольку квадрат длины отрезка BC в
T
1
и будет целым, то отношение квадратов единиц измерения и T
2
— рациональное число. Но скалярное произведение векторов (в T
2
— целое, значит, в оно рационально, поскольку произведение длин этих векторов в будет рационально относиться к произведению их длин в T
2
, а косинус угла не изменится. Аналогично, (
−−→
BA,
−−→
BD)
рационально.
Пусть
−−→
BC
в T
1
— это (x, y),
−−→
BA
— это (z, t),
−−→
BD
— это (p, q). Тогда px +
+qy = и pz +qt = n — рациональны, откуда p =
mt − ny
xt − yz
, q =
nx − mz
xt − yz
— рациональные числа (поскольку xt−yz = 0, так как A, B, C не лежали на одной прямой. Следовательно, точка D в имеет рациональные координаты. Тогда, выбрав другую единицу измерения, можно координаты всех точек сделатьцелыми.
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
1 ... 49 50 51 52 53 54 55 56 ... 64
Второе решение. Как ив первом решении, можно считать, что в нашем множестве найдутся точки A, B, C, не лежащие на одной прямой.
Докажем, что tg ∠BAC — либо рациональное число, либо не существует.
Рассмотрим координаты этих точек в системе, соответствующей тройке, B, C. Если x
A
= случай x
A
= аналогичен, то tg ∠BAC =
=
±
x
C
− x
A
y
C
− рационален (или не существует. Если же x
B
= и x
C
=
= x
A
, то числа p =
y
B
− y
A
x
B
− и q =
y
C
− y
A
x
C
− рациональны. Но p = tg α,
q = tg β
, где α и β — углы, образуемые лучами AB и AC с положительным направлением оси Ox, поэтому из формулы tg ∠CAB = tg(β − α) =
=
p − q
1 + следует рациональность tg ∠BAC или тангенс не существует,
если pq = −1). Аналогично, рациональными являются тангенсы углов всех треугольников с вершинами в данных точках. Рассмотрим систему координат с центром A и единичным вектором по оси Ax, равным
−−→
AB
Для любой точки D нашего множества tg ∠DAB и tg ∠DBA рациональны, поэтому уравнения прямых AD и BD имеют рациональные коэффициенты. Тогда и точка D имеет рациональные координаты. Изменив масштаб, мы получим целочисленные координаты у всех точек. Первое решение. Достаточно доказатьэто неравенство при 0 <
< x при x оно очевидно, при x получается заменой =
π
2
− x). При k 2 имеем cos
k
x
− sin
k
x = (cos
k
x
− sin
k
x)(sin
2
x + cos
2
x) =
= (cos
k+2
x
− sin
k+2
x) + sin
2
x cos
2
x(cos
k−2
x
− sin
k−2
x)
cos
k+2
x
− Поэтому неравенство сводится к случаю n = m + 1, за исключением n =
= 3
. Кроме того sin
n
x
cos
n−1
x
− sin
n−1
x
cos
k
x
− sin
k
x
cos
k−1
x
− при n k > 1. Действительно, приведя к общему знаменателю, получаем неравенство sin
k−1
x cos
k−1
x(cos
n−k
x
− sin
n−k
x)(cos x
− sin x) которое очевидно. Поэтому неравенство сводится к случаями. Докажем их sin
3
x = (cos x
− sin x)(1 + sin x cos x)
3 2
(cos x
− sin поскольку cos x sin x =
1 2
sin 2x
1 2
;
cos
2
x
− sin
2
x = (cos x
− sin x)(cos x + sin x)
3 2
(cos x
− sin ибо sin x + cos x =
√
2 sin
x +
π
4
3 2
УЧЕБНЫЙ ГОД, 11
КЛАСС
391
Второе решение. Опятьже, неравенство достаточно доказатьдля
0 < x <
π
4
. Рассмотрим f(y) = cos
y
x
− sin
y
x
, где 0 < x <
π
4
, y Имеем f(0) = 0, f(y) > 0 при y > 0, f(y) → 0 при y → ∞. Далее) = cos
y
x ln cos x
− sin
y
ln sin x = cos
y
x(ln cos x
− tg
y
x ln sin поэтому имеет единственный кореньпри y > 0, так как функция) = монотонна. Из f(2) = f(2)(cos
2
x + sin
2
x) = f (4)
следует,
что f
(2) > 0
, f
(4) < 0
. Отсюда, при n > m 3 получаем неравенство sin
n
x
− cos
n
x
| | sin
m
x
− Если же m 2, то из соотношений f(1) f(2) f(3) f(n) при > видно, что достаточно доказатьнеравенство 3f(1) 2f(3), которое следует из sin x cos x =
sin 2x
2
1 2
, поскольку f(3) = f(1)(1 +
+ sin x cos x)
3 2
f (1)
660. Сначала докажем, что если с любой площади выходит не более двух улиц, то площади можно покраситьв 13 цветов так, чтобы ни с какой площади нельзя было попасть на площадьтого же цвета, проехав менее трех улиц. Для этого рассмотрим следующий вспомогательный ориентированный граф его вершинами будут площади, а ориентированными ребрами будут соединены пары площадей, между которыми в нашем городе есть путь, проходящий не более, чем по двум улицам. Легко видеть, что в этом графе из каждой вершины выходит не более 6 ребер. Нужно доказать, что вершины этого графа можно раскрасить в 13 цветов правильным образом.
Это утверждение легко доказывается индукцией по числу вершин.
Действительно, в случае, если вершин не больше 13, утверждение очевидно. Далее, легко видеть, что если в ориентированном графе из каждой вершины выходит не более 6 ребер, то существует вершина, в которую входит не более 6 ребер. Удалив из графа эту вершину, мы получим граф,
удовлетворяющий нашему условию и содержащий меньшее число вершин.
По индуктивному предположению, мы можем раскраситьвершины этого графа в 13 цветов, после чего удаленную вершину мы также можем покра- ситьв один из цветов, так как она соединена не более, чем с 12 вершинами.
Теперьдля каждого цвета разделим все площади данного цвета на типов, в зависимости оттого, на площади каких цветов ведут улицы, выходящие сданной площади. Поскольку других цветов 12, для каждого цвета есть вариантов, в которых обе улицы ведут на площади одного цвета,
и
12·11 2
= вариантов, в которых они ведут на площади разных цветов.
Итого, 78 вариантов. Таким образом, мы можем разбитьвсе площади на 13 = 1014 районов
КЛАСС
391
Второе решение. Опятьже, неравенство достаточно доказатьдля
0 < x <
π
4
. Рассмотрим f(y) = cos
y
x
− sin
y
x
, где 0 < x <
π
4
, y Имеем f(0) = 0, f(y) > 0 при y > 0, f(y) → 0 при y → ∞. Далее) = cos
y
x ln cos x
− sin
y
ln sin x = cos
y
x(ln cos x
− tg
y
x ln sin поэтому имеет единственный кореньпри y > 0, так как функция) = монотонна. Из f(2) = f(2)(cos
2
x + sin
2
x) = f (4)
следует,
что f
(2) > 0
, f
(4) < 0
. Отсюда, при n > m 3 получаем неравенство sin
n
x
− cos
n
x
| | sin
m
x
− Если же m 2, то из соотношений f(1) f(2) f(3) f(n) при > видно, что достаточно доказатьнеравенство 3f(1) 2f(3), которое следует из sin x cos x =
sin 2x
2
1 2
, поскольку f(3) = f(1)(1 +
+ sin x cos x)
3 2
f (1)
660. Сначала докажем, что если с любой площади выходит не более двух улиц, то площади можно покраситьв 13 цветов так, чтобы ни с какой площади нельзя было попасть на площадьтого же цвета, проехав менее трех улиц. Для этого рассмотрим следующий вспомогательный ориентированный граф его вершинами будут площади, а ориентированными ребрами будут соединены пары площадей, между которыми в нашем городе есть путь, проходящий не более, чем по двум улицам. Легко видеть, что в этом графе из каждой вершины выходит не более 6 ребер. Нужно доказать, что вершины этого графа можно раскрасить в 13 цветов правильным образом.
Это утверждение легко доказывается индукцией по числу вершин.
Действительно, в случае, если вершин не больше 13, утверждение очевидно. Далее, легко видеть, что если в ориентированном графе из каждой вершины выходит не более 6 ребер, то существует вершина, в которую входит не более 6 ребер. Удалив из графа эту вершину, мы получим граф,
удовлетворяющий нашему условию и содержащий меньшее число вершин.
По индуктивному предположению, мы можем раскраситьвершины этого графа в 13 цветов, после чего удаленную вершину мы также можем покра- ситьв один из цветов, так как она соединена не более, чем с 12 вершинами.
Теперьдля каждого цвета разделим все площади данного цвета на типов, в зависимости оттого, на площади каких цветов ведут улицы, выходящие сданной площади. Поскольку других цветов 12, для каждого цвета есть вариантов, в которых обе улицы ведут на площади одного цвета,
и
12·11 2
= вариантов, в которых они ведут на площади разных цветов.
Итого, 78 вариантов. Таким образом, мы можем разбитьвсе площади на 13 = 1014 районов
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Докажем, что полученное разбиение подходит. Пустьв районе A есть площади и a
2
, а в районе B — площади и такие, что из выходит улица, ведущая на b
1
, а из b
2
— на a
2
. Тогда, поскольку площади и принадлежат одному району, из них выходят улицы, ведущие на площади одних и тех же цветов. Это означает, что из выходит улица, ведущая на площадьтого же цвета, что и a
2
, а следовательно, того же цвета, что и a
1
. Таким образом, мы получили путь длины 2 между площадями одного цвета, что невозможно. Полученное противоречие завершает решение задачи. Ответ. 10010.
Пустьдля натурального числа n имеют место указанные представления+ Воспользуемся тем, что каждое из чисел a
1
, . . . , дает такой же остаток при делении на 9, что и сумма цифр обозначим этот остаток через r
(0 r 8), а соответствующий остаток для чисел b
1
, . . . , b
2003
— через s
(0 s Тогда числа n − 2002r и n − 2003s кратны 9, а значит, и число (n −
− 2002r) − (n − 2003s) = 2003s − 2002r = 2003(r + s) − 4005r кратно Число 4005r также кратно 9, а число 2003 — взаимно просто с 9; отсюда следует, что число r + s кратно Если при этом r = s = 0, то n 9 · 2003 (поскольку b
1
, . . . , делятся на 9). Если же r = 0, то r + s = 9, и потому имеет место по крайней мере одно из неравенств r 5 или s 5; для числа n получаются неравенства n 5 · 2002 или n 5 · 2003 соответственно.
А так как 10010 = 5 · 2002 = 4 · 2002 + 2002 · 1, и числа 4 и 2002 имеют одинаковую сумму цифр, то число 10010 — искомое. Будем считать, что K лежит в AOD все остальные случаи разбираются аналогично).
Пусть L
— точка, симметричная L относительно BC см. рис. Тогда =
∠OBC − ∠L
BC =
∠OBC − но ∠OBC = ∠OAD, так как ABCD — вписанный, следовательно =
∠OAD − ∠KAD = ∠OAK = так как ABOK — вписанный. Значит, ∠L
BO =
∠OBK. Аналогично Далее, ∠BKO = ∠BAO = ∠CDO = ∠CKO, так как четырехугольники и CDKO — вписанные.
Теперьрассмотрим четырехугольник см. рис. 300). Пусть точка пересечения CK и BL
, M — точка пересечения BK и CL
Докажем, что полученное разбиение подходит. Пустьв районе A есть площади и a
2
, а в районе B — площади и такие, что из выходит улица, ведущая на b
1
, а из b
2
— на a
2
. Тогда, поскольку площади и принадлежат одному району, из них выходят улицы, ведущие на площади одних и тех же цветов. Это означает, что из выходит улица, ведущая на площадьтого же цвета, что и a
2
, а следовательно, того же цвета, что и a
1
. Таким образом, мы получили путь длины 2 между площадями одного цвета, что невозможно. Полученное противоречие завершает решение задачи. Ответ. 10010.
Пустьдля натурального числа n имеют место указанные представления+ Воспользуемся тем, что каждое из чисел a
1
, . . . , дает такой же остаток при делении на 9, что и сумма цифр обозначим этот остаток через r
(0 r 8), а соответствующий остаток для чисел b
1
, . . . , b
2003
— через s
(0 s Тогда числа n − 2002r и n − 2003s кратны 9, а значит, и число (n −
− 2002r) − (n − 2003s) = 2003s − 2002r = 2003(r + s) − 4005r кратно Число 4005r также кратно 9, а число 2003 — взаимно просто с 9; отсюда следует, что число r + s кратно Если при этом r = s = 0, то n 9 · 2003 (поскольку b
1
, . . . , делятся на 9). Если же r = 0, то r + s = 9, и потому имеет место по крайней мере одно из неравенств r 5 или s 5; для числа n получаются неравенства n 5 · 2002 или n 5 · 2003 соответственно.
А так как 10010 = 5 · 2002 = 4 · 2002 + 2002 · 1, и числа 4 и 2002 имеют одинаковую сумму цифр, то число 10010 — искомое. Будем считать, что K лежит в AOD все остальные случаи разбираются аналогично).
Пусть L
— точка, симметричная L относительно BC см. рис. Тогда =
∠OBC − ∠L
BC =
∠OBC − но ∠OBC = ∠OAD, так как ABCD — вписанный, следовательно =
∠OAD − ∠KAD = ∠OAK = так как ABOK — вписанный. Значит, ∠L
BO =
∠OBK. Аналогично Далее, ∠BKO = ∠BAO = ∠CDO = ∠CKO, так как четырехугольники и CDKO — вписанные.
Теперьрассмотрим четырехугольник см. рис. 300). Пусть точка пересечения CK и BL
, M — точка пересечения BK и CL
УЧЕБНЫЙ ГОД, 11
КЛАСС
393
A
B
C
D
K
O
L
L
B
C
K
L
O
P
M
N
Q
R
T
Рис. Рис. Так как CO — биссектриса ∠MCK, BO — биссектриса ∠NBK, а KO
— биссектриса ∠MKN, то O равноудалена от сторон четырехугольника L
N и является центром вписанной в него окружности. Пусть P , Q,
R
, T — точки касания этой окружности со сторонами ML
, L
N
, NK и
KM
соответственно. Тогда + BL
= (CR + KR) + (BQ
− L
Q)
= CP + KT + BT
− L
P = (KT + BT ) + (CP
− L
P )
= KB + Значит, CK + BL = KB + CL, и четырехугольник BLCK является описанным, что и требовалосьдоказать.
663. См. решение задачи 656.
664. Положим) =
n
i=1 где A(n) и B(n) взаимно просты.
Заметим, что B(n) > n/2 (действительно, наибольшая степень двойки, не превосходящая n, является делителем ровно одного из чисел, 2, . . . , и потому является делителем знаменателя суммы Предположим, что при всех n число A(n) является степенью простого. Пусть p > n
0
+ 5
— простое число. Тогда A(p−1)...p слагаемые суммы S(p − 1) разбиваются на пары, для каждой из которых числитель суммы делится на p). Следовательно, A(p − 1) = p
k
, k ∈ Далее, докажем, что числитель A(p
n
−1) также кратен p и, стало быть,
является степенью p) при всех натуральных Проведем индукцию по База доказана
КЛАСС
393
A
B
C
D
K
O
L
L
B
C
K
L
O
P
M
N
Q
R
T
Рис. Рис. Так как CO — биссектриса ∠MCK, BO — биссектриса ∠NBK, а KO
— биссектриса ∠MKN, то O равноудалена от сторон четырехугольника L
N и является центром вписанной в него окружности. Пусть P , Q,
R
, T — точки касания этой окружности со сторонами ML
, L
N
, NK и
KM
соответственно. Тогда + BL
= (CR + KR) + (BQ
− L
Q)
= CP + KT + BT
− L
P = (KT + BT ) + (CP
− L
P )
= KB + Значит, CK + BL = KB + CL, и четырехугольник BLCK является описанным, что и требовалосьдоказать.
663. См. решение задачи 656.
664. Положим) =
n
i=1 где A(n) и B(n) взаимно просты.
Заметим, что B(n) > n/2 (действительно, наибольшая степень двойки, не превосходящая n, является делителем ровно одного из чисел, 2, . . . , и потому является делителем знаменателя суммы Предположим, что при всех n число A(n) является степенью простого. Пусть p > n
0
+ 5
— простое число. Тогда A(p−1)...p слагаемые суммы S(p − 1) разбиваются на пары, для каждой из которых числитель суммы делится на p). Следовательно, A(p − 1) = p
k
, k ∈ Далее, докажем, что числитель A(p
n
−1) также кратен p и, стало быть,
является степенью p) при всех натуральных Проведем индукцию по База доказана
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Переход от n − 1 к n. Имеем S(p
n
− 1) = S(p
n−1
− 1)/p + S
, где первое слагаемое как раз равно сумме слагаемых со знаменателями, делящимися на p). Сумма разбивается на несколько (а именно, p
n−1
) сумм вида 1
pl+i
, l = 0, 1, . . . , p
n−1
− 1. Каждая из них имеет числитель, делящийся на p, что устанавливается как и для S(p −
− 1). Осталосьубедиться, что числительдроби S(p
n−1
− 1)/p делится на. Действительно, A(p
n−1
− 1) = в силу индуктивного предположения,
причем s > 1 (вспомним, что B(p
n−1
− 1) p
n−1
/2
p/2, а S(p
n−1
−
− 1) S(n
0
+ 4)
S(4) > Положим H
p
(n) := S(p
n
−p)−S(p
n
−1) =
p−1
i=1 1
−p
n
+ i
. Если n > k, то числительдроби делится на p
k
, ноне на ибо H
p
(n)
− S(p − 1)
— дробь, числитель которой делится на p
n
). Отсюда получаем, что оба числителя A(p
n
− 1) и A(p
n
− p) делятся на p, но один из них не делится на p
k+1
. Значит, одна из дробей S(p
n
− 1) и S(p
n
− p) не превосходит при n = k + 2 — противоречие г класс. Возьмем три различных числа a, b, c ∈ M. Из рациональности чисел+ следует рациональность чисел+ b
√
2
− (b
2
+ a
√
2) = (a
− b)(a + b −
√
2) =
1 2
(a
√
2
− b
√
2)(a
√
2 +
+ b
√
2
− 2) и c
2
+ a
√
2
− (c
2
+ b
√
2) = a
√
2
− b
√
2
, те. числа a
√
2 + Значит, a
√
2 =
1 2
(a
√
2 + b
√
2 + a
√
2
− рационально. Заметим, что ∠LAK = ∠BAK + ∠BAL = 1/2(∠BO
2
A +
+
∠BO
1
A) =
∠BO
2
O
1
+
∠BO
1
O
2
= 180
◦
− ∠LBK, поэтому четырехугольник вписанный. Но тогда ∠BO
2
O
1
=
∠BAL = следовательно O
1
O
2
KL.
667. Достаточно доказатьследующее утверждение если любой белый отрезок пересекается хотя бы с k черными, то найдется черный, пересекающийся со всеми белыми.
Предположим противное. Выберем для каждого черного отрезка белый, не пересекающийся с ним. Такой белый отрезок лежит либо левее соответствующего черного, либо правее его. Следовательно, есть хотя бы
k
черных отрезков, для каждого из которых
его
белый отрезок лежит по одну и туже сторону от него (пусть, для определенности, левее. Для
Переход от n − 1 к n. Имеем S(p
n
− 1) = S(p
n−1
− 1)/p + S
, где первое слагаемое как раз равно сумме слагаемых со знаменателями, делящимися на p). Сумма разбивается на несколько (а именно, p
n−1
) сумм вида 1
pl+i
, l = 0, 1, . . . , p
n−1
− 1. Каждая из них имеет числитель, делящийся на p, что устанавливается как и для S(p −
− 1). Осталосьубедиться, что числительдроби S(p
n−1
− 1)/p делится на. Действительно, A(p
n−1
− 1) = в силу индуктивного предположения,
причем s > 1 (вспомним, что B(p
n−1
− 1) p
n−1
/2
p/2, а S(p
n−1
−
− 1) S(n
0
+ 4)
S(4) > Положим H
p
(n) := S(p
n
−p)−S(p
n
−1) =
p−1
i=1 1
−p
n
+ i
. Если n > k, то числительдроби делится на p
k
, ноне на ибо H
p
(n)
− S(p − 1)
— дробь, числитель которой делится на p
n
). Отсюда получаем, что оба числителя A(p
n
− 1) и A(p
n
− p) делятся на p, но один из них не делится на p
k+1
. Значит, одна из дробей S(p
n
− 1) и S(p
n
− p) не превосходит при n = k + 2 — противоречие г класс. Возьмем три различных числа a, b, c ∈ M. Из рациональности чисел+ следует рациональность чисел+ b
√
2
− (b
2
+ a
√
2) = (a
− b)(a + b −
√
2) =
1 2
(a
√
2
− b
√
2)(a
√
2 +
+ b
√
2
− 2) и c
2
+ a
√
2
− (c
2
+ b
√
2) = a
√
2
− b
√
2
, те. числа a
√
2 + Значит, a
√
2 =
1 2
(a
√
2 + b
√
2 + a
√
2
− рационально. Заметим, что ∠LAK = ∠BAK + ∠BAL = 1/2(∠BO
2
A +
+
∠BO
1
A) =
∠BO
2
O
1
+
∠BO
1
O
2
= 180
◦
− ∠LBK, поэтому четырехугольник вписанный. Но тогда ∠BO
2
O
1
=
∠BAL = следовательно O
1
O
2
KL.
667. Достаточно доказатьследующее утверждение если любой белый отрезок пересекается хотя бы с k черными, то найдется черный, пересекающийся со всеми белыми.
Предположим противное. Выберем для каждого черного отрезка белый, не пересекающийся с ним. Такой белый отрезок лежит либо левее соответствующего черного, либо правее его. Следовательно, есть хотя бы
k
черных отрезков, для каждого из которых
его
белый отрезок лежит по одну и туже сторону от него (пусть, для определенности, левее. Для
УЧЕБНЫЙ ГОД, 9
КЛАСС
395
каждого из этих черных отрезков его левый конец лежит правее правого конца соответствующего ему белого отрезка. Тогда, если мы выберем из правых концов белых отрезков самый левый, то он будет лежатьлевее хотя былевых концов черных отрезков, те. этот белый отрезок не будет пересекаться ни с одним из этих k отрезков. Противоречие. Ответ. a
2003
= 10p
Пустьв записи числа 1/n естьпредпериод A из m цифр и период B из
k
цифр. Тогда из формулы суммы геометрической прогрессии имеем 1)
=
A(10
k
− 1) + B
10
m
(10
k
− Следовательно, 10
m
(10
k
− 1) ... n. Наоборот, пусть m, k — наименьшие числа такие, что 10
m
(10
k
− 1) ... n те естьмаксимальная из степеней двойки и пятерки, на которые делится n, а k — минимальное число такое,
что (10
k
− 1) ...
n
НОД(n, 10
m
)
)
, и пусть C =
10
m
(10
k
− 1)
n
. Положим A =
=
C
10
k
− 1
, B = C−A(10
k
−1). Тогда B < 10
k
−1, A < 10
m
, и дробь имеет предпериод A с нулями, дополняющими его до m цифр) и период аналогично, ибо m и k были выбраны минимальными.
Из условия наследует, что p = 2, p = 5 и p не может бытьчис- лом, в десятичной записи которого присутствуют только нули и единицы.
Последнее следует из того, что сумма цифр такого числа должна равняться, и, значит, оно непростое. Мы докажем, что последовательность будет периодической с периодом 2. Период обыкновенной дроби равен (10
n
− 1)/p, где n — наименьшее натуральное число, для которого 1) ... p. Таким образом, a
2
= 2(10
n
− 1)/p. Докажем, что a
3
=
= 10p
. Поскольку делится на 2, ноне делится ни на 2 2
, ни на 5, период обыкновенной дроби будет равен (10
k+1
− 10)/a
2
, где k — наименьшее натуральное число, для которого (10
k+1
− 10) ... a
2
= 2(10
n
− 1)/p в обозначениях первого абзаца A = 0, так как a
2
> 10
(a
2
... 18), поэтому = C
). Следовательно, k является наименьшим натуральным числом,
для которого 1)p ... 10
n
− Покажем, что в этом случае k = n. Сначала установим, что n ... k. Предположим противное, тогда n = kq + r, где 0 < r < k. Заметим, что 1)p ... (10
k
− 1)p ... (10
n
− 1) и (10
n
− 1) ... (10
n
− А значит 1)p = ((10
n
− 1)p − (10
kq
− 1)p) ... (10
n
− Стало быть, (10
r
− 1)p ... (10
n
− 1), что невозможно, ибо k было наименьшим числом, удовлетворяющим условию (∗). Поэтому, n = km и (10
k
−
КЛАСС
395
каждого из этих черных отрезков его левый конец лежит правее правого конца соответствующего ему белого отрезка. Тогда, если мы выберем из правых концов белых отрезков самый левый, то он будет лежатьлевее хотя былевых концов черных отрезков, те. этот белый отрезок не будет пересекаться ни с одним из этих k отрезков. Противоречие. Ответ. a
2003
= 10p
Пустьв записи числа 1/n естьпредпериод A из m цифр и период B из
k
цифр. Тогда из формулы суммы геометрической прогрессии имеем 1)
=
A(10
k
− 1) + B
10
m
(10
k
− Следовательно, 10
m
(10
k
− 1) ... n. Наоборот, пусть m, k — наименьшие числа такие, что 10
m
(10
k
− 1) ... n те естьмаксимальная из степеней двойки и пятерки, на которые делится n, а k — минимальное число такое,
что (10
k
− 1) ...
n
НОД(n, 10
m
)
)
, и пусть C =
10
m
(10
k
− 1)
n
. Положим A =
=
C
10
k
− 1
, B = C−A(10
k
−1). Тогда B < 10
k
−1, A < 10
m
, и дробь имеет предпериод A с нулями, дополняющими его до m цифр) и период аналогично, ибо m и k были выбраны минимальными.
Из условия наследует, что p = 2, p = 5 и p не может бытьчис- лом, в десятичной записи которого присутствуют только нули и единицы.
Последнее следует из того, что сумма цифр такого числа должна равняться, и, значит, оно непростое. Мы докажем, что последовательность будет периодической с периодом 2. Период обыкновенной дроби равен (10
n
− 1)/p, где n — наименьшее натуральное число, для которого 1) ... p. Таким образом, a
2
= 2(10
n
− 1)/p. Докажем, что a
3
=
= 10p
. Поскольку делится на 2, ноне делится ни на 2 2
, ни на 5, период обыкновенной дроби будет равен (10
k+1
− 10)/a
2
, где k — наименьшее натуральное число, для которого (10
k+1
− 10) ... a
2
= 2(10
n
− 1)/p в обозначениях первого абзаца A = 0, так как a
2
> 10
(a
2
... 18), поэтому = C
). Следовательно, k является наименьшим натуральным числом,
для которого 1)p ... 10
n
− Покажем, что в этом случае k = n. Сначала установим, что n ... k. Предположим противное, тогда n = kq + r, где 0 < r < k. Заметим, что 1)p ... (10
k
− 1)p ... (10
n
− 1) и (10
n
− 1) ... (10
n
− А значит 1)p = ((10
n
− 1)p − (10
kq
− 1)p) ... (10
n
− Стало быть, (10
r
− 1)p ... (10
n
− 1), что невозможно, ибо k было наименьшим числом, удовлетворяющим условию (∗). Поэтому, n = km и (10
k
−
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ 1)p ... (10
mk
− 1). Отсюда заключаем, что p ... (10
k(m−1)
+ 10
k(m−2)
+. . .
. . . + 10
k
+ 1)
. Но p — простое число, следовательно, если m = 1, то = 10
k(m−1)
+ 10
k(m−2)
+ . . . + 10
k
+ 1
, что невозможно, ибо p не может бытьчислом из нулей и единиц. Итак, мы установили, что k = n, а значит (10
n+1
− 10)/a
2
= 10p
. Для завершения решения осталосьлишь заметить, что периоды чисел 1/p и 1/(10p) равны. Переформулируем задачу на языке графов. Нам дан полный граф с N вершинами, ребра которого покрашены в два цвета. Требуется доказать, что мы можем выделить в этом графе цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей. Доказательство проведем по индукции. Для полного графа стремя вершинами утверждение очевидно. Пустьдоказываемое утверждение верно для N =
= k
. Рассмотрим полный граф с k + 1 вершиной. Удалим из рассмотрения одну вершину M с выходящими из нее ребрами. Для оставшегося графа с
k
вершинами по предположению индукции существует цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей.
Возможны два случая) Все ребра цикла окрашены в один цвет. Занумеруем вершины цикла по порядку A
1
, A
2
, . . . , A
k
. Тогда, удалив ребро и соединив вершину
M
с вершинами и A
2
, мы получим цикл, состоящий не более чем из двух одноцветных частей) Не все ребра цикла окрашены в один цвет. Пустьизменение цвета происходит в вершинах и A
m
, те. в цикле есть две одноцветные части. первого цвета) и A
m
A
m+1
. . . второго цвета. Тогда посмотрим на цвет ребра A
m
M
. Если это ребро первого цвета, то цикл. . . A
m
M A
m+1
. . . A
1
— искомый, если же оно второго цвета, то искомым будет цикл A
1
A
2
. . . A
m−1
M A
m
. . . То естьв любом случае мы получили требуемый цикл с k+1 вершиной. Первое решение. Воспользуемся следующими неравенствами + b
, которые следуют из очевидного неравенства + для положительных x, y. Сложив эти 3 неравенства, получим неравенство + b
+
2
b + c
+
2
c + a
4
a + 2b + c
+
4
b + 2c + a
+
4
c + 2a + которое после сокращения на 2 и замены в знаменателях дробей a + b + на 1 превратится в доказываемое неравенство.
mk
− 1). Отсюда заключаем, что p ... (10
k(m−1)
+ 10
k(m−2)
+. . .
. . . + 10
k
+ 1)
. Но p — простое число, следовательно, если m = 1, то = 10
k(m−1)
+ 10
k(m−2)
+ . . . + 10
k
+ 1
, что невозможно, ибо p не может бытьчислом из нулей и единиц. Итак, мы установили, что k = n, а значит (10
n+1
− 10)/a
2
= 10p
. Для завершения решения осталосьлишь заметить, что периоды чисел 1/p и 1/(10p) равны. Переформулируем задачу на языке графов. Нам дан полный граф с N вершинами, ребра которого покрашены в два цвета. Требуется доказать, что мы можем выделить в этом графе цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей. Доказательство проведем по индукции. Для полного графа стремя вершинами утверждение очевидно. Пустьдоказываемое утверждение верно для N =
= k
. Рассмотрим полный граф с k + 1 вершиной. Удалим из рассмотрения одну вершину M с выходящими из нее ребрами. Для оставшегося графа с
k
вершинами по предположению индукции существует цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей.
Возможны два случая) Все ребра цикла окрашены в один цвет. Занумеруем вершины цикла по порядку A
1
, A
2
, . . . , A
k
. Тогда, удалив ребро и соединив вершину
M
с вершинами и A
2
, мы получим цикл, состоящий не более чем из двух одноцветных частей) Не все ребра цикла окрашены в один цвет. Пустьизменение цвета происходит в вершинах и A
m
, те. в цикле есть две одноцветные части. первого цвета) и A
m
A
m+1
. . . второго цвета. Тогда посмотрим на цвет ребра A
m
M
. Если это ребро первого цвета, то цикл. . . A
m
M A
m+1
. . . A
1
— искомый, если же оно второго цвета, то искомым будет цикл A
1
A
2
. . . A
m−1
M A
m
. . . То естьв любом случае мы получили требуемый цикл с k+1 вершиной. Первое решение. Воспользуемся следующими неравенствами + b
, которые следуют из очевидного неравенства + для положительных x, y. Сложив эти 3 неравенства, получим неравенство + b
+
2
b + c
+
2
c + a
4
a + 2b + c
+
4
b + 2c + a
+
4
c + 2a + которое после сокращения на 2 и замены в знаменателях дробей a + b + на 1 превратится в доказываемое неравенство.
1 ... 50 51 52 53 54 55 56 57 ... 64
