Документ взят из кэша поисковой машины. Адрес оригинального документа : http://dfgm.math.msu.su/files/0students/2009-dip-shnurnikov.pdf Дата изменения: Fri May 15 15:44:02 2009 Дата индексирования: Sat Apr 9 22:56:39 2016 Кодировка: Windows-1251 Поисковые слова: п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п р п р п р п

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. Ломоносова

Механико-математический факультет

Дипломная работа

Количества областей в разбиениях плоскости прямыми и другие задачи комбинаторной геометрии.

студента 5 курса кафедры дифференциальной геометрии и приложений И.Н. Шнурникова

Научный руководитель: академик А.Т. Фоменко

Москва 2009


Содержание.
Введение 1. Разбиения плоскости прямыми
1.1 1.2 1.3 1.4 1.5 Примеры, история вопроса и его постановка . . . . . . . . . . . . . . . . . . . Формулировка теоремы и следствия из нее . . . . . . . . . . . . . . . . . . . . Доказательство теоремы и вспомогательных утверждений . . . . Обзор работ предшественников . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Уточнения некоторых доказанных ранее утверждений . . . . . . . . . . . . . 2 4 ........... 4 ........... 5 ........... 6 . . . . . . . . . . 20 . . . . . . . . . . 21 30 30 31

2. Мощность отделяемого множества вершин многомерного куба
2.1 Формулировка и мотивация гипотезы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Доказательства гипотезы в частных случаях . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Серии специальных и ретрагируемых спайнов

41

38 3.1 Оценка количества двумерных клеток специальных спайнов . . . . . . . . . . . . . 38 3.2 Серия специальных спайнов с одной двумерной клеткой. . . . . . . . . . . . . . . . . 40 3.3 Специальные спайны с одной двумерной клеткой аналоги примеров Адамса.

4. Ограничения на топологию 3-многообразий, являющихся пересечением трех квадрик 43
4.1 4.2 4.3 4.4 Возникновение задачи из теории интегрируемых систем . . Условия применимости теорем алгебраической геометрии . Невырожденность в R6 и в С6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Прямая без вещественных точек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 43 44 45 47 49 52 54 56

5. Алгоритмы пересечения поверхностей прямой
5.1 Поверхность вращения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Линейчатая поверхность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Поверхность выдавливания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Литература

1


Введение.
Диплом состоит из пяти независимых друг от друга параграфов, каждый из которых посвящен отдельной задаче комбинаторной геометрии. Первые четыре чисто теоретичны, пятый параграф написан для практического использования.

(1) В параграфе про прямые решен вопрос о том, на сколько областей n прямых делят плоскость. Этот вопрос был впервые поставлен Б. Грюнбаумом в
[Gru72]. Он заметил эквивалентность вопросов для аффинной и вещественной проективной плоскостей. Н. Мартинов в [M ar93] в качестве ответа привел некоторое подмножество множества натуральных чисел, показал, что каждое число из этого подмножества подходит, и попытался доказать, что числа не из этого подмножества не подходят. Не зная об этих работах, В.И. Арнольд в [Арн08] поставил еще раз вопрос о количестве областей и доказал неравенства, из которых можно сформулировать ответ. Мною доказано, что числа не из множества Н. Мартинова не подходят, т.е. вопрос Б. Грюнбаума теперь решен полностью. В ходе приведенного ниже доказательства (теоремы 1, впервые сформулированной Н. Мартиновым) были усилены неравенства В.И. Арнольда.

А.Немировского, К.Роса утверждает, что любая касательная гиперплоскость к сфере строго отделяет от центра сферы не более чем 2n-2 вершин куба. В разделе 2.2 доказана эта гипотеза для n 6 (теорема 2). Построена серия примеров гиперплоскостей, строго отделяющих ровно 2n-2 вершин n-мерного куба для любого n (пример 2). Доказано, что гиперплоскости, ортогональные радиус-векторам вершин куба, строго отделяют менее чем 2n-2 вершин куба при n 3 (теорема 3).

(2) Рассмотрим n-мерный куб и вписанную в него сферу. Гипотеза А.Бен-Тала,

(3) В параграфе про спайны оценено количество специальных ретрагируемых спайнов. (а) Оценка количества двумерных клеток специальных спайнов. (б) Улучшенная оценка количества незамкнутых гиперболических многообразий из [F M P 03] (лемма 2). Оценка осталась экспоненциальной, однако увеличилось основание с 6 до 6 2. Для этого был рассмотрен новый граф особенностей и подходящий для него способ подсчета спайнов. (в) По идее А. Т. Фоменко регулярные окрестности особых графов в спайнах многообразий из [F M P 03] были проверены на возможность ретрагироваться на свою границу (границу окрестности) и доказано, что все они ретрагируются (лемма 3). Т.е. как следствие существует много двумерных полиэдров, обобщающих примеры Адамса. (4) В параграфе про квадрики найдены:
Q3 = {f1 (z1 , . . . , z6 ) = d1 , C
(а) условия на параметры квадрик, при которых совместная поверхность уровня

f2 (z1 , . . . , z6 ) = d2 ,

f3 (z1 , . . . , z6 ) = d3 }

невырождена в C6 (теорема 4 и замечание к ней), (б) явно найдена прямая (лежащая в Q3 C6 ), определяемая вещественным паC раметром и комплексным (для почти всех исходных многообразий Q3 ) параметром R ч, на которой нет точек с вещественными координатами. 2


Найденную прямую можно использовать для применения теоремы Коллара (см. [K ol]) для определения топологического типа трехмерного многообразия, заданного в R6 тремя квадратичными уравнениями (интегралом площадей f2 , геометрическим интегралом f1 и гамильтонианом f3 движения четырехмерного твердого тела): 1. x2 + x2 + x2 + x2 + x2 + x2 = d1 , 1 2 3 4 5 6 2. x1 x4 + x2 x5 + x3 x6 = d2 , 3. c1 x2 + c2 x2 + c3 x2 + c4 x2 + c5 x2 + c6 x2 = d3 . 1 2 3 4 5 6 Для трех поверхностей компьютерной геометрии поверхности вращения, линейчатой поверхности и поверхности выдавливания приведены явные алгоритмы, находящие все точки пересечения поверхности и прямой. Поверхности заданы в параметрическом виде, и система двух уравнений двух неизвестных (определяющая точки пересечения) сведена к одному уравнению одного неизвестного.

(5) Алгоритмы пересечения поверхностей прямой.

3


1. Разбиения плоскости прямыми.
Рассмотрим набор , состоящий из n попарно различных проективных прямых на вещественной двумерной проективной плоскости RP2 . Удалим из плоскости RP2 (с обычной топологией) все точки всех прямых набора , получим подмножество плоскости RP2 . Наделим полученное подмножество индуцированной (из плоскости RP2 ) топологией. Если получившееся топологическое пространство имеет ровно f компонент связности, то будем говорить, что набор прямых делит плоскость RP2 на f областей. Цель раздела 1. состоит в нахождении (для каждого натурального числа n) значений f (количеств областей) для плоскости RP2 , разделенной всеми возможными наборами прямых . Гипотетическая формула для возможных значений количеств областей, примеры наборов прямых, разделяющих плоскость RP2 на любое задаваемое формулой число, были известны с 1993 года, см. [M ar93], см. утверждения 3 и 4 пункта 1.3. В пункте 1.3 доказано, любое число, не задаваемое формулой (для возможных значений количеств областей), не может быть количеством областей разделенной плоскости RP2 (теорема 1). Таким образом, теперь известны все возможные количества областей и доказано, что другие числа не возможны.

состоящим из n прямых, назовем nнедостижимыми. Пример 1. Одна прямая делит плоскость RP2 на одну область; две прямые делят на две области; три прямые делят на три или на четыре области; четыре прямые делят на 4, 6 или 7 областей. Пример 2. Если все прямые набора пересекаются в одной точке, то число областей равно n числу прямых набора. Пример 3. Если все прямые набора, кроме одной, пересекаются в одной точке, то число областей равно 2(n - 1). Пример 4. Если все прямые набора, кроме двух, пересекаются в одной точке, то число областей равно 3(n - 2) или 3n - 5. Пример 5. Если все прямые набора, кроме трех, пересекаются в одной точке, то число областей равно 4(n - 3), или 4n - 11, или 4n - 10, или 4n - 9. Пример 6. Если все прямые набора, кроме i < n , пересекаются в одной точке, 2 то число областей равно (i + 1)(n - i) + j, где число j это любое целое число из отрезка [0, i(i-1) ]. 2 Пример 7. Если среди прямых набора ровно n - k проходят через одну точку, то число областей не менее (k + 1)(n - k ). Б. Грюнбаум в [Gru72] доказал n-недостижимость всех натуральных чисел из отрезков

1.1 Примеры, история вопроса и его постановка. Определение. Те натуральные числа из отрезка [n, 1 + n(n2-1) ], которые не могут быть количеством областей проективной плоскости RP2 , разделенной набором ,

[n + 1, 2n - 3] при n

4

и

[2n - 1, 3n - 7] при n 9.

6

и выдвинул гипотезу (2.4) о n-недостижимости всех чисел из отрезка

[3n - 4, 4n - 13] при n
4


Эту гипотезу решили Н.Д. Мартинов в [M ar90], а также Р. Кордовил в 1980 году и Г.И. Пурди в 1980 году. Позже Н.Д. Мартинов в [M ar93] сформулировал теорему, определяющую все n недостижимых чисел (и доказал ее в одну сторону). Привел примеры наборов прямых, делящих плоскость на любое число, заявленное им как nдостижимое. Опубликовал неверное доказательство того, что все заявленные им nнедостижимые числа действительно nнедостижимы. Итак, мне оставалось доказать nнедостижимость чисел (заявленных как недостижимые) (см. теорему 1). Однако я не знал работ Н.Мартинова и Б.Грюнбаума, поэтому я переоткрыл теорему Мартинова и дал другое доказательсво достижимости (см. утверждения 3 и 4).

1.2 Формулировки теорем и следствия из них. Обозначение. Для набора прямых за n() обозначим количество прямых в нем, а за f () обозначим количество областей разделенной им плоскости RP2 . Утверждение 1. Для всех наборов прямых верны неравенства
n() f () 1+ n()(n() - 1) 2

Индукция по числу n() прямых в наборе. База n() = 1 тогда f () = 1. Переход: вырезание nй прямой (при n 2) увеличивает число областей настолько, сколько точек пересечения nя прямая имела с предыдущими n - 1й, т.е. от 1 до n - 1.

Обозначение. Для каждого натурального n 4 за dn обозначим число 2n - 5 3 - 4 Замечание про число dn . Для всех натуральных чисел n 4 верны неравенства
d2 + 3dn n +3 2 n d2 + dn n +3 2

1 2

По определению целой части получаем

dn
Прибавляя ко всем трем частям
1 2

31 2n - 5 - < dn + 1 42
и возводя все в квадрат, имеем

d2 + dn + n

1 4

9 3 2n - 5 < d2 + 3dn + n 4 4

3 Прибавим ко всем трем частям 5 4 и заметим четность d2 + 3dn . n Обозначение. Для всех натуральных чисел n k 2 за f (n, k ) обозначим минимально возможное количество областей плоскости RP2 , разделенной n прямыми с максимальной кратностью точек пересечения ровно k , (т.е. есть точка пересечения k прямых и нет точек пересечения хотя бы k + 1 прямых).

5


Утверждение 7. Для натуральных чисел k
f (n, k ) 2

2иn

k + 1 верно неравенство (1)

n2 - n + 2k k+3

Теорема 1. (а) Для всех наборов прямых c n = n() верно включение
dn -1

f ()
k=0

[(k + 1)(n - k ); (k + 1)(n - k ) +

k (k - 1) ] 2

[(dn + 1)(n - dn ); 1 +

n(n - 1) ] () 2

где dn = [ 2n - 5 3 - 1 ] при n 3 и d1 = d2 = 0. 4 2 (б) Все натуральные числа множества
dn -1

[(k + 1)(n - k ); (k + 1)(n - k ) +
k=0

k (k - 1) ] 2

[(dn + 1)(n - dn ); 1 +

n(n - 1) ] 2

()

являются n-достижимыми. Замечание. Множество делено корректно (т.е. знак натурального ряда), так как хотя бы для одного i. Знак левых границ i + 1-х хотя бы

достижимых чисел, приведенное в теореме 1, опрестоит между непересекающимися отрезками чисел при n 4 верно dn 1 и dn - 1 i 0 выполняется стоит, потому что правые границы i-х отрезков меньше на два, то есть

(i + 1)(n - i) +

i(i - 1) 2

(i + 2)(n - i - 1) - 2 dn - 1 и поэтому i2 + 3i +4 2 d2 + dn n +3 2

i(i - 1) +i+2 2

n - i - 2,

(0)

что выполняется, так как i

n

по замечанию про число dn . Замечание. Множество достижимых чисел, приведенное в теореме 1, состоит из dn + 1 подмножеств подряд идущих натуральных чисел, причем из неравенства (0) предыдущего замечания следует, что между каждыми двумя соседними подмножествами есть хотя бы одно n-недостижимое число. Замечание. Рассмотрим n кривых на проективной плоскости RP2 , каждая из которых делит проективную плоскость RP2 на одну область, и кривые попарно пересекаются в одной точке. Такие кривые называются в [GP W 05] псевдопрямыми. Теорема 1 для таких кривых верна, а ее доказательство аналогично.

1.3 Доказательства теоремы и вспомогательных утверждений. Обозначение. Для произвольного набора n различных прямых на проективной плоскости RP2 за aj обозначим число точек пересечения кратности ровно j.
не более k

Утверждение 2. Пусть в наборе из n
k

2 прямых в одной точке пересекаются n. Тогда этот набор делит плоскость RP2 на 1+
j =2

aj (j - 1) областей.
6


Индукция по n, база n = 2, тогда k = 2, a2 = 1 и две прямые делят плоскость RP на две области. Предположим, что утверждение 2 верно для любого набора из n - 1 прямой. Удалим из (остатка) плоскости RP2 ещ? одну (произвольную) прямую ln . Если прямая ln пересекает объединение первых n - 1 прямых в p > 0 точках, то удаление прямой ln приведет к разделению p частей остатка плоскости RP2 на две каждая, величина 1 + k=2 aj (j - 1) увеличится на p (при переходе n - 1 n числа aj j и k могут измениться). Число областей и значение формулы при переходе индукции увеличились на равные числа p и, следовательно, остались равными.
2

ства

Утверждение 3. Для всех натуральных n

4 все натуральные числа множе-

n 2

[(k + 1)(n - k ); (k + 1)(n - k ) +
k=0

k (k - 1) ] 2

являются

n - достижимыми.

k(k-1) n Для всех целых чисел 0 k и0 t покажем существование n 2 2 2 прямых l1 , . . . , ln , делящих плоскость RP на (k + 1)(n - k ) + t областей. Представим t в виде

t = (k - 1) + (k - 2) + ћ ћ ћ + (k - q ) + rq ,
где 0 rq k - q - 1 и 0 q k - 1 (выберем любое представление). Возьмем k - q - 1 прямых l1 , l2 , . . . , lk-q-1 пересекающимися в точке A, прямая lk-l пересекает их в точках A1 , A2 , . . . , Ak-q-1 (отличных от точки A). Прямые lk-q+1 , . . . , lk-q+n-k пересекаются в точке O, причем прямая lk-q+i проходит через точку Ai для 1 i k - q - 1 - rq . Прямая lk-q+k-q-rq проходит через точку A. Возможность следует из неравенства n - k > k - q - rq . Точки O, A, A1 , . . . , Ak-q-1 попарно различны и каждая из них (назовем е? X ) принадлежит только тем прямым, которые описаны выше как проходящие через точку X. Все остальные точки пересечения n прямых друг с другом имеют кратность 2 (т.е. каждая из прямых ln-q+1 , . . . , ln не проходит через точки пересечения других прямых). Для нахождения числа областей плоскости RP2 применим утверждение 2, для этого сначала посчитаем сумму кратностей, уменьшенных на 1, для групп точек пересечения:

ћ rq для точек Ak

-q -rq

,...,A

k-q -1

,

ћ n - k - 1 для точки O, ћ (n-k )(k -q ) для точек пересечения прямых l1 , . . . , l
k -q

с прямыми l

k-q +1

,...,l

n- q

,

ћ ((n - q ) + (n - q + 1) + ћ ћ ћ + (n - 1)) для точек пересечения прямых l1 , . . . , l с прямой ln-q+i+1 для всех i = 0, 1, . . . , q - 1.

n-q +i

А затем сложим полученные числа вместе и вместе с единицей, получим равенство числа областей плоскости RP2 сумме

1 + rq + (n - k - 1) + (n - k )(k - q ) + ((n - q ) + (n - q + 1) + ћ ћ ћ + (n - 1)) =
7


= rq + (n - k )(k - q + 1) + (n - q )q + = (n - k )(k + 1) + (k - q )q + rq +
Тем самым доказательство завершено.

q (q - 1) = 2

q (q - 1) = (n - k )(k + 1) + t. 2 4 все натуральные числа множе-

ства [(dn + 1)(n - dn ); 1 + n(n2-1) ] являются n-достижимыми. Все натуральные числа множества

Утверждение 4. Для всех натуральных n

[(dn + 1)(n - dn ); (dn + 2)(n - dn - 1) - 1] [(dn + 1)(n - dn ); (dn + 1)(n - dn ) +
2

dn (dn - 1) ] 2

dn -dn по замеявляются n-достижимыми по утверждению 3 и т.к. n - 2dn - 3 2 чанию про число dn . Значит, осталось доказать n-достижимость натуральных чисел множества

[(dn + 2)(n - dn - 1); 1 +

n(n - 1) ]. 2

Так как

(dn + 2)(n - dn - 1) + n2 -n 2

dn (dn + 1) (n - dn - 2)(n - dn - 3) + = 2 2

=

2dn + 5 n2 - n - (dn + 2) + 1 = 1 + , 2 2 то

1+

n2 - n = (dn + 2)(n - dn - 1) + ((n - dn - 3) + ћ ћ ћ + 1) + ((dn ) + ћ ћ ћ + 1) 2

любое натуральное число m, такое, что

(dn + 2)(n - dn - 1)

m

1+

n(n - 1) 2

можно представить хотя бы одним способом в виде

m = (dn + 2)(n - dn - 1) + ((n - dn - 3) + ћ ћ ћ + (n - dn - a)) + (dn + ћ ћ ћ + (dn - p)) + rp ,

где 2

a

(n - dn - 1),

-1

p

(dn - 1) и 0

rp

(dn - p - 1),

(причем a = 2 означает отсутствие суммирования первой группы слагаемых), т.к.

(dn + 2)(n - dn - 1) + (n-dn -2)(n-dn -3) , то берем a = n - dn - 2 1, p = max{q -1|m - (dn + 2)(n - dn - 1) - (n-dn -2)(n-dn -3) - (dn + ћ ћ ћ + (dn - q )) 2 (n-dn -2)(n-dn -3) 0}, а rp = m - (dn + 2)(n - dn - 1) - - (dn + ћ ћ ћ + (dn - p)) ; 2
8

вариант 1): если m


, то берем a = max{b 2|m - (dn + 2)(n - dn - 1) - (n - dn - 3) - ћ ћ ћ - (n - dn - b) 0}, вариант 2)а): если m - (dn + 2)(n - dn - 1) - ((n - dn - 3) - ћ ћ ћ - (n - dn - a)) > 0, то p = max{q -1|m - (dn + 2)(n - dn - 1) - (n - dn - 3) - ћ ћ ћ - (n - dn - a) - (dn + ћ ћ ћ + (dn - q )) 0}, а rp = m-(dn +2)(n-dn -1)-((n - dn - 3) - ћ ћ ћ - (n - dn - a))- (dn + ћ ћ ћ + (dn - q )) ; вариант 2)б): если m - (dn + 2)(n - dn - 1) - ((n - dn - 3) - ћ ћ ћ - (n - dn - a)) = 0, то p = -1, r-1 = 0. 2 n Так как n - dn - 4 dn + (dn - 1) + ћ ћ ћ + 1 = dn (d2 +1) следует из n 4 + dn +3dn , 2 то p в варианте 2)а) найдется всегда. Теперь построим набор n прямых, делящих плоскость RP2 на m (с прежними ограничениями) областей: Пусть dn - p - 1 прямых l1 , . . . , ldn -p-1 пересекаются в точке A, прямая dn - p пересекает их в точках A1 , . . . , Adn -p-1 . Выберем точку O вне прямых l1 , . . . , ldn -p . Прямые ld
n

вариант 2): если m < (dn + 2)(n - dn - 1) +

(n-dn -2)(n-dn -3) 2

-p-1

,...,l

dn -p+(n-dn -1)-(a-2)

пересекаются в точке O, прямые

ld

n

-p+(n-dn -1)-(a-2)+1

,...,l

dn -p+(n-dn -1)

не проходят через точку O и любые три прямые из прямых

ld

n

-p+1

,...,l

dn -p+(n-dn -1)

или не пересекаются в одной точке, или пересекаются в точке O. Также прямая ldn -p+i+1 проходит через точку Ai для каждого

i = 1, . . . , dn - p - 1 - rp .
Прямая ldn -p+1 проходит через точку A. Возможность гарантируется первым неравенством из следующих:

(dn - p) + 1 + (dn - p - 1 - rp ) n 2dn + 2

(dn - p) + (n - dn - 1)

d2 + dn n + 3 2dn + 2 (dn - 1)(dn - 2) 0. 2 Через точки O, A, A1 , . . . , Adn -p-1 проходят только те прямые, про которые их прохождение написано, все остальные точки пересечения имеют кратность 2. Возможность следует из того, что прямые, проходящие через точку A : l1 , . . . , l
dn -p-1

и

ld

n

-p+1

;

и прямые, проходящие через (точку O и хотя бы одну из точек Ai ,) вне точек O, A по хотя бы три не пересекаются, все их точки пересечения с прямой ldn -p это точки Ai , а остальные прямые проходят через не более чем одну из точек O, Ai (через точку A никакая оставшаяся прямая не проходит). Для нахождения числа областей плоскости RP2 применим утверждение 2, для этого сначала посчитаем сумму кратностей, уменьшенных на 1, для групп точек пересечения: 9


ћ (n - dn - 1) - a + 1 для точки O, ћ (dn + 1)(n - dn - 1) для точек пересечения прямых l1 , . . . , l остальных,
dn -p

,l

n- p

, . . . , dn и

ћ ((n - dn - 1 - a + 2) + ћ ћ ћ + (n - dn - 1 - a + a - 1)) для точек пересечения прямых ldn -p+1 , . . . , ldn -p+n-dn -1 , отличных от точки O, ћ ((dn - p) + ћ ћ ћ + dn ) для точек пересечения прямых l1 , . . . , l личных от точек A, A1 , . . . , Adn -p , ћ rp для точек Ad
n

dn -p

,l

n- p

, . . . , dn , от-

-p-rp

...,A

dn -p-1

.

А затем сложим полученные числа вместе и вместе с единицей, получим, что число областей плоскости RP2 равно сумме

1+((n-dn -1)-a+1)+(dn +1)(n-dn -1)+((n - dn - 1 - a + 2) + ћ ћ ћ + (n - dn - 1 - a + a - 1)) + + ((dn - p) + ћ ћ ћ + dn ) + rp = = rp +(dn + ћ ћ ћ + (dn - p))+((n - dn - a) + ћ ћ ћ + (n - dn - 3))+(dn +2)(n-dn -1) = m.
Тем самым доказательство завершено.

Пример. Перечислим крайние случаи доказательства утверждения 4:
ћ если dn - 1 = p, то точек A, Ai нет, ћ если a = 2, то в точке O пересекаются n - dn - 1 прямая, ћ если a = n - dn - 1, то в точке O пересекаются две прямые, ћ если p = -1, то dn + 1 прямая пересекаются в точке A, ћ если p = dn - 2, то точки A нет, а точка A1 есть, ћ если rp = 0, то через каждую из точек A1 , . . . , A
dn -p-1

проходит по три прямые,
dn -p-1

ћ если rp = dn - p - 1, то через каждую из точек A1 , . . . , A прямые.

проходит по две

Утверждение 5. Пусть существуют такие натуральные числа m, n, k, что число m является n-достижимым и
(k + 1)(n - k ) > m > k (n - k + 1) + (k - 1)(k - 2) . 2

Тогда в любом наборе из n прямых, разбивающих плоскость RP2 на m областей, кратность любой точки пересечения не превосходит k . Предположим противное: существует набор с точкой пересечения A кратности q k + 1. Для оценки числа областей плоскости RP2 применим утверждение 2, для этого сначала посчитаем сумму кратностей, уменьшенных на 1, для групп точек пересечения: 10


ћ q - 1 для точки A, ћ q (n - q ) для точек пересечения q прямых, проходящих через точку A, с остальными n - q прямыми.
А затем сложим полученные числа вместе и вместе с единицей, получим, что

m

1 + (q - 1) + q (n - q ) = q (n - q + 1).

Разберем два случая. (а) Если q n - k , то из k + 1

q

n - k следует
противоречие.

m

q (n - q + 1)

(k + 1)(n - k ) > m,

(б) Если q n - k + 1, то для оценки числа областей плоскости RP2 применим утверждение 2, для этого сначала посчитаем сумму кратностей, уменьшенных на 1, для групп точек пересечения:

ћ q - 1 для точки A, ћ q (n - q ) для точек пересечения q прямых, проходящих через точку A, с остальными n - q прямыми. ћ
(n-q )(n-q -1) 2

для точек пересечения n - q прямых друг с другом.

А затем сложим полученные числа вместе и вместе с единицей, получим, что

m

1 + (q - 1) + q (n - q ) +

(n - q )(n - q - 1) (n - q )(n - q - 1) = q (n - q + 1) + . 2 2 (k + 1)(n - k ) > m > k (n - k + 1) (k + 1)(n - k ) > k (n - k + 1) + 1, 2k + 2, поэтому n + 2, 2 (k - 1)(k - 2) , 2

Из неравенства следует

сократив на k (n - k ), получим n - k > k + 1 и n

l
значит

n-k+1

l(n - l + 1)
поэтому m

(n - k + 1)k
(k-1)(k-2) 2

и

(n - l)(n - l - 1) 2

k (n - k + 1) +

. Противоречие. k 2 верно неравенство

Утверждение 6. Для всех натуральных чисел n
f (n, k ) 1+

n(n - 1) . k Для любого набора из n прямых, из которых не более k пересекаются в одной точке, делящего плоскость RP2 на f (n, k ) областей и имеющего aj точек пересечения кратности i, верно неравенство
11


f (n, k )

1+

n(n - 1) k - 2 + (a2 + ћ ћ ћ + ak-1 ). k k

Рассмотрим любой набор из n прямых, из которых не более k пересекаются в одной точке, и набор прямых делит плоскость RP2 на f (n, k ) областей. По утверждению 2
k

f (n, k ) = 1 +
i=2

(i - 1)ai .

Число пар прямых равно

n(n - 1) = 2

k

a
i=2

i

i(i - 1) , 2

так как на плоскости RP2 любые две прямые пересекаются и точка пересечения 2 кратности i дает i(i-1) пару прямых. Умножим равенство числа пар на k и выделим 2 выделим сумму из равенства утверждения 2, получим

n(n - 1) = k

k

i=2

i(i - 1) ai = k

k

k

ai (i - 1) -
i=2 i=2

a

i

i-1-

i(i - 1) k

.

Заметим, что множители в последней сумме равны

i-1-

i(i - 1) k

=

(i - 1)(k - i) k
k

k-2 k

при

2

i

k - 1.

Поэтому и

n(n - 1) k 1+

ai (i - 1) -
i=2

k-2 (a2 + ћ ћ ћ + ak-1 ) k
k-1

f (n, k )

n(n - 1) k - 2 + (a2 + ћ ћ ћ + a k k 2иn

)

Утверждение 7. Для натуральных чисел k
f (n, k ) 2

k + 1 верно неравенство (1)

n2 - n + 2k k+3

Рассмотрим любой набор из n прямых, из которых не более k пересекаются в одной точке, делящий плоскость RP2 на f (n, k ) областей. За aj (как и раньше) обозначим число точек пересечения кратности j. Докажем неравенство Е. Мельхиора из [M el41] : a2 3 + a4 + 2a5 + ћ ћ ћ + (k - 3)ak (2) Так как n k + 1, то на каждой прямой есть хотя бы две точки пересечения с другими прямыми. Поэтому каждая область проективной плоскости ограничивается хотя бы тремя отрезками прямых. Обозначим за bj число областей, ограниченных ровно j отрезками, j = 3, 4, . . . , x. По утверждению 2 число областей проективной плоскости равно

f (n, k ) = b3 + ћ ћ ћ + bx = 1 + a2 + ћ ћ ћ + (k - 1)ak
12

(3)


Для каждой области посчитаем число отрезков прямых, ее ограничивающих и сложим эти числа для всех областей, получим 3b3 + 4b4 + ћ ћ ћ + xbx . С другой стороны, каждый отрезок (между двумя соседними точками пересечения) каждой прямой посчитается два раза (для двух областей, к нему примыкающих). На каждой прямой отрезков столько же, сколько и точек пересечения. Сумма по всем прямым количества точек пересечения, находящихся на прямой (суммируемой) равна сумме кратностей всех точек пересечения, то есть равна

2a2 + 3a3 + ћ ћ ћ + k ak .
Приравняв посчитанное двумя способами, получим

3b3 + 4b4 + ћ ћ ћ + xbx = 2(2a2 + 3a3 + ћ ћ ћ + k ak )
Вычитая из равенства (4) правое равенство (3), умноженное на 3, получим

(4)

b4 + 2b5 + ћ ћ ћ + (x - 3)bx = -3 + a2 - a4 - ћ ћ ћ - (k - 3)a

k

(5)

Неравенство (2) следует из неотрицательности левой части равенства (5). Перепишем неравенство (2) в виде

-a2 + a4 + 2a5 + ћ ћ ћ + (k - 3)ak

-3

(6)

По утверждению 2 для рассматриваемого набора прямых верно равенство:

a2 + 2a3 + ћ ћ ћ + (k - 1)ak = f (n, k ) - 1
Умножим неравенство (6) на венство
k k -1 2

(7)

, а равенство (7) на

k+3 2

и сложим, получим нера-

ai
i=2

k-1 k+3 (i - 3) + (i - 1) 2 2

-3

k-1 2

+ (f (n, k ) - 1)

k+3 2

(8)

Для упрощения и оценки левой части неравенства (8) заметим

k-1 k+3 (i - 3) + (i - 1) = ik + i - 2k 2 2

i(i - 1)

(9) 0, которое

так как правое неравенство (9) равносильно неравенству (i - 2)(i - k ) верно при используемых значениях индекса суммирования 2 i k . Удвоенное число пар прямых равно

2a2 + 6a3 + ћ ћ ћ + k (k - 1)ak = n(n - 1)

(10)

Из неравенства (9), примененного к левым частям неравенства (8) и равенства (10) следует неравенство правых частей (8) и (10):

-3

k-1 2

+ (f (n, k ) - 1)

k+3 2

n(n - 1)

(11)

Откуда и следует требуемое неравенство

f (n, k )

2

n2 - n + 2k k+3
13

(1)


ния 7 обращается в равенство при условии b4 = b5 = ћ ћ ћ = bx области треугольные. Это возможно, например, в следующих 1) k 2, n = k + 1, тогда a2 = k , a3 = ћ ћ ћ = ak-1 = 0, ak = 1, 2) k = 4, n = 13, a2 = 12, a3 = 4, a4 = 9, см. рис. (n = 13). 3) k = 3, n = 6, a2 = 3, a3 = 4, см. рис. (n = 6). 4) k = 3, n = 7, a2 = 3, a3 = 6 см. рис. (n = 7). В случаях 1), 3), 4) оценка (1) утверждения 7 точна. Требование n k + 1 необходимо, так как используется в f (n = k , k ) = k оценка (1) неверна.

Замечание к утверждению 7. Неравенство (2) из доказательства утвержде-

= 0, то есть когда все случаях: см. рис. (n = k + 1).

доказательстве, и для

Утверждение 8. Выберем натуральные числа a 2иb 1. На евкли2 довой плоскости R рассмотрим попарно параллельные прямые l1 , . . . , la . Прямые

la+1 , la+2 , . . . , l2a попарно параллельны и перпендикулярны прямым l1 , . . . , la . Прямые k l2a+1 , . . . , l2a+b не паралелльны прямым l1 , . . . , la , la+1 , . . . , l2a . За s = j =2 aj (j - 1) обозначим сумму уменьшенных на 1 кратностей точек пересечения (находящихся на евклидовой плоскости) всех 2a + b прямых между собой, где aj это количество точек пересечения кратности j (как и раньше). То