\documentclass[12pt,a4paper]{article}

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


\usepackage[T2A]{fontenc}
\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{Задача \arabic{zadacha}.} }

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

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

\begin{document}

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

\bigskip

\bigskip

\centerline{ К. Куюмжиян, Е. Молчанов, И. Шнурников}

\bigskip

\bigskip

Пусть набор из~$n$ различных прямых делит плоскость на~$f$ частей. Цель следующей серии задач~--- найти все возможные числа $f$ частей плоскости для фиксированного числа прямых~$n$. В 1993 г. Н. Мартинов нашел все такие числа, а в 2007 г. В.И.~Арнольд предложил новую схему доказательства, которой мы будем следовать.


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

\bigskip
Число прямых в наборе всегда будет обозначаться через $n$ ($n\geqslant 1$), а число частей (много\-угольных или неограниченных областей) плоскости, разделённой этим набором,  через~$f$.

\medskip
 \pb \label{fminmax} Для произвольного $n$ найдите минимальное и максимальное возможные значения $f$.

\pb Для каждого отдельного значения $n$ найдите все возможные числа $f$, где

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

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

\medskip
Максимальное число параллельных прямых в наборе обозначим через $p$. Максимальное число проходящих через одну точку прямых в наборе обозначим через $q$. Число точек пересечения, каждая из которых принадлежит $i$ прямым набора, обозначим через $r_i$, где $2\leqslant i \leqslant q.$


\medskip
\pb \label{3ocenki} Докажите, что

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

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

(c) оценки пунктов (a) и (b) реализуются,

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

\pb \label{3lakuni} Докажите, что число областей $f$ не может принадлежать интервалам

 (a) $(n+1 ;\ 2n)\ $ для $n\geqslant 3$,

 (b) $(2n ;\ 3n-3)\ $ для $n\geqslant 5$,

 (c) $(3n-2;\ 4n-8)\ $ для $n\geqslant 8$.

\pb \label{fpqmax} Найдите максимальные возможные значения $f$ для фиксированных чисел

(a) $n$ и $p$,

(b) $n$ и $q$.

\medskip
Для фиксированных $n$ и $p$, $1\lle p \lle n$, обозначим через $a(n,p)$ и $b(n,p)$ следующие числа:
$$
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} Для любого целого числа $p$, $1\lle p \lle n$, и любого целого числа $f$, где $a(n,p)\leqslant f \leqslant b(n,p)$, приведите пример набора из $n$ прямых, делящего плоскость на $f$ областей и имеющего максимум $p$ параллельных прямых.

\medskip
{\bf Основная теорема.} Для фиксированного $n$ множество всех возможных чисел~$f$ есть объединение натуральных чисел отрезков $[a(n,p);\ b(n,p)]$ по всем $p$, где $1\lle p \lle n.$

\bigskip
Другими словами, все возможные числа областей $f$ реализуются примерами задачи~\ref{primer}. Однако пока не очевидно, почему числа, не попадающие в отрезки $[a(n,p);\ b(n,p)]$, не могут быть числами областей. Дело в том, что для фиксированных чисел~$n$ и~$p$ соответствующие наборы могут делить плоскость менее чем на $a(n,p)$ частей.

\medskip
\pb Найдите все пары чисел $n$ и $p$, для которых существует набор из~$n$ прямых, делящий плоскость на менее чем $a(n,p)$ частей.

\medskip
Для данного $n$ {\it лакуной} назовём интервал $(b(n,p+1); \ a(n,p))$, содержащий не менее одного целого числа. Число лакун для данного $n$ обозначим через $L(n).$  Занумеруем лакуны числами от 1 до $L(n)$ по убыванию $p$ (т.е. слева направо).

\medskip
\pb \label{chislolakun} (a) Выразите число лакун $L(n)$ явной формулой через $n$ для $n\g 3$.

(b) Сколько целых чисел содержит лакуна номер $j$ для
$1 \lle j \lle L(n)$?

\pb
%\footnote {таких наборов прямых не существует, но эта задача нужна для доказательства основной теоремы.}
\label{pq v lakune}
Предположим, что существуют $n$ прямых, делящих плоскость на $f$ частей, где число $f$ принадлежит лакуне номер $j$. Докажите, что $p \lle j-1$ и $q\lle j$.
%Докажите, что если существует набор прямых с параметрами $n, f, p$ и $q$, такими, что число $f$ принадлежит лакуне номер $j$, то $p \lle j-1$ и $q\lle j$.

\pb \label{r ocenka par} Докажите, что
$$\sum_{i=2}^q i(i-1)r_i\g n(n-p).$$


\pb \label{sqrtn lakun} (a) Докажите, что $f\g n+1+\frac{n(n-p)}q.$

(b) Докажите, что число $f$ не может принадлежать лакуне номер $j$ для $1 \lle j \lle \sqrt{n}$.

\pb \label{r ocenka Melchiora} Докажите, что если $p<n$, то
%$$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) Докажите, что $$f\g 2\frac{n(n-p)}{q+3}.$$

(b) Докажите, что число $f$ не может принадлежать лакуне номер $j$ для $1 \lle j \lle L(n)-2$.

\pb В выпуклом $n$--угольнике ($n \g 4$) проведены все диагонали, причём никакие три из них не пересекаются в одной точке.

(a) Сколько получилось точек пересечения диагоналей? (Вершины не считаются точками пересечения диагоналей.)

(b) На сколько частей диагонали разбивают внутренность $n$--угольника?

\pbz \label{l-1+l} Докажите, что число $f$ областей плоскости, разделённой $n$ прямыми, не может принадлежать последним двум лакунам (номер $L(n)-1$ и $L(n)$).

\pbz На плоскости даны $n$ точек, не лежащие на одной прямой. Рассмотрим прямые, проходящие ровно через две из данных точек, и обозначим число таких прямых через $m$. Докажите, что $C_{m+2}^2\g n.$

%\end{document}

\newpage
\centerline{{\Large\bf Наборы прямых на плоскости}}

\bigskip

\centerline{ К. Куюмжиян, Е. Молчанов, И. Шнурников}

\bigskip

\centerline{{\Large\bf Задачи после промежуточного финиша}}

\bigskip

Рассмотрим плоскости $\alpha_1$ и $\alpha_2$ в трёхмерном пространстве и точку $O$, не лежащую ни на одной из них. {\it Центральным проектированием} называется преобразование, при котором точке $X$ плоскости $\alpha_1$ ставится в соответствие точка пересечения прямой $OX$ с плоскостью~$\alpha_2$.

\medskip
\pb Пусть на плоскости $\alpha_1$ дан набор прямых. Найдите образы прямых и областей плоскости $\alpha_1$ при центральном проектировании на плоскость $\alpha_2$ относительно точки $O$. Можно считать, что в наборе есть две пересекающиеся прямые.


\medskip
 Будем считать, что прямые, параллельные данной прямой $l$, проходят через {\it бесконечно удалённую точку}, соответствующую направлению $l$. Центральное проектирование бесконечно удалённой точки, соответствующей направлению $l$, есть точка  пересечения плоскости $\alpha_2$ с прямой, проходящей через точку $O$ параллельно $l$ (если $l$ параллельна $\alpha_2$, то образом будет бесконечно удалённая точка плоскости $\alpha_2$, соответствующая направлению $l$).

\pb \label{proekcia} Докажите, что центральное проектирование есть взаимно однозначное отображение плоскостей вместе с их бесконечно удалёнными точками. Найдите образ и прообраз бесконечно удалённых точек плоскостей $\alpha_1$ и $\alpha_2$, соответственно.

\medskip
Назовём {\it проективной плоскостью} плоскость вместе с её бесконечно удалёнными точками, а {\it набором прямых} на проективной плоскости --- набор прямых вместе с соответствующими им бесконечно удалёнными точками. При этом одна из прямых набора может быть бесконечно удалённой. Для набора $n$ прямых на проективной плоскости обозначим через $t_i$ число точек проективной плоскости, принадлежащих~$i$ прямым, где $2\leqslant i \leqslant n$.

\medskip
\pb \label{pari} Докажите, что для $n$ прямых на проективной плоскости
 $$
 \sum_{i\geqslant 2}i(i-1)t_i=n(n-1).
 $$

\medskip
Заметим, что проективная плоскость позволяет объяснить следующее сходство между параллельными прямыми и прямыми, проходящими через одну точку. Возьмём два набора из $k+1$ прямых на плоскости: первый состоит из $k$ параллельных прямых и одной секущей, а второй из $k+1$ проходящих через одну точку прямых:

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



\noindent Оба набора делят плоскость на $2k+2$ области, и это не случайное совпадение. Если к обоим наборам добавить бесконечно удалённую прямую, то получатся наборы из $k+2$ прямых, которые переводятся друг в друга центральным проектированием и поэтому имеют одинаковое число областей. В этой связи можно ожидать, что решить задачу \ref{l-1+l} будет проще на проективной плоскости.

\pb Дано~$n$ прямых на проективной плоскости. Определите области проективной плоскости так, чтобы при центральном проектировании
области переходили в области взаимно однозначно. Как по двум данным точкам и набору прямых узнать, принадлежат ли точки одной области?


\medskip
В дальнейшем число областей проективной плоскости будем обозначать через~$f$, а максимальное число прямых набора, проходящих через одну точку, через~$m$.

\medskip
\pb \label{f ocenki} %Проективная плоскость разделена $n$ прямыми на $f$ областей.
 Докажите следующие аналоги задач~\ref{3ocenki}, \ref{r ocenka Melchiora} и~\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) Если $m<n$, то
$$
%\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) Если $m<n$, то для любого целого числа $M, \ M \g m$, верно
$$
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}  Пусть $n \g 2m+2$ и $t_m\g 2$. Докажите, что $f \g (m+1)(n-m)$. Верно ли это для $n=2m+1$?


\pbz \label{l-1} Сформулируйте и  докажите основную теорему для наборов $n$ прямых на проективной плоскости. Завершите доказательство основной теоремы для обычной плоскости.

\pb (a) На сколько областей могут разделить плоскость $n$ окружностей, проходящих через одну точку?

(b) Рассмотрим на сфере окружности, получаемые как сечения сферы плоскостями, проходящими через её центр. На сколько частей могут разделить сферу $n$ таких окружностей?

\bigskip
Дальнейшая цель~--- доказать теорему Сильвестра и её обобщения.

\medskip
\pb{\bf (Теорема Сильвестра)} \label{Sylvester} (a) На плоскости даны $n$ точек, не лежащих на одной прямой. Докажите, что найдётся прямая, на которой лежат только две данные точки.

(b) На плоскости проведены $n$ прямых, причём не все они параллельны и не все пересекаются в одной точке. Докажите, что найдётся точка, принадлежащая ровно двум прямым.

\medskip
Оказывается, что в условиях задачи \ref{Sylvester}(b) найдётся несколько таких точек. Чтобы оценить их число, удобнее рассматривать наборы прямых на проективной плоскости. Обозначим через $p_j$ число $j$-угольных областей проективной плоскости, образован\-ных этим набором прямых.

\medskip
\pb \label{Melchior} Докажите, что если $t_n=0$, то
$$
\sum_{i\geqslant 2}(3-i)t_i+\sum_{j\geqslant 3}(3-j)p_j=3.
$$



\pb \label{t_2 for n<9} Дан набор $n$ прямых на проективной плоскости такой, что $t_n=0.$ Найдите минимальные возможные значения $t_2$ отдельно для каждого $n \lle 9$.

\pb (a) Приведите примеры наборов~$n$ прямых с $t_2=\frac n2$ для чётных $n\g 6$.

\smallskip

(b) Приведите примеры наборов $n$ прямых с $t_2=3\left[\frac n4\right]$ для нечётных $n\g 7$.

\pbzz
Докажите, что если $t_n=0$, то $t_2\geqslant \frac 3 7 n$.


\pbzz(Гипотеза Дирака 1951-го года). Если $t_n=0$, то $t_2\g [\frac n2]$.

\bigskip
Очередная цель  --- доказать ряд неравенств, в которых участвуют сразу несколько чисел~$t_i$.


\medskip
\pbz \label{pt and t inequalities} Если $t_n=t_{n-1}=t_{n-2}=0,$ то
$$
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} Дано $n$ прямых на проективной плоскости. Отметим красным цветом точки пересечения, принадлежащие ровно двум прямым.
 Синим цветом отметим точки пересечения, принадлежащие не менее чем трём прямым.
 Отрезки прямых с одноцветными концами, не содержащие внутри себя цветных точек, покрасим в цвет своих концов.
 Обозначим через $x$ и $y$ числа красных и синих отрезков соответственно.
  Покрасим зелёным цветом области, ограниченные не менее чем четырьмя отрезками данных прямых и содержащие на своей границе хотя бы одну красную точку.
  Число пар, состоящих из зелёной области и лежащей на её границе синей точки, обозначим через $z.$ Докажите, что

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

(b) Если не существует таких двух точек, что любая данная прямая проходит хотя бы через одну из них, то
$$
y+z\g \frac 32 \sum_{i\geqslant 3}t_i.
$$


(c) Если $t_n=t_{n-1}=t_{n-2}=0$, то
$$
x+z\lle 3p_4+\sum_{j\g 5} jp_j.
$$

\pbz
Найдите новые соотношения между $t_i$ и $p_j$ (не выводящиеся тривиально из задач \ref{Melchior} и \ref{pt and t inequalities}, но, возможно, использующие задачу \ref{for pt and t}).





\end{document}
