Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2003/02/50.pdf
Дата изменения: Fri Dec 23 19:27:22 2005
Дата индексирования: Tue Oct 2 00:31:16 2012
Кодировка: Windows-1251

Поисковые слова: asteroid
#
K Oi L
Рис. 2

КВАНT 2003/?2

Oj

Будем обозначать через Vij

6 (О.Гольберг). Заметим, что окружности не пересекаются и (поскольку sin x < x при x > 0) 1 меньше радианной OOj i меры угла KOiOj (рис.2), где OK и OL касаi i тельные к окружности j . угол KOiL, через Wij

Но

2 < Vij , значит, OOj i

()

lОR

е

1 PPl l

+1

+2

m? l + 1; m,lОR

е

1 + Pl Pm

lОR, tОS

е

( k - 2) 1 < . (2) PlQt 2

Оценим первую из сумм. Проведем общие внутренние каса2 2 7 9 8

l+

l

объединение Vij с вертикальным ему углом, через Vij 1 < радианную меру угла Vij , Wij = 2 Vij . Тогда OOj i 1 1 1 < Vij = Wij . < OOj 2 4 i Рассмотрим выпуклую оболочку центров данных окружностей. При этом три центра не могут лежать на одной прямой, так как в противном случае проходящая через них прямая пересекает три окружности. Следовательно, в выпуклой оболочке k вершин, где k ? 3 . Обозначим через P , P2 , K , Pk вершины выпуклой оболочки по порядку, на1 пример, по часовой стрелке, Qk +1, K , Qn вершины, не вошедшие в выпуклую оболочку. Пусть R = {1, K , k}, S = {k + 1, K , n}. Предположим, что S не пусто, т.е. k< n . Выберем произвольно l О S . Углы Wlj , j ? l , пересекаются только в вершине Ql , так как в противном случае прямая, проходящая через Ql и общую точку этих углов, пересекает три окружности. Поэтому

()

()

() ()

()

2
Рис. 4

l

2

l+

7

9

2 8

l

2
Рис. 5

l

е (Wlj )
j ?l

< 2 Ю

е
j ?l

1 1 < OOj 4 l

е (Wlj )
j ?l

<

. 2

Сложив эти неравенства по всем l О S , получим

тельные к окружностям с центрами Pl -1, Pl , Pl +1 , как показано на рисунке 4. Пусть они пересекаются в точке W и пересекают отрезки PPl -1 и PPl + 1 в точках V и U соответl l ственно. Тогда РUWV < , так как если РUWV ? , то найдется прямая, пересекающая все три окружности с центрами Pl -1, Pl и Pl +1 (рис.5). Итак, получаем, что т.е.
РWVPl + РPlUW + l < , РWVPl + РWUPl < - l .

2

i ? j; i, j ОS

е

1 + OOj i

i ОS, j ОR

е

1 < ( n - k) . OiPj 2

(1)

Выберем теперь произвольно l О R . РасPl+ смотрим углы V , j ? l . Pl lj Они все лежат в угле, образованном касательными из Pl к окружностям с центрами Pl -1 и Pl +1 (здесь и далее Pl P0 = Pk , Pk + 1 = P1 ), лежащими вне выпуклой Рис. 3 оболочки (рис.3). Поэтому если обозначить углы Pl -1Pl Pl +1 , l О R , через l , то


Из равенства радиусов окружностей следует, что V середина отрезка PPl -1 , поэтому l
sin РWVPl = 2 PPl l
-1

Ю +

1 Pl Pl

-1

= ?

sin РWVPl РWVPl < Ю 2 2 РWVPl РWUPl - l + < . 2 2 2
k

1 PP ll 1 PPl l

-1

1 Pl Pl

+1

Сложив эти неравенства по всем l О R , получаем
2
lОR

е

-1

<

lОR

е

- l = , так как 2

е

l =1

l = ( k - 2) .
(3)

Итак,

е (Vlj )
j ?l

1 ? l + Vl l -1 + Vl l +1 . 2 1 Vl l -1 + Vl l + 1 ? l . 2

(

)(

)

lОR

е

1 PPl l

-1

?

. 2 1 1 + 2е Pi Pj PiPi iОR

Отсюда
j ? l - 1, l, l + 1

Сложив неравенства (1), (2) и (3), получаем

е

V + lj

()

(

)(

)

2

i ? j; i, j ОS

е

1 1 +2 е +2 QQj Qi Pj i iОS, j ОR


j ? i + 1; i, j ОR

е

-1

?

Сложив эти неравенства по всем l О R и воспользовавшись равенством

е
получаем
lОR

k

( k - 2 ) ( n - k) + + = ( n - 1) . 2 2 2 2 2е
i? j

l =1

l = ( k - 2) ,

Но сумма в левой части есть

е

Vl

(

l +1

)

+2

m? l + 1; m,lОR

е

Vl

( m)

+

lОR, tОS

е

( Vlt ) ? ( k - 2) .

е
i? j

1 ? ( n - 1) , что и требовалось доказать. OOj 4 i Публикацию подготовили Н.Агаханов, Д.Терешин

1 , поэтому OOj i