\documentclass[12pt,a4paper]{article}
\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{Problem \arabic{zadacha}.} }

\newcommand{\pbz}{\par\refstepcounter{zadacha}%
\textbf{Problem \arabic{zadacha}$^{*}$.} }

\newcommand{\pbzz}{\par\refstepcounter{zadacha}%
\textbf{Problem \arabic{zadacha}$^{\bigstar}$.} }
%


\begin{document}
\righthyphenmin=2
\centerline{{\Large\bf Planar arrangements of lines}}

\bigskip
\centerline{ Solutions of problems before intermediate finish}

\bigskip
\bigskip
\pb \label{fminmax} The answer is: $n+1 \lle f \lle \frac{n(n+1)}2+1$. The both inequalities can be proved by induction on~$n$. The base of induction
$n=1$, $f=2$ is evident. Let us add one line. If it has~$x$ intersection points with the old lines, then the number of regions increases by~$x+1$ after adding this line.
Hence, the~$n$th line increases the number of regions by at least~1 and at most~$n$.


\pb The answer is:
\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}
 The impossibility of the other values can be deduced from problems~\ref{fminmax} and~\ref{3ocenki}(a)(b).

\pb \label{3ocenki}
(a) Let us consider~$p$ parallel lines of the arrangement and then add the other lines one by one. Each added line has at least~$p$
intersection points with the preceding lines, hence, the number of regions increases by at least~$p+1$. In total, if we add~$n-p$ lines, we obtain
$f \g (p+1)(n-p+1)$.

(b) Let us consider~$q$ concurrent lines and then add all the remaining lines one by one. Every new line has at
least~$q-1$ intersection points with the preceding lines, hence the number of regions increases by at least~$q$
after adding this line. If we add~$n-q$ lines, we obtain $f \g q(n-p+2)$.

(c) Let us consider~$p$ parallel lines, then fix a point on one of these lines and pass~$n-p$ other lines through this point one by one. Each new line
increases the number of regions by~$p$, and finally we obtain $(p+1)(n-p)$ regions.

Let us consider~$q$ concurrent lines. All the other~$n-q$ lines will be parallel to one chosen line of these~$q$ lines. Pass them one by one. Every new line increases the number of regions by~$q$, so we obtain~$q(n-q+2)$ regions.

(d) {\it Solution 1.} Let us add the lines one by one. If the line has~$x$ intersection points with the preceding lines, then the number of regions
increases by~$x+1$. On the other hand, each of these~$x$ intersection points either has multiplicity~2, or one plus its previous multiplicity. 
Hence the sum $\sum_{i \g 2} (i-1)r_i$ increases by~$x$ after adding this line.

 {\it Solution 2.} Let us intersect the given arrangement with the disk of a sufficiently big radius (such that the disc contains all the intersection points of lines). Consider the following graph: its vertices are the intersection points of lines with each other and with the boundary of the disc, its edges are
the line and circle segments which do not contain intersection points except its ends. The number of vertices of
this graph equals $v=2n+\sum_{i \g 2} r_i$, the number of edges equals $e=3n+\sum_{i \g 2} ir_i$. The number of
regions $f$ of the plane is less by one than the number of the regions of the disc divided by the edges of the
graph. Using the Euler formula for the graphs, we obtain
$$
f=n+1+\sum_{i \g 2} (i-1)r_i.
$$



\pb \label{3lakuni} (a) If all the lines are parallel, then $f=p+1$. If not all the lines are parallel, then $1\lle p \lle n-1$. Using problem~\ref{3ocenki},
we obtain $f \g (p+1)(n-p+1)$. The expression $(p+1)(n-p+1)$ is the quadratic trinomial in~$p$ with the negative leading coefficient.
For~$p=1$ and~$p=n-1$, the value of the trinomial $(p+1)(n-p+1)$ is~$2n$. Hence, for~$1\lle p \lle n-1$ the value of the trinomial $(p+1)(n-p+1)$
is not less than~$2n$.

(b) If all or all except one lines are parallel, then $f=n+1$ or $f=2n$. Otherwise, using problem~\ref{3ocenki}(a), we have $f \g (p+1)(n-p+1)$.
The expression $(p+1)(n-p+1)$ is a quadratic trinomial with respect to~$p$ with the negative leading coefficient. For~$p=2$ and~$p=n-2$
the value of the trinomial $(p+1)(n-p+1)$ equals~$3n-3$. Hence, for $2\lle p \lle n-2$ the value of the trinomial $(p+1)(n-p+1)$
is not less than $3n-3$.
Consequently, for $2\lle p \lle n-2$ we have $f\g 3n-3$. If $p=1$, then, using problem~\ref{3ocenki}(b), we have $f\g q(n-q+2)$. If $q=n$, then $f=2n$.
Consider the quadratic trinomial $q(n-q+2)$. For $3\lle q \lle n-1$ we have $f \g q(n-q+2) \g 3n-3.$ The remaining case is $p=1$, $q=2$, where the
number of regions is
$$
1+\frac{n(n+1)}2\g 3n-3\quad  \lra \quad n^2 -5n +8 \g 0.
$$

(c) If $p\geqslant n-2$ or $q\geqslant n-1$, then $f\leqslant 3n-2$. If $3\leqslant p\leqslant n-3$ or $4
\leqslant q\leqslant n-2$, then by problem~\ref{3ocenki} we have $f\geqslant 4n-8$. The remaining case is
$p\leqslant 2$ and $q\leqslant 3.$ By problem~\ref{3ocenki} we have $f=n+1+r_2+2r_3$. Each line of the arrangement
intersects at least~$n-2$ other lines. Hence, the number of pairs of intersecting lines equals $r_2+3r_3$, which is
not less than $\frac{n(n-2)}2$. Consequently,
$$
f\g n+1 +\frac 23(r_2+3r_3)\geqslant n+1+\frac{n^2-2n}3\geqslant 4n-8
$$
for $n\geqslant 8$.


\pb \label{fpqmax}(a) Consider~$p$ parallel lines in the arrangement of~$n$ lines and add the remaining lines one by one. The line number~$i$, $1\lle i \lle n-p$, intersects the preceding lines in at most $p+i-1$ points, hence the number of regions increases by at most $p+i$. If we add $n-p$ lines,
we obtain
$$
f \lle (p+1)(n-p+1)+C_{n-p}^2.
$$
The bound is reached for the arrangement containing $p$ parallel lines and $n-p$ lines in general position (i.e. no two are parallel and no three are concurrent), such that they are also in general position with the~$p$ parallel lines.

%
(b) Consider~$q$ concurrent lines in the arrangement of~$n$ lines and add the remaining lines one by one. The line number $i$, $1\lle i \lle n-q$,
intersects the preceding ones in at most~$q+i-1$ points, hence the number of regions increases by at most~$q+i$.
If we add $n-q$ lines, we obtain
$$
f \lle q(n-p+2)+C_{n-q+1}^2=1+C_{n+1}^2-C_{q-1}^2.
$$
The bound is reached for the arrangements of~$q$ concurrent lines and~$n-q$ lines in general position such that they are also in general position with
the~$q$ concurrent lines.

\pb \label{primer} Let us take~$n-p$ lines in general position and choose some~$t$ intersection points of these lines, where $t \lle \min\{p,C_{n-p}^2\}$. Now add~$p$ parallel lines in such a way that they pass through~$t$ chosen points but do not
pass through the other intersection points of the $n-p$ lines. Also, the~$p$ added lines should not be parallel to any of the first~$n-p$ lines. Then
it is easy to check that this arrangement has at most~$p$ parallel lines, and that the number of regions equals
$$
f=(p+1)(n-p+1)+C_{n-p}^2-t.
$$


\pb For given~$n$ and~$p$, the minimal number of regions of the arrangement equals $(p+1)(n-p+1)$. To reach it, we can take the arrangement containing
$n-p+1$ concurrent lines and $p-1$ parallel lines such that the parallel lines are also parallel to one chosen line of the first $n-p+1$ ones. Now note that 
$$
(p+1)(n-p+1)<a(n,p)\  \lra \ C_{n-p}^2>p\  \lra\ n>p+\frac 12+\sqrt{2p+\frac 14}.
$$
The second inequality is also equivalent to $n\g p+\frac 12+\sqrt{2p+\tfrac 94}$ (if we write $C_{n-p}^2\g p+1$).

\pb \label{chislolakun} (a) 
\begin{gather*}
L(n)=\max\{k \g 1 \ |\ b(n,n-k+1)\lle a(n,n-k)-2\} \mbox{ for }n\g 3.\\
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{gather*}
It follows that $L(n)=\left[\sqrt{2n -\frac{15}4}-\frac 12\right]$.


(b) Since
$$
n \g \frac{L^2(n)+L(n)}2+2,  \text{  then } \min\left\{n-j, \ \frac{j(j-1)}2\right\}=\frac{j(j-1)}2  \text{  for } 1\lle j \lle L(n).
$$
Hence, $a(n,n-j)=(n-j+1)(j+1)$, and the $j$th gap contains $n-\frac{j(j+1)}2-1$ integers.

\pb \label{pq v lakune} If $j \lle p \lle n-j $ or $j+1\lle q \lle n-j+1$, then by problem~\ref{3ocenki} we have $f\g (n-j+1)(j+1)=a(n,n-j)$. If
$p \g n-j+1$, then, as follows from problem~\ref{fpqmax},
$$
f \lle (p+1)(n-p+1)+C_{n-p}^2\lle b(n,n-j+1).
$$
If $q \g n-j+2$, then by problem~\ref{fpqmax} we have
$$
f\lle q(n-q+2)+C_{n-q}^2+1\lle b(n,n-j+1).
$$

\pb \label{r ocenka par} The number of pairs of intersecting lines equals $\sum_{i=2}^q\frac{i(i-1)}2r_i$ which is not less than $\frac{n(n-p)}2$,
since every line intersects at least~$n-p$ lines.



\pb \label{sqrtn lakun} (a) Using problems~\ref{3ocenki} and~\ref{r ocenka par}, we obtain that
$$
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) Suppose the contrary, then by problem~\ref{pq v lakune} we have $p \lle j-1$ and $q\lle j$, where~$j$ is the
number of the gap. Note that $n-p\g n-j+1$ and $n+1 \g n-j+1$. It contradicts with~(a):
$$
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} Let us intersect the given arrangement with a disc of a sufficiently big radius,
such that it contains all the intersection points. We obtain a graph: its vertices are the intersection points of
the lines of the arrangement and the intersection points of the lines with the circle, its edges are the line and circle segments, 
which do not contain intersection points except their ends. The number
of vertices~$v$ and the number of edges~$e$ equal $2n+\sum_{i \g 2} r_i$ and $3n+\sum_{i \g 2} ir_i$,
respectively. The interior of the disc contains~$f$ regions, where
$$
f=n+1+\sum_{i \g 2} (i-1)r_i.
$$
The sum of the numbers of bounding edges for all the regions in the disc equals
$$
2e-2n=4n+2\sum_{i \g 2} ir_i.
$$
Since $p<n$, every region in the disc is bounded by at least three edges of the graph. So we have $2e-2n \g 3f$,
which gives the required inequality.

























\pb \label{l-2 lakun} (a) Let $a=\frac 2{q+3}$ and $b=\frac{q-1}{q+3}$. Consider the following quadratic trinomial in the variable~$i$:
$$
a(i^2-i)+b(3-i)-(i-1)=a(i-2)(i-q)\lle 0 \quad \text{for} \quad 2 \lle i \lle q.
$$
Let us multiply its corresponding values by~$r_i$ and sum up for all~$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),
$$
where the last inequality is obtained from problems~\ref{r ocenka par}, \ref{r ocenka Melchiora}, and~\ref{3ocenki}. Consequently,
$$
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) Suppose the contrary, then by problem~\ref{pq v lakune} we have $p \lle j-1$ and $q\lle j$. Using that $n-p \g
n-j+1$, we get a contradiction with~(a):
$$
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),
$$
because
$$
\frac {(q+3)(j+1)}2\lle \frac {j^2+4j+3}2\lle \frac 12 L^2(n)< n.
$$

\pb (a) The intersection point determines two diagonals passing through it and the ends of these diagonals, which form a four-tuple of vertices of the given~$n$-gon. 
Conversely, every four-tuple of distinct vertices of the~$n$-gon determines one intersection point of diagonals. Hence, the number of intersection 
points is $C_n^4$.



(b) {\it Solution~1.} Let us pass the diagonals one by one. If the added diagonal has~$x$ intersection points with the previous diagonals, 
then the number of regions of the interior of the~$n$-gon is increased by~$x+1$. We can treat it as every diagonal and every intersection point increases 
the number of regions by~1. Hence, the required number of regions equals $1+C_n^4+\frac{n(n-3)}2$, because the number of intersection points was 
found in~(a), and the number of diagonals equals~$\frac{n(n-3)}2$.


{\it Solution~2.} Let us consider a graph: its vertices are the vertices of the $n$-gon and the intersection points of the diagonals, its edges are 
the diagonal segments and the sides of the $n$-gon. In this graph, the number of vertices equals $v=n+C_n^4$, and the number of edges equals 
$e=2C_n^4+\frac {n(n-1)}2$. By the Euler formula, the number of regions equals $1+e-v=1+C_n^4+\frac {n(n-3)}2$.

\pb See problem~\ref{main theorem}.

\pb Let us draw the lines each of which passes through exactly two of given points. These~$m$ lines divide the plane into at most~$1+m+C_m^2$ 
regions. Consider all the points of the given set such that for each of these point, no line passing through exactly two points of the given set, passes 
through this point. It turns out that every region formed by the arrangement of~$m$ lines contains at most one such point (prove it yourself). Also 
find yourself~$m$ regions not containing such points. In total, $m$ lines contain at most~$2m$ points of the initial set. Hence $n\lle
2m+1+C_m^2=C_{m+2}^2$.


\bigskip
\bigskip
\centerline{{\bf The solutions of the problems after intermediate finish}}

\medskip
\pb For the parallel planes~$\alpha_1$ and~$\alpha_2$, the central projection is just a dilatation, which maps lines to lines and regions to regions. 
Now suppose that~$\alpha_1$ and~$\alpha_2$ intersect, and let~$l_1$ and~$l_2$ be the intersection lines of the planes~$\alpha_1$ and~$\alpha_2$ 
with planes passing through the point~$O$ parallel to planes~$\alpha_2$ and~$\alpha_1$, respectively. If a line~$l$ does not coincide 
with~$l_1$, then its image is a line for $l\| l_1$, and is a pointed line if $l\nparallel l_1$ (the line with one point thrown out, namely the point of 
intersection with~$l_2$). If a region intersects~$l_1$, then its image consists of two unbounded regions. If a non-bounded region is incident to 
two non parallel rays, then its image is incident to~$l_2$.

\pb \label{proekcia} It is one-to-one by definition. The image and the pre-image will be the lines~$l_2$ and~$l_1$ together with their infinite points. Recall that~$l_1$ and~$l_2$ are the lines of intersection of the planes~$\alpha_1$ and $\alpha_2$ with the planes passing through~$O$ parallel 
to~$\alpha_2$ and~$\alpha_1$, respectively.

\pb \label{pari} Every two lines have exactly one common points on the plane considered with its infinite points (if these lines are parallel or one of the lines is infinite, then this point is infinite). The number of pairs of lines is~$C_n^2$. If an intersection point belongs to~$i$ points, it is an intersection point for~$C_i^2$ pairs of lines, which gives the required.

\pb First we suppose that not all the lines of the arrangement of~$n$ lines are concurrent, and define the ``region'' in the projective plane in this case. 
If one of the lines is infinite, then the regions coincide with the regions of the usual plane divided by~$n-1$ remaining lines. 
If the arrangement does not contain the infinite line, then the following objects will be the regions:
\begin{itemize}
  \item a bounded region of the plane,
  \item a non-bounded region of the plane incident to two parallel rays,
  \item a pair of non-bounded regions of the plane, the first one incident to two non-parallel rays~$l_1$ and~$l_2$, the second one to 
  non-parallel rays~$l_3$ and~$l_4$, such that $l_1\| l_3$ and $l_2 \| l_4$. The infinite points corresponding to the directions which are between~$l_1$ 
  and~$l_2$ also belong to this region, they ``glue up'' two its infinite parts.
\end{itemize}
If all the lines of the arrangement are concurrent, ``regions'' are defined in a similar way. 
Two points belong to the same region if and only if they are connected by a polygonal line not intersecting the lines of the arrangement. Here the ends of the polygonal line are the two given points, and the other vertices can be infinite. Its segments incident to an infinite vertex are rays 
which are parallel to the direction of this infinite point. After this re-definition, the polygonal line is mapped to a polygonal line via a central 
projection. Consequently, two points belong to one region if and only if their images via the central projection belong to one region. So the 
correspondence between regions is one-to-one.

\pb  \label{f ocenki} (a) {\it Solution~1. } Let us map one line of the arrangement to the infinite line via a central projection. 
The number of regions and the values~$t_i$ do not change, but now the number of regions of the projective plane coincides with 
the number of regions~$f$ of the usual plane, divided by the arrangement of~$n-1$ remaining lines. By problem~\ref{3ocenki}, 
we have $f=n+\sum_{i\g 2}(i-1)r_i$. Now note that
$$
n-1=\sum_{i \g 2} (i-1)(t_i-r_i),
$$
since the infinite line contains $t_i-r_i$ intersection points, which belong to~$i-1$ lines of the arrangement, and plus the infinite point.

{\it Solution~2.} Induction on~$n$. The base $n=1$ is evident. The step follows from the fact that each added line 
increases the number of regions by the number of the points of intersection with the previous lines.

(b) Induction on~$n$. The base $n=m$, $f=m$ is evident. The added line number~$j$, $1\lle j \lle n-m$, has at least~$m$ 
and at most~$m+j-1$ points of intersection with the previous lines, since every two lines intersect in the projective plane. 
The required inequality follows from the fact that each added line increases the number of regions by the number of points of intersection 
with the previous lines.


(c) Consider the graph in the projective plane: its vertices are the intersection points of lines, the edges are the line segments. We allow edges to pass through infinite points, such an edge consists of two rays belonging to the same line together with the infinite point of this direction which glues up the two rays. The number of vertices~$v$ and the number of edges~$e$ of this graph equal $\sum_{i \g 2} r_i$ and $\sum_{i \g 2} ir_i$, respectively. 
Since $m<n$,  each region is bounded by at least three edges of the graph, hence
$$
3f\lle 2e\; \lra\;  3+3\sum_{i\g 2}(i-1)t_i \lle 2\sum_{i \g 2} ir_i\;  \lra \; \sum_{i\g
2}(3-i)t_i\g 3.
$$

(d) Let $a=\frac 2{M+3}$ and $b=\frac{M-1}{M+3}$. Consider the following quadratic trinomial in variable~$i$:
$$
a(i^2-i)+b(3-i)-(i-1)=a(i-2)(i-M)\lle 0 \quad \text{if} \quad 2 \lle i \lle m.
$$
Multiply the corresponding values of this trinomial by~$t_i$ and sum up for all~$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),
$$
where the last inequality follows from problems~\ref{pari}, \ref{f ocenki}(a) and~(c). Consequently,
$$
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} Let us choose two points~$P$ and~$Q$ incident to~$m$ lines each, and denote by~$N$ 
the set of lines of the initial arrangement passing through at least one of~$P$ and~$Q$. Two cases are possible:

(i) the line~$PQ$ does not belong to the initial arrangement. Then~$N$ contains~$2m$ lines and divides the projective plane into $m^2+2m-1$ regions 
(if we do not consider other lines).

(ii) the line~$PQ$ belongs to the initial arrangement. Then~$N$ contains~$2m-1$ lines and divides the projective plane into~$m^2$ regions (if we do not consider other lines).

In both cases every remaining line of the arrangement (i.e. a line not from~$N$) intersects the lines from~$N$ in at least~$m$ points, and 
there are at most two lines which intersect the lines from~$N$ in exactly~$m$ points. In the case~(i) the inequality is held because
$$
f \g m^2+2m-1+(m+1)(n-2m)-2 \g (m+1)(n-m).
$$

Now consider the case~(ii). If the arrangement contains at most one line which intersects the lines from~$N$ in~$m$ points, then the number of regions 
can be bounded using the number of intersection points of the other lines as follows:
$$
f\g m^2+(m+1)(n-2m+1)-1=(m+1)(n-m).
$$
If the arrangement contains two lines intersecting~$N$ in~$m$ points each, and their intersection point does not belong to the lines from~$N$, then we similarly obtain~$f\g (m+1)(n-m)$.

The remaining case is when the arrangement contains two lines intersecting~$N$ in~$m$ points each, and their intersection point 
belongs to a line of~$N$. Denote these lines by~$l_{2m}$ and~$l_{2m+1}$, and their intersection point by~$R$. Let us prove in this case that 
every other line of the arrangement intersects $N\cup l_{2m} \cup l_{2m+1}$ in at least~$m+2$ points. It will follow from this fact that 
$$
f\g m^2+2m+(m+2)(n-2m-1)\g (m+1)(n-m)
$$
which will end the proof in the case~(ii).

Let us denote the lines passing through the point~$P$ in the sequence order, counting from the line~$PQ$, by $l_1, \dots, l_{m-1}$. 
Similarly denote the lines passing through~$Q$ in the sequence order, counting from~$PQ$, by $l_m, \dots, l_{2m-2}$. Denote by~$A_{i,j}$ the 
point of intersection of lines~$l_i$ and~$l_{m-1+j}$, where $1\lle i,j \lle m-1$. 
Without loss of generality, we may assume that the line~$PQ$ is infinite, that the line~$l_{2m}$ passes through the points~$A_{i,i}$ for $1\lle i \lle m-1$, 
and that the line~$l_{2m+1}$ passes through the points $A_{i,m-i}$ for $1\lle i \lle m-1$. Then the lines~$l_{2m}$ and~$l_{2m+1}$ intersect in the 
point~$A_{\frac m2, \frac m2}$, and~$m$ is even. Consider an arbitrary remaining line~$l$ of the arrangement. It intersects~$N$ in 
at least~$m+1$ points. If at least one point of intersection of~$l$ with~$l_{2m}$ or with~$l_{2m+1}$ does not belong to the lines 
from~$N$, then~$l$ intersects $N\cup l_{2m} \cup l_{2m+1}$ in at least~$m+2$ points.

Let us note that if the line~$l$ passes through the point~$A_{\frac m2, \frac m2}$, then the intersection points of~$l$ 
with the lines $l_{\frac m2-1}$ and $l_{\frac m2+1}$ or with the lines $l_{m-1+\frac m2-1}$ and $l_{m-1+\frac m2+1}$ differ from the points~$A_{ij}$. 
Hence, the line~$l$ intersects~$N$ in at least~$m+2$ points.

Without loss of generality, we may assume that the intersection point of lines~$l$ and~$PQ$ and the intersection point of the 
lines~$l_{2m}$ and~$PQ$ belong to one line segment $PQ$ of the line~$PQ$ (in the projective line, two points divide the line into two segments). 
Then the line~$l$ intersects~$l_{2m+1}$ in a point~$A_{a,b}$ with $|a-b|\g 2$. Hence, the line~$l$ passes through at most 
$\min\{a, b\}+\min\{m-1-a, m-1-b\}\lle m-3$ points of form~$A_{i,j}$. Consequently, the line~$l$ intersects~$N$ in at least~$m+2$ points.


The statement is not true for $n=2m+1$. The counterexample for every even~$m \g 4$ can be constructed as follows: $m$ lines pass through each 
of~$P$ and~$Q$, the line~$PQ$ is common. Two more lines intersect these~$2m-1$ lines in~$m$ points each. It gives $f=m^2+2m<(m+1)^2$.


\pbz \label{main theorem} If we add the infinite line to the arrangement, the number of regions does not change, the number of lines~$n$ 
increases by~1, and we obtain~$p+1$ concurrent lines instead of~$p$ parallel lines. It gives us the following statement:

{\it The number~$f$ can be the number of regions of the projective plane divided by~$n$ lines if and only if~$f$ 
belongs to at least one of the intervals $[a(n,m), \ b(n,m)]$, $n\g m \g 2$, where
$$
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\}.
$$  }

As before, a {\it gap} is an interval $(b(n,m), a(n,m-1))$ which contains at least one integer. It follows from problem~\ref{chislolakun} 
that $L(n)=\left[\sqrt{2n -5\frac{3}4}-\frac 12\right]$. In the sequel we denote $L(n)$ just by~$L$, omitting~$n$. 
Taking into consideration problem~\ref{l-2 lakun}, it remains to prove that the number of regions cannot belong to the two last 
gaps numbered~$L-1$ and~$L$.

Suppose that there exists an arrangement such that the value~$f$ belongs to the $(L-1)$th gap, namely to the interval 
$$
\left((n-L+2)(L-1)+C_{L-2}^2, \ \ L(n-L+1)\right).
$$
It follows from problem~\ref{pq v lakune} that $m=\max\{p+1, \ q\}\lle L-1$. Apply problem~\ref{f ocenki} for $M=L-1$:
$$
f \g \frac{2(n^2-n)}{L+2}\g L(n-L+1).
$$
In the last inequality, we used that $n\g \frac{L^2+L}2+3$ as follows:
$$
n^2-n \g (n+\frac L2 -3)(n-L+1) \g \left(\frac{L^2+2L}2\right)(n-L+1).
$$
It contradicts with the fact that~$f$ belongs to the $(L-1)$th gap.

Now let us assume that there exists an arrangement of lines in the projective plane such that the number of regions belongs to the $L$th gap:
$$
f \in \left(L(n-L+1)+C_{L-1}^2,\ (L+1)(n-L)\right).
$$
By problem~\ref{3lakuni} we may assume that $L \g 4$. Using problem~\ref{pq v lakune}, we have $m \lle L$. Consider~3 cases.

(1) If $m<L$, then by problem~\ref{f ocenki}(d) for $M=L-1$ we obtain
$$
f>\frac{2(n^2-n)}{L+2}\g (L+1)(n-L),
$$
because it follows from $n\g \frac{n^2+n}2+3$ that
$$
\frac{(L+2)(L+1)}2(n-L)\lle (n+L-2)(n-L)\lle n^2-2n.
$$

(2) If $m=L$ and $t_m=1$, then throw out one line passing through a point which belonged to~$m$ lines. This operation decreases the number of regions. We can apply the inequality from problem~\ref{f ocenki}(d) for $M=L-1$ to the remaining arrangement of~$n-1$ lines and obtain 
$$
f \g 2\left(\frac{n^2-3n+2L}{L+2}\right)\g (L+1)(n-L).
$$
Let us prove the last inequality. If $n \g \frac{L^2+L}2+4$, then
$$
n^2-3n+2L \g (n-L)(n+L-3)\g (n-L)\left(\frac{L^2+3L+2}2\right).
$$
The case $n=\frac{L^2+L}2+3$ can be checked directly.

(3) If $m=L$ and $t_m\g 2$, then $n\g 2m+2$, and it follows from the preceding case that $f\g (L+1)(n-L)$.

\pb (a) Answer: it is the set of values from the main theorem for an arrangement of~$n$ lines in the plane. Let us consider a circle 
centered in the common intersection point and make an inversion with respect 
to this circle. We obtain an arrangement of lines, and the number of regions 
did not change. Conversely, if an arrangement of lines is given, then we can make an inversion with respect to some circle such that 
its circle does not belong to any line. We will get an arrangement of circles with the same number of regions.

(b) Answer: it is the set of doubled values from the main theorem for the projective plane. 
Consider the projection of the sphere with center~$O$ to the plane~$\alpha$ tangent to the sphere in its south pole. Then a point~$X$ of the 
sphere is mapped to the point of intersection of the line~$OX$ with the plane~$\alpha$. If~$OX$ is parallel to~$\alpha$ then~$X$ 
is mapped to the infinite point of direction~$OX$. Under this projection, the big circles of the sphere are mapped to the lines 
of the projective plane, and the pair of opposite (symmetric wrt the center) regions of the sphere are mapped to the same region of the 
projective plane. Hence, the number of regions of the sphere equals the doubled number of regions of the projective plane divided by the corresponding 
arrangement of lines. Conversely, for every given arrangement of lines on the projective plane, we can construct an arrangement of big circles on the sphere via the inverse projection from the projective plane to the sphere, and this operation will double the number of regions.

\pb \label{Sylvester}(a) Consider the pair ``line $AB$, point $C$ not on this line'', such that the points $A$, $B$, $C$ belong to the given set and 
the distance from the point~$C$ to the line~$AB$ is minimal among all such pairs. Suppose that the line~$AB$ contains a point~$D$ from the given set. 
Without loss of generality, we may suppose that~$D$ is between~$A$ and~$B$ 
and that the angle $ADC\g 90^{\circ}$. 
Then the distance between~$D$ and~$AC$ is less than the distance between~$C$ and~$AB$, which contradicts the choice of points~$A$, $B$, 
and~$C$. Hence, the line~$AB$ does not contain the initial points except~$A$ and~$B$.

(b) {\it Solution~1.} Suppose the contrary, i.e. each intersection point belongs to at least three given lines. It can be easily seen that we are not in the case when there are only two directions of lines. Now we can 
assume that the arrangement contains three pairwise non-parallel lines which are not concurrent. For all such triples of lines, consider the triangle 
formed by these three lines, and choose among them the triangle~$ABC$ of the minimal nonzero area. 
Since at least three points pass through each of~$A$, $B$, and~$C$, and using the fact that the area of~$ABC$ is minimal, we obtain that 
the lines passing through~$A$, $B$, and~$C$ parallel to~$BC$, $CA$, and~$AB$, respectively, belong to the arrangement. Let us denote 
by~$A_1$, $B_1$, and~$C_1$ the intersection points of these three lines. 
The vertices of~$ABC$ are the midpoints of sides of~$A_1B_1C_1$. Hence, the areas of triangles~$A_1BC$, $B_1CA$, and~$C_1AB$ 
also equal the area of~$ABC$. If we similarly continue with the triangles~$A_1BC$, $B_1CA$, and~$C_1AB$, we obtain 
the infinite number of initial lines, contradiction.

{\it Solution~2.} Let us reduce the problem to the case~(a) via the polar duality. Consider a circle whose center does not belong to the 
lines of the arrangement. Make a polar transformation with respect to this circle. For every point, it puts into correspondence a line, and for 
every line, it puts into correspondence a point. The arrangement of~$n$ lines is mapped to the arrangement of~$n$ non-collinear points. 
Using~(a), there exists a line~$l$ containing exactly two poles~$A$ and~$B$. If we make this polar transformation once more (i.e. the inverse), we obtain that 
there exist exactly two lines of the arrangement passing through the pole~$L$ of the line~$l$, 
namely the polar duals~$a$ and~$b$ of points~$A$ and~$B$. Here we used the fact that the polar dual of the intersection point of two lines is the line 
which passes through the poles of these lines.

\pb \label{Melchior} Consider a graph on the projective plane: its vertices are the intersection points of lines, the edges are the line segments which do not contain other intersection points in their interior. Let us denote by~$v$ and~$e$ the numbers of vertices and edges of this graph, respectively. We 
denot by~$f$, as usually, the number of regions of the projective plane. Without loss of generality let us assume that one of lines is infinite (if not, 
find a central projection mapping one of the lines to the infinite line, this operation does not change the values $v$, $e$, $f$,  $t_i$, and~$p_j$).
Note that if a connected graph on the projective plane contains all the infinite points, then the Euler formula can be written as follows: $v-e+f=1$. 
Since $t_n=0$, all the regions of the projective plane formed by the graph are bounded by at least three edges. Hence, $p_2=0$. Note that then
$$
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.  
$$
Consequently, 
 $$
 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} Answer:
$\begin{array}{clclcccccc}
n:  & 3 & 4 & 5 & 6 & 7& 8 & 9 \\ \hline
t_2: & 3 & 3 & 4 & 3 & 3 & 4 & 6
                               \end{array}$.
The example for $n \g 6$ is constructed in problem~\ref{t_2 primer}.

If follows from the problem~\ref{Melchior} that $t_2\g 3$.

(i) Show that for~5 lines we have $t_2\g 4$. It follows from problem~\ref{pari} that $10=t_2+3t_3+6t_4$. Hence, $t_2$ is not divisible by~3.

(ii) Show that for~8 lines we have $t_2 \g 4$. If $t_5+t_6+t_7=1$, then $t_2\g 4$. Otherwise it follows from problem~\ref{pari} that 
$28=t_2+3t_3+6t_4$. Hence, $t_2$ is not divisible by~3.

(iii) Show that for~9 lines we have $t_2 \g 6$. If $t_6+t_7+t_8= 1$, then it follows from problem~\ref{Melchior} that $t_2 \g 6$.
If $t_5=1$, then five concurrent lines intersect four other lines in at least $5\cdot 4-2C_{4}^2=8$ points of multiplicity~2, i.e. $t_2\g 8$. 
If $t_5+t_6+t_7+t_8=0$, then
$$
36=t_2+3t_3+6t_4 \quad \text{ and} \quad t_2\g 3+t_4.
$$
Now using $t_2<6$ from problem~\ref{Melchior} we obtain that $t_2=3$, $t_3=11$, $t_4=0$, and all the regions are triangular,  
 $p_3=26=f$. It remains to show that such a configuration does not exist.

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


\pb \label{t_2 primer} (a) Take all the sides of a regular $\frac n2$gon and its $\frac n2$ symmetry axes. For these $n$ lines $t_2=\frac n2$.

(b) If $n=4k+1$, then add the infinite line to the example for $4k$ lines. If $n=4k+3$, then take the preceding example 
for $4k+4$ lines and remove one line which does not pass through the vertices of the $2k+2$-gon. 
In both cases we obtain~$n$ lines and $t_2=3k$.

\pbzz The proof can be found in the paper ``On the number of ordinary lines determined by n points'', after 
L.~M.~Kelly and  W.~O.~J.~Moser in the ``Canadian Journal of Mathematics'', 1958, pp. 210-219.

\pbzz The best known result is: $t_2\g \frac{6}{13}n$ for $n\g 8$. The proof can be found in the paper ``There exist
$\frac{6n}{13}$ ordinary points'', after J.~Csima and E.~T.~Sawyer in the journal ``Discrete and Computational
Geometry'', 1993, {\bf 9} pp. 187-202.


\pbz \label{t inequality} If there exist two poinst such that every line passes through at least one of these points, 
then the required inequality can be shown as follows. Suppose that~$a$ lines pass through the first of these points and that~$b$ pass through the 
second. If $a+b=n$, then
$$
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.
$$
If $a+b=n+1$, then
$$
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.
$$

Now let us assume that there are no two points such that every line passes through at least one of them. Apply all the three items of problem~\ref{for pt and t}:
$$3
p_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.
$$
Using problem~\ref{Melchior}, we obtain:
$$
\sum_{i\g 2}(9-3i)t_i=9+3p_4+\sum_{j\g 5} (3j-9)p_j.
$$
Note that $3j-9\g j$ for $j \g 5$ and $p_j\g 0$. Hence, we have 
$$
\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,
$$
which implies the required inequality for~$t_i$s.

% !!! отсюда

\pb \label{for pt and t} Consider the corresponding graph: its vertices are the intersection points (colored in one of two colors), 
the edges are the line segments which do not contain other intersection points except their ends. 

(a) Every red vertex is a red edge of four edges. Every red edge has two red edges, every non-colored edge has one red edge, blue 
edges do not have red ends. There are~$t_2$ red vertices. Hence,
$$
4t_2=2x+\sum_{i\g 2}it_i-x-y,
$$
which gives the required equality.

(b) Consider an arbitrary blue point~$O$ and delete all the lines of the arrangement passing through it. 
The remaining lines are not concurrent, hence they divide the projective plane into regions, each of them bounded by at least three edges. 
The point~$O$ belongs to one of such regions. By a case-by-case consideration, we see that at least one of the three possibilities holds for~$O$:

(1) In the initial graph, the point~$O$ is incident to at least three blue edges.

(2) The point~$O$ is incident to at least two blue edges, and~$O$ is the vertex of the boundary of at least one green region.

(3) The point~$O$ is the vertex of the boundary of at least two green regions.

It means that for every blue vertex, the sum of the number of blue edges incident to it with the doubled number of green regions incident to it is at least~3. If we sum up these sums for all the blue vertices, we obtain $2y+2s\g \sum_{i\g 3}t_i$.

(c) For a green region~$u$, let us define by~$x(u)$ and~$s(u)$ the number of red edges and the number of blue vertices at the boundary of~$u$, 
respectively. For a green region~$u$ let
$$
d(u) = \left\{
   \begin{array}{ll}
     0,  & \hbox{if \ \ $s(u)\geqslant 1$;} \\
     1,  & \hbox{if \ \ $s(u)=0$.}
   \end{array}
 \right.
 $$
It is easy to prove that if a green region~$u$ is bounded by~$j$ edges, then
$$
s(u)\leqslant (j-1)-x(u)+d(u).
$$

Denote by~$X$ and by~$D$ the sums of~$x(u)$ and~$d(u)$, respectively, by all the green regions. Summing up the inequality obtained above 
for all the green regions, we get
$$
s \lle \sum_{j\g 4} (j-1)p_j \  -X+D.
$$
Note that every red edge is incident to at least one green region (since $t_n=t_{n-1}=0$). A red edge is called dark red if it is 
adjacent to two green regions. Let us denote by~$x_1$ the number of dark-red edges. Then $X=x+x_1$. 
Let us distinguish the 4-hedral regions such that all their vertices are red (all the distinguished regions are green). It is easy to show 
that every distinguished region is incident to at least two dark-red enges. Hence, the number of distinguished regions is at most~$x_1$. 
It follows that $D\lle x_1+\sum_{j\g 5 }p_j$. Now merge all the inequalities.
















\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
(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$--угольника. В таком графе $e=n+C_n^4$ вершин и $v=2C_n^4+\frac {n(n-1)}2$ ребер. Откуда по формуле Эйлера число частей равно $1+v-e=1+C_n^4+\frac {n(n-3)}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 \label{ft formula} (a) Докажем, что области проективных плоскостей $\alpha_1$ и $\alpha_2$ взаимно однозначно соответствуют друг другу при центральном проектировании. Заметим, что две точки, не лежащие на прямых набора, принадлежат одной области тогда и только тогда, когда их можно соединить ломаной, не пересекающей прямые набора. При этом звено ломаной может состоять из луча, соединяющего некоторую точку с бесконечно удаленной точкой, соответствующей направлению луча. Если точки $A$ и $B$ не лежат на прямых набора и принадлежат одной области плоскости $\alpha_1$, то их
образы при центральном проектировании в силу взаимной однозначности (см. задачу \ref{proekcia}) не лежат на прямых набора образов и принадлежат одной области плоскости $\alpha_2$. Обратное тоже верно.

Для обычных плоскостей утверждение неверно. Например, для набора прямых, содержащего прообраз бесконечно удаленной прямой плоскости $\alpha_2$, число областей после центрального проектирования уменьшится.

(b)  Переведем одну из прямых набора центральным проектированием в бесконечно удаленную. Число областей и числа $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$ прямым набора, на считая бесконечно удаленной.

\pb \label{f ocenki}

(a) Индукция по $n$, база $n=m, f=m$. Добавляемая прямая имеет не менее $m$ точек пересечения с предыдущими
прямыми, т.к. на проективной плоскости любые две прямые пересекаются.

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

(c) Из задач \ref{pari} и \ref{ft formula} следует, что
$$f-1=\sum_{i\g 2}(i-1)t_i\g \sum_{i\g 2}\frac{i(i-1)}m t_i=\frac{n(n-1)}m.$$

(d) Рассмотрим граф на проективной плоскости, вершины которого --- точки пересечения прямых друг с другом,
ребра --- отрезки прямых. При этом допускается прохождение ребра через бесконечно удаленную точку, в этом случае ребро состоит из двух лучей, лежащих на одной прямой, и бесконечно удаленной точки соответствующего направления, соединяющей два луча. Число вершин $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.$$

(e) Положим $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{ft formula} и \ref{f ocenki}. Следовательно,
$$f \g 2\frac{n(n-1)}{M+3} +(1+3\frac{M-1}{M+3})= 2\frac{n(n-1)+2M}{M+3}.$$


\pb \label{l-1} При добавлении к набору бесконечно удаленной прямой число областей не меняется, число прямых $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$ будем опускать.
Предположим, что существует набор прямых, для которого число $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$ принадлежит предпоследней лакуне.


\pbz \label{l} (a) Выберем две точки $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-m)-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.$

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

(1) Если $m<L$, то по задаче \ref{f ocenki}(e) для $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}(e) для $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).$

Доказательство основной теоремы теперь следует из предыдущих задач.


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


\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) Рассмотрим окружность, чей центр не принадлежит данным прямым. Сделаем полярное преобразование относительно этой окружности, т.е. каждой точке поставим в соответствие ее поляру, а каждой поляре поставим в соответствие ее полюс. Набор из $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$ не может делится на три.

(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$ не может делится на три.

(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 \quad \text{ и} \quad t_2\g 3+t_4.$$
Отсюда при условии $t_2<6$ получаем, что $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.$

\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)



\smallskip
 {\bf Лемма.} {\it Пусть для набора $n$ прямых верно $t_n=t_{n-1}=0$. Пусть степени обоих концов некоторого ребра соответствующего графа равны четырем. Тогда из двух примыкающих к этому ребру областей хотя бы одна ограничена не менее чем четырьмя ребрами графа.}

 {\it Доказательство.} Обозначим концы этого ребра через $A$ и $B$, а прямые, проходящие через точки $A$ и $B$ и отличные от прямой $AB$, через $l_1$ и $l_2$ соответственно. Обозначим точку пересечения прямых $l_1$ и $l_2$ через $C$. Предположим, что обе примыкающие к ребру $AB$ области ограничены тремя ребрами. Одно из этих ребер --- это $AB$, а два других (для каждой области) находятся на прямых $l_1$ и $l_2$ и имеют общую точку. Точка $C$ --- это единственная общая точка прямых $l_1$ и $l_2$, поэтому каждая из двух примыкающих к ребру $AB$ областей ограничена ребром с концами в точках $A$ и $C$, ребром с концами в точках $B$ и $C$ и самим ребром $AB$. Следовательно, на прямой $l_1$ есть ровно две точки пересечения с остальными прямыми набора, и это точки $A$ и $C$. На проективной плоскости любые две различные прямые пересекаются в единственной точке, поэтому каждая прямая из набора, кроме $l_1$, проходит или через точку $A$, или через точку $C$. Степень точки $A$ равна четырем, т.е. через точку $A$ проходит, не считая $l_1$, только прямая $AB$. Тогда через точку $C$ вместе с прямой $l_1$ проходит  $n-1$ прямых, что противоречит условию $t_{n-1}=0$. Следовательно, обе примыкающие к ребру $AB$ области не могут быть ограничены тремя ребрами графа каждая. $\quad \square$




\bigskip
\end{document}


\begin{thebibliography}{}%

%
\bibitem{1}
Dirac~G.A. Collinearity properties of sets of points, {\it Quart. J. Math.} {\bf 2} (1951), 221-227.

%
\bibitem{2}
Gr$\mathrm{\ddot{u}}$nbaum B. {\it  Arrangements and Spreads.} AMS, Providence, Rhode Island, 1972.
%
\bibitem{3}
 Hirzebruch F. Singularities of algebraic surfaces and characteristic numbers. {\it Contemporary Math.} (1986) {\bf 58}, 141-155.
%
\bibitem{4}
Kelly~L.M., Moser~W.O.J. On the number of ordinary lines determined by $n$ points, {\it Canadian J. Math. }, v. 10, (1958), 210-219.
%
\bibitem{5}
 Martinov N. Classification of arrangements by the number of their cells. {\it Discrete and Comput. Geometry} (1993) {\bf 9}, №1, 39-46.
%
\bibitem{6}
 Melchior E.  $\mathrm{\ddot{U}}$ber Vielseite der Projektiven Ebene.  {\it Deutsche Mathematik} (1940) {\bf 5}, 461-475.
%
\bibitem{7}
Арнольд В.И. На сколько частей
делят плоскость $n$ прямых?
{\it Матем. просве\-ще\-ние сер. 3} (2008) {\bf 12},  95–104.
%
\bibitem{8}
 Окунев А.,  http://www.mccme.ru/mmks/mar08/Okunev.pdf
%
\bibitem{9}
Прасолов В.В., Задачи по планиметрии, М.: МЦНМО, 2001
%
\bibitem{10}
 Шнурников И.Н. На сколько областей делят плоскость $n$ прямых, среди которых не более $n-k$ коллинеарных?  {\it Вестник Моск. ун-та, сер. 1} (2010) {\bf 5}, 32-36.
\end{thebibliography}
