\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
\newtheorem{vkZad}{Задача}
\newcommand{\lle}{\leqslant}
\newcommand{\g}{\geqslant}

\newcounter{zadacha}
\setcounter{zadacha}0

\newcommand{\pb}{\par\smallskip\refstepcounter{zadacha}%
\textbf{Problem \arabic{zadacha}.} }

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

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

\begin{document}

\centerline{{\Large\bf Planar arrangements of lines}}

\bigskip
\centerline{ K. Kuyumzhiyan, E. Molchanov, I. Shnurnikov}

\bigskip
\bigskip
By an arrangement of lines we mean a finite family of $n$ distinct lines in the plane. Suppose that these $n$ lines cut the plane into~$f$ regions. The aim of the series of problems below is to determine all possible values of $f$ for a fixed $n$.
In 1993, N.~Martinov indicated all possible numbers $f$ and in 2007 V.I.~Arnold suggested a new sketch of proof that we are going to follow.

\bigskip
\bigskip
\centerline{{\bf Before intermediate finish}}

\bigskip
We always denote by $n$ ($n\geqslant 1$) and by $f$ the number of lines in an arrangement and the number of regions in the plane partition, respectively. Let us note that regions in the plane partition are polygonal or unbounded.

\medskip
 \pb \label{fminmax} For every~$n$, find the minimal and the maximal possible values of~$f$.

\pb For every~$n$, find all possible numbers $f$, if

(a) $1\leqslant n\leqslant 5$,

(b) $n =6,\  7$.

\medskip
Let us denote by $p$ the maximal number of parallel lines in an arrangement, and by~$q$ the maximal number of concurrent (i.e. passing through one point) lines in an arrangement. Let us denote by $r_i$ ($2 \lle i \lle q$) the number of points which are incident to exactly $i$ lines of an arrangement.


\medskip
\pb \label{3ocenki} Prove the following.

(a) $f\geqslant (p+1)(n-p+1),$

(b) $f\geqslant q(n-q+2),$

(c) There exist arrangements such that the bounds (a) and (b) are reached.

(d) $f=n+1+\sum_{i=2}^q(i-1)r_i.$

\pb \label{3lakuni} Prove that the number of regions $f$ cannot belong to intervals

 (a) $(n+1 ;\ 2n)\ $ for $n\geqslant 3$,

 (b) $(2n ;\ 3n-3)\ $ for $n\geqslant 5$,

 (c) $(3n-2;\ 4n-8)\ $ for $n\geqslant 8$.

\pb \label{fpqmax} Find maximal possible values of $f$ if the values

(a) $n$ and $p$,

(b) $n$ and $q$

are given.

\medskip
For $p$ and $n$, where $1\lle p \lle n$, denote by $a(n,p)$ and $b(n,p)$ the following numbers:
$$
b(n,p)=(p+1)(n-p+1)+C_{n-p}^2 \ , \qquad  a(n,p)=b(n,p)-\min\left\{p,C_{n-p}^2\right\}.
$$

%
\pb \label{primer} For any integer $p$, $1\lle p \lle n$, and any integer $f$, $a(n,p)\leqslant f \leqslant b(n,p)$, construct a configuration of $n$ lines
splitting the plane into $f$ regions and having at most~$p$ parallel lines.

\medskip
{\bf Main Theorem.} For a given $n$, the set of all possible values of~$f$ is formed by the union of integers in the intervals $[a(n,p);\ b(n,p)]$ for all $p$, where $1\lle p \lle n$.

\bigskip
In other words, all the possibilities for~$f$ appear in Problem~\ref{primer}.
However, it is not clear why the number of regions cannot be an integer from none of the intervals $[a(n,p);\ b(n,p)]$.
In fact, one of the difficulties is that for fixed~$n$ and~$p$, there exist arrangements splitting the plane into less than $a(n,p)$ regions.

\medskip
\pb Find all the pairs $(n, p)$ such that there exists a configuration of lines splitting the plane into less than $a(n,p)$ regions.

\medskip
For a given~$n$, by a {\it gap} we mean the interval $(b(n,p+1); \ a(n,p))$ if it contains at least one integer. The number of gaps for a given~$n$ is denoted by $L(n)$. We enumerate the gaps from left to right with integers from~1 to $L(n)$.

\medskip
\pb \label{chislolakun} (a) Give an explicit formula for $L(n)$ (expressing it in $n$) for $n\g 3$.

(b) How many integers does a gap number~$j$ contain, where $1 \lle j \lle L(n)$?

\pb
%\footnote {таких наборов прямых не существует, но эта задача нужна для доказательства основной теоремы.}
\label{pq v lakune}
Suppose that there exists a configuration of~$n$ lines splitting the plane into $f$ regions, where $f$ belongs to the gap number~$j$.
Prove that $p \lle j-1$ and $q\lle j$.
%Докажите, что если существует набор прямых с параметрами $n, f, p$ и $q$, такими, что число $f$ принадлежит лакуне номер $j$, то $p \lle j-1$ и $q\lle j$.

\pb \label{r ocenka par} Prove that
$$
\sum_{i=2}^q i(i-1)r_i\g n(n-p).
$$


\pb \label{sqrtn lakun} (a) Prove that $f\g n+1+\frac{n(n-p)}q$.

(b) Prove that $f$ cannot belong to the gap number $j$ if $1 \lle j \lle \sqrt{n}$.

\pb \label{r ocenka Melchiora} Prove that if $p<n$, then
%$$r_2+n \g 3+\sum_{i=4 }^q (i-3)r_i.$$
$$
r_2+n \g 3+r_4+2r_5+3r_6+\dots + (q-3)r_q.
$$


\pb \label{l-2 lakun} (a) Prove that
$$
f\g 2\frac{n(n-p)}{q+3}.
$$

(b) Prove that $f$ cannot belong to the gap number~$j$ if $1 \lle j \lle L(n)-2$.

\pb In a convex $n$--gon ($n \g 4$) all the diagonals are drawn, and suppose that no three of them are concurrent.

(a) How many intersection points of diagonals are there? (Vertices are not considered as intersection points.)

(b) Into how many parts do the diagonals
split the interior of the $n$--gon?

\pbz \label{l-1+l} Consider an arrangement of $n$ lines in the plane. Prove that the number $f$ of regions cannot belong to the two last gaps
(enumerated as~$L(n)-1$ and~$L(n)$).

\pbz Consider~$n$ points on the plane, not all of them being collinear. Take all the lines containing exactly two of these points. Let~$m$ be the number of such lines. Prove that~$C_{m+2}^2\g n$.


\newpage

\centerline{{\Large\bf Planar arrangements of lines}}

\bigskip
\centerline{ K. Kuyumzhiyan, E. Molchanov, I. Shnurnikov}

\bigskip

\centerline{{\Large\bf After intermediate finish}}

\bigskip

Consider two planes $\alpha_1$ and $\alpha_2$ in the 3-dimentional space and a point~$O$, $O\not \in \alpha_1\cup \alpha_2$. By a {\it central projection} we mean
a transformation which maps a point $X$ of the plane $\alpha_1$ to the point of intersection of the line~$OX$ with the plane~$\alpha_2$.

\medskip
\pb Consider an arrangement of lines in $\alpha_1$. Find the images of lines and of regions of the plane $\alpha_1$ after the central projection with center~$O$ to the plane~$\alpha_2$. You can suppose that the arrangement has two intersecting lines.


\medskip

We suppose that all the lines which are parallel to a given line~$l$, contain the {\it infinite point} corresponding to the direction~$l$.
The result of the central projection of the infinite point corresponding to the direction~$l$ is the intersection point of the plane~$\alpha_2$
with the line passing through~$O$ parallel to~$l$ (if~$l$ is parallel to $\alpha_2$, then the image is the infinite point of~$\alpha_2$ corresponding to the direction~$l$).

\pb \label{proekcia} Prove that central projection is a one-to-one correspondence between planes considered with their infinite points. Find the image and the preimage of infinite points of the planes~$\alpha_1$ and~$\alpha_2$ respectively.

\medskip
Let us call by the {\it projective plane} the usual plane with its infinite points, and by an {\it arrangement of lines} in a projective plane an arrangement of lines with their corresponding infinite points. Here one of the lines can be infinite. For an arrangement of~$n$ lines in the projective plane,
we denote by~$t_i$
the number of intersection points incident to exactly~$i$ lines, where $2\leqslant i \leqslant n$.

\medskip
\pb \label{pari} Prove that for~$n$ lines in the projective plane
 $$
 \sum_{i\geqslant 2}i(i-1)t_i=n(n-1).
 $$

\medskip
The notion of the projective plane helps to explain the following similarity between parallel and concurrent lines. Let us consider two arrangements of~$k+1$
lines in the usual plane: in the first one~$k$ parallel lines intersect the $(k+1)$th line, in the second there are~$k+1$ concurrent lines, see the picture.

\medskip
\begin{center}
\begin{tabular}{lcr}
\includegraphics{kartinka1.mps} & \qquad \qquad & \includegraphics{kartinka0.mps}
\end{tabular}
\end{center}



\noindent Each of these arrangements cuts the plane into~$2k+2$ regions, and this fact has the following explanation. We can add the infinite lines to
the
both arrangements. We will obtain two arrangements of~$k+2$ lines in the projective planes, and there exists a central projection mapping one
arrangement to another. Hence, they cut the plane into the same number of regions. That's why it seems more convenient to solve the problem~\ref{l-1+l} in the projective plane instead of the usual one.

\pb For an arrangement of~$n$ lines in the projective plane, define the notion of {\it region} so that any central projection gives a one-to-one correspondence between the regions of different projective planes. How can one verify whether two given points belong to one region (for a fixed arrangement)?

\
\medskip

Below, we denote the number of regions of the projective plane by~$f$, and the maximal number of concurrent lines in the arrangement by~$m$.

\medskip
\pb \label{f ocenki} %Проективная плоскость разделена $n$ прямыми на $f$ областей.
Prove the following analogues of problems~\ref{3ocenki}, \ref{r ocenka Melchiora}, and~\ref{l-2 lakun}.
%\ref{fpqmax},  \ref{sqrtn lakun},

(a)  %Докажите, что для прямых на проективной плоскости
$$
%f=1+\sum_{i\geqslant 2}(i-1)t_i.
f=1+t_2+2t_3+\ldots+(n-1)t_n,
$$


(b)
$$
m(n-m+1)\lle f \lle m(n-m+1)+C^2_{n-m}.
$$

(c) If $m<n$, then
$$
%\sum_{i\g 2}(3-i)t_i\g 3.
t_2\g 3+t_4+2t_5+3t_6+\ldots+(m-3)t_m.
$$

(d) If $m<n$, then for every integer~$M$, $M \g m$, it is true that
$$
f\g 2\left(\frac{n^2-n+2M}{M+3}\right).
$$
%f\g 1+\frac{n(n-1)}m \quad \text{и} \quad

\pbz \label{l} Let $n \g 2m+2$, and let $t_m\g 2$. Prove that $f \g (m+1)(n-m)$. Is it true for $n=2m+1$?


\pbz \label{l-1} Formulate and prove the main theorem for the arrangements of~$n$ lines in the projective plane. Complete the proof of the main theorem
for the usual plane.

\pb (a) Into how many regions can the plane be divided by~$n$ circles passing through a fixed point?

(b) For the usual sphere, let the big circles (intersections of the sphere with planes passing through the center of the sphere) play the role of lines. Into how many regions can~$n$ big circles cut the sphere?

\bigskip
The next aim is to prove the Sylvester theorem and its generalizations.

\medskip
\pb{\bf (The Sylvester theorem)} \label{Sylvester} (a) Given~$n$ non collinear points in a plane, prove that there exists a line containing exactly two of these points.

(b) Consider an arrangement of~$n$ lines such that not all the lines are parallel and not all are concurrent. Prove that there exists an intersection point incident to exactly two lines.

\medskip
It turns out that under the assumptions of problem~\ref{Sylvester}(b), there exist several points incident to exactly two lines. To estimate their number, it is more convenient to consider the arrangements of lines in the projective plane.
For a given arrangement of lines in the projective plane, let us denote by~$p_j$ the number of regions bounded by~$j$ segments of lines. Note
that a region bounded by~$j$ segments of lines is a polygon with~$j$ sides whenever it has an empty intersection with the infinite line.


\medskip
\pb \label{Melchior} Prove that if $t_n=0$, then
$$
\sum_{i\geqslant 2}(3-i)t_i+\sum_{j\geqslant 3}(3-j)p_j=3.
$$



\pb \label{t_2 for n<9} Consider an arrangement of~$n$ lines in the projective plane such that $t_n=0$. For every $n \lle 9$, determine the minimal possible value of $t_2$ in such arrangement.

\pb (a) For every even $n\g 6$, construct an arrangement of~$n$ lines with $t_2=\frac n2$.

\smallskip

(b) For every odd $n\g 7$, construct an arrangement of~$n$ lines with $t_2=3\left[\frac n4\right]$.

\pbzz
Prove that if $t_n=0$, then $t_2\geqslant \frac 3 7 n$.

%(b) $t_2\geqslant \frac 6{13} n$.

\pbzz(Dirak conjecture, 1951). If $t_n=0$, then $t_2\g [\frac n2]$.

\bigskip
The next aim is to prove inequalities involving the numbers~$t_i$ for different~$i$.


\medskip
\pbz \label{pt and t inequalities} If $t_n=t_{n-1}=t_{n-2}=0$, then
$$
t_2+\frac 32 t_3 \geqslant 8+ \sum_{i\geqslant 4}\left(2i-7\frac 12\right)t_i.
$$

\pb \label{for pt and t} Consider~$n$ points in the projective plane. Let us mark with red color the intersection
points which are incident to exactly two lines, and with blue color the intersection points which are incident to
at least three lines. If the endpoints of a line segment are of one color, we mark this segment with the same
color (if its interior does not contain other colored points). We denote by~$x$ and~$y$ the numbers of red and
blue segments, respectively. Let us mark with green color the regions bounded by at least four segments of the
given lines and containing at least one red point on its boundary. We denote by~$z$ the number of pairs (a green
region, a blue point on its boundary). Prove that

(a)
$$
x-y=2t_2-\sum_{i\geqslant 3}it_i.
$$

(b) If the arrangement is not the union of two groups of concurrent lines, then
$$
y+z\g \frac 32 \sum_{i\geqslant 3}t_i.
$$


(c) If $t_n=t_{n-1}=t_{n-2}=0$, then
$$
x+z\lle 3p_4+\sum_{j\g 5} jp_j.
$$

\pbz
Find new inequalities involving numbers~$t_i$ and~$p_j$ (which do not follow trivially from problems~\ref{Melchior} and~\ref{pt and t inequalities}, but, possibly, use problem~\ref{for pt and t}).



\end{document}
