\documentclass[12pt,a4paper]{article}

% корректная обработка переносов, в том числе при поиске и копировании
\defaulthyphenchar=127
\lccode`\-=`\-
\usepackage{cmap}
\newcommand\softhyphen{\char127\relax}
% также в локальную копию файла t2a.cmap внесено изменение:
%  <7F> <002D>   заменено на   <7F> <00AD>

\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{epsfig}
 \usepackage{graphicx}
 \usepackage{graphics}
\usepackage{amssymb} \usepackage{amsmath}
\usepackage{amsthm} \usepackage{euscript}
\textwidth=16.5cm \oddsidemargin=-2mm \topmargin=-30pt\textheight=690pt

\newcommand{\lle}{\leqslant}
\newcommand{\g}{\geqslant}
\newcommand{\lra}{\Leftrightarrow}

\newcounter{zadacha}
\setcounter{zadacha}0

\newcommand{\pb}{\par\smallskip\refstepcounter{zadacha}%
\textbf{Задача \arabic{zadacha}.} }

\newcommand{\pbz}{\par\refstepcounter{zadacha}%
\textbf{Задача \arabic{zadacha}$^{*}$.} }

\newcommand{\pbzz}{\par\refstepcounter{zadacha}%
\textbf{Задача \arabic{zadacha}$^{\bigstar}$.} }
%


\begin{document}
\righthyphenmin=2
\centerline{{\Large\bf Наборы прямых на плоскости}}

\bigskip
\centerline{ Решения задач до промежуточного финиша}

\bigskip
\bigskip
\pb \label{fminmax} Ответ: $n+1 \lle f \lle \frac{n(n+1)}2+1$. Оба неравенства доказываются индукцией по $n$, база
$n=1$, $f=2$. Если добавляемая прямая пересекает предыдущие в~$x$ точках, то при её добавлении число областей
увеличивается на~$x+1$. Следовательно, при добавлении $n$-й прямой число областей увеличивается не менее, чем на~1,
и не более, чем на~$n$.


\pb Ответ:
\begin{description}
   \item[n=1,] $f=2,$
   \item[n=2,] $f\in \{3,4\},$
   \item[n=3,] $f\in \{4, \ 6,7\},$
   \item[n=4,] $f\in \{5,\ 8, \dots, 11\},$
   \item[n=5,] $f\in \{6,\ 10,\ 12, \dots, 16\},$
   \item[n=6,] $f\in \{7,\ 12,\ 15, \dots, 22\},$
   \item[n=7,] $f\in \{8,\ 14,\ 18, \dots, 29\}.$
   \end{description}
Невозможность остальных чисел следует из задач \ref{fminmax} и \ref{3ocenki}(a)(b).

\pb \label{3ocenki}
(a) Рассмотрим~$p$ параллельных прямых набора и будем добавлять остальные прямые набора по очереди. Очередная прямая имеет не менее~$p$ точек пересечения с предыдущими прямыми, поэтому при её добавлении число областей увеличится на не менее, чем $p+1$. Добавив~$n-p$ прямых, получим $f \g (p+1)(n-p+1)$.

(b) Рассмотрим $q$ пересекающихся в одной точке прямых набора и будем добавлять остальные прямые набора по очереди. Очередная прямая имеет не менее $q-1$ точек пересечения с предыдущими прямыми, поэтому при её добавлении число областей увеличится на не менее, чем $q$. Добавив $n-q$ прямых, получим $f \g q(n-p+2)$.

(c) Рассмотрим~$p$ параллельных прямых, через некоторую точку на одной из них поведем остальные~$n-p$ прямых
поочерёдно. При добавлении каждой прямой число областей увеличивается на~$p$ и в итоге будет равно $(p+1)(n-p)$.

Рассмотрим~$q$ прямых, проходящих через одну точку. Будем проводить остальные ${(n-q)}$ прямых параллельно одной из
первых~$q$ прямых по очереди. Тогда при добавлении очередной прямой число областей увеличивается на~$q$ и в итоге
будет равно~$q(n-q+2)$.

(d) {\it Решение 1.} Будем добавлять прямые поочерёдно. Если очередная прямая пересекает предыдущие в $x$ точках,
то её добавление увеличивает число областей на $x+1$. С другой стороны, каждая из этих $x$ точек пересечения или
имеет кратность два, или до добавления прямой имела кратность на единицу меньше. Следовательно, сумма $\sum_{i \g
2} (i-1)r_i$ при добавлении этой прямой увеличивается на $x$.

 {\it Решение 2.} Пересечём набор прямых с кругом достаточно большого радиуса, содержащим внутри себя все
точки пересечения прямых набора. Рассмотрим граф, вершины которого~--- точки пересечения прямых друг с другом и с
окружностью круга, рёбра~--- отрезки прямых и дуги окружности, не содержащие отличных от своих концов вершин
графа. Число вершин $v$ и рёбер $e$ этого графа равны $2n+\sum_{i \g 2} r_i$ и $3n+\sum_{i \g 2} ir_i$
соответственно. Число $f$ частей плоскости, разделённой набором прямых, на единицу меньше числа областей,
образованных графом. Следовательно, по формуле Эйлера для графов имеем
$$
f=n+1+\sum_{i \g 2} (i-1)r_i.
$$



\pb \label{3lakuni} (a) Если все прямые параллельны, то $f=p+1$. Если не все прямые параллельны, то $1\lle p \lle
n-1$. По задаче \ref{3ocenki} имеем $f \g (p+1)(n-p+1)$. Выражение $(p+1)(n-p+1)$ есть квадратный трёхчлен
относительно~$p$ с отрицательным старшим коэффициентом. При~$p=1$ и~$p=n-1$ трёхчлен $(p+1)(n-p+1)$ принимает
значение~$2n$. Следовательно, при $1\lle p \lle n-1$ трёхчлен $(p+1)(n-p+1)$ принимает значения, не меньшие $2n$.

(b) Если все или все кроме одной прямой параллельны, то $f=n+1$ или $f=2n$. По задаче \ref{3ocenki}(a) имеем $f \g
(p+1)(n-p+1)$. Выражение $(p+1)(n-p+1)$ есть квадратный трёхчлен относительно~$p$ с отрицательным старшим
коэффициентом. При~$p=2$ и~$p=n-2$ трёхчлен $(p+1)(n-p+1)$ принимает значение~$3n-3$. Следовательно, при $2\lle p
\lle n-2$ трёхчлен $(p+1)(n-p+1)$ принимает значения, не меньшие $3n-3$. Поэтому при $2\lle p \lle n-2$ имеем $f\g
3n-3$. Если $p=1$, то по задаче \ref{3ocenki}(b) имеем $f\g q(n-q+2)$. Если $q=n$, то $f=2n$. Рассмотрим
квадратный трёхчлен $q(n-q+2)$. При $3\lle q \lle n-1$ имеем $f \g q(n-q+2) \g 3n-3.$ Остался случай $p=1$ и
$q=2$, в котором число областей равно
$$
1+\frac{n(n+1)}2\g 3n-3\quad  \lra \quad n^2 -5n +8 \g 0.
$$

(c) Если $p\geqslant n-2$ или $q\geqslant n-1$, то $f\leqslant 3n-2$. Если $3\leqslant p\leqslant n-3$ или $4
\leqslant q\leqslant n-2$, то по задаче~\ref{3ocenki} получим $f\geqslant 4n-8$. Остался случай $p\leqslant 2$ и
$q\leqslant 3.$ По задаче~\ref{3ocenki} имеем $f=n+1+r_2+2r_3$. Каждая прямая набора пересекается не менее, чем с
$n-2$ другими. Поэтому число пар пересекающихся прямых равно $r_2+3r_3$ и не меньше, чем $\frac{n(n-2)}2$.
Следовательно,
$$
f\g n+1 +\frac 23(r_2+3r_3)\geqslant n+1+\frac{n^2-2n}3\geqslant 4n-8
$$
 при $n\geqslant 8$.


\pb \label{fpqmax}(a) Рассмотрим $p$ параллельных прямых набора из $n$ прямых и будем добавлять остальные прямые по очереди. Очередная прямая номер $i$, $1\lle i \lle n-p$ пересекает предыдущие прямые в не более, чем $p+i-1$ точках и поэтому её добавление увеличивает число областей на не более,чем $p+i$. Добавив $n-p$ прямых, получим
$$
f \lle (p+1)(n-p+1)+C_{n-p}^2.
$$
 Оценка достигается для наборов $p$ параллельных прямых и $n-p$ прямых общего положения (т.е. никакие две не параллельны и никакие три не проходят через одну точку), находящихся также в общем положении с $p$ параллельными прямыми.

(b) Рассмотрим $q$ пересекающихся в одной точке прямых набора из $n$ прямых и будем добавлять остальные прямые по очереди. Очередная прямая номер $i$, $1\lle i \lle n-q$, пересекает предыдущие прямые в не более, чем $q+i-1$ точках, и поэтому её добавление увеличивает число областей на не более,чем $q+i$. Добавив $n-q$ прямых, получим
$$
f \lle q(n-p+2)+C_{n-q+1}^2=1+C_{n+1}^2-C_{q-1}^2.
$$
Оценка достигается для наборов $q$ пересекающихся в одной точке прямых и $n-q$ прямых общего положения,
находящихся также в общем положении с $q$ пересекающимися прямыми.

\pb \label{primer} Возьмем $n-p$ прямых в общем положении. Выберем $t$ точек из их точек пересечения для некоторого $t \lle \min\{p,C_{n-p}^2\}$. Проведем $p$ параллельных прямых так, чтобы они проходили через выбранные точки пересечения и не проходили бы через другие точки пересечения $n-p$ прямых между собой. При этом выберем направление для $p$ параллельных прямых отличным от любой из первых $n-p$ прямых. Тогда предъявленный набор имеет максимум $p$ параллельных прямых и делит плоскость на
$$
f=(p+1)(n-p+1)+C_{n-p}^2-t
$$
частей.


\pb Минимальное число областей для наборов прямых с данными числами $n$, $p$ равно $(p+1)(n-p+1)$. Достигается,
например, если $n-p+1$ прямых проходят через одну точку, а все остальные $p-1$ прямых параллельны одной из $n-p+1$
прямых. Осталось заметить, что
$$
(p+1)(n-p+1)<a(n,p)\  \lra \ C_{n-p}^2>p\  \lra\ n>p+\frac 12+\sqrt{2p+\frac 14}.
$$
В последнем равносильном переходе можно было прийти к $n\g p+\frac 12+\sqrt{2p+\tfrac 94}$.

\pb \label{chislolakun} (a) 
$L(n)=\max\{k \g 1 \ |\ b(n,n-k+1)\lle a(n,n-k)-2\}\mbox{ при } n\g 3,$ 
\begin{multline*}
b(n,n-k+1)\lle a(n,n-k)-2 \quad \lra \quad \min\left\{n-k, \ \frac{k(k-1)}2\right\}\lle n-k-2 \quad\lra \\
\lra \quad n\g \frac{k^2+k}2+2\quad \lra\quad k\lle \sqrt{2n -\frac{15}4}-\frac 12.
\end{multline*}
 Откуда $L(n)=\left[\sqrt{2n -\frac{15}4}-\frac 12\right]$.

(b) Так как
$$n \g \frac{L^2(n)+L(n)}2+2,  \text{  то }  \min\left\{n-j, \ \frac{j(j-1)}2\right\}=\frac{j(j-1)}2 \text{  при } 1\lle j \lle L(n).$$
Поэтому $a(n,n-j)=(n-j+1)(j+1)$, и лакуна номер $j$ содержит $n-\frac{j(j+1)}2-1$ целое число.


\pb \label{pq v lakune} Если $j \lle p \lle n-j $ или $j+1\lle q \lle n-j+1$, то по задаче \ref{3ocenki} получаем $f\g (n-j+1)(j+1)=a(n,n-j).$ Если $p \g n-j+1$, то вследствие задачи \ref{fpqmax} получаем
$$f \lle (p+1)(n-p+1)+C_{n-p}^2\lle b(n,n-j+1).$$
Если $q \g n-j+2$, то вследствие задачи \ref{fpqmax} имеем
$$
f\lle q(n-q+2)+C_{n-q}^2+1\lle b(n,n-j+1).
$$

\pb \label{r ocenka par} Число пар пересекающихся прямых равно $\sum_{i=2}^q\frac{i(i-1)}2r_i$ и не меньше, чем $\frac{n(n-p)}2$, поскольку каждая прямая пересекается с не менее, чем $n-p$ прямыми.



\pb \label{sqrtn lakun} (a) По задачам \ref{3ocenki} и \ref{r ocenka par} имеем
$$f-(n+1)=\sum_{i\g 2}(i-1)r_i\g \sum_{i \g 2}^q \frac{i(i-1)}q r_i\g \frac{n(n-p)}q.$$
(b) Предположим противное, тогда по задаче \ref{pq v lakune} имеем $p \lle j-1$ и $q\lle j$, где $j$~--- номер
лакуны. Используя $n-p\g n-j+1$, получаем противоречие с предыдущим пунктом:
$$
f\g n+1+\frac{n(n-p)}q\g (n-j+1)(\frac nq +1)\g (n-j+1)(j+1)=a(n,n-j).
$$

\pb \label{r ocenka Melchiora} Пересечём набор прямых с кругом достаточно большого радиуса, содержащим внутри себя все точки пересечения прямых набора. Получим граф, вершины которого~--- точки пересечения прямых друг с другом и с окружностью круга, рёбра~--- отрезки прямых и дуги окружности, не содержащие отличных от своих концов вершин графа. Число вершин $v$ и рёбер $e$ этого графа равны $2n+\sum_{i \g 2} r_i$ и $3n+\sum_{i \g 2} ir_i$ соответственно. Внутри круга находится $f$ областей, где
$$
f=n+1+\sum_{i \g 2} (i-1)r_i.
$$
Сумма по всем областям внутри круга числа ограничивающих их рёбер равна
$$
2e-2n=4n+2\sum_{i \g 2} ir_i.
$$
Так как $p<n$, то каждая область внутри круга ограничена не менее, чем тремя
рёбрами графа. Следовательно, $2e-2n \g 3f,$ откуда получаем требуемое неравенство.


\pb \label{l-2 lakun} (a) Положим $a=\frac 2{q+3},\  b=\frac{q-1}{q+3}$. Рассмотрим квадратный трёхчлен
относительно переменной $i$
$$
a(i^2-i)+b(3-i)-(i-1)=a(i-2)(i-q)\lle 0 \quad \text{при} \quad 2 \lle i \lle q.
$$
Умножим соответствующие значения многочлена на $r_i$ и сложим по всем $2 \lle i \lle q$:
$$
0 \g a\sum_{i=2}^qi(i-1)r_i+b\sum_{i=2}^q(3-i)r_i-\sum_{i=2}^q (i-1)r_i\g an(n-p)+b(3-n)-(f-n-1),
$$
где последнее неравенство получено из задач \ref{r ocenka par}, \ref{r ocenka Melchiora} и \ref{3ocenki}. Следовательно,
$$
f \g 2\frac{n(n-p)}{q+3} +(n+1+\frac{q-1}{q+3}(3-n))\g 2\frac{n(n-p)}{q+3}.
$$

(b) Предположим противное, тогда по задаче \ref{pq v lakune} имеем $p \lle j-1$ и $q\lle j$. Используя $n-p \g
n-j+1$, получаем противоречие с предыдущим пунктом:
$$
f \g 2\frac{n(n-p)}{q+3} \g (n-j+1)\frac{2n}{q+3}\g (n-j+1)(j+1)=a(n,n-j),
$$
т.к.
$$
\frac {(q+3)(j+1)}2\lle \frac {j^2+4j+3}2\lle \frac 12 L^2(n)< n.
$$

\pb (a) Точка пересечения определяет две проходящие через неё диагонали и их концы, т.е. четвёрку вершин $n$-угольника. Обратно, каждая четвёрка различных вершин $n$-угольника определяет одну точку пересечения диагоналей. Следовательно, число точек пересечения равно $C_n^4$.

(b) {\it Решение 1.} Будем проводить диагонали по очереди. Если добавленная диагональ имеет $x$ точек пересечения
с предыдущими диагоналями, то она увеличивает число частей внутренности $n$-угольника на $x+1$. Значит, каждая
точка пересечения и каждая диагональ увеличивает число частей на единицу. Тогда искомое число частей равно
$1+C_n^4+\frac{n(n-3)}2$, т.к. число точек пересечения известно из предыдущего пункта, а число диагоналей равно
$\frac{n(n-3)}2$.


{\it Решение 2.} Рассмотрим граф с вершинами в точках пересечения диагоналей и вершинах $n$-угольника, рёбра
которого суть отрезки диагоналей и стороны $n$-угольника. В таком графе $v=n+C_n^4$ вершин и $e=2C_n^4+\frac
{n(n-1)}2$ рёбер. Откуда по формуле Эйлера число частей равно $1+e-v=1+C_n^4+\frac {n(n-3)}2$.

\pb См. задачу \ref{main theorem}.

\pb Нарисуем на плоскости прямые, каждая из которых проходит через две из данных точек. Эти $m$ прямых разобьют
плоскость на не более, чем $1+m+C_m^2$ областей. Рассмотрим все точки данного множества, через которые не проходит ни одной прямой, проходящей ровно через две точки данного множества. Оказывается, что в каждой области, образованной набором $m$
прямых, находится не более одной такой точки (это остаётся вам доказать). Также остаётся найти $m$ областей,
внутри которых таких точек нет. На $m$ прямых находится не более $2m$ точек данного множества. Поэтому $n\lle
2m+1+C_m^2=C_{m+2}^2$.


\bigskip
\bigskip
\centerline{{\bf Решения задач после промежуточного финиша}}

\medskip
\pb Для параллельных плоскостей $\alpha_1$ и $\alpha_2$ центральное проектирование есть преобразование подобия, переводящее прямые в прямые и области в области. Пусть плоскости $\alpha_1$ и $\alpha_2$ пересекаются и пусть $l_1$ и $l_2$~--- прямые пересечения плоскостей $\alpha_1$ и $\alpha_2$ с плоскостями, проходящими через точку $O$ параллельно плоскостям $\alpha_2$ и $\alpha_1$ соответственно. Образ отличной от $l_1$ прямой $l$ есть прямая, если $l\| l_1$, и есть прямая с выколотой точкой (точкой пересечения с $l_2$), если $l\nparallel l_1$. Если область пересекает $l_1$, то её образ состоит из двух неограниченных областей. Если неограниченная область примыкает к двум непараллельным лучам, то её образ примыкает к $l_2$.

\pb \label{proekcia} Взаимная однозначность вытекает из определений. Образом и прообразом будут соответственно прямые $l_2$ и $l_1$ вместе со своими бесконечно удалёнными точками. Прямые $l_1$ и $l_2$~--- прямые пересечения плоскостей $\alpha_1$ и $\alpha_2$ с плоскостями, проходящими через точку $O$ параллельно плоскостям $\alpha_2$ и $\alpha_1$ соответственно.

\pb \label{pari} Любые две прямые имеют ровно одну общую точку на плоскости с бесконечно удалёнными точками (если прямые параллельны или одна из них бесконечно удалена, то эта общая точка бесконечно удалена). Количество пар прямых равно $C_n^2$. В точке, принадлежащей $i$ прямым, пересекается $C_i^2$ пар прямых, откуда и получаем требуемое.

\pb Определим, что такое <<область>> проективной плоскости, разделённой набором $n$ прямых, предположив сначала,
что не все прямые проходят через одну точку. Если одна из прямых набора бесконечно удалена, то областями будем
называть части обычной плоскости, разделённой остальными $n-1$ прямыми. Если в наборе нет бесконечно удалённой
прямой, тогда областью будет называться:
\begin{itemize}
  \item ограниченная область плоскости,
  \item неограниченная область плоскости, примыкающая к двум параллельным лучам,
  \item пара неограниченных областей плоскости, одна из которых примыкает к непараллельным лучам $l_1$ и $l_2$, а другая к 
  непараллельным лучам $l_3$ и $l_4$ при условии $l_1\| l_3$ и $l_2 \| l_4$. При этом считается, что бесконечно удалённые точки, соответствующие направлениям от $l_1$ до $l_2$, соединяют неограниченные области пары и вместе
   с ними входят в одну область на проективной плоскости.
\end{itemize}
Если же все прямые набора проходят через одну точку проективной плоскости, то <<области>> определяются аналогично.
Две точки принадлежат одной области тогда и только тогда, когда их можно соединить ломаной, не пересекающей
прямые. При этом концы ломаной совпадают с данными точками, а промежуточные вершины могут быть бесконечно
удалёнными точками. Звеньями ломаной, выходящими из бесконечно удалённой точки, считаются лучи, параллельные
направлению этой бесконечно удалённой точки. При центральном проектировании так доопределенная ломаная переходит в
ломаную. Следовательно, две точки находятся в одной области тогда и только тогда, когда их образы при центральном
проектировании находятся в одной области. Это означает взаимно однозначное соответствие областей.

\pb  \label{f ocenki} (a) {\it Решение 1. }  Переведем одну из прямых набора центральным проектированием в
бесконечно удалённую. Число областей и числа $t_i$ при этом не изменятся. Теперь число областей проективной
плоскости совпадает с числом $f$ областей обычной плоскости, разделённой набором из $n-1$ прямых. По задаче
\ref{3ocenki} имеем $f=n+\sum_{i\g 2}(i-1)r_i$. Осталось заметить, что
$$
n-1=\sum_{i \g 2} (i-1)(t_i-r_i),
$$
т.к. на бесконечно удалённой прямой находятся $t_i-r_i$ точек пересечения, принадлежащих $i-1$ прямым набора, на
считая бесконечно удалённой.

{\it Решение 2.} Индукция по числу прямых, база $n=1$. Для перехода заметим, что добавляемая прямая увеличивает
число областей на количество своих точек пересечения с предыдущими прямыми.



(b) Индукция по $n$, база $n=m, f=m$. Добавляемая прямая номер $j$, $1\lle j \lle n-m$, имеет не менее $m$ и не более
$m+j-1$ точек пересечения с предыдущими прямыми, т.к. на проективной плоскости любые две прямые пересекаются.
Осталось заметить, что добавляемая прямая увеличивает число областей на количество своих точек пересечения с
предыдущими прямыми.


(c) Рассмотрим граф на проективной плоскости, вершины которого~--- точки пересечения прямых друг с другом, рёбра
--- отрезки прямых. При этом допускается прохождение ребра через бесконечно удалённую точку, в этом случае ребро
состоит из двух лучей, лежащих на одной прямой, и бесконечно удалённой точки соответствующего направления,
соединяющей два луча. Число вершин $v$ и рёбер $e$ этого графа равны $\sum_{i \g 2} r_i$ и $\sum_{i \g 2} ir_i$
соответственно. Если $m<n$, то каждая область проективной плоскости ограничена не менее чем тремя рёбрами графа,
поэтому
$$
3f\lle 2e\quad  \lra\quad  3+3\sum_{i\g 2}(i-1)t_i \lle 2\sum_{i \g 2} ir_i\quad  \lra \quad \sum_{i\g
2}(3-i)t_i\g 3.
$$

(d) Положим $a=\frac 2{M+3}$ и $b=\frac{M-1}{M+3}$. Рассмотрим квадратный трёхчлен относительно пере\-менной $i$
$$
a(i^2-i)+b(3-i)-(i-1)=a(i-2)(i-M)\lle 0 \quad \text{при} \quad 2 \lle i \lle m.
$$
Умножим соответствующие значения многочлена на $t_i$ и сложим по всем $2 \lle i \lle m$:
$$
0 \g a\sum_{i=2}^m i(i-1)t_i+b\sum_{i=2}^m (3-i)t_i-\sum_{i=2}^m (i-1)t_i\g an(n-1)+3b-(f-1),
$$
где последнее неравенство получено из задач \ref{pari}, \ref{f ocenki}(a) и (c). Следовательно,
$$
f \g 2\frac{n(n-1)}{M+3} +\left(1+\frac{3(M-1)}{M+3}\right)= 2\frac{n(n-1)+2M}{M+3}.
$$

\pbz \label{l} Выберем две точки $P$ и $Q$, через каждую из которых проходит $m$ прямых. Обозначим через $N$
множество прямых исходного набора, проходящих через хотя бы одну из точек $P$ и $Q$. Возможны два случая:

(i) прямая $PQ$ не принадлежит набору. В этом случае $N$ содержит $2m$ прямых и делит проективную плоскость (без
учёта остальных прямых) на $m^2+2m-1$ область.

(ii) прямая $PQ$ принадлежит набору. В этом случае $N$ содержит $2m-1$ прямых и делит проективную плоскость (без
учёта остальных прямых) на $m^2$ область.

В обоих случаях каждая из оставшихся прямых набора (не принадлежащая $N$) пересекает прямые из $N$ не менее чем в
$m$ точках, причём существует не более двух прямых, пересекающих прямые из $N$ ровно в $m$ точках. Тем самым
случай (i) разобран, поскольку
$$f \g m^2+2m-1+(m+1)(n-2m)-2 \g (m+1)(n-m).$$

Рассмотрим случай (ii). Если набор прямых содержит не более одной прямой, пересекающей $N$ в $m$ точках, то тогда
оцениваем число областей через число точек пересечения остальных прямых:
$$
f\g m^2+(m+1)(n-2m+1)-1=(m+1)(n-m).
$$
Если набор прямых содержит две прямые, пересекающие $N$ в $m$ точках каждая, и их точка пересечения не лежит на
прямых $N$, то аналогично получим $f\g (m+1)(n-m)$.

Остался случай, когда набор содержит две прямые, пересекающие $N$ в $m$ точках каждая, и их точка пересечения лежит
на прямых $N$. Обозначим эти прямые через $l_{2m}$ и $l_{2m+1}$, а их точку пересечения через $R$. Докажем в этом
случае, что любая другая прямая набора пересекает $N\cup l_{2m} \cup l_{2m+1}$ не менее, чем в $m+2$ точках. Из
этого вытекает, что 
$$
f\g m^2+2m+(m+2)(n-2m-1)\g (m+1)(n-m),
$$ 
и тем самым доказательство случая (ii) будет
завершено.

 Обозначим прямые, проходящие через точку $P$, по порядку их следования, считая от прямой $PQ$, $l_1, \dots, l_{m-1}$. 
 Аналогично обозначим прямые, проходящие через точку $Q$, по порядку их следования, считая от прямой $PQ$, $l_m, \dots, l_{2m-2}$. Обозначим через $A_{i,j}$ точку пересечения прямых $l_i$ и $l_{m-1+j}$ для $1\lle i,j \lle m-1$. Не ограничивая общности, 
 будем считать прямую $PQ$ бесконечно удалённой, прямую $l_{2m}$ проходящей через точки $A_{i,i}$ 
 для $1\lle i \lle m-1$, прямую $l_{2m+1}$ проходящей через точки $A_{i,m-i}$ для $1\lle i \lle m-1$. Тогда 
 прямые $l_{2m}$ и $l_{2m+1}$ пересекаются в точке $A_{\frac m2, \frac m2}$ и $m$ чётно. Рассмотрим произвольную 
 оставшуюся прямую $l$ из набора. Она пересекает $N$ не менее, чем в $m+1$ точке. Если хотя бы одна точка 
 пересечения $l$ с $l_{2m}$ или с $l_{2m+1}$ не лежит на прямых из $N$, то тогда~$l$ пересекает $N\cup l_{2m} \cup l_{2m+1}$ 
 не менее, чем в $m+2$ точках.

 Заметим, что если прямая $l$ проходит через точку $A_{\frac m2, \frac m2}$, то точки пересечения прямой $l$ с прямыми $l_{\frac m2-1}$ и $l_{\frac m2+1}$ или с прямыми $l_{m-1+\frac m2-1}$ и $l_{m-1+\frac m2+1}$ отличны от точек $A_{ij}$. Следовательно, прямая $l$ пересекает $N$ не менее, чем в $m+2$ точках.

 Не ограничивая общности, будем считать, что точка пересечения прямых $l$ и $PQ$ и точка пересечения прямых $l_{2m}$ и $PQ$ лежат на одном отрезке прямой $PQ$, образованном точками $P$ и $Q$. Тогда прямая $l$ пересекает $l_{2m+1}$ в точке $A_{a,b}$ с $|a-b|\g 2.$ Следовательно, прямая $l$ проходит через не более чем $\min\{a, b\}+\min\{m-1-a, m-1-b\}\lle m-3$ точек из точек $A_{i,j}$. Значит, прямая $l$ пересекает $N$ не менее, чем в $m+2$ точках.


Для $n=2m+1$ утверждение неверно, пример строится для чётного $m \g 4$ следующим образом. Через точки $P$ и $Q$
проходят по $m$ прямых, причём прямая $PQ$ общая. Ещё две прямые пересекают эти $2m-1$ прямые в $m$ точках
каждая. В итоге $f=m^2+2m<(m+1)^2.$


\pbz \label{main theorem} При добавлении к набору бесконечно удалённой прямой число областей не меняется, число
прямых $n$ увеличивается на 1, а вместо $p$ параллельных прямых получается $p+1$ прямых, проходящих через одну
точку. Соответственно получаем:

{\it Число $f$ областей может быть числом областей проективной плоскости, разделённой $n$ прямыми, тогда и только тогда, когда $f$ принадлежит хотя бы одному из отрезков $[a(n,m), \ b(n,m)]$ для $n\g m \g 2$, где
$$
b(n,m)=m(n-m+1)+C_{n-m}^2 \ , \quad a(n,m)=b(n,m)-\min\{m-1, C_{n-m}^2\}.
$$  }

Лакуной будет также называться интервал $(b(n,m), a(n,m-1))$, содержащий не менее одного целого числа. Из задачи
\ref{chislolakun} получаем, что $L(n)=\left[\sqrt{2n -5\frac{3}4}-\frac 12\right].$ В дальнейшем зависимость
$L=L(n)$ от $n$ будем опускать. После задачи \ref{l-2 lakun} осталось доказать, что число областей не может
принадлежать последним двум лакунам номер $L-1$ и $L$.

Предположим, что существует набор прямых, для которого число $f$ принадлежит предпоследней лакуне~--- интервалу
$$
\left((n-L+2)(L-1)+C_{L-2}^2, \ \ L(n-L+1)\right).
$$
Из задачи \ref{pq v lakune} следует, что $m=\max\{p+1, \
q\}\lle L-1.$ Применим задачу \ref{f ocenki} для $M=L-1$:
$$
f \g \frac{2(n^2-n)}{L+2}\g L(n-L+1).
$$
В последнем неравенстве использовалось $n\g \frac{L^2+L}2+3$ следующим образом:
$$
n^2-n \g (n+\frac L2 -3)(n-L+1) \g \left(\frac{L^2+2L}2\right)(n-L+1).
$$
Тем самым получено противоречие с тем, что число $f$ принадлежит предпоследней лакуне.

 Предположим, что существует набор прямых на проективной плоскости, для которого число областей попадает в последнюю лакуну номер
$L$:
$$
f \in \left(L(n-L+1)+C_{L-1}^2,\ (L+1)(n-L)\right).
$$
По задаче \ref{3lakuni} можно считать, что $L \g 4.$ В силу задачи \ref{pq v lakune} имеем $m \lle L.$ Рассмотрим 3 случая.

(1) Если $m<L$, то по задаче \ref{f ocenki}(d) для $M=L-1$ получаем
$$f>\frac{2(n^2-n)}{L+2}\g (L+1)(n-L),$$
т.к. из $n\g \frac{n^2+n}2+3$ следует, что
$$\frac{(L+2)(L+1)}2(n-L)\lle (n+L-2)(n-L)\lle n^2-2n.$$

(2) Если $m=L$ и $t_m=1$, то удалим из набора одну прямую, проходящую через точку, принадлежащую $m$ прямым. Число
областей при этом только уменьшится. Применим к полученному набору из $n-1$ прямой неравенство задачи \ref{f
ocenki}(d) для $M=L-1$ и получим
$$f \g 2\left(\frac{n^2-3n+2L}{L+2}\right)\g (L+1)(n-L).$$
Обоснуем последнее неравенство.  Если $n \g \frac{L^2+L}2+4,$ то
$$n^2-3n+2L \g (n-L)(n+L-3)\g (n-L)\left(\frac{L^2+3L+2}2\right).$$
Случай $n=\frac{L^2+L}2+3$ проверяется непосредственной проверкой.

(3) Если $m=L$ и $t_m\g 2$, то $n\g 2m+2$ и из предыдущего пункта получаем $f\g (L+1)(n-L).$

\pb (a) Ответ: это множество чисел из основной теоремы для наборов $n$ прямых на плоскости. Сделаем инверсию
относительно некоторой окружности с центром в точке, принадлежащей всем окружностям набора. Получится набор прямых, 
число областей при этом не изменится. Обратно, если дан набор прямых, то можно сделать инверсию относительно
окружности, чей центр не принадлежит прямым. Получится набор окружностей, число областей при этом не изменится.

(b) Ответ: это множество удвоенных чисел областей из основной теоремы для проективной плоскости. Рассмотрим
проекцию сферы из её центра $O$ на плоскость $\alpha$, касающуюся сферы в южном полюсе. При этой проекции точка
$X$ сферы переходит в точку пересечения прямой $OX$ с плоскостью $\alpha$. Если прямая $OX$ параллельна плоскости
$\alpha$, то точка $X$ переходит в бесконечно удалённую точку по направлению $OX$. При этой проекции большие круги
на сфере перейдут в прямые на проективной плоскости. А пара противоположных областей сферы перейдёт в одну область
проективной плоскости. Следовательно, число областей сферы в два раза больше числа областей проективной плоскости,
разделённой соответствующим набором прямых. Наоборот, по любому набору прямых на проективной плоскости можно при
помощи обратной проекции на сферу получить набор больших кругов и удвоенное число областей.

\pb \label{Sylvester}(a) Рассмотрим пару <<прямая $AB$, не лежащая на ней точка $C$>> такую, что точки $A, B,C$ принадлежат заданному множеству, и расстояние от точки $C$ до прямой $AB$ минимально среди всех таких пар. Предположим, что на прямой $AB$ находится точка $D$ из исходного множества. Не ограничивая общности, будем считать, что точка $D$ находится между точками $A$ и $B$ и что угол $ADC\g 90^{\circ}$. Тогда расстояние от точки $D$ до прямой $AC$ будет меньше расстояния от точки $C$ до прямой $AB$, что противоречит выбору точек $A, B, C$. Следовательно, на прямой $AB$ нет отличных от $A$ и $B$ точек данного множества.

(b) {\it Решение 1.} Предположим противное. Случай, когда все прямые параллельны одной из двух
данных прямых, разбирается отдельно. Далее считаем, что среди прямых набора найдутся три попарно не параллельные и не
пересекающиеся в одной точке. Рассмотрим все треугольники, образованные тройками исходных прямых, и выберем
треугольник $ABC$ минимальной (ненулевой) площади. Поскольку через его вершины $A$, $B$ и $C$ проходит не менее трёх
данных прямых и его площадь минимальная, то прямые, проходящие через вершины $A$, $B$ и $C$ параллельно $BC, CA$ и
$AB$ соответственно, принадлежит данному набору. Обозначим точки пересечения этих прямых через $A_1, B_1$ и $C_1$.
Треугольник $ABC$~--- серединный треугольник для треугольника $A_1B_1C_1$. Следовательно, площади треугольников
$A_1BC$, $B_1CA$ и $C_1AB$ равны площади $ABC$. Аналогично рассмотрим треугольники $A_1BC$, $B_1CA$ и $C_1AB$
вместо $ABC$ и т.д. В итоге получим неограниченное число прямых. Противоречие.

{\it Решение 2.} Сведём задачу к предыдущей при помощи полярной (или проективной) двойственности. Рассмотрим
окружность, чей центр не принадлежит данным прямым. Сделаем полярное преобразование относительно этой окружности,
т.е. каждой точке поставим в соответствие её поляру, а каждой поляре поставим в соответствие её полюс. Набор из
$n$ прямых перейдёт в набор из $n$ точек, не лежащих на одной прямой. По предыдущему пункту найдется прямая $l$,
на которой лежат ровно два полюса, $A$ и~$B$. Сделаем обратное полярное преобразование и получим, что через полюс
$L$ прямой $l$ проходит ровно две прямые из набора~--- поляры $a$ и $b$ точек $A$ и $B$. Здесь
использовался факт, что поляра точки пересечения двух прямых совпадает с прямой, проходящей через
их полюса.

\pb \label{Melchior} Рассмотрим граф на проективной плоскости, вершины которого~--- точки пересечения прямых,
рёбра~--- отрезки прямых, не содержащие внутри себя точек пересечения. Обозначим через $v$ и $e$ число вершин и
рёбер графа соответственно. Через~$f$ обозначим, как обычно, число областей проективной плоскости. Не умаляя
общности, будем считать, что одна из прямых набора бесконечно удалена. Если это не так, подберём центральное
проектирование так, чтобы некоторая прямая набора стала бесконечно удалённой, числа $v, e, f, t_i$ и $p_j$ при
этом не изменятся. Заметим, что если связный граф на проективной плоскости содержит все бесконечно удалённые
точки, то верна формула Эйлера $v-e+f=1.$ Поскольку $t_n=0,$ то все области проективной плоскости, образованные
графом, ограничены не менее, чем тремя рёбрами. Следовательно, $p_2=0.$ Заметим, что тогда $$v=\sum_{i\geqslant
2}t_i, \quad e=\sum_{i\geqslant 2}it_i=\frac 12 \sum_{j\geqslant 3}jp_j, \quad f=\sum_{j\geqslant 3}p_j.  $$
 Следовательно,
 $$3=3f-(2e+e)+3v=3\sum_{j\geqslant 3}p_j-\left(\sum_{j\geqslant 3}jp_j+\sum_{i\geqslant 2}it_i\right)+3\sum_{i\geqslant 2}t_i=\sum_{j\geqslant 3}(3-j)p_j+\sum_{i\geqslant 2}(3-i)t_i.$$

\pb \label{t_2 for n<10} Ответ:
$\begin{array}{clclcccccc}
n:  & 3 & 4 & 5 & 6 & 7& 8 & 9 \\ \hline
t_2: & 3 & 3 & 4 & 3 & 3 & 4 & 6
                               \end{array}$.
Пример для $n \g 6$ см. в задаче \ref{t_2 primer}.

Из задачи \ref{Melchior} следует, что $t_2\g 3.$

(i) Докажем, что для 5 прямых $t_2\g 4$. Из задачи \ref{pari} следует, что $10=t_2+3t_3+6t_4$. Следовательно, $t_2$ не может делиться на~3.

(ii) Докажем, что для 8 прямых $t_2 \g 4$. Если $t_5+t_6+t_7=1$, то $t_2\g 4.$ В противном случае из задачи \ref{pari} следует, что $28=t_2+3t_3+6t_4$. Поэтому $t_2$ не может делиться на~3.

(iii) Докажем, что для 9 прямых $t_2 \g 6$. Если $t_6+t_7+t_8= 1,$ то из задачи \ref{Melchior} следует, что $t_2 \g 6$.
Если $t_5=1,$ то пять прямых, проходящих через одну точку, пересекают остальные 4 прямые не менее
 чем в $5\cdot 4-2C_{4}^2=8$ точках кратности 2, т.е. $t_2\g 8.$ Если  $t_5+t_6+t_7+t_8=0$, то $36=t_2+3t_3+6t_4$  и  $t_2\g 3+t_4$.
Отсюда при условии $t_2<6$ из задачи \ref{Melchior} получаем, что $t_2=3$, $t_3= 11$, $t_4=0$, и все области
треугольные, $p_3=26=f$. Осталось доказать невозможность такой конфигурации.

%Рассмотрим любую из этих девяти прямых. Так как остальные восемь прямых пересекают её в точках кратности 2 или 3,
%то либо на ней находится 4 точки пересечения кратности 3, либо


\pb \label{t_2 primer} (a) Возьмём все стороны правильного $\frac n2$-угольника и $\frac n2$ его осей симметрии. Для этих $n$ прямых $t_2=\frac n2$.

(b) Если $n=4k+1$, то добавим к примеру для $4k$ прямых бесконечно удалённую прямую. Если $n=4k+3$, то возьмём предыдущий пример для $4k+4$ прямых и удалим прямую, не проходящую через вершины $2k+2$-угольника. В обоих случаях получим $n$ прямых и $t_2=3k$.

\pbzz Доказательство см. в статье <<On the number of ordinary lines determined by n points>>, опубликованной
L.~M.~Kelly и  W.~O.~J.~Moser в журнале <<Canadian Journal of Mathematics>> в 1958 г. на стр. 210-219.

\pbzz Наилучший известный результат: $t_2\g \frac{6}{13}n$ для $n\g 8$. Доказательство см. в статье <<There exist
$\frac{6n}{13}$ ordinary points>>, опубликованной J.~Csima и E.~T.~Sawyer в журнале <<Discrete and Computational
Geometry>>  в 1993 г. в выпуске 9 на стр. 187-202.


\pbz \label{t inequality} Если существуют такие две точки, что любая данная прямая проходит через хотя бы одну из них, то требуемое неравенство проверяется непосредственно следующим образом. Пусть через одну из этих точек проходит~$a$ прямых, через другую~---~$b$ прямых. Тогда, если $a+b=n,$ то
$$a\g 3,\ b\g 3, \quad t_2=ab,\quad \sum_{i\g 4} \left(2i-7\frac 12\right)t_i\lle 2a+2b-15.$$
Если $a+b=n+1,$ то
$$a\g 4,\ b\g 4, \quad t_2=(a-1)(b-1),\quad \sum_{i\g 4} \left(2i-7\frac 12\right)t_i= 2a+2b-15.$$

Теперь считаем, что не существует таких двух точек, что любая прямая набора проходит через по крайней мере одну из них. Воспользуемся всеми тремя пунктами задачи \ref{for pt and t}:
$$3p_4+\sum_{j\g 5}jp_j\g z+x =z+\left(y+2t_2-\sum_{i\g 3}it_i\right)\g \frac 32\sum_{i \g 3}t_i +2t_2-\sum_{i\g 3}it_i=2t_2-\sum_{i\g 3}\left(i-\frac 32\right)t_i.$$
Вследствие задачи \ref{Melchior} имеем:
$$\sum_{i\g 2}(9-3i)t_i=9+3p_4+\sum_{j\g 5} (3j-9)p_j.$$
Заметим, что $3j-9\g j$ для $j \g 5$ и что $p_j\g 0.$ Следовательно, получаем
$$\sum_{i\g 2}(9-3i)t_i=9+3p_4+\sum_{j\g 5} (3j-9)p_j\g 3p_4+\sum_{j\g 5}jp_j \g 2t_2-\sum_{i\g 3}\left(i-\frac 32\right)t_i,$$
откуда вытекает требуемое неравенство на числа $t_i.$



\pb \label{for pt and t} Рассмотрим соответствующий граф, вершины которого~--- точки пересечения (покрашенные в один из двух цветов),
 рёбра~--- отрезки прямых, не содержащие внутри себя других точек пересечения.

(a) Каждая красная вершина является красным концом четырех рёбер. При этом у красных рёбер по два красных конца,
у бесцветных рёбер по одному, а у синих рёбер красных концов нет. Число красных вершин равно $t_2.$ Поэтому
$$
4t_2=2x+\sum_{i\g 2}it_i-x-y,
$$
 откуда получаем требуемое.

(b) Рассмотрим произвольную синюю вершину $O$ и удалим все проходящие через неё прямые набора. Оставшиеся прямые
не будут проходить через одну точку и поэтому разделят проективную плоскость на области, каждая из которых
ограничена не менее чем тремя рёбрами. Точка $O$ принадлежит одной из таких областей. Перебором можно убедиться в
том, что для вершины $O$ всегда выполняется одно из следующих трёх условий.

(1) Из точки $O$ выходит не менее трёх синих рёбер (в исходном графе).

(2) Из точки $O$ выходит не менее двух синих рёбер и точка $O$ является вершиной границы хотя бы одной зелёной
области.

(3) Точка $O$ является вершиной границы не менее чем двух зелёных областей.

Тем самым для каждой синей вершины сумма числа исходящих из неё синих рёбер с удвоенным числом граничащих с ней
зелёных областей не меньше трёх. Сложим эти суммы по всем синим вершинам и получим $2y+2s\g \sum_{i\g 3}t_i$.

(c) Для зелёной области $u$ обозначим через~$x(u)$ и~$s(u)$ число красных рёбер и число синих вершин на границе $u$, соответственно. 
Для зелёной области $u$ положим
$$
d(u) = \left\{
   \begin{array}{ll}
     0,  & \hbox{если \ \ $s(u)\geqslant 1$;} \\
     1,  & \hbox{если \ \ $s(u)=0$.}
   \end{array}
 \right.
 $$
Нетрудно доказать, что если зелёная область $u$ ограничена $j$ рёбрами, то
$$
s(u)\leqslant (j-1)-x(u)+d(u).
$$

Обозначим через $X$ и через $D$ суммы $x(u)$ и $d(u)$ по всем зелёным областям соответственно. Тогда, складывая
предыдущее неравенство по всем зелёным областям, получим
$$
s \lle \sum_{j\g 4} (j-1)p_j \  -X+D.
$$
 Заметим, что к любому красному ребру примыкает не менее одной зелёной области (это следует из $t_n=t_{n-1}=0$). Назовём красное ребро тёмно-красным, если
 к нему примыкают две зелёные области. Обозначим через $x_1$ число тёмно-красных рёбер. Тогда $X=x+x_1$. 
 Выделим четырехугольные области, все вершины которых красные (все выделенные области зелёные). Нетрудно доказать, что каждая 
 выделенная 
 область ограничена не менее чем двумя тёмно-красными рёбрами. Следовательно, число выделенных областей не
 превосходит $x_1$. Отсюда следует, что $D\lle x_1+\sum_{j\g 5 }p_j$. Осталось соединить все полученные
 неравенства.



\end{document}
