ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.04.2024
Просмотров: 56
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Лемма. Если угольник можно разбить на прямоугольники, то
его можно разбить на не более чем k − 1 прямоугольник.
Д ока за тел ьс т во. Сумма углов многоугольника S = (и все углы в нем, очевидно, поили по 270
◦
. Если все по 90
◦
, то это прямоугольник. Пусть найдется угол A в 270
◦
. Продолжим одну из его сторон внутрь многоугольника до пересечения с контуром. Многоугольник разобьется на две части, причем сумма внутренних углов частей не превосходит суммы внутренних углов многоугольника (продолжение стороны отрезает от угла A угол в 90
◦
, который попадает в одну из частей,
и угол в 180
◦
, который лежит на стороне другой части, поэтому исчезает;
в тоже время дополнительно в этих частях могут возникнутьтолько два угла потам, где продолжение стороны дошло до контура многоуголь-
Второе решение.
Сделаем развертку тетраэдра ABCD (см.
рис. 251). Пустьсфера касается грани ABC в точке O — центре вписанной окружности, грани ACD ( на рис. 251) — в точке M пересечения медиан, грани BCD ( BCD
2
) — в точке H пересечения высот. По свойству касательных, проведенных к сфере из одной точки, AM = AO,
556. Предположим противное. Тогда найдется такое n (n > 1), что любой набор из n − 1 выделенного подмножества имеет общий элемент и существует выделенных подмножеств A
1
, A
2
, . . . , A
n
, не имеющих общего элемента. Исключим из набора A
1
, A
2
, . . . , множество A
i
. Оставшиеся имеют общий элемент, который мы обозначим через x
i
. Заметим, что при i = j. Каждое из множеств содержит все элементы множества, кроме x
i
, поэтому, если из множеств исключить элементы множества {x
1
, x
2
, . . . , x
n
}, тов каждом из них останется 2k −
− n + 1 элемент (в частности, n 2k + 1). Следовательно, объединение множеств A
1
, A
2
, . . . , состоит не более чем из n + n(2k − n + 1) =
= n(2k + 2
− n) элементов. Максимальное значение выражения n(2k +
+ 2
−n) равно (k+1)
2
. Но тогда, по условию задачи, все должны иметь общий элемент. Противоречие. Ответ. Нельзя.
Допустим, что можно, и рассмотрим способ добиться этого за наименьшее количество действий. Пусть a
k
, b
k
— числа, получавшиеся из и 98 после го действия, s — число действий. Тогда a
s
= b
s
= итак как мы рассматриваем оптимальный способ. Действия,
проведенные над и b
s−1
, различны. Значит, m = и нам шаге мы имели числа a
s−1
= и b
s−1
= n
2
− 1 (или наоборот на дальнейшее решение это не влияет. Общее количество s действий не больше,
чем n − 18, так как на s − 1 шаге мы получили n, а каждый шаг увеличивает числа по крайней мерена. Тогда n
2
− 1 могло получиться только последовательным прибавлением единиц, так как от ближайшего квадрата добудет единицы. Следовательно, b
1
> (n
− поэтому все числа b
1
, . . . , не являются полными квадратами. Поэтому, с другой стороны a
s
= a
2
s−1
19 2
. Противоречие
568. Пусть Φ
1
, . . . , Φ
k
— всевозможные расположения фигуры Φ в прямоугольнике. Утверждение задачи можно переформулировать так:
можно взятьфигуры такой неотрицательной толщины d
i
, i = 1 ,. . . , рационально, что суммарная толщина всех фигур над каждой клеткой прямоугольника будет равна Предположим, что это утверждение неверно. Покажем, что тогда существует такое заполнение клеток прямоугольника числами, при котором сумма всех чисел положительна, а сумма чисел в клетках, закрываемых фигурой при любом ее положении, неположительна.
Введем обозначения индексом j, j = 1, . . . , m · n, будем нумеровать клетки прямоугольника, индексом i, i = 1, . . . , k, — положения фигуры на прямоугольнике.
Положим P
ij
= 1
, если я клетка закрыта фигурой Φ
i
, P
ij
= 0
, если незакрыта. Тогда набору чисел {d
i
} соответствует заполнение клеток прямоугольника числами θ
j
= 1
−
i
d
i
P
ij
, характеризующими уклонение покрытия прямоугольника фигурами от равномерного. По нашему предположению, все числа не могут бытьравными нулю.
Выберем числа d
j
0 так, чтобы величина |θ| уклонения была минимальна, где |θ|
2
=
j
θ
2
j
. Покажем, что получившиеся числа и образуют искомое заполнение клеток прямоугольника Почему существует набор {d
i
}, для которого |θ| — минимален?
После раскрытия скобок получаем
582. Задача является частным случаем задачи 575, когда точки E и совпадают сточкой точка K в данной задаче — это точка F задачи. Вначале докажем, что
его можно разбить на не более чем k − 1 прямоугольник.
Д ока за тел ьс т во. Сумма углов многоугольника S = (и все углы в нем, очевидно, поили по 270
◦
. Если все по 90
◦
, то это прямоугольник. Пусть найдется угол A в 270
◦
. Продолжим одну из его сторон внутрь многоугольника до пересечения с контуром. Многоугольник разобьется на две части, причем сумма внутренних углов частей не превосходит суммы внутренних углов многоугольника (продолжение стороны отрезает от угла A угол в 90
◦
, который попадает в одну из частей,
и угол в 180
◦
, который лежит на стороне другой части, поэтому исчезает;
в тоже время дополнительно в этих частях могут возникнутьтолько два угла потам, где продолжение стороны дошло до контура многоуголь-
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
ника). Заметим, что общее количество углов в уменьшилось. Если они еще остались, будем повторять операцию с частями. В конце мы получим частей без углов 270
◦
, те прямоугольников с общей суммой углов S = 360
◦
· n (2k − 2) · 180
◦
, откуда n k − 1. Лемма доказана.
Из леммы следует, что в нашем многоугольнике число вершин больше, иначе его можно разбить на 99 прямоугольников. Разобьем его на m треугольников и рассмотрим сумму их углов S = 180
◦
m
. Найдем теперь S, учитывая, что углы треугольников входят в состав углов многоугольника. Каждый угол многоугольника дает вклад не менее из угла может бытьвычтено 180
◦
, если его вершина лежит на стороне какого-нибудьтреугольника), поэтому S = 180
◦
· m > 200 · 90
◦
, откуда > 100
, что и требовалосьдоказать.
Замечание. Оценка в задаче является точной объединение клеток квадрата 100×100, кроме клеток, лежащих выше главной диагонали, дает пример многоугольника, который главной диагональю разбивается на треугольник. Ответ. Не существуют.
Предположим противное. Если у многочлена kx
2
+ lx + с целыми коэффициентами два целых корня и x
2
, то m и l делятся на k, потому что x
1
x
2
=
m
k
, а x
1
+ x
2
=
−
l
k
. Из чисел a и a + 1 одно четное. Без потери общности можно считать, что четное — a. Тогда b и c тоже четные.
Отсюда (b+1) и (c+1) нечетные. Пусть и y
2
— целые корни уравнения + 1)x
2
+ (b + 1)x + (c + 1)
. Тогда y
1
y
2
=
c + 1
a + и y
1
+ y
2
=
−
b + 1
a + 1
— нечетные числа. Получили противоречие сумма и произведение двух целых чисел не могут одновременно бытьнечетными.
534. Первое решение. Пусть L — точка пересечения прямых KO и N
, а прямая, проходящая через L параллельно AC, пересекает AB ив точках и соответственно (см. рис. Покажем, что A
1
L = LC
1
. Действительно, ∠BA
1
L =
∠MOL как острые углы с соответственно перпендикулярными сторонами. Отсюда четырехугольник A
1
M LO
— вписанный, и ∠MLA
1
=
∠MOA
1
= Аналогично ∠C
1
LN =
∠C
1
ON = α
. Тогда OMA
1
=
ONC
1
, откуда. Значит, A
1
OC
1
— равнобедренный, и его высота является и медианой. Итак, A
1
L = LC
1
. Но тогда точка L, очевидно, лежит на медиане BB
1
, те совпадает сиз условия задачи.
Второе решение см. рис. 249). Проведем через точку D отрезок
C
1
A
1
с концами на AB и BC параллельно AC. Тогда C
1
D = DA
1
, так как, по условию, D лежит на медиане угла B.
ника). Заметим, что общее количество углов в уменьшилось. Если они еще остались, будем повторять операцию с частями. В конце мы получим частей без углов 270
◦
, те прямоугольников с общей суммой углов S = 360
◦
· n (2k − 2) · 180
◦
, откуда n k − 1. Лемма доказана.
Из леммы следует, что в нашем многоугольнике число вершин больше, иначе его можно разбить на 99 прямоугольников. Разобьем его на m треугольников и рассмотрим сумму их углов S = 180
◦
m
. Найдем теперь S, учитывая, что углы треугольников входят в состав углов многоугольника. Каждый угол многоугольника дает вклад не менее из угла может бытьвычтено 180
◦
, если его вершина лежит на стороне какого-нибудьтреугольника), поэтому S = 180
◦
· m > 200 · 90
◦
, откуда > 100
, что и требовалосьдоказать.
Замечание. Оценка в задаче является точной объединение клеток квадрата 100×100, кроме клеток, лежащих выше главной диагонали, дает пример многоугольника, который главной диагональю разбивается на треугольник. Ответ. Не существуют.
Предположим противное. Если у многочлена kx
2
+ lx + с целыми коэффициентами два целых корня и x
2
, то m и l делятся на k, потому что x
1
x
2
=
m
k
, а x
1
+ x
2
=
−
l
k
. Из чисел a и a + 1 одно четное. Без потери общности можно считать, что четное — a. Тогда b и c тоже четные.
Отсюда (b+1) и (c+1) нечетные. Пусть и y
2
— целые корни уравнения + 1)x
2
+ (b + 1)x + (c + 1)
. Тогда y
1
y
2
=
c + 1
a + и y
1
+ y
2
=
−
b + 1
a + 1
— нечетные числа. Получили противоречие сумма и произведение двух целых чисел не могут одновременно бытьнечетными.
534. Первое решение. Пусть L — точка пересечения прямых KO и N
, а прямая, проходящая через L параллельно AC, пересекает AB ив точках и соответственно (см. рис. Покажем, что A
1
L = LC
1
. Действительно, ∠BA
1
L =
∠MOL как острые углы с соответственно перпендикулярными сторонами. Отсюда четырехугольник A
1
M LO
— вписанный, и ∠MLA
1
=
∠MOA
1
= Аналогично ∠C
1
LN =
∠C
1
ON = α
. Тогда OMA
1
=
ONC
1
, откуда. Значит, A
1
OC
1
— равнобедренный, и его высота является и медианой. Итак, A
1
L = LC
1
. Но тогда точка L, очевидно, лежит на медиане BB
1
, те совпадает сиз условия задачи.
Второе решение см. рис. 249). Проведем через точку D отрезок
C
1
A
1
с концами на AB и BC параллельно AC. Тогда C
1
D = DA
1
, так как, по условию, D лежит на медиане угла B.
УЧЕБНЫЙ ГОД, 10
КЛАСС
327
A
B
C
N
M
K
O
L
B
1
A
1
C
1
A
B
C
N
M
K
O
D
C
1
A
1
Рис. Рис. Заметим, что как вертикальные, и ∠C
1
M D =
= 180
◦
− ∠BMD = 180
◦
− ∠A
1
N D
(BM = BN как касательные. Отсюда Кроме того A
1
=
1 2
· MD · MC
1
· sin ∠C
1
M D
1 2
· ND · NA
1
· sin ∠A
1
N D
=
M D
N D
·
M C
1
N значит MC
1
= N A
1
. Следовательно, OMC
1
=
так как = ON
). Отсюда OC
1
= OA
1
, значит, OD — высота OA
1
C
1
. Таким образом, OD ⊥ AC (A
1
C
1
AC), но и OK ⊥ AC, значит, O лежит на. Ответ. m = n = l = Положим d = НОД(m, n, l). Пусть m = dm
1
, n = dn
1
, l = dl
1
. Тогда+ n
1
) = d
2
d
2
mn
, где d
mn
=
НОД(m
1
, n
1
)
; откуда m
1
+ n
1
= d
· Складывая это равенство с двумя аналогичными, получаем+ n
1
+ l
1
) = d
· (d
2
mn
+ d
2
ml
+ Покажем, что d взаимно просто с суммой m
1
+ n
1
+ l
1
. В самом деле, если у d и этой суммы естьобщий делитель 1
, то он будет общим делителем всех чисел m
1
, итак как сумма любых двух из них делится на. Но тогда произведение d · d
1
— общий делительчисел m, n и l, что противоречит определению числа d. Следовательно, d является делителем числа 2 (равенство (1)), откуда d 2. Заметим, что числа d
mn
, попарно взаимно просты (иначе у чисел m
1
, n
1
, нашелся бы общий делитель, неравный. Поэтому m
1
= d
mn
· d
ml
· m
2
, n
1
= d
mn
· d
nl
· n
2
,
l
1
= d
nl
· d
ml
· l
2
, где m
2
, n
2
, l
2
— натуральные числа. В таких обозначениях первое из исходных уравнений приобретает такой вид
КЛАСС
327
A
B
C
N
M
K
O
L
B
1
A
1
C
1
A
B
C
N
M
K
O
D
C
1
A
1
Рис. Рис. Заметим, что как вертикальные, и ∠C
1
M D =
= 180
◦
− ∠BMD = 180
◦
− ∠A
1
N D
(BM = BN как касательные. Отсюда Кроме того A
1
=
1 2
· MD · MC
1
· sin ∠C
1
M D
1 2
· ND · NA
1
· sin ∠A
1
N D
=
M D
N D
·
M C
1
N значит MC
1
= N A
1
. Следовательно, OMC
1
=
так как = ON
). Отсюда OC
1
= OA
1
, значит, OD — высота OA
1
C
1
. Таким образом, OD ⊥ AC (A
1
C
1
AC), но и OK ⊥ AC, значит, O лежит на. Ответ. m = n = l = Положим d = НОД(m, n, l). Пусть m = dm
1
, n = dn
1
, l = dl
1
. Тогда+ n
1
) = d
2
d
2
mn
, где d
mn
=
НОД(m
1
, n
1
)
; откуда m
1
+ n
1
= d
· Складывая это равенство с двумя аналогичными, получаем+ n
1
+ l
1
) = d
· (d
2
mn
+ d
2
ml
+ Покажем, что d взаимно просто с суммой m
1
+ n
1
+ l
1
. В самом деле, если у d и этой суммы естьобщий делитель 1
, то он будет общим делителем всех чисел m
1
, итак как сумма любых двух из них делится на. Но тогда произведение d · d
1
— общий делительчисел m, n и l, что противоречит определению числа d. Следовательно, d является делителем числа 2 (равенство (1)), откуда d 2. Заметим, что числа d
mn
, попарно взаимно просты (иначе у чисел m
1
, n
1
, нашелся бы общий делитель, неравный. Поэтому m
1
= d
mn
· d
ml
· m
2
, n
1
= d
mn
· d
nl
· n
2
,
l
1
= d
nl
· d
ml
· l
2
, где m
2
, n
2
, l
2
— натуральные числа. В таких обозначениях первое из исходных уравнений приобретает такой вид
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ d
ml
· m
2
+ d
mn
· d
nl
· n
2
= d
· те Не умаляя общности, мы можем считать, что число d
mn
— наименьшее из чисел d
mn
, и d
nl
. Имеем m
2
+ d
nl
· n
2
d
ml
+ d
nl
2d
mn
d · так как d 2). Итак, все неравенства являются на самом деле равенствами, отсюда m
2
= n
2
= 1
, d = 2 и d
ml
= d
mn
= d
nl
. Но числа d
ml
,
d
mn
, попарно взаимно просты, следовательно, они равны 1, и мы нашли единственное решение m = n = l = 2.
536. Обозначим через количество камней в клетке с номером i. Тогда последовательность A = (задает конфигурацию — расположение камней по клеткам. Пусть α — кореньуравнения x
2
= x + 1
, больший Назовем весом конфигурации A число w(A) =
a
i
α
i
. Покажем, что разрешенные действия не меняют веса. Действительно, α
n+1
− α
n
− α
n−1
=
= α
n−1
(α
2
−α−1) = 0, α
n+1
−2α
n
+α
n−2
= α
n−2
(α
−1)(α
2
−α−1) = Докажем индукцией по k — числу камней, что любая последователь- ностьдействий завершается. При k = 1 это верно. Пустьпри числе камней, меньшем k, утверждение верно. Рассмотрим процесс, начинающийся с конфигурации A = (с k
. Наибольший номер непустой клетки при разрешенных действиях не уменьшается, но и расти бесконечно он не может — он не может превыситьчисла n, при котором α
n
> w(A)
. Значит, с какого-то момента наибольший номер непустой клетки перестает изменяться, и с камнями, попавшими в эту клетку, уже ничего не происходит. Выбросим эти камни, и применим предположение индукции к остав- шимся.
В конечной конфигурации в каждой клетке не более одного камня, и нет двух непустых клеток подряд. Докажем, что любые две конфигурации = (и B = (с такими свойствами имеют разные веса. Пусть n
— наибольший номер, при котором a
i
= b
i
; пусть, для определенности 1
, b
n
= 0
. Выбросим из A и B все камни с номерами, большими они в A и B совпадают. Для оставшихся конфигураций и имеем α
n
;
w(B
) < α
n−1
+ α
n−3
+ α
n−5
+ . . . = α
n−1 1
1
− α
−2
= Таким образом, для любой конфигурации естьтолько одна конечная ста- ким же весом только к ней и может привести процесс класс. См. решение задачи 529.
538. Ответ. 99 мудрецов
ml
· m
2
+ d
mn
· d
nl
· n
2
= d
· те Не умаляя общности, мы можем считать, что число d
mn
— наименьшее из чисел d
mn
, и d
nl
. Имеем m
2
+ d
nl
· n
2
d
ml
+ d
nl
2d
mn
d · так как d 2). Итак, все неравенства являются на самом деле равенствами, отсюда m
2
= n
2
= 1
, d = 2 и d
ml
= d
mn
= d
nl
. Но числа d
ml
,
d
mn
, попарно взаимно просты, следовательно, они равны 1, и мы нашли единственное решение m = n = l = 2.
536. Обозначим через количество камней в клетке с номером i. Тогда последовательность A = (задает конфигурацию — расположение камней по клеткам. Пусть α — кореньуравнения x
2
= x + 1
, больший Назовем весом конфигурации A число w(A) =
a
i
α
i
. Покажем, что разрешенные действия не меняют веса. Действительно, α
n+1
− α
n
− α
n−1
=
= α
n−1
(α
2
−α−1) = 0, α
n+1
−2α
n
+α
n−2
= α
n−2
(α
−1)(α
2
−α−1) = Докажем индукцией по k — числу камней, что любая последователь- ностьдействий завершается. При k = 1 это верно. Пустьпри числе камней, меньшем k, утверждение верно. Рассмотрим процесс, начинающийся с конфигурации A = (с k
. Наибольший номер непустой клетки при разрешенных действиях не уменьшается, но и расти бесконечно он не может — он не может превыситьчисла n, при котором α
n
> w(A)
. Значит, с какого-то момента наибольший номер непустой клетки перестает изменяться, и с камнями, попавшими в эту клетку, уже ничего не происходит. Выбросим эти камни, и применим предположение индукции к остав- шимся.
В конечной конфигурации в каждой клетке не более одного камня, и нет двух непустых клеток подряд. Докажем, что любые две конфигурации = (и B = (с такими свойствами имеют разные веса. Пусть n
— наибольший номер, при котором a
i
= b
i
; пусть, для определенности 1
, b
n
= 0
. Выбросим из A и B все камни с номерами, большими они в A и B совпадают. Для оставшихся конфигураций и имеем α
n
;
w(B
) < α
n−1
+ α
n−3
+ α
n−5
+ . . . = α
n−1 1
1
− α
−2
= Таким образом, для любой конфигурации естьтолько одна конечная ста- ким же весом только к ней и может привести процесс класс. См. решение задачи 529.
538. Ответ. 99 мудрецов
УЧЕБНЫЙ ГОД, 11
КЛАСС
329
Все 100 мудрецов гарантированно спастисьне могут, поскольку цвет колпака у последнего мудреца никто из них не видит.
Покажем, как можно спасти 99 мудрецов.
Белому, синему и красному цветам сопоставим числа 0, 1 и 2 соответственно. В первую минуту мудрец, стоящий позади всех, должен выкрик- нутьцвет, соответствующий остатку отделения на 3 суммы всех чисел,
сопоставленных цветам колпаков мудрецов, стоящих впереди. Тогда мудрец, стоящий непосредственно передним, сможет вычислитьцвет своего колпака, так как видит колпаки всех 98 мудрецов, стоящих впереди этот цвет они должен выкрикнутьво вторую минуту. В третью минуту мудрец,
стоящий в колонне м, вычисляет, основываясьна информации, полученной из двух предыдущих выкриков и видя колпаки 97 стоящих впереди,
цвет своего колпака, выкрикивает его, и т. д. См. решение задачи 531.
540. Пусть P Q — любое горизонтальное ребро одного из кубиков.
Обозначим через C
P вертикально расположенный прямоугольник, нижняя сторона которого — P Q, а верхняя лежит на поверхности куба. Пусть Q
— число пересечений данной ломаной с прямоугольником C
P Q
. Ребро покрасим в белый цвет, если n
P четно, ив черный, если n
P нечетно. Все остальные, те. вертикальные ребра кубиков, покрасим в белый цвет.
Докажем теперь, что приведенная раскраска удовлетворяет условию задачи.
Пусть P QRS — вертикальная грань и P Q и RS — ее горизонтальные ребра. Если ломаная не пересекает P QRS, то прямоугольники C
P Q
и
C
RS
пересекаются с ломаной в одних и тех же точках. Поэтому ребра P и RS покрашены в один цвет, и, следовательно, эта грань удовлетворяет требованию задачи. Если же ломаная пересекает прямоугольник P то n
P и отличаются на 1 и, следовательно, имеют разную четность.
Поэтому ребра P Q и RS покрашены в разные цвета, что означает выполнение условия задачи ив этом случае.
ПустьтеперьP QRS — горизонтальная грань. Объединение прямоугольников, и C
SP
естьбоковая поверхностьпаралле- лепипеда, состоящего из кубиков, расположенных в точности над гранью. Замкнутая ломаная пересекает поверхностьпараллелепи- педа четное число раз (сколько раз ломаная
заходит
внутрьпараллеле- пипеда, столько раз она и
выходит
из него).
Заметим, что ломаная не пересекает верхнюю граньпараллелепипе- да. Если грань P QRS не отмечена, то ломаная не пересекает ее. Тогда все точки пересечения ломаной с поверхностью параллелепипеда расположе-
КЛАСС
329
Все 100 мудрецов гарантированно спастисьне могут, поскольку цвет колпака у последнего мудреца никто из них не видит.
Покажем, как можно спасти 99 мудрецов.
Белому, синему и красному цветам сопоставим числа 0, 1 и 2 соответственно. В первую минуту мудрец, стоящий позади всех, должен выкрик- нутьцвет, соответствующий остатку отделения на 3 суммы всех чисел,
сопоставленных цветам колпаков мудрецов, стоящих впереди. Тогда мудрец, стоящий непосредственно передним, сможет вычислитьцвет своего колпака, так как видит колпаки всех 98 мудрецов, стоящих впереди этот цвет они должен выкрикнутьво вторую минуту. В третью минуту мудрец,
стоящий в колонне м, вычисляет, основываясьна информации, полученной из двух предыдущих выкриков и видя колпаки 97 стоящих впереди,
цвет своего колпака, выкрикивает его, и т. д. См. решение задачи 531.
540. Пусть P Q — любое горизонтальное ребро одного из кубиков.
Обозначим через C
P вертикально расположенный прямоугольник, нижняя сторона которого — P Q, а верхняя лежит на поверхности куба. Пусть Q
— число пересечений данной ломаной с прямоугольником C
P Q
. Ребро покрасим в белый цвет, если n
P четно, ив черный, если n
P нечетно. Все остальные, те. вертикальные ребра кубиков, покрасим в белый цвет.
Докажем теперь, что приведенная раскраска удовлетворяет условию задачи.
Пусть P QRS — вертикальная грань и P Q и RS — ее горизонтальные ребра. Если ломаная не пересекает P QRS, то прямоугольники C
P Q
и
C
RS
пересекаются с ломаной в одних и тех же точках. Поэтому ребра P и RS покрашены в один цвет, и, следовательно, эта грань удовлетворяет требованию задачи. Если же ломаная пересекает прямоугольник P то n
P и отличаются на 1 и, следовательно, имеют разную четность.
Поэтому ребра P Q и RS покрашены в разные цвета, что означает выполнение условия задачи ив этом случае.
ПустьтеперьP QRS — горизонтальная грань. Объединение прямоугольников, и C
SP
естьбоковая поверхностьпаралле- лепипеда, состоящего из кубиков, расположенных в точности над гранью. Замкнутая ломаная пересекает поверхностьпараллелепи- педа четное число раз (сколько раз ломаная
заходит
внутрьпараллеле- пипеда, столько раз она и
выходит
из него).
Заметим, что ломаная не пересекает верхнюю граньпараллелепипе- да. Если грань P QRS не отмечена, то ломаная не пересекает ее. Тогда все точки пересечения ломаной с поверхностью параллелепипеда расположе-
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
ны на его боковой поверхности. В этом случае сумма n
P Q
+ n
QR
+ n
RS
+
+ четна. Поэтому число сторон грани P QRS, отмеченных черным цветом, четно.
Если же грань P QRS отмечена, то одна из точек пересечения ломаной с поверхностью параллелепипеда принадлежит P QRS. Тогда сумма Q
+ n
QR
+ n
RS
+ n
SP
нечетна и, следовательно, нечетное число сторон грани P QRS окрашено в черный цвет. Ответ. Трехчленов, не имеющих корней, больше.
Пусть m n — целые корни уравнения x
2
+ ax + b = 0
. Тогда + n =
−a, mn = b, следовательно, m, n < 0, 0 < mn 1997,
|n| |m| 1997. Рассмотрим уравнение x
2
− nx + mn = 0. Его коэффициенты целые числа от 1 доте. оно принадлежит рассматриваемому множеству, ноне имеет корней, так как D = n
2
−4mn = n(n−
− 4m) < 0. Итак, любому уравнению с целыми корнями мы поставили в соответствие уравнение, не имеющее корней при этом разным уравнениям сопоставлены разные. Кроме того, уравнения x
2
+ cx + d
, где c четно,
d
нечетно и D < 0, не представимы в виде x
2
− nx + mn = 0. Значит,
уравнений, не имеющих корней, больше. Для каждой из вершин многоугольника, лежащих по одну сторону от l, отметим отрезок, высекаемый на l прямыми, на которых лежат выходящие из нее стороны. Тогда условие задачи означает, что точка P лежит внутри многоугольника тогда и только тогда, когда она принадлежит нечетному числу отмеченных отрезков.
Но каждая из точек пересечения l со сторонами многоугольника будет концом ровно одного из отмеченных отрезков, а каждая из точек пересечения с продолжением стороны многоугольника (лежащей по нужную сторону от l) — концом ровно двух отмеченных отрезков.
Следовательно, при движении точки P по прямой l четностьколиче- ства содержащих ее отмеченных отрезков изменяется при каждом пересечении границы многоугольника. Осталось заметить, что, когда P расположена так, что все точки пересечения прямых с l находятся по одну сторону от нее, количество покрывающих ее отрезков равно нулю, иона лежит вне многоугольника. Отсюда и следует утверждение задачи. Первое решение. Пусть O — центр сферы, O
1
— точка пересечения биссектрис ABC, H — ортоцентр ACD, M — точка пересечения медиан ABD и O
1
, H, M — точки касания (см. рис. Точка O
1
— центр окружности, вписанной в ABC. Пустьэта окруж- ностькасается сторон BC, CA ив точках A
1
, B
1
, соответственно. Тогда O
1
A
1
= O
1
B
1
= O
1
C
1
, следовательно, прямоугольные треугольники, равны, откуда ∠OA
1
O
1
=
∠OB
1
O
1
=
ны на его боковой поверхности. В этом случае сумма n
P Q
+ n
QR
+ n
RS
+
+ четна. Поэтому число сторон грани P QRS, отмеченных черным цветом, четно.
Если же грань P QRS отмечена, то одна из точек пересечения ломаной с поверхностью параллелепипеда принадлежит P QRS. Тогда сумма Q
+ n
QR
+ n
RS
+ n
SP
нечетна и, следовательно, нечетное число сторон грани P QRS окрашено в черный цвет. Ответ. Трехчленов, не имеющих корней, больше.
Пусть m n — целые корни уравнения x
2
+ ax + b = 0
. Тогда + n =
−a, mn = b, следовательно, m, n < 0, 0 < mn 1997,
|n| |m| 1997. Рассмотрим уравнение x
2
− nx + mn = 0. Его коэффициенты целые числа от 1 доте. оно принадлежит рассматриваемому множеству, ноне имеет корней, так как D = n
2
−4mn = n(n−
− 4m) < 0. Итак, любому уравнению с целыми корнями мы поставили в соответствие уравнение, не имеющее корней при этом разным уравнениям сопоставлены разные. Кроме того, уравнения x
2
+ cx + d
, где c четно,
d
нечетно и D < 0, не представимы в виде x
2
− nx + mn = 0. Значит,
уравнений, не имеющих корней, больше. Для каждой из вершин многоугольника, лежащих по одну сторону от l, отметим отрезок, высекаемый на l прямыми, на которых лежат выходящие из нее стороны. Тогда условие задачи означает, что точка P лежит внутри многоугольника тогда и только тогда, когда она принадлежит нечетному числу отмеченных отрезков.
Но каждая из точек пересечения l со сторонами многоугольника будет концом ровно одного из отмеченных отрезков, а каждая из точек пересечения с продолжением стороны многоугольника (лежащей по нужную сторону от l) — концом ровно двух отмеченных отрезков.
Следовательно, при движении точки P по прямой l четностьколиче- ства содержащих ее отмеченных отрезков изменяется при каждом пересечении границы многоугольника. Осталось заметить, что, когда P расположена так, что все точки пересечения прямых с l находятся по одну сторону от нее, количество покрывающих ее отрезков равно нулю, иона лежит вне многоугольника. Отсюда и следует утверждение задачи. Первое решение. Пусть O — центр сферы, O
1
— точка пересечения биссектрис ABC, H — ортоцентр ACD, M — точка пересечения медиан ABD и O
1
, H, M — точки касания (см. рис. Точка O
1
— центр окружности, вписанной в ABC. Пустьэта окруж- ностькасается сторон BC, CA ив точках A
1
, B
1
, соответственно. Тогда O
1
A
1
= O
1
B
1
= O
1
C
1
, следовательно, прямоугольные треугольники, равны, откуда ∠OA
1
O
1
=
∠OB
1
O
1
=
УЧЕБНЫЙ ГОД, КЛАСС ϕ
. Кроме того, O
1
A
1
⊥ BC, поэтому по теореме о трех перпендикулярах, OA
1
⊥ BC, те линейный угол двугранного угла с гранями BOC и BO
1
C
. С другой стороны, BOC — биссектор двугранного угла с гранями BDC и BAC (O — центр вписанной сферы, поэтому угол между гранями BDC и ABC равен 2ϕ. Аналогично, грани ADC и
ADB
наклонены к основанию ABC под углом 2ϕ. Отсюда следует, что проекция точки D на плоскость ABC равноудалена от AB, BC и и, учитывая то, что точки и C лежат по одну сторону от AB, и B от AC, и A — от BC, получаем, что O
= O
1
, те высота тет- раэдра.
A
B
C
D
A
1
B
1
C
1
M
H
O
O
1
Рис. Поскольку AB ⊥ и AB ⊥
⊥ DO
1
, то AB ⊥ DO
1
C
1
. Опустим из точки O перпендикуляры OH
1
и
OM
1
на и DC
1
. Тогда OH
1
⊥
⊥ ADC, так как OH
1
⊥ и AC (AC ⊥ DO
1
B
1
). Значит, те. Аналогично, те, и, значит, M ∈ DC
1
. Итак,
прямая DM — одновременно медиана и высота ADB, значит, AD =
= DB
. Тогда AO
1
= BO
1
, следовательно и точки C, O
1
, лежат на одной прямой.
По теореме о трех перпендикулярах CO ⊥ AD (OH ⊥ ADC и CH ⊥
⊥ AD), кроме того, CO ⊥ AB (AB ⊥ CDC
1
), поэтому CO ⊥ ADB. Но ADB, значит, точка O лежит на CM. Отсюда следует, что M центр окружности, вписанной в ADB основание конуса с вершиной описанного около сферы, — вписанная в ADB окружность, поскольку ADB). Рассмотрим CDC
1
. В нем и CM — высоты, C
1
O
— биссектриса, значит C
1
D = C
1
C
, откуда C
1
O
1
: O
1
C = C
1
M : M D =
= 1 : 2
. Центры вписанных окружностей ABC и ADB являются точками пересечения медиан, поэтому ABC и ADB — равносторонние.
Отсюда, учитывая то, что высота пирамиды попадает в центр основания, получаем, что тетраэдр — правильный.
. Кроме того, O
1
A
1
⊥ BC, поэтому по теореме о трех перпендикулярах, OA
1
⊥ BC, те линейный угол двугранного угла с гранями BOC и BO
1
C
. С другой стороны, BOC — биссектор двугранного угла с гранями BDC и BAC (O — центр вписанной сферы, поэтому угол между гранями BDC и ABC равен 2ϕ. Аналогично, грани ADC и
ADB
наклонены к основанию ABC под углом 2ϕ. Отсюда следует, что проекция точки D на плоскость ABC равноудалена от AB, BC и и, учитывая то, что точки и C лежат по одну сторону от AB, и B от AC, и A — от BC, получаем, что O
= O
1
, те высота тет- раэдра.
A
B
C
D
A
1
B
1
C
1
M
H
O
O
1
Рис. Поскольку AB ⊥ и AB ⊥
⊥ DO
1
, то AB ⊥ DO
1
C
1
. Опустим из точки O перпендикуляры OH
1
и
OM
1
на и DC
1
. Тогда OH
1
⊥
⊥ ADC, так как OH
1
⊥ и AC (AC ⊥ DO
1
B
1
). Значит, те. Аналогично, те, и, значит, M ∈ DC
1
. Итак,
прямая DM — одновременно медиана и высота ADB, значит, AD =
= DB
. Тогда AO
1
= BO
1
, следовательно и точки C, O
1
, лежат на одной прямой.
По теореме о трех перпендикулярах CO ⊥ AD (OH ⊥ ADC и CH ⊥
⊥ AD), кроме того, CO ⊥ AB (AB ⊥ CDC
1
), поэтому CO ⊥ ADB. Но ADB, значит, точка O лежит на CM. Отсюда следует, что M центр окружности, вписанной в ADB основание конуса с вершиной описанного около сферы, — вписанная в ADB окружность, поскольку ADB). Рассмотрим CDC
1
. В нем и CM — высоты, C
1
O
— биссектриса, значит C
1
D = C
1
C
, откуда C
1
O
1
: O
1
C = C
1
M : M D =
= 1 : 2
. Центры вписанных окружностей ABC и ADB являются точками пересечения медиан, поэтому ABC и ADB — равносторонние.
Отсюда, учитывая то, что высота пирамиды попадает в центр основания, получаем, что тетраэдр — правильный.
1 ... 41 42 43 44 45 46 47 48 ... 64
Второе решение.
Сделаем развертку тетраэдра ABCD (см.
рис. 251). Пустьсфера касается грани ABC в точке O — центре вписанной окружности, грани ACD ( на рис. 251) — в точке M пересечения медиан, грани BCD ( BCD
2
) — в точке H пересечения высот. По свойству касательных, проведенных к сфере из одной точки, AM = AO,
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ αα
α
β
β
α
β
β
β
γ
α
γ γ Рис. 251
CM = CO
, поэтому треугольники AMC и AOC с общей стороной равны. Отсюда ∠MAC = ∠OAC и ∠MCA = ∠OCA. Из аналогичных равенств для других пар углов получаем, что если ∠OAC = ∠OAB = α,
∠OBA = ∠OBC = β и ∠OCB = ∠OCA = γ, то ∠CAM = α, ∠CBH =
= β
, ∠ACM = ∠BCH = γ. Далее, из ABC: 2α + 2β + 2γ = 180
◦
, те, а из BKC: β + γ + ∠HCK = 90
◦
, значит, ∠HCK = Отсюда ∠KBD
2
= α
, ∠HD
2
C = β
, ∠HD
2
B = углы с перпендикулярными сторонами, и тогда ∠MCD
1
=
∠HCD
2
= α
, ∠MD
1
C =
=
∠HD
2
C = β
. Теперьиз D
1
P C
: ∠D
1
P C = 180
◦
− (α + β + γ) = значит, медиана является и высотой AD
1
C
. Отсюда AD
1
= и α = γ (∠MAC = ∠MCA). Следовательно, AD
1
T =
CD
1
S
и,
значит, ∠D
1
AT =
∠D
1
CS = α
; кроме того, D
1
P
— биссектриса угла. Мы получили, что медиана AT является и биссектрисой те. Итак, α = β = γ = Отсюда следует, что грани ABC, ACD и BCD тетраэдра — правильные треугольники, те, значит, тетраэдр правильный. Занумеруем горизонтали и вертикали по порядку, начиная от края,
и назовем полями клетки, стоящие на пересечении рядов с нечетными номерами. В частности, все клетки в углах — поля. Заметим, что дырка будет перемещаться только по полям.
Если поле A покрыто доминошкой, то одна из узких сторон доминош- ки граничит с другим полем B; проведем стрелку из центра A в центр B.
α
β
β
α
β
β
β
γ
α
γ γ Рис. 251
CM = CO
, поэтому треугольники AMC и AOC с общей стороной равны. Отсюда ∠MAC = ∠OAC и ∠MCA = ∠OCA. Из аналогичных равенств для других пар углов получаем, что если ∠OAC = ∠OAB = α,
∠OBA = ∠OBC = β и ∠OCB = ∠OCA = γ, то ∠CAM = α, ∠CBH =
= β
, ∠ACM = ∠BCH = γ. Далее, из ABC: 2α + 2β + 2γ = 180
◦
, те, а из BKC: β + γ + ∠HCK = 90
◦
, значит, ∠HCK = Отсюда ∠KBD
2
= α
, ∠HD
2
C = β
, ∠HD
2
B = углы с перпендикулярными сторонами, и тогда ∠MCD
1
=
∠HCD
2
= α
, ∠MD
1
C =
=
∠HD
2
C = β
. Теперьиз D
1
P C
: ∠D
1
P C = 180
◦
− (α + β + γ) = значит, медиана является и высотой AD
1
C
. Отсюда AD
1
= и α = γ (∠MAC = ∠MCA). Следовательно, AD
1
T =
CD
1
S
и,
значит, ∠D
1
AT =
∠D
1
CS = α
; кроме того, D
1
P
— биссектриса угла. Мы получили, что медиана AT является и биссектрисой те. Итак, α = β = γ = Отсюда следует, что грани ABC, ACD и BCD тетраэдра — правильные треугольники, те, значит, тетраэдр правильный. Занумеруем горизонтали и вертикали по порядку, начиная от края,
и назовем полями клетки, стоящие на пересечении рядов с нечетными номерами. В частности, все клетки в углах — поля. Заметим, что дырка будет перемещаться только по полям.
Если поле A покрыто доминошкой, то одна из узких сторон доминош- ки граничит с другим полем B; проведем стрелку из центра A в центр B.
УЧЕБНЫЙ ГОД, 9
КЛАСС
333
Заметим, что если B — дырка, то, сдвинув доминошку по стрелке, мы переместим дырку на Проведем так стрелки из каждого поля (кроме дырки. Если естьпуть по стрелкам из поляна дырку, можно перегнатьдырку на A, сдвинув сперва доминошку вдольпоследней стрелки пути, затем — вдольпредпо- следней, и т. д.
Путьпо стрелкам либо приходит на дырку, либо зацикливается. Докажем, что доминошки, соответствующие циклу, охватывают многоугольник с нечетным числом клеток внутри.
Действительно, рассмотрим цикл как линию из стрелок. Если постро- итьновую квадратную сетку с узлами в центрах полей, то цикл пройдет по линиям этой сетки и будет охватыватьмногоугольник, который сетка разбивает на квадраты со стороной 2. Докажем наше утверждение индукцией по числу квадратов. Для одного квадрата оно верно — если выложитьдо- мино по границе, внутри будет только одна клетка. Многоугольник же из
k
квадратов получается добавлением квадрата на границе многоугольника из k − 1 квадрата, и нетрудно проверить, что при выкладывании границы доминошками внутри добавляется 2 или 4 клетки.
Итак, цикл должен охватыватьмногоугольник с нечетным числом клеток внутри. Но это невозможно, так как этот многоугольник должен быть заполнен целым числом доминошек, те. содержатьчетное число клеток,
так как дырка исходно расположена на краю.
Значит, циклов нет, и существует путьпо стрелкам, приходящий на дырку г класс. Абсциссы и точек пересечения параболы и прямой y = удовлетворяют уравнению+ (p
− 1)x + q = По теореме Виета x
1
+ x
2
= 1
− p. Аналогично получаем, что абсциссы и точек пересечения параболы и прямой y = 2x связаны соотношением+ x
4
= 2
− Если x
1
< x
2
, а x
3
< x
4
, то проекция левой дуги равна x
1
− x
3
, а правой — x
4
− см. рис. 252). Разностьих равна (x
4
− x
2
)
− (x
1
−
− x
3
) = (x
3
+ x
4
)
− (x
1
+ x
2
) = (2
− p) − (1 − p) = 1.
546. Отметим углы параллелограммов, являющиеся частью углов многоугольника. Пусть в многоугольнике n сторон. Тогда сумма отмеченных углов равна 180
◦
· (n − 2). К каждой стороне многоугольника примыка-
КЛАСС
333
Заметим, что если B — дырка, то, сдвинув доминошку по стрелке, мы переместим дырку на Проведем так стрелки из каждого поля (кроме дырки. Если естьпуть по стрелкам из поляна дырку, можно перегнатьдырку на A, сдвинув сперва доминошку вдольпоследней стрелки пути, затем — вдольпредпо- следней, и т. д.
Путьпо стрелкам либо приходит на дырку, либо зацикливается. Докажем, что доминошки, соответствующие циклу, охватывают многоугольник с нечетным числом клеток внутри.
Действительно, рассмотрим цикл как линию из стрелок. Если постро- итьновую квадратную сетку с узлами в центрах полей, то цикл пройдет по линиям этой сетки и будет охватыватьмногоугольник, который сетка разбивает на квадраты со стороной 2. Докажем наше утверждение индукцией по числу квадратов. Для одного квадрата оно верно — если выложитьдо- мино по границе, внутри будет только одна клетка. Многоугольник же из
k
квадратов получается добавлением квадрата на границе многоугольника из k − 1 квадрата, и нетрудно проверить, что при выкладывании границы доминошками внутри добавляется 2 или 4 клетки.
Итак, цикл должен охватыватьмногоугольник с нечетным числом клеток внутри. Но это невозможно, так как этот многоугольник должен быть заполнен целым числом доминошек, те. содержатьчетное число клеток,
так как дырка исходно расположена на краю.
Значит, циклов нет, и существует путьпо стрелкам, приходящий на дырку г класс. Абсциссы и точек пересечения параболы и прямой y = удовлетворяют уравнению+ (p
− 1)x + q = По теореме Виета x
1
+ x
2
= 1
− p. Аналогично получаем, что абсциссы и точек пересечения параболы и прямой y = 2x связаны соотношением+ x
4
= 2
− Если x
1
< x
2
, а x
3
< x
4
, то проекция левой дуги равна x
1
− x
3
, а правой — x
4
− см. рис. 252). Разностьих равна (x
4
− x
2
)
− (x
1
−
− x
3
) = (x
3
+ x
4
)
− (x
1
+ x
2
) = (2
− p) − (1 − p) = 1.
546. Отметим углы параллелограммов, являющиеся частью углов многоугольника. Пусть в многоугольнике n сторон. Тогда сумма отмеченных углов равна 180
◦
· (n − 2). К каждой стороне многоугольника примыка-
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
x
y
0
y
=
x
y
=
2x
x
3
x
1
x
2
x
4
Рис. Рис. ют стороной по два отмеченных угла (см. рис. 253), их сумма, очевидно,
не менее 180
◦
. Просуммировав такие пары по всем сторонам, получим не менее 180
◦
· n, те, по крайней мерена больше, чем при подсчете другим способом. Избыток возникает за счет того, что некоторые углы посчитаны дважды, а именно те, которые примыкают сразу к двум сторонам. Поскольку каждый такой угол меньше 180
◦
, то таких углов не менее трех. Но вершины таких углов как рази являются хорошими вершинами многоугольника. Ответ. Найдутся.
Подойдут, например, числа a = 5555554445, b = 5554445555, c =
= 4445555555
. Убедимся в этом S(a + b) = S(11110000000) < 5, S(a +
+ c) = S(10001110000) < 5
, S(b + c) = S(10000001110) < 5, S(a + b +
+ c) = S(15555555555) = 51 > Как можно найти такие числа Заметим, что S(2(a + b + c)) = S((a +
+ b) + (a + c) + (b + c))
S(a + b) + S(a + c) + S(b + c) 12, т. е.
число n = 2(a + b + c) при делении на 2 должно резко увеличиватьсвою сумму цифр. Такое возможно, если в числе много единиц, тогда в частном появится много пятерок. Возьмем, например, n = 31111111110, тогда) = 12
, а S
n
2
= 51
. Разложим n натри слагаемых с суммой цифр и меньших, а затем решим систему уравнений a + b = 11110000000, a + c = 10001110000, b +
+ c = 10000001110
548. Ответ. Верно.
Занумеруем всевозможные начальные положения, те. пары (лабиринт, положение ладьи) — их конечное число. Составим программу Π
1
x
y
0
y
=
x
y
=
2x
x
3
x
1
x
2
x
4
Рис. Рис. ют стороной по два отмеченных угла (см. рис. 253), их сумма, очевидно,
не менее 180
◦
. Просуммировав такие пары по всем сторонам, получим не менее 180
◦
· n, те, по крайней мерена больше, чем при подсчете другим способом. Избыток возникает за счет того, что некоторые углы посчитаны дважды, а именно те, которые примыкают сразу к двум сторонам. Поскольку каждый такой угол меньше 180
◦
, то таких углов не менее трех. Но вершины таких углов как рази являются хорошими вершинами многоугольника. Ответ. Найдутся.
Подойдут, например, числа a = 5555554445, b = 5554445555, c =
= 4445555555
. Убедимся в этом S(a + b) = S(11110000000) < 5, S(a +
+ c) = S(10001110000) < 5
, S(b + c) = S(10000001110) < 5, S(a + b +
+ c) = S(15555555555) = 51 > Как можно найти такие числа Заметим, что S(2(a + b + c)) = S((a +
+ b) + (a + c) + (b + c))
S(a + b) + S(a + c) + S(b + c) 12, т. е.
число n = 2(a + b + c) при делении на 2 должно резко увеличиватьсвою сумму цифр. Такое возможно, если в числе много единиц, тогда в частном появится много пятерок. Возьмем, например, n = 31111111110, тогда) = 12
, а S
n
2
= 51
. Разложим n натри слагаемых с суммой цифр и меньших, а затем решим систему уравнений a + b = 11110000000, a + c = 10001110000, b +
+ c = 10000001110
548. Ответ. Верно.
Занумеруем всевозможные начальные положения, те. пары (лабиринт, положение ладьи) — их конечное число. Составим программу Π
1
УЧЕБНЫЙ ГОД, 9
КЛАСС
335
обхода всех полей для первого начального положения. Предположим теперь, что начальным было положение № 2. Применим программу Π
1
, и если ладья обошла не все поля, допишем в конце несколько команд, чтобы обойти оставшиеся поля. Получим программу Π
2
. Применим программу
Π
2
к ладье в м начальном положении, снова допишем программу и т. д 2
3 Рис. 254
549. Ответ. За 24 часа.
Отметим на одном циферблате положения часовых стрелок всех часов. Циферблат разобьется на 5 секторов. Занумеруем их по кругу
(см. рис. 254). Пустьчасовая стрелка проходит секторы за время x
1
, x
2
, x
3
, x
4
, соответственно (некоторые из этих чисел, возможно,
нулевые). Заметим, что если мы станем уста- навливатьна всех часах время, соответствующее положению внутри сектора, то каждая часовая стрелка пройдет через начало сектора. Это значит, что суммарное время перевода окажется заведомо больше, чем если бы мы устанавливали все часы на начало сектора.
Обозначим через суммарное время, необходимое для установки всех часов на начало го сектора. Ясно, что время перевода отдельной стрелки является суммой некоторых x
j
. Например, время перевода на начало первого сектора равно для пятых часов и x
2
+ x
3
+ x
4
+ для вторых. Тогда (x
2
+x
3
+x
4
+x
5
)+(x
3
+x
4
+x
5
)+(x
4
+x
5
)+x
5
= Остальные выражаются аналогично. Тогда+ S
2
+ S
3
+ S
4
+ S
5
= (1 + 2 + 3 + 4)(x
1
+ x
2
+ x
3
+ x
4
+ x
5
) =
= 10
· 12 = 120 часов.
Поэтому наименьшая сумма не превосходит 120 : 5 = 24 часа. С другой стороны, если все секторы одинаковы (например, часы показывают 12 ч ч 24 мин, 4 ч 48 мин, 7 ч 12 мини ч 36 мин, то все равны 24 часам,
поэтому менее, чем 24 часами не обойтись. Проведем через точку E прямую, параллельную AB. Пустьона пересекает ив точках P и Q соответственно. Поскольку QE и параллельны сторонами соответственно, то по теореме Фалеса
MQ
MA
=
ME
MB
=
ML
MC
, поэтому 1
. Аналогично, поскольку D
P Q, тот. е. ED — это медиана в треугольнике EL
. Однако из параллельности EP и EL сторонами соответственно следует равенство углов ∠EP L = ∠ABL, ∠ELP = ∠LBC, но = ∠LBC, поэтому ∠EP L = ∠ELP . Тем самым, треугольник
КЛАСС
335
обхода всех полей для первого начального положения. Предположим теперь, что начальным было положение № 2. Применим программу Π
1
, и если ладья обошла не все поля, допишем в конце несколько команд, чтобы обойти оставшиеся поля. Получим программу Π
2
. Применим программу
Π
2
к ладье в м начальном положении, снова допишем программу и т. д 2
3 Рис. 254
549. Ответ. За 24 часа.
Отметим на одном циферблате положения часовых стрелок всех часов. Циферблат разобьется на 5 секторов. Занумеруем их по кругу
(см. рис. 254). Пустьчасовая стрелка проходит секторы за время x
1
, x
2
, x
3
, x
4
, соответственно (некоторые из этих чисел, возможно,
нулевые). Заметим, что если мы станем уста- навливатьна всех часах время, соответствующее положению внутри сектора, то каждая часовая стрелка пройдет через начало сектора. Это значит, что суммарное время перевода окажется заведомо больше, чем если бы мы устанавливали все часы на начало сектора.
Обозначим через суммарное время, необходимое для установки всех часов на начало го сектора. Ясно, что время перевода отдельной стрелки является суммой некоторых x
j
. Например, время перевода на начало первого сектора равно для пятых часов и x
2
+ x
3
+ x
4
+ для вторых. Тогда (x
2
+x
3
+x
4
+x
5
)+(x
3
+x
4
+x
5
)+(x
4
+x
5
)+x
5
= Остальные выражаются аналогично. Тогда+ S
2
+ S
3
+ S
4
+ S
5
= (1 + 2 + 3 + 4)(x
1
+ x
2
+ x
3
+ x
4
+ x
5
) =
= 10
· 12 = 120 часов.
Поэтому наименьшая сумма не превосходит 120 : 5 = 24 часа. С другой стороны, если все секторы одинаковы (например, часы показывают 12 ч ч 24 мин, 4 ч 48 мин, 7 ч 12 мини ч 36 мин, то все равны 24 часам,
поэтому менее, чем 24 часами не обойтись. Проведем через точку E прямую, параллельную AB. Пустьона пересекает ив точках P и Q соответственно. Поскольку QE и параллельны сторонами соответственно, то по теореме Фалеса
MQ
MA
=
ME
MB
=
ML
MC
, поэтому 1
. Аналогично, поскольку D
P Q, тот. е. ED — это медиана в треугольнике EL
. Однако из параллельности EP и EL сторонами соответственно следует равенство углов ∠EP L = ∠ABL, ∠ELP = ∠LBC, но = ∠LBC, поэтому ∠EP L = ∠ELP . Тем самым, треугольник
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ равнобедренный, и медиана ED является высотой, что и требо- валось.
A
B
C
L
M
P
D
E
Q
Рис. 255
551. Ответ.
3N
4
звена (здесь целая частьчисла Заметим, что в каждой паре звеньев, бывших соседями, но переставших ими быть, по крайней мере одно звено должно бытьраскры- то. Это же верно для пары несосед- них звеньев, которые должны стать соседями.
Если разбитьзвенья на группы так, чтобы любые два звена в группе являлисьили впоследствии стали соседними (ноне то и другое вместе),
то из каждой такой группы может остаться нераскрытым не более одного звена. Такой группой, например, являются 4 звена, которые в старой цепочке следовали в порядке 1–2–3–4, а в новой должны бытьв порядке. Другие примеры в старой 1–2–3, в новой 1–3 (ас ними не связано, или в старой 1–2, а в новой они не связаны.
Разбив мысленно цепочку на четверки, с возможным остатком вили звена, и потребовав такой порядок, при котором четверки и остаток изменяются указанным образом, заказчица обеспечит раскрытие не менее
3N
4
звеньев (лишнее звено из остатка прицепляется с другого конца).
С другой стороны, раскрыв в исходной цепочке каждое второе звено,
ювелир мысленно разобьет вторую цепочку на части, где в сумме не менее половины всех звеньев. В каждой части надо раскрыть не более половины звеньев, поэтому не менее четверти звеньев можно оставить нераскрытыми. Одновременно с операциями на доске будем вести записьв тетради. Но вместо каждого числа x, появляющегося на доске, будем писать в тетради число и b — исходные числа. Когда на доске пара чисел, y)
, где x > y, заменяется на пару − y
, в тетради происходит замена те, как в алгоритме Евклида, большее число заменяется на разность.
Следовательно, на каком-то шаге мы запишем в тетрадь пару чисел, равных НОД(a, b). В это же время оба числа на доске станут равными
ab
НОД(a, b)
, те. НОК(a, b).
A
B
C
L
M
P
D
E
Q
Рис. 255
551. Ответ.
3N
4
звена (здесь целая частьчисла Заметим, что в каждой паре звеньев, бывших соседями, но переставших ими быть, по крайней мере одно звено должно бытьраскры- то. Это же верно для пары несосед- них звеньев, которые должны стать соседями.
Если разбитьзвенья на группы так, чтобы любые два звена в группе являлисьили впоследствии стали соседними (ноне то и другое вместе),
то из каждой такой группы может остаться нераскрытым не более одного звена. Такой группой, например, являются 4 звена, которые в старой цепочке следовали в порядке 1–2–3–4, а в новой должны бытьв порядке. Другие примеры в старой 1–2–3, в новой 1–3 (ас ними не связано, или в старой 1–2, а в новой они не связаны.
Разбив мысленно цепочку на четверки, с возможным остатком вили звена, и потребовав такой порядок, при котором четверки и остаток изменяются указанным образом, заказчица обеспечит раскрытие не менее
3N
4
звеньев (лишнее звено из остатка прицепляется с другого конца).
С другой стороны, раскрыв в исходной цепочке каждое второе звено,
ювелир мысленно разобьет вторую цепочку на части, где в сумме не менее половины всех звеньев. В каждой части надо раскрыть не более половины звеньев, поэтому не менее четверти звеньев можно оставить нераскрытыми. Одновременно с операциями на доске будем вести записьв тетради. Но вместо каждого числа x, появляющегося на доске, будем писать в тетради число и b — исходные числа. Когда на доске пара чисел, y)
, где x > y, заменяется на пару − y
, в тетради происходит замена те, как в алгоритме Евклида, большее число заменяется на разность.
Следовательно, на каком-то шаге мы запишем в тетрадь пару чисел, равных НОД(a, b). В это же время оба числа на доске станут равными
ab
НОД(a, b)
, те. НОК(a, b).
УЧЕБНЫЙ ГОД, КЛАСС класс. Из рис. 16 следует, что a > 0. Если y = p и y = q — уравнения заданных прямых, то абсциссы точек A, D и E — корни x
1
< x
2
< уравнения ax
3
+ bx
2
+ cx + d
− p = 0, а точек B, C и F — корни X
1
<
< X
2
< уравнения aX
3
+ bX
2
+ cX + d
− q = 0. По теореме Виета
x
1
+ x
2
+ x
3
=
−
b
a
= X
1
+ X
2
+ X
3
. Отсюда x
2
− X
2
= (X
1
− x
1
) +
+ (X
3
− x
3
)
, что и требовалось доказать. Обозначим через и данные многоугольники. Предположим,
что они имеют общую внутреннюю точку. Возможны два случая) Один многоугольник содержится внутри другого, скажем, лежит внутри F
2
. Пусть A — одна из вершин F
1
. Тогда, как легко видеть, найдутся три вершины P , Q, R многоугольника такие, что треугольник P содержит A случай, когда A лежит на стороне треугольника P QR, легко приводит к противоречию. При этом хотя бы один из углов P AQ, больше 90
◦
. Пусть, для определенности, ∠P AQ
◦
. Тогда имеем P Q
2
AP
2
+ AQ
2
. Получаем, что, вопреки условию, один из отрезков и AQ не больше противоречие) Сторона одного многоугольника пересекает сторону другого. Пусть,
например, сторона AB многоугольника пересекает сторону P Q многоугольника. Пусть AP BQ — выпуклый четырехугольник (случай, когда среди точек A, B, P , Q найдутся три, лежащие на одной прямой, легко рассматривается. Хотя бы один из его углов, скажем, P AQ, не меньше. Тогда 1 P Q
2
AP
2
+ AQ
2
, следовательно, один из отрезков и AQ не больше. Получаем противоречие. 1. Докажем, что стороны треугольника параллельны соответствующим сторонам треугольника ABC. Пусть AC > AB. Имеем OL = и ∠P OB = ∠ROB см. рис. 256), поэтому ∠K
a
OR =
= 2
∠LOB. Угол LOB внешний в треугольнике AOB, значит ∠K
a
OR =
= 2(α/2 + β/2) = α + β
. Случай AC < AB разбирается аналогично.
Подобными же рассуждениями получаем, что ∠K
b
OR = α + β
. Следовательно, точки и симметричны относительно прямой OR, поэтому прямые и AB параллельны.
Итак, соответствующие стороны треугольников и параллельны (M
a
, M
b
, M
c
— середины сторон треугольника, поэтому эти треугольники гомотетичны. Центр этой гомотетии является общей точкой прямых M
a
K
a
, и M
c
K
c
2. Пустьпрямая вторично пересекает вписанную в треугольник
ABC
окружностьв точке T . Будем считать, что AC > AB. Докажем, что описанная вокруг треугольника T K
a
L
окружностьпроходит через осно-
1
< x
2
< уравнения ax
3
+ bx
2
+ cx + d
− p = 0, а точек B, C и F — корни X
1
<
< X
2
< уравнения aX
3
+ bX
2
+ cX + d
− q = 0. По теореме Виета
x
1
+ x
2
+ x
3
=
−
b
a
= X
1
+ X
2
+ X
3
. Отсюда x
2
− X
2
= (X
1
− x
1
) +
+ (X
3
− x
3
)
, что и требовалось доказать. Обозначим через и данные многоугольники. Предположим,
что они имеют общую внутреннюю точку. Возможны два случая) Один многоугольник содержится внутри другого, скажем, лежит внутри F
2
. Пусть A — одна из вершин F
1
. Тогда, как легко видеть, найдутся три вершины P , Q, R многоугольника такие, что треугольник P содержит A случай, когда A лежит на стороне треугольника P QR, легко приводит к противоречию. При этом хотя бы один из углов P AQ, больше 90
◦
. Пусть, для определенности, ∠P AQ
◦
. Тогда имеем P Q
2
AP
2
+ AQ
2
. Получаем, что, вопреки условию, один из отрезков и AQ не больше противоречие) Сторона одного многоугольника пересекает сторону другого. Пусть,
например, сторона AB многоугольника пересекает сторону P Q многоугольника. Пусть AP BQ — выпуклый четырехугольник (случай, когда среди точек A, B, P , Q найдутся три, лежащие на одной прямой, легко рассматривается. Хотя бы один из его углов, скажем, P AQ, не меньше. Тогда 1 P Q
2
AP
2
+ AQ
2
, следовательно, один из отрезков и AQ не больше. Получаем противоречие. 1. Докажем, что стороны треугольника параллельны соответствующим сторонам треугольника ABC. Пусть AC > AB. Имеем OL = и ∠P OB = ∠ROB см. рис. 256), поэтому ∠K
a
OR =
= 2
∠LOB. Угол LOB внешний в треугольнике AOB, значит ∠K
a
OR =
= 2(α/2 + β/2) = α + β
. Случай AC < AB разбирается аналогично.
Подобными же рассуждениями получаем, что ∠K
b
OR = α + β
. Следовательно, точки и симметричны относительно прямой OR, поэтому прямые и AB параллельны.
Итак, соответствующие стороны треугольников и параллельны (M
a
, M
b
, M
c
— середины сторон треугольника, поэтому эти треугольники гомотетичны. Центр этой гомотетии является общей точкой прямых M
a
K
a
, и M
c
K
c
2. Пустьпрямая вторично пересекает вписанную в треугольник
ABC
окружностьв точке T . Будем считать, что AC > AB. Докажем, что описанная вокруг треугольника T K
a
L
окружностьпроходит через осно-
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ P
K
a
O
R
A
C
B
L Рис. Рис. 257
вание H высоты треугольника ABC. Для этого достаточно проверитьвы- полнение равенства M
a
L
· M
a
H = M
a
P
2
, так как M
a
P
2
= M
a
K
a
· см. рис. Это можно сделать, выразив длины отрезков M
a
P
, и через стороны треугольника ABC. Мы докажем его, пользуюсь известными свойствами точки касания со стороной BC соответствующей вневпи- санной окружности треугольника точка симметрична P относительно и отрезок пересекает вписанную окружностьв точке, диаметрально противоположной точке P . Поэтому прямые и параллельны центр вписанной окружности, см. рис. 258).
A
C
B
L Рис. Рис. Пользуясь параллельностью прямых AH и OP , равенством M
a
P
=
= и теоремой Фалеса, получаем H
LP
=
=
P M
a
+ P H
M
a
L + LP
=
M
a
H
M
a
P
, что и требовалось.
Так как четырехугольник T вписанный, углы M
a
T и равны. Угол легко выражается через углы треугольника ABC:
∠M
a
LK
a
= 180
◦
− 2∠ALB = β − γ см. рис. 259). Рассмотрим те- перьчетырехугольник M
b
T HM
a
. Заметим, что ∠HCA = ∠CHM
b
=
= треугольник CM
b
H
— равнобедренный ), ∠CM
a
M
b
= β
. По
K
a
O
R
A
C
B
L Рис. Рис. 257
вание H высоты треугольника ABC. Для этого достаточно проверитьвы- полнение равенства M
a
L
· M
a
H = M
a
P
2
, так как M
a
P
2
= M
a
K
a
· см. рис. Это можно сделать, выразив длины отрезков M
a
P
, и через стороны треугольника ABC. Мы докажем его, пользуюсь известными свойствами точки касания со стороной BC соответствующей вневпи- санной окружности треугольника точка симметрична P относительно и отрезок пересекает вписанную окружностьв точке, диаметрально противоположной точке P . Поэтому прямые и параллельны центр вписанной окружности, см. рис. 258).
A
C
B
L Рис. Рис. Пользуясь параллельностью прямых AH и OP , равенством M
a
P
=
= и теоремой Фалеса, получаем H
LP
=
=
P M
a
+ P H
M
a
L + LP
=
M
a
H
M
a
P
, что и требовалось.
Так как четырехугольник T вписанный, углы M
a
T и равны. Угол легко выражается через углы треугольника ABC:
∠M
a
LK
a
= 180
◦
− 2∠ALB = β − γ см. рис. 259). Рассмотрим те- перьчетырехугольник M
b
T HM
a
. Заметим, что ∠HCA = ∠CHM
b
=
= треугольник CM
b
H
— равнобедренный ), ∠CM
a
M
b
= β
. По
УЧЕБНЫЙ ГОД, 10
КЛАСС
339
этому ∠M
a
M
b
H = β
− γ, значит M
a
T HM
b
— вписанный (∠M
a
T H =
=
∠M
a
M
b
H
) и, следовательно, ∠M
a
T M
b
= M
a
HM
b
= Обозначим через K точку пересечения отрезка T со вписанной окружностью. Так как вписанный в окружность угол K
a
T равен γ, а дуга вписанной окружности равна α + β это было доказано ранее),
точки и K симметричны относительно прямой OR. Но точки и как отмечено ранее, также симметричны относительно этой прямой. Значит точки K и совпадают, что означает, что прямые и пересекаются в точке T вписанной окружности.
Замечание. Из доказанного следует известная теорема Фейербаха:
окружностьдевяти точек (те. окружность) и вписанная окруж- ностькасаются (точкой касания является центр гомотетии T ).
КЛАСС
339
этому ∠M
a
M
b
H = β
− γ, значит M
a
T HM
b
— вписанный (∠M
a
T H =
=
∠M
a
M
b
H
) и, следовательно, ∠M
a
T M
b
= M
a
HM
b
= Обозначим через K точку пересечения отрезка T со вписанной окружностью. Так как вписанный в окружность угол K
a
T равен γ, а дуга вписанной окружности равна α + β это было доказано ранее),
точки и K симметричны относительно прямой OR. Но точки и как отмечено ранее, также симметричны относительно этой прямой. Значит точки K и совпадают, что означает, что прямые и пересекаются в точке T вписанной окружности.
Замечание. Из доказанного следует известная теорема Фейербаха:
окружностьдевяти точек (те. окружность) и вписанная окруж- ностькасаются (точкой касания является центр гомотетии T ).
1 ... 42 43 44 45 46 47 48 49 ... 64
556. Предположим противное. Тогда найдется такое n (n > 1), что любой набор из n − 1 выделенного подмножества имеет общий элемент и существует выделенных подмножеств A
1
, A
2
, . . . , A
n
, не имеющих общего элемента. Исключим из набора A
1
, A
2
, . . . , множество A
i
. Оставшиеся имеют общий элемент, который мы обозначим через x
i
. Заметим, что при i = j. Каждое из множеств содержит все элементы множества, кроме x
i
, поэтому, если из множеств исключить элементы множества {x
1
, x
2
, . . . , x
n
}, тов каждом из них останется 2k −
− n + 1 элемент (в частности, n 2k + 1). Следовательно, объединение множеств A
1
, A
2
, . . . , состоит не более чем из n + n(2k − n + 1) =
= n(2k + 2
− n) элементов. Максимальное значение выражения n(2k +
+ 2
−n) равно (k+1)
2
. Но тогда, по условию задачи, все должны иметь общий элемент. Противоречие. Ответ. Нельзя.
Допустим, что можно, и рассмотрим способ добиться этого за наименьшее количество действий. Пусть a
k
, b
k
— числа, получавшиеся из и 98 после го действия, s — число действий. Тогда a
s
= b
s
= итак как мы рассматриваем оптимальный способ. Действия,
проведенные над и b
s−1
, различны. Значит, m = и нам шаге мы имели числа a
s−1
= и b
s−1
= n
2
− 1 (или наоборот на дальнейшее решение это не влияет. Общее количество s действий не больше,
чем n − 18, так как на s − 1 шаге мы получили n, а каждый шаг увеличивает числа по крайней мерена. Тогда n
2
− 1 могло получиться только последовательным прибавлением единиц, так как от ближайшего квадрата добудет единицы. Следовательно, b
1
> (n
− поэтому все числа b
1
, . . . , не являются полными квадратами. Поэтому, с другой стороны a
s
= a
2
s−1
19 2
. Противоречие
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Переписав выражение ((x ∗ y) ∗ z) ∗ t двумя способами, получим равенство (x + y + z) ∗ t = (x ∗ y) + z + t. Подставив в него x = y = имеем z ∗ t = z + t + C, где C = 0 ∗ 0. Тогда (x ∗ y) ∗ z = (x + y + C) +
+ z + C = x + y + z
, откуда C = 0.
559. Будем говорить, что три вершины угольника (n > 3), через которые проходит описанная окружность, образуют отмеченный треугольник. Докажем, что все отмеченные треугольники образуют триангуляцию многоугольника, те. разбиение многоугольника непересекающими- ся диагоналями на треугольники. Это следует из следующих свойств 1) и) отмеченных треугольников) Никакие два отмеченных треугольника не имеют общей внутренней точки. Действительно, если и A
2
B
2
C
2
— различные отмеченные треугольники, аи сооответствующие описанные окружности, то точки A
1
, B
1
, расположены на дуге окружности S
1
, лежащей внутри, а точки A
2
,B
2
, C
2
— на дуге окружности S
2
, лежащей внутри S
1
(см.
рис. 260) и утверждение очевидно. Рассуждения не меняются, если одна или две вершины наших треугольников совпадают.
A
1
B
1
C
1
A
2
B
2
C
2
S
2
S
1
Рис. 260 2) Если ABC — отмеченный треугольники диагональ угольника, ток стороне примыкает еще один отмеченный треугольник. В
самом деле, рассмотрим вершины n-угольника,
лежащие сточкой по разные стороны от Среди этих вершин выберем такую вершину что угол ADB наименьший (из условия, что никакие четыре вершины не лежат на одной окружности, следует единственностьтакой вершины).
Легко понять, что окружность, проходящая через точки A, B и D, будет описанной для угольника, соответственно треугольник ABD отмечен- ный.
Далее будем называтьотмеченный треугольник граничным соответственно внутренним, если соответствующая описанная окружность граничная (внутренняя. Пусть Γ — число граничных треугольников, B
— число внутренних, Π — число оставшихся отмеченных треугольников
(назовем их простыми. Каждая из n сторон угольника принадлежит одному из треугольников, причем граничным треугольникам принадлежат по две стороны, простым — по одной, а внутренним — ни одной. Отсюда получим соотношение + Π = Так как любая триангуляция состоит из n − 2 треугольников, то + Π + B = n
− 2.
(2)
+ z + C = x + y + z
, откуда C = 0.
559. Будем говорить, что три вершины угольника (n > 3), через которые проходит описанная окружность, образуют отмеченный треугольник. Докажем, что все отмеченные треугольники образуют триангуляцию многоугольника, те. разбиение многоугольника непересекающими- ся диагоналями на треугольники. Это следует из следующих свойств 1) и) отмеченных треугольников) Никакие два отмеченных треугольника не имеют общей внутренней точки. Действительно, если и A
2
B
2
C
2
— различные отмеченные треугольники, аи сооответствующие описанные окружности, то точки A
1
, B
1
, расположены на дуге окружности S
1
, лежащей внутри, а точки A
2
,B
2
, C
2
— на дуге окружности S
2
, лежащей внутри S
1
(см.
рис. 260) и утверждение очевидно. Рассуждения не меняются, если одна или две вершины наших треугольников совпадают.
A
1
B
1
C
1
A
2
B
2
C
2
S
2
S
1
Рис. 260 2) Если ABC — отмеченный треугольники диагональ угольника, ток стороне примыкает еще один отмеченный треугольник. В
самом деле, рассмотрим вершины n-угольника,
лежащие сточкой по разные стороны от Среди этих вершин выберем такую вершину что угол ADB наименьший (из условия, что никакие четыре вершины не лежат на одной окружности, следует единственностьтакой вершины).
Легко понять, что окружность, проходящая через точки A, B и D, будет описанной для угольника, соответственно треугольник ABD отмечен- ный.
Далее будем называтьотмеченный треугольник граничным соответственно внутренним, если соответствующая описанная окружность граничная (внутренняя. Пусть Γ — число граничных треугольников, B
— число внутренних, Π — число оставшихся отмеченных треугольников
(назовем их простыми. Каждая из n сторон угольника принадлежит одному из треугольников, причем граничным треугольникам принадлежат по две стороны, простым — по одной, а внутренним — ни одной. Отсюда получим соотношение + Π = Так как любая триангуляция состоит из n − 2 треугольников, то + Π + B = n
− 2.
(2)
УЧЕБНЫЙ ГОД, 10
КЛАСС
341
Вычитая (2) из (1), получаем Γ − B = 2, что и требовалось. Ответ. Удачная расстановка единственна — все числа равны +Первое решение. Докажем индукцией последующее утверждение:
если в таблице из 2
n
−1 столбцов и k строк (k+1 не делится на 3) расставлены числа ±1 так, что выполняется условие задачи, то все числа таблицы равны +1. При n = 1 имеем один столбец высоты k. Пустьв нем стоят числа a
1
, a
2
, . . . , a
n
— по порядку сверху вниз. Тогда a
1
= условие задачи для первой клетки, a
2
= a
1
a
3
, следовательно a
3
= 1
, 1 = a
3
= следовательно a
4
= a
2
= a
1
. Итак далее. Получаем, что все числа, стоящие в клетках с номером, кратным трем, равны 1, а все остальные равны. Поскольку k + 1 не делится на 3, то возможны две ситуации) a
k−1
= a
1
, a
k
= 1
;
2) a
k−1
= 1
, a
k
= Но равен произведению своих соседей, те. Следовательно, и столбец состоит из одних единичек. Для доказательства индуктивного перехода введем следующие обозначения. Если A, B
— две таблицы одинакового размера, то пусть A · B — таблица, в каждой клетке которой записано произведение чисел из тех же клеток таблиц A и. A будет обозначатьтаблицу, полученную из A зеркальной симметрией:
первый столбец меняется с последним, второй — с предпоследними так далее. Нетрудно видеть, что если таблицы A и B удовлетворяют условию,
то это же можно сказатьо таблицах A · B и A. Таблицу, в которой стоят только единицы, будем обозначать Докажем, что если в таблице размера k × (2
n+1
− 1) расставлены числа согласно условию, то расстановка симметрична A = A. Это равносильно тому, что A · A = 1. В таблице A · A весьцентральный столбец
(с номером 2
n
) состоит из единиц, так как центральные столбцы у A и одинаковы. Следовательно, если мы рассмотрим отдельно часть таблицы слева от центрального столбца, то числа в этой меньшей таблице расставлены согласно условию. Размер ее — k × (2
n
− 1), так что по предположению индукции, все числа в ней — единицы. Тоже касается и правой части A·A. Итак, A·A = 1. Это значит, что для любого числа из центрального столбца таблицы A числа слева и справа от него одинаковы, поэтому само оно равно произведению своих верхнего и нижнего соседей. Как мы доказали в базе индукции, из этого следует, что центральный столбец заполнен единицами. Теперьснова рассмотрим частьтаблицы A слева от центрального столбца. Применяя предположение индукции, убеждаемся,
что в ней стоят только единицы. Правая часть симметрична левой, поэтому иона состоит из единиц. Переход индукции доказан. Для всех таблиц размера k × (2
n
− 1) (где k + 1 не делится на 3) единственностьрасста-
КЛАСС
341
Вычитая (2) из (1), получаем Γ − B = 2, что и требовалось. Ответ. Удачная расстановка единственна — все числа равны +Первое решение. Докажем индукцией последующее утверждение:
если в таблице из 2
n
−1 столбцов и k строк (k+1 не делится на 3) расставлены числа ±1 так, что выполняется условие задачи, то все числа таблицы равны +1. При n = 1 имеем один столбец высоты k. Пустьв нем стоят числа a
1
, a
2
, . . . , a
n
— по порядку сверху вниз. Тогда a
1
= условие задачи для первой клетки, a
2
= a
1
a
3
, следовательно a
3
= 1
, 1 = a
3
= следовательно a
4
= a
2
= a
1
. Итак далее. Получаем, что все числа, стоящие в клетках с номером, кратным трем, равны 1, а все остальные равны. Поскольку k + 1 не делится на 3, то возможны две ситуации) a
k−1
= a
1
, a
k
= 1
;
2) a
k−1
= 1
, a
k
= Но равен произведению своих соседей, те. Следовательно, и столбец состоит из одних единичек. Для доказательства индуктивного перехода введем следующие обозначения. Если A, B
— две таблицы одинакового размера, то пусть A · B — таблица, в каждой клетке которой записано произведение чисел из тех же клеток таблиц A и. A будет обозначатьтаблицу, полученную из A зеркальной симметрией:
первый столбец меняется с последним, второй — с предпоследними так далее. Нетрудно видеть, что если таблицы A и B удовлетворяют условию,
то это же можно сказатьо таблицах A · B и A. Таблицу, в которой стоят только единицы, будем обозначать Докажем, что если в таблице размера k × (2
n+1
− 1) расставлены числа согласно условию, то расстановка симметрична A = A. Это равносильно тому, что A · A = 1. В таблице A · A весьцентральный столбец
(с номером 2
n
) состоит из единиц, так как центральные столбцы у A и одинаковы. Следовательно, если мы рассмотрим отдельно часть таблицы слева от центрального столбца, то числа в этой меньшей таблице расставлены согласно условию. Размер ее — k × (2
n
− 1), так что по предположению индукции, все числа в ней — единицы. Тоже касается и правой части A·A. Итак, A·A = 1. Это значит, что для любого числа из центрального столбца таблицы A числа слева и справа от него одинаковы, поэтому само оно равно произведению своих верхнего и нижнего соседей. Как мы доказали в базе индукции, из этого следует, что центральный столбец заполнен единицами. Теперьснова рассмотрим частьтаблицы A слева от центрального столбца. Применяя предположение индукции, убеждаемся,
что в ней стоят только единицы. Правая часть симметрична левой, поэтому иона состоит из единиц. Переход индукции доказан. Для всех таблиц размера k × (2
n
− 1) (где k + 1 не делится на 3) единственностьрасста-
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
новки доказана. Если k = 2
n
− 1, то k + 1 = 2
n
, поэтому доказано и утверждение задачи 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 Рис. Второе решение. Пусть R — удачная расстановка в таблице 1) × (2
n
− 1). Расставим числа на клетчатой плоскости, как показано на рис. 261 (симметрия буквы R означает, что там стоит таблица отраженная соответствующим образом. Тогда расстановка на всей плоскости удовлетворяет нашим условиям (те. любое число естьпроизведе- ние его четырех соседей) и, кроме того, она периодична, те. при сдвиге на вверх или вправо она переходит в себя. Докажем индукцией по n, что любая периодичная перестановка состоит из единиц.
a
13
a
22
a
23
a
24
a
31
a
32
a
33
a
34
a
35
a
42
a
43
a
44
a
53
Рис. База при n = 0 очевидна a = a
4
, где a — число в клет- ке.
Пусть n Рассмотрим фрагмент таблицы, показанный на рис. 262. Имеем a
23
= a
13
a
22
a
24
a
33
, a
32
= a
22
a
31
a
33
a
42
, a
34
=
= a
24
a
33
a
35
a
44
, a
43
= a
33
a
42
a
44
a
53
, откуда a
33
= a
23
a
32
a
34
a
43
=
= a
13
a
31
a
35
a
53
a
2 22
a
2 24
a
2 42
a
2 44
a
4 33
= a
13
a
31
a
35
a
53
, те. тоже соотношение верно для
разреженной
таблицы, состоящей из чисел, находящихся в пересечениях нечетных строк с нечетными столбцами. Эта таблица 2
n−1
- периодична, поэтому по предположению индукции она состоит из единиц
новки доказана. Если k = 2
n
− 1, то k + 1 = 2
n
, поэтому доказано и утверждение задачи 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 Рис. Второе решение. Пусть R — удачная расстановка в таблице 1) × (2
n
− 1). Расставим числа на клетчатой плоскости, как показано на рис. 261 (симметрия буквы R означает, что там стоит таблица отраженная соответствующим образом. Тогда расстановка на всей плоскости удовлетворяет нашим условиям (те. любое число естьпроизведе- ние его четырех соседей) и, кроме того, она периодична, те. при сдвиге на вверх или вправо она переходит в себя. Докажем индукцией по n, что любая периодичная перестановка состоит из единиц.
a
13
a
22
a
23
a
24
a
31
a
32
a
33
a
34
a
35
a
42
a
43
a
44
a
53
Рис. База при n = 0 очевидна a = a
4
, где a — число в клет- ке.
Пусть n Рассмотрим фрагмент таблицы, показанный на рис. 262. Имеем a
23
= a
13
a
22
a
24
a
33
, a
32
= a
22
a
31
a
33
a
42
, a
34
=
= a
24
a
33
a
35
a
44
, a
43
= a
33
a
42
a
44
a
53
, откуда a
33
= a
23
a
32
a
34
a
43
=
= a
13
a
31
a
35
a
53
a
2 22
a
2 24
a
2 42
a
2 44
a
4 33
= a
13
a
31
a
35
a
53
, те. тоже соотношение верно для
разреженной
таблицы, состоящей из чисел, находящихся в пересечениях нечетных строк с нечетными столбцами. Эта таблица 2
n−1
- периодична, поэтому по предположению индукции она состоит из единиц
УЧЕБНЫЙ ГОД, 11
КЛАСС
343
Абсолютно аналогично, остальные три
разреженных
подтаблицы состоят из единиц, что и требовалось класс. См. решение задачи Рис. 263
562. Первое решение. Случай правильного очевиден.
Пусть
AB
= AC см. рис. 263). Обозначим через O, I центры описанной и вписанной окружностей. Тогда IA
1
⊥ BC;
OA
2
⊥ BC так как O и лежат на серединном перпендикуляре к Следовательно, OA
2
и OA
2
IA
1
—
трапеция.
Точка P пересечения диагоналей этой трапеции делит OI в отношении : P I = OA
2
: IA
1
= R : r
, где, r — радиусы соответственно описанной и вписанной окружностей. Проведя аналогичные рассуждения для трапеций OB
2
IB
1
, если ABC — равнобедренный, то одна из них вырождается в отрезок) получаем, что отрезки A
1
A
2
, B
1
B
2
, делят OI в отношении R : r и проходят через одну точку P Второе решение. Касательная в точке к описанной окружности параллельна BC. Рассмотрев касательные l
B
, в точках B
2
, аналогично получим l
B
AC, l
C
AB. Поэтому треугольник ABC гомоте- тичен треугольнику, образованному прямыми l
A
, l
B
, l
C
. При этой гомотетии переходит в A
2
, B
1
— в B
2
, C
1
— в C
2
. Поэтому прямые A
1
A
2
,
B
1
B
2
, пересекутся в центре гомотетии. Пусть ABC — один из треугольников семейства S. Его высоту примем за единицу. Так как треугольники из S попарно пересекаются,
то они лежат в некоторой полосе ширины 2, параллельной стороне Аналогично, взяв полосы, параллельные BC и CA, рассмотрим их пересечение это будет шестиугольник H с углами пои расстояниями между противоположными сторонами, равными 2. У такого шестиугольника длины сторон чередуются, обозначим их a и b см. рис. 264).
Пустьвначале a b, тогда все треугольники из S содержат центр фигуры см. рис. Если же a > b, то рассмотрим прямые l
X
, l
Y
, l
Z
, параллельные сторонам шестиугольника и равноудаленные от них. В качестве искомых точек
КЛАСС
343
Абсолютно аналогично, остальные три
разреженных
подтаблицы состоят из единиц, что и требовалось класс. См. решение задачи Рис. 263
562. Первое решение. Случай правильного очевиден.
Пусть
AB
= AC см. рис. 263). Обозначим через O, I центры описанной и вписанной окружностей. Тогда IA
1
⊥ BC;
OA
2
⊥ BC так как O и лежат на серединном перпендикуляре к Следовательно, OA
2
и OA
2
IA
1
—
трапеция.
Точка P пересечения диагоналей этой трапеции делит OI в отношении : P I = OA
2
: IA
1
= R : r
, где, r — радиусы соответственно описанной и вписанной окружностей. Проведя аналогичные рассуждения для трапеций OB
2
IB
1
, если ABC — равнобедренный, то одна из них вырождается в отрезок) получаем, что отрезки A
1
A
2
, B
1
B
2
, делят OI в отношении R : r и проходят через одну точку P Второе решение. Касательная в точке к описанной окружности параллельна BC. Рассмотрев касательные l
B
, в точках B
2
, аналогично получим l
B
AC, l
C
AB. Поэтому треугольник ABC гомоте- тичен треугольнику, образованному прямыми l
A
, l
B
, l
C
. При этой гомотетии переходит в A
2
, B
1
— в B
2
, C
1
— в C
2
. Поэтому прямые A
1
A
2
,
B
1
B
2
, пересекутся в центре гомотетии. Пусть ABC — один из треугольников семейства S. Его высоту примем за единицу. Так как треугольники из S попарно пересекаются,
то они лежат в некоторой полосе ширины 2, параллельной стороне Аналогично, взяв полосы, параллельные BC и CA, рассмотрим их пересечение это будет шестиугольник H с углами пои расстояниями между противоположными сторонами, равными 2. У такого шестиугольника длины сторон чередуются, обозначим их a и b см. рис. 264).
Пустьвначале a b, тогда все треугольники из S содержат центр фигуры см. рис. Если же a > b, то рассмотрим прямые l
X
, l
Y
, l
Z
, параллельные сторонам шестиугольника и равноудаленные от них. В качестве искомых точек
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
a
a
a
b
b
b
l
Z
l
Y
l
X
X
Y
Z
l
Z
l
Y
l
X
X
Y
Z
T
Рис. Рис. Рис. 266
X
, Y и Z возьмем середины отрезков, высекаемых сторонами на этих прямых (см. рис. Покажем, что любой треугольник T , T ∈ S, содержит какую-то точку из множества M = {X, Y, Заметим, что T пересекает любую из прямых l
X
, и см. рис. так как иначе T лежит в полосе меньшей ширины, чем его высота. Предположим противное T не содержит точек X, Y или Z, тогда без ограничения общности можно считать, что T пересекает выше и левее X, а левее Y см. рис. 266). Так как T ∼ XY Z, то легко видеть , что правая нижняя вершина T лежит в XY Z, а значит, T не пересекает l
Z
— про- тиворечие.
A
B
C
O
Рис. 267
564. Рассмотрим граф, вершинами которого являются города, ребрами — авиалинии. По условию получится связный граф, степени вершин которого равны трем.
Предположим, что в графе, степени вершин которого не превосходят трех, естьдва пересекающихся (по вершине) цикла (см. рис. 267). Тогда рассмотрим вершину, в которой они
разветвляются
. Эта вершина,
очевидно, имеет степеньтри. Удалим эту вершину и три выходящих из нее ребра OA, OB, OC. Нетрудно заметить, что граф сохранил связность, так как существует путь, соединяющий вершины A, B и Рассмотрим полученный граф. Если в нем естьдва пересекающихся цикла, то повторим операцию. Итак далее. Очевидно, что никакие две удаленные вершины не соединены ребром в исходном графе, так как мы удаляли только вершины степени три, а после каждой операции степени вершин, соседних с удаленной, уменьшались, те. они не могут стать равными трем.
Предположим, что в связном графе n вершин и не менее чем 3
·n ребер.
Докажем, что в таком графе обязательно есть два пересекающихся цикла.
Предположим, что это не так. В силу связности графа, в нем можно выде- литьдерево с n вершинами. Будем
возвращать
в граф оставшиеся после выделения дерева ребра. Добавление каждого ребра увеличивает ко
a
a
a
b
b
b
l
Z
l
Y
l
X
X
Y
Z
l
Z
l
Y
l
X
X
Y
Z
T
Рис. Рис. Рис. 266
X
, Y и Z возьмем середины отрезков, высекаемых сторонами на этих прямых (см. рис. Покажем, что любой треугольник T , T ∈ S, содержит какую-то точку из множества M = {X, Y, Заметим, что T пересекает любую из прямых l
X
, и см. рис. так как иначе T лежит в полосе меньшей ширины, чем его высота. Предположим противное T не содержит точек X, Y или Z, тогда без ограничения общности можно считать, что T пересекает выше и левее X, а левее Y см. рис. 266). Так как T ∼ XY Z, то легко видеть , что правая нижняя вершина T лежит в XY Z, а значит, T не пересекает l
Z
— про- тиворечие.
A
B
C
O
Рис. 267
564. Рассмотрим граф, вершинами которого являются города, ребрами — авиалинии. По условию получится связный граф, степени вершин которого равны трем.
Предположим, что в графе, степени вершин которого не превосходят трех, естьдва пересекающихся (по вершине) цикла (см. рис. 267). Тогда рассмотрим вершину, в которой они
разветвляются
. Эта вершина,
очевидно, имеет степеньтри. Удалим эту вершину и три выходящих из нее ребра OA, OB, OC. Нетрудно заметить, что граф сохранил связность, так как существует путь, соединяющий вершины A, B и Рассмотрим полученный граф. Если в нем естьдва пересекающихся цикла, то повторим операцию. Итак далее. Очевидно, что никакие две удаленные вершины не соединены ребром в исходном графе, так как мы удаляли только вершины степени три, а после каждой операции степени вершин, соседних с удаленной, уменьшались, те. они не могут стать равными трем.
Предположим, что в связном графе n вершин и не менее чем 3
·n ребер.
Докажем, что в таком графе обязательно есть два пересекающихся цикла.
Предположим, что это не так. В силу связности графа, в нем можно выде- литьдерево с n вершинами. Будем
возвращать
в граф оставшиеся после выделения дерева ребра. Добавление каждого ребра увеличивает ко
УЧЕБНЫЙ ГОД, 11
КЛАСС
345
личество циклов по крайней мерена один. Однако, если какое-либо ребро добавит не менее двух циклов, они будут пересекающимися, что противоречит нашему предположению. С другой стороны, каждый цикл содержит не менее трех вершин, и никакая вершина не входит в два цикла. Кроме того, дерево с n вершинами содержит ровно n − 1 ребро. Следовательно,
ребер не более, чем (n − 1) +
n
3
<
4n
3
. Противоречие.
Пусть N = 1998 — количество вершин в исходном графе, тогда исходное количество ребер равно 2
N
. За каждую операцию выкидывания вершины количество вершин уменьшается на одну, а количество ребер уменьшается натри. Предположим, что было сделано x операций. Тогда стало вершин и 2
N
−3x ребер. До тех пор, пока выполняется неравенство 2
N
− 3x
4 3
(N
− x), вершины удалятьможно. Решив это неравенство,
получаем x
N
10
, те. можно удалить 10
+ 1 = 200
вершин.
Отсюда и следует утверждение задачи. Ответ. r
1998
= Пусть r
n
— радиус й окружности, S
n
= r
1
+ r
2
+ . . . + r
n
. Тогда уравнение (n + й окружности имеет вид+ (y
− (2S
n
+ r
n+1
))
2
= Условие касания означает то, что уравнение y+(y−(2S
n
+r
n+1
))
2
= имеет один корень, тогда его дискриминант D = (2r
n+1
− 1)
2
− 8S
n
= те, так как r
n+1
> 0
. Отсюда r
2
=
3 2
, r
3
=
5 2
. По индукции легко проверить, что r
n+1
= n +
1 2
. Действительно, если r
n+1
=
= n +
1 при n k, то 2
+ . . . +
k
−
1 2
+ 1 2
=
2
k(k + 1)
2
−
k
2
+
1 2
=
= k +
1 2
= (k + 1)
−
1 2
.
566. Ответ. Да.
Пустьнабор N = {a
1
, . . . , a
n
} состоит из чисел, удовлетворяющих данному условию U. Тогда набор N
1
=
{b
1
, . . . , b
n
, b
n+1
}, где b
1
= a
1
,
. . . , b
n
= a
n
, b
n+1
= также удовлетворяет U. Прибавим к каждому число c = (b
2
− b
1
)
2
· (b
3
− b
1
)
2
· . . . · (b
n+1
− b
n
)
2
. Получим набор состоящий из натуральных чисел и также удовлетворяющий U, так как+ c)
− (b
j
+ c))
2
= (b
i
− и (b
i
+ c)(b
j
+ c) = b
i
b
j
+ c(b
j
+ b
j
+ c)
— делится на (b
i
− b
j
)
2
КЛАСС
345
личество циклов по крайней мерена один. Однако, если какое-либо ребро добавит не менее двух циклов, они будут пересекающимися, что противоречит нашему предположению. С другой стороны, каждый цикл содержит не менее трех вершин, и никакая вершина не входит в два цикла. Кроме того, дерево с n вершинами содержит ровно n − 1 ребро. Следовательно,
ребер не более, чем (n − 1) +
n
3
<
4n
3
. Противоречие.
Пусть N = 1998 — количество вершин в исходном графе, тогда исходное количество ребер равно 2
N
. За каждую операцию выкидывания вершины количество вершин уменьшается на одну, а количество ребер уменьшается натри. Предположим, что было сделано x операций. Тогда стало вершин и 2
N
−3x ребер. До тех пор, пока выполняется неравенство 2
N
− 3x
4 3
(N
− x), вершины удалятьможно. Решив это неравенство,
получаем x
N
10
, те. можно удалить 10
+ 1 = 200
вершин.
Отсюда и следует утверждение задачи. Ответ. r
1998
= Пусть r
n
— радиус й окружности, S
n
= r
1
+ r
2
+ . . . + r
n
. Тогда уравнение (n + й окружности имеет вид+ (y
− (2S
n
+ r
n+1
))
2
= Условие касания означает то, что уравнение y+(y−(2S
n
+r
n+1
))
2
= имеет один корень, тогда его дискриминант D = (2r
n+1
− 1)
2
− 8S
n
= те, так как r
n+1
> 0
. Отсюда r
2
=
3 2
, r
3
=
5 2
. По индукции легко проверить, что r
n+1
= n +
1 2
. Действительно, если r
n+1
=
= n +
1 при n k, то 2
+ . . . +
k
−
1 2
+ 1 2
=
2
k(k + 1)
2
−
k
2
+
1 2
=
= k +
1 2
= (k + 1)
−
1 2
.
566. Ответ. Да.
Пустьнабор N = {a
1
, . . . , a
n
} состоит из чисел, удовлетворяющих данному условию U. Тогда набор N
1
=
{b
1
, . . . , b
n
, b
n+1
}, где b
1
= a
1
,
. . . , b
n
= a
n
, b
n+1
= также удовлетворяет U. Прибавим к каждому число c = (b
2
− b
1
)
2
· (b
3
− b
1
)
2
· . . . · (b
n+1
− b
n
)
2
. Получим набор состоящий из натуральных чисел и также удовлетворяющий U, так как+ c)
− (b
j
+ c))
2
= (b
i
− и (b
i
+ c)(b
j
+ c) = b
i
b
j
+ c(b
j
+ b
j
+ c)
— делится на (b
i
− b
j
)
2
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Поэтому, взяв в качестве исходного набор N = {1, 2}, последовательным применением указанной выше процедуры мы получим набор N
2
, состоящий из трех, набор N
4
— из четырех, . . . , N
2n−4
— из n чисел. Рассмотрим множества M центров сфер диаметра 1, лежащих в данном тетраэдре T . Так как M — множество точек, удаленных от всех граней T не менее, чем на 1/2, то M — это тетраэдр с гранями, параллельными граням тетраэдра T , те и T гомотетичны. Центры вписанных сфер обоих тетраэдров совпадают, поэтому коэффициент k гомотетии равен − 1/2
r
, где r — радиус сферы, вписанной в T С другой стороны, две сферы единичного диаметра не пересекаются,
поэтому расстояние между их центрами не меньше 1, значит, длина одного из ребер тетраэдра M, содержащего эти центры, не меньше 1. Отсюда следует, что k
1 длины ребер тетраэдра T не больше 100), те, откуда 2r
100 99
> 1, 01
. Итак, диаметр сферы, вписанной в, больше 1,01, те. в качестве искомой можно выбрать сферу, вписанную в T .
Поэтому, взяв в качестве исходного набор N = {1, 2}, последовательным применением указанной выше процедуры мы получим набор N
2
, состоящий из трех, набор N
4
— из четырех, . . . , N
2n−4
— из n чисел. Рассмотрим множества M центров сфер диаметра 1, лежащих в данном тетраэдре T . Так как M — множество точек, удаленных от всех граней T не менее, чем на 1/2, то M — это тетраэдр с гранями, параллельными граням тетраэдра T , те и T гомотетичны. Центры вписанных сфер обоих тетраэдров совпадают, поэтому коэффициент k гомотетии равен − 1/2
r
, где r — радиус сферы, вписанной в T С другой стороны, две сферы единичного диаметра не пересекаются,
поэтому расстояние между их центрами не меньше 1, значит, длина одного из ребер тетраэдра M, содержащего эти центры, не меньше 1. Отсюда следует, что k
1 длины ребер тетраэдра T не больше 100), те, откуда 2r
100 99
> 1, 01
. Итак, диаметр сферы, вписанной в, больше 1,01, те. в качестве искомой можно выбрать сферу, вписанную в T .
568. Пусть Φ
1
, . . . , Φ
k
— всевозможные расположения фигуры Φ в прямоугольнике. Утверждение задачи можно переформулировать так:
можно взятьфигуры такой неотрицательной толщины d
i
, i = 1 ,. . . , рационально, что суммарная толщина всех фигур над каждой клеткой прямоугольника будет равна Предположим, что это утверждение неверно. Покажем, что тогда существует такое заполнение клеток прямоугольника числами, при котором сумма всех чисел положительна, а сумма чисел в клетках, закрываемых фигурой при любом ее положении, неположительна.
Введем обозначения индексом j, j = 1, . . . , m · n, будем нумеровать клетки прямоугольника, индексом i, i = 1, . . . , k, — положения фигуры на прямоугольнике.
Положим P
ij
= 1
, если я клетка закрыта фигурой Φ
i
, P
ij
= 0
, если незакрыта. Тогда набору чисел {d
i
} соответствует заполнение клеток прямоугольника числами θ
j
= 1
−
i
d
i
P
ij
, характеризующими уклонение покрытия прямоугольника фигурами от равномерного. По нашему предположению, все числа не могут бытьравными нулю.
Выберем числа d
j
0 так, чтобы величина |θ| уклонения была минимальна, где |θ|
2
=
j
θ
2
j
. Покажем, что получившиеся числа и образуют искомое заполнение клеток прямоугольника Почему существует набор {d
i
}, для которого |θ| — минимален?
После раскрытия скобок получаем
УЧЕБНЫЙ ГОД, 9
КЛАСС
347
Заменим одно число на d
i
= d
i
+ x
, x −d
i
. Тогда θ
j
= θ
j
− следовательно |θ
|
2
=
j
θ
2
j
=
j
θ
2
j
− 2x
j
θ
j
P
ij
+ x
2
j
P
2
ij
, те. Здесь a =
j
P
2
ij
=
j
P
ij
= N
, где N — число клеток в фигуре, c = |θ|
2
. Квадратный трехчлен y = y(x), заданный на множестве x −d
i
, принимает наименьшее значение при x = 0 в случае 0
, если d
i
> 0
, ив случае b
i
0, если d
i
= 0
. Таким образом, предположив, что |θ| минимален на наборе {d
i
}, мы получаем, что если d
i
> 0
, то 0
, а если d
i
= 0
, то b
i
0. Значит, сумма чисел, закрываемых фигурой это как раз) — неположительна; с другой стороны, сумма всех чисел в прямоугольнике положительна, так как она равна, а. Действительно, так как при 0 b
i
= 0
1998–1999 г класс. Ответ. Заметим, что 9A = 10A − A. При вычитании этих чисел столбиком нив одном разряде, кроме младшего, не приходится заниматьединицу из следующего разряда. Таким образом, сумма цифр разности равна разности суммы цифр чисел 10A и A которые равны) плюс 9.
|θ|
2
=
X
j
1 −
X
i
d
i
P
ij
!
2
=
X
i
d
2
i
X
j
P
2
ij
+
X
i,k
M
ik
d
i
d
k
+ m · n − где M
ik
0. Таким образом N
X
i
(d
i
− 1)
2
+
X
i,k
M
ik
d
i
d
k
+ m · n − где N — число клеток в фигуре. Отсюда следует, что, если d
i
> 2 для некоторого i, тов то время как |θ|
2
= m·n, если все d
i
= 0. Итак,
функция |θ|
2
— многочлен второй степени, заданный на множестве 0 d
1
, . . . , d
m·n
те. на (m · мерном кубе. Многочлен достигает своего наименьшего значения на кубе.
Точка минимума имеет рациональные координаты, так как это многочлен второй степени и его коэффициенты — целые числа, те. координаты этой точки — решение линейной системы уравнений с целыми коэффициентами
КЛАСС
347
Заменим одно число на d
i
= d
i
+ x
, x −d
i
. Тогда θ
j
= θ
j
− следовательно |θ
|
2
=
j
θ
2
j
=
j
θ
2
j
− 2x
j
θ
j
P
ij
+ x
2
j
P
2
ij
, те. Здесь a =
j
P
2
ij
=
j
P
ij
= N
, где N — число клеток в фигуре, c = |θ|
2
. Квадратный трехчлен y = y(x), заданный на множестве x −d
i
, принимает наименьшее значение при x = 0 в случае 0
, если d
i
> 0
, ив случае b
i
0, если d
i
= 0
. Таким образом, предположив, что |θ| минимален на наборе {d
i
}, мы получаем, что если d
i
> 0
, то 0
, а если d
i
= 0
, то b
i
0. Значит, сумма чисел, закрываемых фигурой это как раз) — неположительна; с другой стороны, сумма всех чисел в прямоугольнике положительна, так как она равна, а. Действительно, так как при 0 b
i
= 0
1998–1999 г класс. Ответ. Заметим, что 9A = 10A − A. При вычитании этих чисел столбиком нив одном разряде, кроме младшего, не приходится заниматьединицу из следующего разряда. Таким образом, сумма цифр разности равна разности суммы цифр чисел 10A и A которые равны) плюс 9.
|θ|
2
=
X
j
1 −
X
i
d
i
P
ij
!
2
=
X
i
d
2
i
X
j
P
2
ij
+
X
i,k
M
ik
d
i
d
k
+ m · n − где M
ik
0. Таким образом N
X
i
(d
i
− 1)
2
+
X
i,k
M
ik
d
i
d
k
+ m · n − где N — число клеток в фигуре. Отсюда следует, что, если d
i
> 2 для некоторого i, тов то время как |θ|
2
= m·n, если все d
i
= 0. Итак,
функция |θ|
2
— многочлен второй степени, заданный на множестве 0 d
1
, . . . , d
m·n
те. на (m · мерном кубе. Многочлен достигает своего наименьшего значения на кубе.
Точка минимума имеет рациональные координаты, так как это многочлен второй степени и его коэффициенты — целые числа, те. координаты этой точки — решение линейной системы уравнений с целыми коэффициентами
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Рассмотрим некоторый путь, соединяющий некоторые два города,
возможно включающий в себя некоторые закрытые после кризиса рейсы.
Покажем, что в этом пути любой закрытый рейс можно заменитьпосле- довательностью незакрытых. Пронумеруем авиакомпании числами от 1 до. Водной из авиакомпаний сохранилисьвсе рейсы предположим, что впервой. Тогда в любой другой авиакомпании закрыли по одному рейсу. Рассмотрим только рейсы первой и второй авиакомпаний из каждого города выходит по одному рейсу этих авиакомпаний. Следовательно,
все города разбиваются на циклы. Водном из этих циклов закрыли один рейс. Очевидно, можно пролететьостальными рейсами этого цикла, следовательно, мы можем
обойти
любой закрытый рейс. Отметим, что мы при этом не используем рейсы других авиакомпаний, следовательно, аналогично можно обойтисьбез остальных закрытых рейсов.
A
B
C
A
0
C
0
D
L
K
I
S
1
S
2
Рис. 268
571. Из точки I проведем касательную к окружности так, чтобы луч
IK
пересекал меньшую дугу A
0
C
(см.
рис. 268). Аналогичным образом проведем касательную IL к окружности Биссектриса AI угла BAC делит дугу
BC
на 2 равных дуги. Поэтому точки A, лежат на одной прямой. Аналогично,
на одной прямой лежат точки C, I и Из равенств 2
C
0
BA
0
=
1 2
C
0
B +
BA
0
,
∠A
0
IC =
1 2
AC
0
+
A
0
C
=
1 2
C
0
B следует, что ∠A
0
IC и A
0
I = Далее, пусть D — середина отрезка BC, тогда касается BC в точке В прямоугольных и катеты и равны и = по доказанному выше. Следовательно, A
0
KI =
Отсюда ∠A
0
IK =
∠A
0
CD =
∠A
0
CB
. Но ∠A
0
CB теорема о вписанном угле) и ∠A
0
AB =
∠A
0
AC
. Значит, ∠A
0
IK следовательно прямая IK параллельна AC. Аналогично, IL AC, следовательно лежат на одной прямой, параллельной AC.
572. Ответ. Можно.
Лемма. Пусть дан набор простых чисел p
1
, . . . , p
n
. Тогда можно
за несколько перекрашиваний добиться того, что поменяют цвет
возможно включающий в себя некоторые закрытые после кризиса рейсы.
Покажем, что в этом пути любой закрытый рейс можно заменитьпосле- довательностью незакрытых. Пронумеруем авиакомпании числами от 1 до. Водной из авиакомпаний сохранилисьвсе рейсы предположим, что впервой. Тогда в любой другой авиакомпании закрыли по одному рейсу. Рассмотрим только рейсы первой и второй авиакомпаний из каждого города выходит по одному рейсу этих авиакомпаний. Следовательно,
все города разбиваются на циклы. Водном из этих циклов закрыли один рейс. Очевидно, можно пролететьостальными рейсами этого цикла, следовательно, мы можем
обойти
любой закрытый рейс. Отметим, что мы при этом не используем рейсы других авиакомпаний, следовательно, аналогично можно обойтисьбез остальных закрытых рейсов.
A
B
C
A
0
C
0
D
L
K
I
S
1
S
2
Рис. 268
571. Из точки I проведем касательную к окружности так, чтобы луч
IK
пересекал меньшую дугу A
0
C
(см.
рис. 268). Аналогичным образом проведем касательную IL к окружности Биссектриса AI угла BAC делит дугу
BC
на 2 равных дуги. Поэтому точки A, лежат на одной прямой. Аналогично,
на одной прямой лежат точки C, I и Из равенств 2
C
0
BA
0
=
1 2
C
0
B +
BA
0
,
∠A
0
IC =
1 2
AC
0
+
A
0
C
=
1 2
C
0
B следует, что ∠A
0
IC и A
0
I = Далее, пусть D — середина отрезка BC, тогда касается BC в точке В прямоугольных и катеты и равны и = по доказанному выше. Следовательно, A
0
KI =
Отсюда ∠A
0
IK =
∠A
0
CD =
∠A
0
CB
. Но ∠A
0
CB теорема о вписанном угле) и ∠A
0
AB =
∠A
0
AC
. Значит, ∠A
0
IK следовательно прямая IK параллельна AC. Аналогично, IL AC, следовательно лежат на одной прямой, параллельной AC.
572. Ответ. Можно.
Лемма. Пусть дан набор простых чисел p
1
, . . . , p
n
. Тогда можно
за несколько перекрашиваний добиться того, что поменяют цвет
УЧЕБНЫЙ ГОД, 9
КЛАСС
349
те и только те числа, которые делятся на все простые числа на-
бора.
Д ока за тел ьс т во. (формула включения–исключения). Для каждого непустого поднабора наших простых чисел перекрасим числа, не взаимно простые с произведением всех чисел этого поднабора. Число, делящееся на все числа набора, перекрашивалосьпри каждом таком перекрашивании, всего перекрашиваний было 2
n
− 1, следовательно, числа, делящиеся на все числа набора, перекрашены. Пустьнекоторое число k не делится хотя бы на одно из чисел набора, например, на p
1
. Тогда оно не перекрашивалось, когда мы перекрашивали числа, не взаимно простые с. Остальные непустые поднаборы чисел можно разбить на пары следующим образом поднабору, не содержащему p
1
, в пару ставится поднабор,
полученный из него добавлением p
1
. При этом число k перекрашивается или при обоих перекрашиваниях пары, или ни при одном. Поэтому число
k
не будет перекрашено.
Лемма доказана.
Первое решение. Для каждого набора простых чисел, произведение которых не больше 1 000 000, перекрасим числа, делящиеся на все эти простые числа. По лемме такая операция возможна. Докажем, что любое число k при этом будет перекрашено. Пусть k имеет m различных простых делителей, тогда оно перекрашивалосьпри 2
m
− 1 операции, т. е.
нечетное число раз.
Второе решение. Назовем два числа эквивалентными, если у них совпадают наборы простых делителей. Заметим, что при наших операциях классы эквивалентности перекрашиваются целиком. Будем говорить,
что один класс больше другого, если все простые делители второго класса являются делителями первого. Из леммы следует, что мы можем перекра- ситьлюбой класс, перекрасив вместе с ним только большие классы.
Сначала перекрасим минимальные классы (класс называется минимальным, если он не больше никакого другого класса. Исключим их из рассмотрения. Среди оставшихся некоторые классы станут после такого исключения минимальными. При необходимости перекрасим их и тоже исключим. Итак далее.
Поскольку классов конечное число, процесс закончится. Ответ. n(n + Общее количество отрезков длины 1 равно 3 ·
n(n + 1)
2
. Все отрезки,
параллельные двум сторонам большого треугольника, не образуют треугольников, так как любой треугольник состоит из отрезков, параллель
КЛАСС
349
те и только те числа, которые делятся на все простые числа на-
бора.
Д ока за тел ьс т во. (формула включения–исключения). Для каждого непустого поднабора наших простых чисел перекрасим числа, не взаимно простые с произведением всех чисел этого поднабора. Число, делящееся на все числа набора, перекрашивалосьпри каждом таком перекрашивании, всего перекрашиваний было 2
n
− 1, следовательно, числа, делящиеся на все числа набора, перекрашены. Пустьнекоторое число k не делится хотя бы на одно из чисел набора, например, на p
1
. Тогда оно не перекрашивалось, когда мы перекрашивали числа, не взаимно простые с. Остальные непустые поднаборы чисел можно разбить на пары следующим образом поднабору, не содержащему p
1
, в пару ставится поднабор,
полученный из него добавлением p
1
. При этом число k перекрашивается или при обоих перекрашиваниях пары, или ни при одном. Поэтому число
k
не будет перекрашено.
Лемма доказана.
Первое решение. Для каждого набора простых чисел, произведение которых не больше 1 000 000, перекрасим числа, делящиеся на все эти простые числа. По лемме такая операция возможна. Докажем, что любое число k при этом будет перекрашено. Пусть k имеет m различных простых делителей, тогда оно перекрашивалосьпри 2
m
− 1 операции, т. е.
нечетное число раз.
Второе решение. Назовем два числа эквивалентными, если у них совпадают наборы простых делителей. Заметим, что при наших операциях классы эквивалентности перекрашиваются целиком. Будем говорить,
что один класс больше другого, если все простые делители второго класса являются делителями первого. Из леммы следует, что мы можем перекра- ситьлюбой класс, перекрасив вместе с ним только большие классы.
Сначала перекрасим минимальные классы (класс называется минимальным, если он не больше никакого другого класса. Исключим их из рассмотрения. Среди оставшихся некоторые классы станут после такого исключения минимальными. При необходимости перекрасим их и тоже исключим. Итак далее.
Поскольку классов конечное число, процесс закончится. Ответ. n(n + Общее количество отрезков длины 1 равно 3 ·
n(n + 1)
2
. Все отрезки,
параллельные двум сторонам большого треугольника, не образуют треугольников, так как любой треугольник состоит из отрезков, параллель
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
ных всем трем сторонам. Следовательно 3
·
3
·
n(n + 1)
2
= n(n + отрезков длины 1 отметитьможно.
Докажем, что большее количество отрезков отметить нельзя.
Рис. Заштрихуем треугольники со стороной 1, как показано на рис. 269. Треугольники содержат все отрезки длины 1, причем каждый отрезок принадлежит ровно одному треугольнику. Для того чтобы не образовался ни один из заштрихованных треугольников, в каждом из них можно отметитьне более двух отрезков. Значит,
количество выделенных отрезков не превышает от их общего числа. При n = 1 неравенство обращается в равенство 0 = 0. При n > докажем, что сумма дробных частей на каждом промежутке между двумя последовательными квадратами удовлетворяет неравенству
2m + 1 Из неравенства между средним арифметическими средним квадратичным получаем+ a +
m
2
+ 2m
− a
2(2m
2
+ 2m) < 2m + при 0 a Следовательно+ a
+
m
2
+ 2m
− a
Просуммировав эти неравенства при a = 0, 1, . . . , m − 1 и неравенство+ m
1 получаемое делением на 2 обеих частей (2) при a = приходим к неравенству (Суммируя неравенство (1) по всем m от 1 до n − 1, получаем 1 Остается заметить, что 0
575. Заметим, что ∠BCF = 180
◦
− ∠BEF = ∠AEF , аналогично = ∠F DC, значит AEF ∼ DCF . Пусть K и L — середины отрезков AE и CD соответственно. Тогда ∠AKF = ∠F LB как углы между медианой и основанием в подобных треугольниках, поэтому точки, K, F , L лежат на одной окружности. Но, так как серединные перпендикуляры к отрезками пересекаются в точке O, то точки K и лежат на окружности с диаметром BO. Но тогда и точка F лежит на этой окружности, и ∠BF O — прямой. Ответ. Выигрывает Петя
ных всем трем сторонам. Следовательно 3
·
3
·
n(n + 1)
2
= n(n + отрезков длины 1 отметитьможно.
Докажем, что большее количество отрезков отметить нельзя.
Рис. Заштрихуем треугольники со стороной 1, как показано на рис. 269. Треугольники содержат все отрезки длины 1, причем каждый отрезок принадлежит ровно одному треугольнику. Для того чтобы не образовался ни один из заштрихованных треугольников, в каждом из них можно отметитьне более двух отрезков. Значит,
количество выделенных отрезков не превышает от их общего числа. При n = 1 неравенство обращается в равенство 0 = 0. При n > докажем, что сумма дробных частей на каждом промежутке между двумя последовательными квадратами удовлетворяет неравенству
2m + 1 Из неравенства между средним арифметическими средним квадратичным получаем+ a +
m
2
+ 2m
− a
2(2m
2
+ 2m) < 2m + при 0 a Следовательно+ a
+
m
2
+ 2m
− a
Просуммировав эти неравенства при a = 0, 1, . . . , m − 1 и неравенство+ m
1 получаемое делением на 2 обеих частей (2) при a = приходим к неравенству (Суммируя неравенство (1) по всем m от 1 до n − 1, получаем 1 Остается заметить, что 0
575. Заметим, что ∠BCF = 180
◦
− ∠BEF = ∠AEF , аналогично = ∠F DC, значит AEF ∼ DCF . Пусть K и L — середины отрезков AE и CD соответственно. Тогда ∠AKF = ∠F LB как углы между медианой и основанием в подобных треугольниках, поэтому точки, K, F , L лежат на одной окружности. Но, так как серединные перпендикуляры к отрезками пересекаются в точке O, то точки K и лежат на окружности с диаметром BO. Но тогда и точка F лежит на этой окружности, и ∠BF O — прямой. Ответ. Выигрывает Петя
УЧЕБНЫЙ ГОД, 10
КЛАСС
351
A
B
C
E
D
O
K
L
F
Рис. Мысленно разобьем контакты на четыре одинаковых группы A, B, и D. В каждой группе пронумеруем контакты числами от 1 до 500. Петя будет отвечатьна любой ход Васи так, чтобы для каждого номера k от контактов A
k
, B
k
, и отходило поровну проводов. До начала игры это условие, очевидно, выполняется. Именно благодаря этому условию проигрышная ситуация впервые случится после Васиного хода.
Опишем подробно Петину стратегию. Если Вася перерезает провод между контактами одной группы, например, провод A
i
A
j
, то Петя перережет провода B
j
B
j
, и D
j
D
j
. Если Вася перерезает провод между проводами из разных групп и с разными номерами, например, провод, то Петя в ответ перережет провода A
j
B
i
, и C
j
D
i
. Если же
Вася перерезал провод между контактами из разных групп с одинаковыми номерами, например, провод A
k
B
k
, то Петя перережет провод Заметим, что из описанной стратегии Пети следует, что провода, которые он собирается резать, не будут отрезаны до его хода. Поэтому Петя всегда сможет разрезатьтребуемые провода.
Отметим, что каждый раз после хода Пети от контактов A
k
, B
k
, и отходит поровну проводов при этом от одного из них столько же проводов отходило уже после Васиного хода. Поэтому ситуация, когда от одного контакта отрезан последний провод, случится впервые после Ва- синого хода. Так как количество проводов конечно, проиграет Вася
КЛАСС
351
A
B
C
E
D
O
K
L
F
Рис. Мысленно разобьем контакты на четыре одинаковых группы A, B, и D. В каждой группе пронумеруем контакты числами от 1 до 500. Петя будет отвечатьна любой ход Васи так, чтобы для каждого номера k от контактов A
k
, B
k
, и отходило поровну проводов. До начала игры это условие, очевидно, выполняется. Именно благодаря этому условию проигрышная ситуация впервые случится после Васиного хода.
Опишем подробно Петину стратегию. Если Вася перерезает провод между контактами одной группы, например, провод A
i
A
j
, то Петя перережет провода B
j
B
j
, и D
j
D
j
. Если Вася перерезает провод между проводами из разных групп и с разными номерами, например, провод, то Петя в ответ перережет провода A
j
B
i
, и C
j
D
i
. Если же
Вася перерезал провод между контактами из разных групп с одинаковыми номерами, например, провод A
k
B
k
, то Петя перережет провод Заметим, что из описанной стратегии Пети следует, что провода, которые он собирается резать, не будут отрезаны до его хода. Поэтому Петя всегда сможет разрезатьтребуемые провода.
Отметим, что каждый раз после хода Пети от контактов A
k
, B
k
, и отходит поровну проводов при этом от одного из них столько же проводов отходило уже после Васиного хода. Поэтому ситуация, когда от одного контакта отрезан последний провод, случится впервые после Ва- синого хода. Так как количество проводов конечно, проиграет Вася
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ класс. ПустьВинни и Пятачок вначале кладут свои орехи во вторую и третью банки, несмотря на ходы Кролика, до тех пор, пока водной из банок не станет 1998 орехов. После этого тот, кто должен кластьорехи в эту банку (пусть, например, это Винни) начинает класть их в I. При этом он уже положил во II банку не менее 999 орехов, значит, в III орехов тоже не менее 999 (туда их клал Пятачок. После этого Пятачок продолжает кластьв III банку орехи, пока там не станет 1998 — это произойдет не более, чем через 500 ходов, так как в III банку также приходится класть орехи Кролику, чтобы не проиграть. После этого Пятачок также может кластьорехи в I банку, так как там не более 500 орехов, положенных Вин- ни, а Кролик вынужден будет положитьорех во II или III, где их уже по. Ответ. a
1
= a
2
= . . . = 2
Пустьдля каких-то двух членов последовательности и a
k+1
их
НОД равен 1. Тогда НОД(a
k
, a
k+1
) =
НОД(a
k
+ a
k+1
, a
k+1
) =
=
НОД(a
k+2
, a
k+1
)
, те. для всех последующих членов последовательности НОД тоже будет равен 1. При этом, начиная с го члена, последовательность превращается в последовательность a
n
= a
n−1
+ которая неограниченно возрастает, что невозможно.
Тогда
a
k+2
a
k+1
+ a
k
2
max{a
k+1
, и max{a
k+1
, a
k
} не возрастает. Следовательно, когда-то он стабилизируется. Если при этом a
k+1
= a
k
, то a
k+2
< d
, a
k+3
< d
, что невозможно. Поэтому a
k+1
= a
k+2
= . . . = d
, откуда d = 2. Но тогда+ 2
НОД(a
k−1
, 2)
= откуда a
k−1
= 2
, и последовательность состоит только из двоек. Пусть O
1
, O
2
, O
3
— центры малых окружностей (см. рис. Так как ∠KO
1
M = 90
◦
+
1 2
∠A, а ∠KLM = 90
◦
−
1 2
∠A, то ∠KO
1
M +
+
∠KLM = 180
◦
, и является серединой дуги KM вписанной в окружности. Аналогично и лежат на этой окружности и являются серединами дуги. Используя результат задачи 571, заключаем,
что построенные касательные проходят через центр окружности, вписанной в треугольник KLM, что и требовалосьдоказать.
580. Будем различатьдва типа ходов — внутренние и внешние, в зависимости оттого, куда ставится фишка, делающая ход внутрьисходного квадрата n × n клеток, или вне его
1
= a
2
= . . . = 2
Пустьдля каких-то двух членов последовательности и a
k+1
их
НОД равен 1. Тогда НОД(a
k
, a
k+1
) =
НОД(a
k
+ a
k+1
, a
k+1
) =
=
НОД(a
k+2
, a
k+1
)
, те. для всех последующих членов последовательности НОД тоже будет равен 1. При этом, начиная с го члена, последовательность превращается в последовательность a
n
= a
n−1
+ которая неограниченно возрастает, что невозможно.
Тогда
a
k+2
a
k+1
+ a
k
2
max{a
k+1
, и max{a
k+1
, a
k
} не возрастает. Следовательно, когда-то он стабилизируется. Если при этом a
k+1
= a
k
, то a
k+2
< d
, a
k+3
< d
, что невозможно. Поэтому a
k+1
= a
k+2
= . . . = d
, откуда d = 2. Но тогда+ 2
НОД(a
k−1
, 2)
= откуда a
k−1
= 2
, и последовательность состоит только из двоек. Пусть O
1
, O
2
, O
3
— центры малых окружностей (см. рис. Так как ∠KO
1
M = 90
◦
+
1 2
∠A, а ∠KLM = 90
◦
−
1 2
∠A, то ∠KO
1
M +
+
∠KLM = 180
◦
, и является серединой дуги KM вписанной в окружности. Аналогично и лежат на этой окружности и являются серединами дуги. Используя результат задачи 571, заключаем,
что построенные касательные проходят через центр окружности, вписанной в треугольник KLM, что и требовалосьдоказать.
580. Будем различатьдва типа ходов — внутренние и внешние, в зависимости оттого, куда ставится фишка, делающая ход внутрьисходного квадрата n × n клеток, или вне его
УЧЕБНЫЙ ГОД, 10
КЛАСС
353
A
B
C
K
L
M
O
1
O
2
O
3
Рис. 271
Пустьполучена позиция, где дальнейшие ходы невозможны,
причем сделано k внутренних ходов и l внешних.
Ясно, что никакие две фишки не находятся в соседних клетках;
поэтому в исходном квадрате n ×
× n не менее чем клеток пусты. Действительно, нетрудно понять, что квадрат разрезается на
доминошки
(в случае четной стороны) или
доминошки
и одну угловую клетку (в случае нечетной, а в каждой
доминошке
естьхотя бы одна пустая клетка. Так как каждый внутренний ход увеличивал количество пустых клеток не более, чем на а каждый внешний — не более, чем на 2, то имеем неравенство + 2l
n
2 Предположив теперь, что n четно, разобьем исходный квадрат на 4
четырехклеточных квадратиков и заметим, что на каждый квадратик при- шлосьне менее двух ходов, в которых участвовали (делали ходили сни- малисьс доски) фишки, стоявшие в клетках этого квадратика. Поскольку в каждом внутреннем ходе участвовали фишки не более, чем двух квадратиков, а в каждом внешнем — не более, чем одного, то + l
2
n
2 Из неравенств (1) и (2) получаем k + l
n
2 3
n
2 3
, те. утверждение задачи в этом случае верно.
Легко видеть, что оно верно также при n = 1 и при n = В случае n = 2m + 1, где m > 1, в
кресте
, образованном третьей сверху горизонталью и третьей слева вертикалью, выделим 2m
доминошек
, а остальную часть исходного квадрата разобьем на m
2
че- тырехклеточных квадратиков. В каждом внутреннем ходе участвовать могли фишки, принадлежащие не более чем двум из m
2
+ рассматриваемых фигура в каждом внешнем — не более чем одной. Имеем неравенство+ поскольку фишки каждого из квадратиков участвовали не менее, чем в двух ходах, афишки каждой
доминошки
— по крайней мере водном ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Из (1) и (3) следует, что 3(k + l) 4m
2
+ 4m = n
2
− 1. Если здесь 0 (mod 3), то, очевидно, 3(k + l) ив противном случае n
2
≡ 1 (mod 3) и k + l
n
2
− 1 3
=
n
2 3
. Тем самым утверждение задачи полностью доказано.
Замечание. Можно доказать, что для любого ε > 0 при достаточно больших n количество ходов будет больше, чем n
2
1 2
− ε
. Один из методов доказательства заключается в следующем.
Предположим противное. Рассмотрим
каемку
нашего квадрата ширины 2,
каемку
квадрата, получающегося выкидыванием первой, и т. д.,
всего k = [nε/8] каемок. Заметим, что внутри последней каемки содержится хотя бы n
2
(1
− ε/2)
2
> n
2
(1
− ε/4) клеток. Тогда за максимум 2
− ходов из нашего квадрата ушло хотя бы 2
1 2
n
2
(1
− фишек значит, было хотя бы ходов, на которых количество фишек в нем уменьшалось на 2; эти ходы вели из первой каемки вовне, и не затрагивали квадрата внутри первой каемки.
Тогда зане более чем n
2
1 2
−
3 ходов из следующего по величине квадрата ушло хотя бы 2
n
2
(1
−ε) фишек значит, было хотя бы εn
2
ходов,
на которых количество фишек в нем уменьшалось на 2; эти ходы вели из второй каемки вовне. Аналогично, из третьей каемки вовне вело хотя бы
2εn
2
ходов, . . . , из й каемки — ходов. Однако при больших n
2
k−2
εn
2
= 2
[nε/8]−2
εn
2
> n
2
, те. ходов гораздо больше, чем предполагалось. Противоречие. Заметим, что 44n естьсумма 4 экземпляров числа n и 4 экземпляров числа 10n. Если складыватьэти числа поразрядно, тов каждом разряде окажется сумма учетверенной цифры из этого же разряда числа n и учетверенной цифры из следующего разряда. Если при этом не происходит никаких переносов, то каждая цифра числа n складывается 8 рази сумма цифр во всех разрядах оказывается равной 800. При переносах же сумма цифр, очевидно, уменьшается (так как из одного разряда вычитается, а к другому прибавляется только 1). Поэтому в ситуации условия задачи переносов не происходит. Это означает, в частности, что любая цифра числа n не превосходит 2. Тогда приумножении напросто умножается на 3 каждая его цифра, а, значит, и сумма цифр. Поэтому сумма цифр числа 3n равна 300.
КЛАСС
353
A
B
C
K
L
M
O
1
O
2
O
3
Рис. 271
Пустьполучена позиция, где дальнейшие ходы невозможны,
причем сделано k внутренних ходов и l внешних.
Ясно, что никакие две фишки не находятся в соседних клетках;
поэтому в исходном квадрате n ×
× n не менее чем клеток пусты. Действительно, нетрудно понять, что квадрат разрезается на
доминошки
(в случае четной стороны) или
доминошки
и одну угловую клетку (в случае нечетной, а в каждой
доминошке
естьхотя бы одна пустая клетка. Так как каждый внутренний ход увеличивал количество пустых клеток не более, чем на а каждый внешний — не более, чем на 2, то имеем неравенство + 2l
n
2 Предположив теперь, что n четно, разобьем исходный квадрат на 4
четырехклеточных квадратиков и заметим, что на каждый квадратик при- шлосьне менее двух ходов, в которых участвовали (делали ходили сни- малисьс доски) фишки, стоявшие в клетках этого квадратика. Поскольку в каждом внутреннем ходе участвовали фишки не более, чем двух квадратиков, а в каждом внешнем — не более, чем одного, то + l
2
n
2 Из неравенств (1) и (2) получаем k + l
n
2 3
n
2 3
, те. утверждение задачи в этом случае верно.
Легко видеть, что оно верно также при n = 1 и при n = В случае n = 2m + 1, где m > 1, в
кресте
, образованном третьей сверху горизонталью и третьей слева вертикалью, выделим 2m
доминошек
, а остальную часть исходного квадрата разобьем на m
2
че- тырехклеточных квадратиков. В каждом внутреннем ходе участвовать могли фишки, принадлежащие не более чем двум из m
2
+ рассматриваемых фигура в каждом внешнем — не более чем одной. Имеем неравенство+ поскольку фишки каждого из квадратиков участвовали не менее, чем в двух ходах, афишки каждой
доминошки
— по крайней мере водном ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Из (1) и (3) следует, что 3(k + l) 4m
2
+ 4m = n
2
− 1. Если здесь 0 (mod 3), то, очевидно, 3(k + l) ив противном случае n
2
≡ 1 (mod 3) и k + l
n
2
− 1 3
=
n
2 3
. Тем самым утверждение задачи полностью доказано.
Замечание. Можно доказать, что для любого ε > 0 при достаточно больших n количество ходов будет больше, чем n
2
1 2
− ε
. Один из методов доказательства заключается в следующем.
Предположим противное. Рассмотрим
каемку
нашего квадрата ширины 2,
каемку
квадрата, получающегося выкидыванием первой, и т. д.,
всего k = [nε/8] каемок. Заметим, что внутри последней каемки содержится хотя бы n
2
(1
− ε/2)
2
> n
2
(1
− ε/4) клеток. Тогда за максимум 2
− ходов из нашего квадрата ушло хотя бы 2
1 2
n
2
(1
− фишек значит, было хотя бы ходов, на которых количество фишек в нем уменьшалось на 2; эти ходы вели из первой каемки вовне, и не затрагивали квадрата внутри первой каемки.
Тогда зане более чем n
2
1 2
−
3 ходов из следующего по величине квадрата ушло хотя бы 2
n
2
(1
−ε) фишек значит, было хотя бы εn
2
ходов,
на которых количество фишек в нем уменьшалось на 2; эти ходы вели из второй каемки вовне. Аналогично, из третьей каемки вовне вело хотя бы
2εn
2
ходов, . . . , из й каемки — ходов. Однако при больших n
2
k−2
εn
2
= 2
[nε/8]−2
εn
2
> n
2
, те. ходов гораздо больше, чем предполагалось. Противоречие. Заметим, что 44n естьсумма 4 экземпляров числа n и 4 экземпляров числа 10n. Если складыватьэти числа поразрядно, тов каждом разряде окажется сумма учетверенной цифры из этого же разряда числа n и учетверенной цифры из следующего разряда. Если при этом не происходит никаких переносов, то каждая цифра числа n складывается 8 рази сумма цифр во всех разрядах оказывается равной 800. При переносах же сумма цифр, очевидно, уменьшается (так как из одного разряда вычитается, а к другому прибавляется только 1). Поэтому в ситуации условия задачи переносов не происходит. Это означает, в частности, что любая цифра числа n не превосходит 2. Тогда приумножении напросто умножается на 3 каждая его цифра, а, значит, и сумма цифр. Поэтому сумма цифр числа 3n равна 300.
582. Задача является частным случаем задачи 575, когда точки E и совпадают сточкой точка K в данной задаче — это точка F задачи. Вначале докажем, что
УЧЕБНЫЙ ГОД, КЛАСС + y
2
x
2
+ Допустим противное x + y
2
< x
2
+ y
3
, тогда, складывая это неравенство с неравенством x
3
+ y
4
x
2
+ y
3
, получим (x+x
3
) + (y
2
+ y
4
) < 2x
2
+ что противоречит неравенствами Из (1) получаем + y
2
x
2
+ y
3
x
3
+ откуда + 2y
2
x
2
+ y
3
+ x
3
+ Замечая, что (1 + x
2
) + (1 + y
4
)
2x + 2y
2
x
2
+ y
3
+ x
3
+ y
4
, получаем неравенство 2 + x
2
+ y
4
x
2
+ y
3
+ x
3
+ y
4
, равносильное требуемому. Возьмем граф на 12 вершинах, которые соответствуют людям, две его вершины соединены, если люди незнакомы.
Если в этом графе нет циклов нечетной длины, то его вершины можно разбитьна две части, в каждой из которых вершины не будут соединены
(см., например, лемму к задаче 224 окружного тура, и поэтому найдутся попарно знакомых.
Предположим теперь, что в графе есть циклы нечетной длины. Рассмотрим нечетный цикл минимальной длины. Пустьего длина равна:
а) 3. Тогда, если среди 9 человек, не входящих в этот цикл, естьдва незнакомых, то среди оставшихся 7 человек из каждых 4 найдутся три знакомых. Таким образом, в подграфе на 7 вершинах каждые два ребра имеют общую вершину. Любое третье ребро обязано проходитьчерез эту вершину, иначе среди 4 человек не найдутся трех знакомых. Поэтому все ребра имеют общую вершину, и, удаляя эту вершину, мы получаем 6 попарно знакомых.
б) 5. Тогда, как и выше, среди оставшихся 7 из каждых 4 найдутся знакомых, и среди этих 7 найдутся 6 знакомых.
A
B
C
D
Рис. в) 7. Тогда среди 5 человек, не входящих в этот цикл, все попарно знакомы. Если естьчеловек из цикла, знакомый со всеми этими 5, то все доказано. В
противном случае, каждый из цикла незнаком с кем- то из оставшихся. Так как 7 > 5, то найдется человек
A
из оставшихся, незнакомый с двумя из цикла B, Из того, что мы взяли нечетный цикл минимальной длины, следует, что эти два незнакомых из цикла должны быть
незнакомы через одного D
(см.
рис. 272). Но тогда D знаком со всеми из пяти оставшихся, потому что удаляя из цикла D и заменяя на A, мы получаем снова цикл длины 7, а в дополнении к циклу длины 7 все попарно знакомы.
г) Цикла длины 9 не может бытьпо условию задачи
2
x
2
+ Допустим противное x + y
2
< x
2
+ y
3
, тогда, складывая это неравенство с неравенством x
3
+ y
4
x
2
+ y
3
, получим (x+x
3
) + (y
2
+ y
4
) < 2x
2
+ что противоречит неравенствами Из (1) получаем + y
2
x
2
+ y
3
x
3
+ откуда + 2y
2
x
2
+ y
3
+ x
3
+ Замечая, что (1 + x
2
) + (1 + y
4
)
2x + 2y
2
x
2
+ y
3
+ x
3
+ y
4
, получаем неравенство 2 + x
2
+ y
4
x
2
+ y
3
+ x
3
+ y
4
, равносильное требуемому. Возьмем граф на 12 вершинах, которые соответствуют людям, две его вершины соединены, если люди незнакомы.
Если в этом графе нет циклов нечетной длины, то его вершины можно разбитьна две части, в каждой из которых вершины не будут соединены
(см., например, лемму к задаче 224 окружного тура, и поэтому найдутся попарно знакомых.
Предположим теперь, что в графе есть циклы нечетной длины. Рассмотрим нечетный цикл минимальной длины. Пустьего длина равна:
а) 3. Тогда, если среди 9 человек, не входящих в этот цикл, естьдва незнакомых, то среди оставшихся 7 человек из каждых 4 найдутся три знакомых. Таким образом, в подграфе на 7 вершинах каждые два ребра имеют общую вершину. Любое третье ребро обязано проходитьчерез эту вершину, иначе среди 4 человек не найдутся трех знакомых. Поэтому все ребра имеют общую вершину, и, удаляя эту вершину, мы получаем 6 попарно знакомых.
б) 5. Тогда, как и выше, среди оставшихся 7 из каждых 4 найдутся знакомых, и среди этих 7 найдутся 6 знакомых.
A
B
C
D
Рис. в) 7. Тогда среди 5 человек, не входящих в этот цикл, все попарно знакомы. Если естьчеловек из цикла, знакомый со всеми этими 5, то все доказано. В
противном случае, каждый из цикла незнаком с кем- то из оставшихся. Так как 7 > 5, то найдется человек
A
из оставшихся, незнакомый с двумя из цикла B, Из того, что мы взяли нечетный цикл минимальной длины, следует, что эти два незнакомых из цикла должны быть
незнакомы через одного D
(см.
рис. 272). Но тогда D знаком со всеми из пяти оставшихся, потому что удаляя из цикла D и заменяя на A, мы получаем снова цикл длины 7, а в дополнении к циклу длины 7 все попарно знакомы.
г) Цикла длины 9 не может бытьпо условию задачи
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
д) Цикл длины 11. Тогда, как и выше при рассмотрении циклов длины, мы видим, что оставшийся человек может бытьне знаком максимум с двумя из цикла. Но тогда в цикле легко найти 5 человек, знакомых между собой и с оставшимся. (Например, взяв идущих через одного по циклу и знакомых с оставшимся класс. Ответ. Нет.
Предположим, что такие 19 чисел существуют и сумма цифр каждого из чисел равна S = 9k + n, n ∈ {0, 1, . . . , 8}. Тогда все эти числа имеют остаток n при делении на 9, и имеет место сравнение 19n = 18n+n ≡ 1999
(mod 9)
, откуда n ≡ 1 (mod 9), те n = 1.
1) Пусть k = 0, те S = 1. Рассмотрим 5 наименьших натуральных чисел с суммой цифр, равной 1. Это числа 1, 10, 100, 1000 и 10000. Но даже их сумма больше 1999.
2) Пусть k = 1, те. Рассмотрим 19 наименьших натуральных чисел чисел с суммой цифр, равной 10. Это числа 19, 28, 37, 46, 55, 64,
73, 82, 91, 109, 118, 127, 136, 145, 154, 163, 172, 181, 190. Их сумма равна < 1999
. Следующее натуральное число с суммой цифр, равной есть, что по крайней мерена больше любого из первых 19 чисел, и значит, сумма будет не менее 1990 + 18 = 2008 > 1999.
3) Пусть k 2, те. Но наименьшее число с суммой цифр не меньше 19 есть 199, а сумма любых 19 таких чисел будет заведомо больше
1999.
Таким образом, мы получили, что 19 чисел, удовлетворяющих условию, не существует. Предположим противное, те. существует такая расстановка целых чисел, что для любого отрезка AB с серединой C выполняется неравенство, где a, b, c — соответственно числа, стоящие в точках, B и C. Пусть A, B, C, A
n
, B
n
, n = 1, 2, . . ., — соответственно точки, 1, 0, −
1 2
n
,
1 числовой прямой, a, b, c, a
n
, b
n
— целые числа, записанные в этих точках. Тогда, по предположению, c <
a + b
2
, a
1
<
a + c
2
,
a
2
<
a
1
+ c
2
, и т. д. Отсюда следует, что max{a, c} > a
1
, так как a
1
<
<
a + c
2
max{a, c} + max{a, c}
2
= max
{a, c}. Аналогично, max{a
1
, c
} >
> a
2
, max{a
2
, c
} > a
3
, . . . , и max{b, c} > b
1
, max{b
1
, c
} > b
2
, . . . . Таким образом, если a
m
> c
, то c < a
m
a
m−1
− 1 . . . a − m, что при a − c невозможно поэтому при m max{1, a − c, b − c} получаем c, b
m
c, откуда a
m
+ b
m
2c, что противоречит нашему предположению УЧЕБНЫЙ ГОД, 11
КЛАСС
357
K
L
M
N
A
B
C
D
Q
F
E
R
Рис. 273
587. Введем обозначения (см. рис. 273). Как было показано в решении задачи 571, RQ KM EF , RE LN QF . Значит, образовавшийся четырехугольник — параллелограмм. Используя то, что касательные к окружности, проведенные из одной точки, равны и AB +CD = AD получаем RQ + EF = RE + QF , так как (RQ + EF ) − (RE + QF ) =
= (a
12
+ a
34
)
− (a
23
+ a
41
)
, где a
ij
— длина общей внешней касательной к окружностями Значит, RQF E — ромб. См. решение задачи 580.
589. Набор натуральных чисел, удовлетворяющий условию задачи,
условимся называть хорошим.
Пустьсуществует хороший набор. Ясно, что если (a, b, c, d) — хороший набор, то и тоже хороший набор, где k =
=
НОД(a, b, c, d). Поэтому в дальнейшем считаем, что
НОД(a, b, c, d) = 1.
(1)
Пустьодно изданных чисел, например a, имеет нечетный простой делитель. Тогда суммы b + c, c + d, b + d и, следовательно, сами числа b, c и
d
делятся на p ибо, например, 2d = (b+d)+(c+d)−(b+c)), что противоречит условию (1). Значит, числа a, b, c, d — степени двойки. Упорядочив данные числа в порядке возрастания, получим a = 2
m
, b = 2
n
, c = 2
r
,
d = 2
s
, где 0 = m n r s, r 1 (иначе m = n = r = 0, значит = b = Тогда число (a + c)
2
= (1 + 2
r
)
2
— нечетно и не может делиться начетное число bd. Противоречие
д) Цикл длины 11. Тогда, как и выше при рассмотрении циклов длины, мы видим, что оставшийся человек может бытьне знаком максимум с двумя из цикла. Но тогда в цикле легко найти 5 человек, знакомых между собой и с оставшимся. (Например, взяв идущих через одного по циклу и знакомых с оставшимся класс. Ответ. Нет.
Предположим, что такие 19 чисел существуют и сумма цифр каждого из чисел равна S = 9k + n, n ∈ {0, 1, . . . , 8}. Тогда все эти числа имеют остаток n при делении на 9, и имеет место сравнение 19n = 18n+n ≡ 1999
(mod 9)
, откуда n ≡ 1 (mod 9), те n = 1.
1) Пусть k = 0, те S = 1. Рассмотрим 5 наименьших натуральных чисел с суммой цифр, равной 1. Это числа 1, 10, 100, 1000 и 10000. Но даже их сумма больше 1999.
2) Пусть k = 1, те. Рассмотрим 19 наименьших натуральных чисел чисел с суммой цифр, равной 10. Это числа 19, 28, 37, 46, 55, 64,
73, 82, 91, 109, 118, 127, 136, 145, 154, 163, 172, 181, 190. Их сумма равна < 1999
. Следующее натуральное число с суммой цифр, равной есть, что по крайней мерена больше любого из первых 19 чисел, и значит, сумма будет не менее 1990 + 18 = 2008 > 1999.
3) Пусть k 2, те. Но наименьшее число с суммой цифр не меньше 19 есть 199, а сумма любых 19 таких чисел будет заведомо больше
1999.
Таким образом, мы получили, что 19 чисел, удовлетворяющих условию, не существует. Предположим противное, те. существует такая расстановка целых чисел, что для любого отрезка AB с серединой C выполняется неравенство, где a, b, c — соответственно числа, стоящие в точках, B и C. Пусть A, B, C, A
n
, B
n
, n = 1, 2, . . ., — соответственно точки, 1, 0, −
1 2
n
,
1 числовой прямой, a, b, c, a
n
, b
n
— целые числа, записанные в этих точках. Тогда, по предположению, c <
a + b
2
, a
1
<
a + c
2
,
a
2
<
a
1
+ c
2
, и т. д. Отсюда следует, что max{a, c} > a
1
, так как a
1
<
<
a + c
2
max{a, c} + max{a, c}
2
= max
{a, c}. Аналогично, max{a
1
, c
} >
> a
2
, max{a
2
, c
} > a
3
, . . . , и max{b, c} > b
1
, max{b
1
, c
} > b
2
, . . . . Таким образом, если a
m
> c
, то c < a
m
a
m−1
− 1 . . . a − m, что при a − c невозможно поэтому при m max{1, a − c, b − c} получаем c, b
m
c, откуда a
m
+ b
m
2c, что противоречит нашему предположению УЧЕБНЫЙ ГОД, 11
КЛАСС
357
K
L
M
N
A
B
C
D
Q
F
E
R
Рис. 273
587. Введем обозначения (см. рис. 273). Как было показано в решении задачи 571, RQ KM EF , RE LN QF . Значит, образовавшийся четырехугольник — параллелограмм. Используя то, что касательные к окружности, проведенные из одной точки, равны и AB +CD = AD получаем RQ + EF = RE + QF , так как (RQ + EF ) − (RE + QF ) =
= (a
12
+ a
34
)
− (a
23
+ a
41
)
, где a
ij
— длина общей внешней касательной к окружностями Значит, RQF E — ромб. См. решение задачи 580.
589. Набор натуральных чисел, удовлетворяющий условию задачи,
условимся называть хорошим.
Пустьсуществует хороший набор. Ясно, что если (a, b, c, d) — хороший набор, то и тоже хороший набор, где k =
=
НОД(a, b, c, d). Поэтому в дальнейшем считаем, что
НОД(a, b, c, d) = 1.
(1)
Пустьодно изданных чисел, например a, имеет нечетный простой делитель. Тогда суммы b + c, c + d, b + d и, следовательно, сами числа b, c и
d
делятся на p ибо, например, 2d = (b+d)+(c+d)−(b+c)), что противоречит условию (1). Значит, числа a, b, c, d — степени двойки. Упорядочив данные числа в порядке возрастания, получим a = 2
m
, b = 2
n
, c = 2
r
,
d = 2
s
, где 0 = m n r s, r 1 (иначе m = n = r = 0, значит = b = Тогда число (a + c)
2
= (1 + 2
r
)
2
— нечетно и не может делиться начетное число bd. Противоречие
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Пустькаждый из многоугольников A, B, C можно отделитьот двух других. Докажем, что их нельзя пересечь одной прямой. Предположим противное X, Y , Z — соответственно точки многоугольников A, B, лежащие на одной прямой. Тогда одна из точек, например Y , лежит на прямой между X и Z. Следовательно, B нельзя отделить от A итак как в противном случае точку Y , лежащую между двумя другими X и нужно отделитьот этих точек одной прямой, что невозможно.
В обратную сторону утверждение можно доказатьдвумя способами.
Пусть многоугольники нельзя пересечь одной прямой) Рассмотрим треугольники с вершинами X ∈ A, Y ∈ B, Z ∈ Пусть из всех таких треугольников наименьшую высоту из вершины имеет треугольник кстати, почему треугольник с наименьшей высотой существует. Тогда прямая, перпендикулярная высоте и проходящая через середину высоты, не пересекает многоугольники B, A итак как, в противном случае, существовал бы треугольник с меньшей высотой,
выходящей из Y
0 2) Рассмотрим две внешние касательные к многоугольниками Тогда они не могут пересекать B. Если мы сдвинем немного ту, которая лежит ближе кв направлении к многоугольнику B, то получим прямую,
отделяющую B от A и Рис. 274
591. Проведем плоскость, параллельную касательной плоскости, пересекающую ребра ив точках B
1
, и соответствен- но.
В плоскости ABC получим конфигурацию, изображенную на рис. 274. Заметим, что = ∠CAM по теореме об угле между касательной и хордой, а ∠CAM = как накрест лежащие при параллельных и секущей, те. Следовательно AB
1
C
1
∼ ACB. Откуда
B
1
C
1
BC
=
AB
1
AC
=
AC
1
AB
.
Аналогично,
C
1
D
1
CD
=
AC
1
AD
=
AD
1
AC
и
B
1
D
1
BD
=
AD
1
AB
=
AB
1
AD
.
Из этих равенств вытекает, что CD
=
AD
1
AB
· AC
=
B
1
D
1
AC
· BD
=
AB
1
AD
· AC
=
B
1
C
1
AD
· BC
В обратную сторону утверждение можно доказатьдвумя способами.
Пусть многоугольники нельзя пересечь одной прямой) Рассмотрим треугольники с вершинами X ∈ A, Y ∈ B, Z ∈ Пусть из всех таких треугольников наименьшую высоту из вершины имеет треугольник кстати, почему треугольник с наименьшей высотой существует. Тогда прямая, перпендикулярная высоте и проходящая через середину высоты, не пересекает многоугольники B, A итак как, в противном случае, существовал бы треугольник с меньшей высотой,
выходящей из Y
0 2) Рассмотрим две внешние касательные к многоугольниками Тогда они не могут пересекать B. Если мы сдвинем немного ту, которая лежит ближе кв направлении к многоугольнику B, то получим прямую,
отделяющую B от A и Рис. 274
591. Проведем плоскость, параллельную касательной плоскости, пересекающую ребра ив точках B
1
, и соответствен- но.
В плоскости ABC получим конфигурацию, изображенную на рис. 274. Заметим, что = ∠CAM по теореме об угле между касательной и хордой, а ∠CAM = как накрест лежащие при параллельных и секущей, те. Следовательно AB
1
C
1
∼ ACB. Откуда
B
1
C
1
BC
=
AB
1
AC
=
AC
1
AB
.
Аналогично,
C
1
D
1
CD
=
AC
1
AD
=
AD
1
AC
и
B
1
D
1
BD
=
AD
1
AB
=
AB
1
AD
.
Из этих равенств вытекает, что CD
=
AD
1
AB
· AC
=
B
1
D
1
AC
· BD
=
AB
1
AD
· AC
=
B
1
C
1
AD
· BC
УЧЕБНЫЙ ГОД, 11
КЛАСС
359
Значит, равносторонний тогда и только тогда, когда AB · CD =
= AC
· BD = AD · BC.
Осталосьзаметить, что углы, образуемые указанными в условии линиями пересечения, соответственно равны углам треугольника A
1
B
1
C
1
592. Ответ. Выигрывает Петя.
Разобьем контакты на четыре одинаковых группы A, B, C и D. В каждой группе пронумеруем контакты числами от 1 до 500. Мысленно покрасим в черный цвет провода между контактами с разными номерами, ив белый цвет — между контактами с одинаковыми номерами.
Петя будет отвечатьна любой ход Васи так, чтобы для каждого номера от контактов A
k
, B
k
, и отходило поровну черных проводов, и если у одного из контактов больше нет белых проводов, то их не было бы и у других контактов с таким же номером. До начала игры это условие,
очевидно, выполняется. Именно благодаря этому условию проигрышная ситуация впервые случится после Васиного хода.
Опишем подробно Петину стратегию. Сначала рассмотрим случай,
когда Вася режет черный провод. Если Вася перерезает провод между контактами одной группы, например, провод A
i
A
j
, то Петя перережет провода B
i
B
j
, и D
i
D
j
. Если Вася перерезает провод между проводами из разных групп и с разными номерами, например, провод A
i
B
j
, то
Петя в ответ перережет провода A
j
B
i
, и C
j
D
i
. Такие ходы Петя может сделать, так как из возможности отрезать один провод от некоторого контакта следует возможностьотрезатьпо одному проводу от вершин с таким же номером.
Остается рассмотретьслучай, когда Вася перерезал белый провод,
т. е, провод между контактами из разных групп, нос одинаковыми номерами. Рассмотрим четыре контакта A
k
, B
k
, и D
k
. Первоначально любые два из них соединены белым проводом. После того, как Вася перерезал первый из этих проводов, например, провод A
k
B
k
, Петя перережет два провода так, чтобы между этих контактов осталосьтри провода, имеющие один общий конец (например, Петя может перерезатьпровода и C
k
A
k
, после чего останутся провода A
k
D
k
, и C
k
D
k
, что подтверждает возможностьтакого хода. Если же Вася когда-нибудьперережет один из этих трех проводов, то от одного из контактов A
k
, или он отрежет последний провод к контактам с этим же номером k, следовательно,
от этого контакта будет отходитьеще какой-то черный провод. Значит, и от трех других контактов с номером k будут отходитьчерные провода, следовательно, Петя может перерезать два оставшихся белых провода между контактами с номером k, что они сделает
КЛАСС
359
Значит, равносторонний тогда и только тогда, когда AB · CD =
= AC
· BD = AD · BC.
Осталосьзаметить, что углы, образуемые указанными в условии линиями пересечения, соответственно равны углам треугольника A
1
B
1
C
1
592. Ответ. Выигрывает Петя.
Разобьем контакты на четыре одинаковых группы A, B, C и D. В каждой группе пронумеруем контакты числами от 1 до 500. Мысленно покрасим в черный цвет провода между контактами с разными номерами, ив белый цвет — между контактами с одинаковыми номерами.
Петя будет отвечатьна любой ход Васи так, чтобы для каждого номера от контактов A
k
, B
k
, и отходило поровну черных проводов, и если у одного из контактов больше нет белых проводов, то их не было бы и у других контактов с таким же номером. До начала игры это условие,
очевидно, выполняется. Именно благодаря этому условию проигрышная ситуация впервые случится после Васиного хода.
Опишем подробно Петину стратегию. Сначала рассмотрим случай,
когда Вася режет черный провод. Если Вася перерезает провод между контактами одной группы, например, провод A
i
A
j
, то Петя перережет провода B
i
B
j
, и D
i
D
j
. Если Вася перерезает провод между проводами из разных групп и с разными номерами, например, провод A
i
B
j
, то
Петя в ответ перережет провода A
j
B
i
, и C
j
D
i
. Такие ходы Петя может сделать, так как из возможности отрезать один провод от некоторого контакта следует возможностьотрезатьпо одному проводу от вершин с таким же номером.
Остается рассмотретьслучай, когда Вася перерезал белый провод,
т. е, провод между контактами из разных групп, нос одинаковыми номерами. Рассмотрим четыре контакта A
k
, B
k
, и D
k
. Первоначально любые два из них соединены белым проводом. После того, как Вася перерезал первый из этих проводов, например, провод A
k
B
k
, Петя перережет два провода так, чтобы между этих контактов осталосьтри провода, имеющие один общий конец (например, Петя может перерезатьпровода и C
k
A
k
, после чего останутся провода A
k
D
k
, и C
k
D
k
, что подтверждает возможностьтакого хода. Если же Вася когда-нибудьперережет один из этих трех проводов, то от одного из контактов A
k
, или он отрежет последний провод к контактам с этим же номером k, следовательно,
от этого контакта будет отходитьеще какой-то черный провод. Значит, и от трех других контактов с номером k будут отходитьчерные провода, следовательно, Петя может перерезать два оставшихся белых провода между контактами с номером k, что они сделает
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Отметим, что каждый раз после хода Пети описанное выше условие выполняется. Следовательно, Петя всегда сможет сделатьход, итак как количество проводов конечно, проиграет Вася г класс. Ответ. a + b + c = Если x
2 1
+ ax
1
+ 1 = и x
2 1
+ bx
1
+ c = 0
, то (a − b)x
1
+ (1
− c) = 0 ⇒
⇒ x
1
=
c − 1
a − Аналогично, из равенств x
2 2
+ x
2
+ a = и x
2 2
+ cx
2
+ b = следует − b
c − очевидно, c = 1), те. С другой стороны, по теореме Виета
1
x
1
— кореньпервого уравнения.
Значит, x
2
— общий кореньуравнений x
2
+ ax + 1 = и x
2
+ x + a =
= 0
, откуда (a − 1)(x
2
− 1) = 0. Но при a = 1 эти уравнения не имеют действительных корней. Значит, x
2
= 1
, тогда x
1
= 1
⇒ a = −2, b + c =
=
−1.
594. Узнав наибольший общий делитель чисел X + 1 и 2, Саша определит четность X. Если X оказалосьчетным, то второй вопрос будет о наибольшем общем делителе X + 2 и 4, а если нечетным, то о наибольшем общем делителе X + 1 и 4. Таким образом, Саша узнает остаток отделения на 4. Вообще, пусть , задав k вопросов (k 5), Саша определил остаток отделения на 2
k
. Тогда (k + м вопросом он узнает наибольший общий делитель X + 2
k
− и заметим, что 0 < 2
k
−
− r
k
< 2
k+1
64 < 100). Если (X + 2
k
− r
k
, 2
k+1
) = 2
k+1
, то остаток отделения на равен 2
k
+ r
k
, а если (X + 2
k
− r
k
, 2
k+1
) = 2
k
, то этот остаток равен Итак, задав 6 вопросов, Саша узнает остаток отделения на 64. Ясно, что чисел с таким остатком при делении на 64 в пределах первой сотни не более 2. Если их все же 2 — скажем, a и a+64, то Петя может задать вопрос
Чему равен наибольший общий делитель X + 3 − r и 3?
, где r
— остаток отделения на 3. Ясно, что если X = a, то ответа если = a + 64
, то 1. Итак, седьмым вопросом число X определится одно- значно.
Замечание. Можно заметить, что первые шесть вопросов Саша употребил на отыскание последних шести цифр двоичной записи числа X.
595. Пусть и N
— точки пересечения серединных перпендикуляров кис прямыми AB и BC соответственно. Тогда ∠ABC =
=
∠N
AB =
∠M
CB
, поэтому точки A, M
, C, лежат на одной ок-
Отметим, что каждый раз после хода Пети описанное выше условие выполняется. Следовательно, Петя всегда сможет сделатьход, итак как количество проводов конечно, проиграет Вася г класс. Ответ. a + b + c = Если x
2 1
+ ax
1
+ 1 = и x
2 1
+ bx
1
+ c = 0
, то (a − b)x
1
+ (1
− c) = 0 ⇒
⇒ x
1
=
c − 1
a − Аналогично, из равенств x
2 2
+ x
2
+ a = и x
2 2
+ cx
2
+ b = следует − b
c − очевидно, c = 1), те. С другой стороны, по теореме Виета
1
x
1
— кореньпервого уравнения.
Значит, x
2
— общий кореньуравнений x
2
+ ax + 1 = и x
2
+ x + a =
= 0
, откуда (a − 1)(x
2
− 1) = 0. Но при a = 1 эти уравнения не имеют действительных корней. Значит, x
2
= 1
, тогда x
1
= 1
⇒ a = −2, b + c =
=
−1.
594. Узнав наибольший общий делитель чисел X + 1 и 2, Саша определит четность X. Если X оказалосьчетным, то второй вопрос будет о наибольшем общем делителе X + 2 и 4, а если нечетным, то о наибольшем общем делителе X + 1 и 4. Таким образом, Саша узнает остаток отделения на 4. Вообще, пусть , задав k вопросов (k 5), Саша определил остаток отделения на 2
k
. Тогда (k + м вопросом он узнает наибольший общий делитель X + 2
k
− и заметим, что 0 < 2
k
−
− r
k
< 2
k+1
64 < 100). Если (X + 2
k
− r
k
, 2
k+1
) = 2
k+1
, то остаток отделения на равен 2
k
+ r
k
, а если (X + 2
k
− r
k
, 2
k+1
) = 2
k
, то этот остаток равен Итак, задав 6 вопросов, Саша узнает остаток отделения на 64. Ясно, что чисел с таким остатком при делении на 64 в пределах первой сотни не более 2. Если их все же 2 — скажем, a и a+64, то Петя может задать вопрос
Чему равен наибольший общий делитель X + 3 − r и 3?
, где r
— остаток отделения на 3. Ясно, что если X = a, то ответа если = a + 64
, то 1. Итак, седьмым вопросом число X определится одно- значно.
Замечание. Можно заметить, что первые шесть вопросов Саша употребил на отыскание последних шести цифр двоичной записи числа X.
595. Пусть и N
— точки пересечения серединных перпендикуляров кис прямыми AB и BC соответственно. Тогда ∠ABC =
=
∠N
AB =
∠M
CB
, поэтому точки A, M
, C, лежат на одной ок-
УЧЕБНЫЙ ГОД, 9
КЛАСС
361
ружности. Далее, ∠AM
C =
∠ABC + ∠M
CA = 2
∠ABC = ∠AOC, так что O лежит на той же окружности, а тогда эта окружностьи есть, и = M
, N = N
. Теперь, поскольку дуга
M этой окружности равна, то симметричная ей относительно MN окружность(с центром) описана около Рис. Тогда ∠LBN =
π
2
− ∠BMN =
=
π
2
− ∠BCA, что и требовалось. Предположим, что существует граф, степени всех вершин которого более двух, но длина любого цикла в этом графе делится на 3. Рассмотрим такой граф G с наименьшим числом вершин. Очевидно, в этом графе существует цикл Z, пустьэтот цикл последовательно проходит по вершинам, A
2
, . . . , A
3k
. Пустьсуществу- ет путь S, соединяющий вершины и и не проходящий по ребрам цикла Z. Рассмотрим циклы и Z
2
, состоящие из пути и двух
половинок
цикла Z. Поскольку длины обоих этих циклов делятся на 3, нетрудно заметить, что длина пути S делится на 3. В частности, из доказанного утверждения следует, что никакая вершина X, не входящая в цикл Z, не может бытьсо- единена ребрами с двумя разными вершинами цикла Z. Кроме того, ребра,
выходящие из вершин цикла Z, отличные от ребер этого цикла, все раз- личны.
Объединим все вершины A
1
, A
2
, . . . , цикла Z в одну вершину которую соединим ребрами со всеми вершинами, которые были соединены с вершинами цикла Z. Очевидно, в полученном графе меньше вершин,
чем в графе G, и степенькаждой вершины по-прежнему более двух. Из доказанного выше следует, что длина любого цикла в графе делится на 3. Мы получили противоречие ведьв выбранном ранее графе G было минимальное количество вершин среди всех таких графов.
Таким образом, в любом графе, степени всех вершин которого более двух, существует цикл, длина которого не делится на 3. Остается лишь применитьэто утверждение для графа, вершины которого соответствуют городам, а ребра — дорогам
КЛАСС
361
ружности. Далее, ∠AM
C =
∠ABC + ∠M
CA = 2
∠ABC = ∠AOC, так что O лежит на той же окружности, а тогда эта окружностьи есть, и = M
, N = N
. Теперь, поскольку дуга
M этой окружности равна, то симметричная ей относительно MN окружность(с центром) описана около Рис. Тогда ∠LBN =
π
2
− ∠BMN =
=
π
2
− ∠BCA, что и требовалось. Предположим, что существует граф, степени всех вершин которого более двух, но длина любого цикла в этом графе делится на 3. Рассмотрим такой граф G с наименьшим числом вершин. Очевидно, в этом графе существует цикл Z, пустьэтот цикл последовательно проходит по вершинам, A
2
, . . . , A
3k
. Пустьсуществу- ет путь S, соединяющий вершины и и не проходящий по ребрам цикла Z. Рассмотрим циклы и Z
2
, состоящие из пути и двух
половинок
цикла Z. Поскольку длины обоих этих циклов делятся на 3, нетрудно заметить, что длина пути S делится на 3. В частности, из доказанного утверждения следует, что никакая вершина X, не входящая в цикл Z, не может бытьсо- единена ребрами с двумя разными вершинами цикла Z. Кроме того, ребра,
выходящие из вершин цикла Z, отличные от ребер этого цикла, все раз- личны.
Объединим все вершины A
1
, A
2
, . . . , цикла Z в одну вершину которую соединим ребрами со всеми вершинами, которые были соединены с вершинами цикла Z. Очевидно, в полученном графе меньше вершин,
чем в графе G, и степенькаждой вершины по-прежнему более двух. Из доказанного выше следует, что длина любого цикла в графе делится на 3. Мы получили противоречие ведьв выбранном ранее графе G было минимальное количество вершин среди всех таких графов.
Таким образом, в любом графе, степени всех вершин которого более двух, существует цикл, длина которого не делится на 3. Остается лишь применитьэто утверждение для графа, вершины которого соответствуют городам, а ребра — дорогам
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Докажем по индукции, что при n = 5m все числа от 1 до n выписаны на доску, a
5m
= 5m
− 2 и при всех k 5m выполняется равенство a
k
+ 5
. База 1 → 4 → 2 → 5 → 3 → 6. Индуктивный шаг так как при n = 5m все числа от 1 до 5m уже выписаны и a
5m
= 5m
− 2, то следующие пятьчисел выглядят так a
5m+1
= 5m + 1
, a
5m+2
= 5m + 4
,
a
5m+3
= 5m + 2
, a
5m+4
= 5m + 5
, a
5m+5
= 5m + 3
. Шаг индукции дока- зан.
Таким образом, числа, дающие при делении на 5 остатки 4, 1 и 0, появляются на доске после увеличения предыдущего числа на 3. Но только такие остатки и могут даватьпри делении на 5 квадраты натуральных чисел. Заметим, что в конце никакие две разноцветные фишки не стоят нив одной строке, нив одном столбце. Действительно, если исходно черная фишка стояла водном столбце с белой, то ее сняли в первый раза если после первого снятия белая фишка стоит водной строке с черной, то ее сняли во второй раз.
Пустьв конце черные фишки стоят в a строках и b столбцах, тогда белые могут стоятьне более, чем в 2n−a строках и 2n−b столбцах. Но тогда черных фишек не более ab, а белых не более (2n − a)(2n − b). Поскольку то либо черных, либо белых фишек осталосьне более Рис. 276
5m
= 5m
− 2 и при всех k 5m выполняется равенство a
k
+ 5
. База 1 → 4 → 2 → 5 → 3 → 6. Индуктивный шаг так как при n = 5m все числа от 1 до 5m уже выписаны и a
5m
= 5m
− 2, то следующие пятьчисел выглядят так a
5m+1
= 5m + 1
, a
5m+2
= 5m + 4
,
a
5m+3
= 5m + 2
, a
5m+4
= 5m + 5
, a
5m+5
= 5m + 3
. Шаг индукции дока- зан.
Таким образом, числа, дающие при делении на 5 остатки 4, 1 и 0, появляются на доске после увеличения предыдущего числа на 3. Но только такие остатки и могут даватьпри делении на 5 квадраты натуральных чисел. Заметим, что в конце никакие две разноцветные фишки не стоят нив одной строке, нив одном столбце. Действительно, если исходно черная фишка стояла водном столбце с белой, то ее сняли в первый раза если после первого снятия белая фишка стоит водной строке с черной, то ее сняли во второй раз.
Пустьв конце черные фишки стоят в a строках и b столбцах, тогда белые могут стоятьне более, чем в 2n−a строках и 2n−b столбцах. Но тогда черных фишек не более ab, а белых не более (2n − a)(2n − b). Поскольку то либо черных, либо белых фишек осталосьне более Рис. 276
