Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2001/05/59.pdf Дата изменения: Fri Dec 23 19:26:35 2005 Дата индексирования: Tue Oct 2 00:30:07 2012 Кодировка: Windows-1251 Поисковые слова: ultraviolet

ОТВЕТЫ,

УКАЗАНИЯ,

РЕШЕНИЯ

BN BN BN R r1 постоянно. отношение R 4. Построим граф, вершины которого соответствуют городам, а ребра дорогам. В этом графе между любыми двумя вершинами есть единственный путь, следовательно, в нем нет циклов (такой граф называется деревом). По условию, в этом графе есть 100 вершин, из которых выходит ровно одно ребро (такие вершины называются висячими) пусть это вершины A1, A2 ,K, A100 . Для каждой пары висячих вершин Ai и A j существует единственный путь между ними; назовем количество ребер на этом пути расстоянием между этими вершинами и будем обозначать через d Ai , A j . Из конечности числа способов разбить эти 100 вершин на 50 пар следует, что при одном из способов достигается максимум суммы расстояний между вершинами в парах. Соединим пары вершин при этом разбиении 50 новыми ребрами (остальные ребра будем называть старыми). Мы докажем, что после этого даже при удалении любого ребра сохраняется связность графа (т.е., возможность из любой вершины попасть в любую другую). Предположим противное: пусть при удалении ребра между вершинами В и С граф распался на две части, которые не связаны между собой. Нетрудно заметить, что удаленное ребро было старым, в одной из полученных частей находится вершина В, а в другой вершина С. Очевидно, в каждой части должна быть вершина, из которой выходит ровно одно старое ребро, и каждое новое ребро соединяет две вершины из одной части. Но тогда в одной из частей должно быть новое ребро, соединяющее вершины Ai и A j , а в другой соединяющее вершины Ak и Am . Однако в этом случае нетрудно проверить, что

Fr I = F GH R JK GH
2 1

BK

I JK

59

2

=

BP

= 1-

NP

= 1-

r

. Отсюда следует, что

ны), аналогично, SCFA = SCB A и S AFB = S AC B . 1 1 Заметим, что точка F лежит внутри треугольника АВС: поскольку A1 и B1 лежат на высотах, а не на их продолжениях, точка F лежит внутри угла АСВ; если бы при этом F лежала вне треугольника АВС, то сумма площадей

S AFC + SBFC = S AB C + SBA C была бы больше площади S тре1 1 угольника АВС противоречие с условием; таким образом, C1 лежит на высоте, а не на ее продолжении. Ввиду равенств S = S AFB + SBFC + SCFA = S AC B + SBA C + SCB A получаем, что S
AC1B

=S

AC1B

, откуда следует совпадение точек C1 и C1 .

1

1

1

e

j

8. n = p3, где p простое, или n = 12. Легко видеть, что указанные в ответе числа удовлетворяют условию задачи. Покажем, что других чисел, удовлетворяющих условию, не существует. Случай нечетного n рассмотрен в решении задачи 8 для 9 класса. Пусть n четно и не является степенью двойки; предm ставим его в виде n = 2 k , где m 1 , а k > 1 нечетное число. Заметим, что k + 2 1 = k + 1 де литель n. Поскольку k + 1, k = 1 , то k + 1 = 2 , > 1 . Поэто2 му 2 + k - 1 = k + 3 тоже делитель n. Заметим, что k + 3 = k + 1 + 2 = 2 + 2 не делится на 22 . Кроме того,

b

g

и k 3 . Значит, n = 2 3 . Но m = 1 не подходит; m 3 также не подходит, так как в этом случае мы получили бы, что 3 2 + 3 - 1 = 10 также делитель n.

b

k + 3, k = 3, k 3 . Из этого заключаем, что k + 3 2 3 = 6 ,
m

bg gbg

11
1. 97 средних чисел. Заметим, что если число k = m является средним, то число k = 100 m также является средним. Поэтому если число k = = 1 не является средним, то число k = 99 также не является средним и количество средних чисел не больше 97 ( k 100 ). Если же число k = 1 является средним, то вес одной из гирек равен S и, следовательно, только k = 99 также является средним числом. Значит, количество средних чисел не превосходит 97. Приведем пример набора из 100 гирек с весами a1 ,K, a100 , для которого все числа от 2 до 98 (всего 97 чисел) средние. Пусть a1 = a2 = 1 , an + 2 = an + an +1 , n = 1, 2, ..., 97 последовательные числа Фибоначчи и S = a1 + a2 + K + a98 . Выберем a100 = S - a99 . Тогда суммарный вес всех гирек равен 2S и в то же время a100 + a99 = a100 + a98 + a97 = a100 + a98 + a96 + a95 = = a100 + a = a100 + a
98 98

d Ai , A

e

j

j + dd

Ak , Am < d Ai , Ak + d A j , Am ,

id

ie

j

что противоречит максимальности суммы расстояний в выбранных парах. Следовательно, при удалении ребра ВС возможность попасть из любой вершины в любую другую должна сохраниться. 5. По условию, P x = x - x1 x - x2 x - x3 , следовательно,

P

b g d id id i dQb xgi = dQb xg - x idQb xg - x idQb xg - x i , где Qb xg
1 2 3

- xi 0 ,

i = 1, 2, 3. Пусть Di (i = 1, 2, 3) дискриминант трехчлена 1 Q x - xi . По условию, Di < 0 , т.е. 2001 - xi > . Перемно4 жив полученные неравенства, имеем 1 P 2001 = 2001 - x1 2001 - x2 2001 - x3 > . 64

bg

b

gd

id

id

i

+a
92

96

+a
90

94

+a

93

=

7. Пусть окружность, проходящая через Н, A1 , B1 , пересека ет второй раз прямую СН в точке C1 . Достаточно доказать, что C1 совпадает с C1 . Рассмотрим точку F, диаметрально противоположную точке Н (рис.10). Углы HA1 F , HB1 F и HC1 F прямые, так как опираются на диа* метр. Поэтому

+a

96

+a

94

+a

+a

+ K + a6 + a4 + a3 + a2 = S .

0 * )
. 10

)



A1 F || BC , B1 F || AC , C1 F || AB . Отсюда следует равенство

+




.

площадей SBFC = SBA C (в тре1 угольниках BFC и + BA C основание об1 щее, а высоты рав-

Следовательно, средними являются числа 2, 3, 4, ..., 51. Но тогда средними будут и числа 100 2 = 98, 100 3 = 97, ... ..., 100 48 = 52, т.е. все числа от 2 до 98 средние. 3. Для каждой из прямых, пересекающих все многоугольники набора P , проведем параллельную ей прямую через центр О 1 некоторой окружности S. Обозначим через S1 множество точек пересечения этих прямых с S. Определим аналогично для набора P2 множество S2 S . Покажем, что S1 U S2 = S . Спроектируем многоугольники наборов P и P2 на произвольную прямую l. Из условия следу1 ет, что при этом получатся два набора отрезков P и P2 та1 ких, что любые два отрезка из разных наборов имеют общую точку. Возьмем отрезок I, левый конец А которого является среди полученных отрезков самым правым. Пусть, например, I принадлежит P , тогда все отрезки P2 содержат точку А. Следо1