%\input pfedya.sty

\documentclass[10pt]{article}
%\font \a=lhr10
%
% Три следующие пакетика -- это способ русификации Latex2e.
% Возможно, у Вас это не так
%
%\usepackage[T1,T2A]{fontenc}
%\usepackage[cp866]{inputenc}
%\usepackage[russian]{babel}
\usepackage{amsthm,amsmath,amsfonts,amssymb}

\textwidth=17.3cm \textheight=24cm
\advance\voffset-15mm
\hoffset=-2.9cm

\newcommand\kratno{\mathrel{\smash{\lower.5ex\hbox{$\vdots$}}}}

\newtheorem{definition}{Определение}[subsection]
\newtheorem*{lemma}{Лемма}
\theoremstyle{plain}
\newtheorem*{theorem}{Теорема}
\renewcommand{\proofname}{Доказательство}
\renewcommand{\refname}{Литература}
\renewcommand{\figurename}{Рис.\ }
%          %чтобы слово "references" печаталось по-русски (для класса article)
\let\le\leqslant
\let\leq\leqslant
\let\ge\geqslant
\let\geq\geqslant
\def\const{\mbox{const}\,}
\def\conv{\mbox{conv}\,}

\newcounter{problem}[subsection]
\newcounter{solution}[subsection]
\renewcommand{\thesection}{}
\renewcommand{\thesubsection}{\arabic{subsection}}
\renewcommand{\thesubsubsection}{\arabic{subsection}-\arabic{subsubsection}}
\renewcommand{\theproblem}{\thesubsection.\arabic{problem}}
\renewcommand{\thesolution}{\thesubsection.\arabic{solution}}
\newenvironment{problem}{\refstepcounter{problem}\smallskip\noindent%
{\bf\arabic{subsection}.\arabic{problem}}}{}
\newenvironment{solution}{\refstepcounter{solution}\medskip\noindent%
{\bf\arabic{subsection}.\arabic{solution}.}}{}

\hyphenation{че-ты-рех-уголь-ник}

\title{Выпуклые многоугольники}
\author{С.~Берлов, К.~Кохась}
%\date{{\small Версия 0.07}}
\begin{document}
\maketitle

\section{Условия задач}

%Эта подборка задач составлена, в основном, по материалам обзора
%\cite{MorrisSoltan}. Рисунки 1--4 взяты из электронного варианта этой статьи на
%сервере AMS.

Будем говорить, что точки плоскости находятся \emph{в общем положении}, если
никакие три из них лежат на одной прямой; \emph{в выпуклом положении},
если они образуют вершины выпуклого многоугольника.

\subsection{Одиночный выпуклый многоугольник}

\begin{problem}
\label{even-odd}
Пусть $X$~--- произвольное конечное множество точек общего положения
на плоскости. Треугольник $ABC$, где $A$, $B$, $C\in X$, назовем
\emph{четным}, если внутри него содержится четное число точек
множества~$X$, и \emph{нечетным}~--- если нечетное.
Пусть $A_1$, $A_2$, \dots, $A_n$~--- произвольные точки из множества $X$.
Докажите, что если все треугольники с вершинами в этих точках имеют одну и
ту же четность, то точки $A_1$, $A_2$, \dots, $A_n$ находятся в
выпуклом положении.
\end{problem}

\begin{problem}
\label{orientation}
Пусть $A_1$, $A_2$, $A_3$, \dots~--- произвольное конечное множество точек
общего положения на плоскости. Треугольник $A_iA_jA_k$, $i<j<k$, назовем
\emph{правильно ориентированным}, если его вершины перечисляются
по часовой стрелке именно в таком порядке, в противном случае назовем его
\emph{неправильно ориентированным}.
Докажите, что для каждого натурального $n$ точки $A_{i_1}$,
$A_{i_2}$, \dots, $A_{i_n}$ находятся в выпуклом положении,
если все треугольники
$A_{i_p}A_{i_q}A_{i_r}$, $i_p< i_q < i_r$, ориентированы одинаково.
\end{problem}

Пусть $N(n)$~--- наименьшее натуральное число, такое что в любом
множестве точек плоскости общего положения, содержащем не менее $N(n)$
точек, обязательно найдется $n$ точек, лежащих в вершинах выпуклого
$n$-угольника. Задача о нахождении числа $N(n)$ или хотя бы получении
каких-либо реалистичных оценок этого числа известна как
\emph{проблема Эрдеша-Секереша}.

\begin{problem}
\label{N(4)=5}
Докажите, что $N(3)=3$, $N(4)=5$.
\end{problem}

\begin{problem}
Докажите, что если на плоскости отмечено 2000 точек общего
положения, то

а) можно образовать не менее 400 непересекающихся выпуклых
четырехугольников с вершинами в этих точках;

б) можно образовать не менее 444 непересекающихся выпуклых
четырехугольников;

в) всегда ли можно вырезать 500 непересекающихся выпуклых
четырехугольников?

г)Кто больше?
\end{problem}

\begin{problem}
Докажите, опираясь на задачи \ref{even-odd}, \ref{orientation},
что число $N(n)$ существует для каждого $n>2$.
\end{problem}

\begin{problem}
Докажите, что $N(5)>8$. На самом деле, $N(5)=9$, но, кажется,
доказательство этого факта слишком рутинно.
\end{problem}

\begin{problem}
а) Докажите, что величина $N(n)$ имеет экспоненциальный рост,
т.\,е.\ существует такое $\alpha\in\mathbb{R}$, что при всех $n$ \ \
$N(n)>\alpha^n$.

б) Докажите, что $N(n)\ge 2^{n-2}+1$.
\end{problem}

\begin{problem}
Открытая проблема.
В силу предыдущей задачи, $N(6)\ge 17$. Верно ли, что $N(6)=17$?
\end{problem}


\begin{problem}
%(\cite{mmo}, задача 67)
В плоскости даны $n>4$ точек, причем никакие три не лежат на одной прямой.
Покажите, что можно найти не менее $n(n-1)(n-2)(n-3)/120$ выпуклых
четырехугольников с вершинами в четырех данных точках.
\end{problem}



\subsection{Пустые выпуклые многоугольники}

Пусть $H(n)$~--- наименьшее натуральное число, такое что в любом
множестве точек плоскости общего положения, содержащем не менее $H(n)$
точек, обязательно найдется $n$ точек, лежащих в вершинах выпуклого
$n$-угольника, не содержащего других точек этого множества.

\begin{problem}
а) Докажите, что $H(3)=3$.

б) %(\cite{mmo}, задача 99)
В плоскости дано $n>3$ точек, причем никакие три точки не лежат на одной
прямой. Всегда ли существует ли окружность, проходящая по крайней мере
через три данные точки и не содержащая внутри себя ни одной из остальных точек?
\end{problem}

\begin{problem}
Чему равно $H(4)$?
\end{problem}

\begin{problem}
\label{problemH(5)}
Докажите, что $H(5)\ge 10$. Кстати, на самом деле  $H(5)=10$.
\end{problem}

\begin{problem}
Докажите, что при $n\ge 7$ \ $H(n)$ не существует.
\end{problem}

\begin{problem}
а) Докажите, что $H(6)\ge 20$, если существует.

б) Открытая проблема. Существует ли $H(6)$?
\end{problem}


\subsection{Другие обобщения}

\subsubsection{Другие размерности}

\begin{problem}
Докажите, что для любого $n$ в любом достаточно большом множестве точек
общего положения в ${\mathbb R}^d$ обязательно найдется $n$ точек
в выпуклом положении.
\end{problem}

\smallskip
Наименьшее число точек, для которого верно утверждение предыдущей задачи
обозначим $N_d(n)$.

\begin{problem}
Открытая проблема. Верно ли, что величина $N_3(n)$ имеет экспоненциальный
рост?
\end{problem}

\subsubsection{Овалы вместо точек}
\emph{Овалом} будем называть выпуклое ограниченное замкнутое множество в
плоскости. Мы будем рассматривать семейства попарно непересекающихся
овалов. Будем говорить, что три овала не коллинеарны, если ни один из
них не лежит целиком в выпуклой оболочке двух других, и, более общо, будем
говорить, что $n$ овалов находятся \emph{в выпуклом положении},
если ни один из них не лежит в выпуклой оболочке остальных.
Будем говорить, что набор овалов определяет (выпуклый)
$k$-угольник, если какие-то $k$ из этих овалов находятся в выпуклом
положении (будем называть эти овалы вершинами),
а остальные овалы лежат в выпуклой оболочке этих $k$ овалов.

\begin{problem}
\label{lem:ovaly}
а) Докажите, что для любых пяти овалов, никакие три из которых не коллинеарны,
какие-то четыре находятся в выпуклом положении.

б) Пусть $m\ge3$. Если в семействе овалов $\Phi$ любые $k\ge m$
овалов определяют всего лишь ровно $m$-угольник, то $\Phi$
состоит из не более чем $m+1$ овалов.
\end{problem}

\smallskip
Обозначим $G(n)$~--- наименьшее натуральное число, такое что в любом
множестве овалов, никакие три из которых не коллинеарны, содержащем
не менее $G(n)$ овалов, обязательно найдется $n$ овалов, находящихся в
выпуклом положении. Очевидно, $G(n)\ge N(n)$. В предыдущей задаче
утверждается, что $G(4)=N(4)=5$. Можно показать, что $G(5)=N(5)=9$.
Неизвестно, верно ли, что $G(n)=N(n)$ при $n\ge 4$.

\begin{problem}
Докажите, что при всех $n$ величина $G(n)$ конечна.
\end{problem}


\subsubsection{Абстрактная выпуклость}

Прямоугольный параллелепипед в ${\mathbb R}^3$ с ребрами,
параллельными координатным осям, будем называть \emph{стандартным}.
Пересечение двух стандартных параллелепипедов, если оно не пусто,~---
также стандартный параллелепипед.
Этим множество параллепипедов сходно с семейством всех выпуклых множеств.
Возникающая выпуклая структура сильно отличается от привычной.
Так, следующая задача утверждает, что выпуклый
по отношению к этой структуре многогранник не может иметь слишком много
вершин.

Рассмотрим три точки $x$, $y$, $z\in{\mathbb R}^3$. Будем говорить, что $x$
лежит между $y$ и~$z$, если $x$ содержится в любом стандартном
параллелепипеде, содержащем $y$ и~$z$.

\begin{problem}
а) Докажите, что среди любых 17 точек в ${\mathbb R}^3$ хотя бы одна лежит
между двумя другими.

б) Докажите, что среди любых $2^{2^{d-1}}+1$ точек в ${\mathbb R}^d$ хотя бы
одна лежит между двумя другими. Для $2^{2^{d-1}}$ точек это утверждение
неверно.
\end{problem}

\smallskip
Не можем не отметить следующую идейно близкую знаменитую теорему Эрдеша.

\begin{problem}
\label{Erdos-monoton}
Во всякой последовательности из $pq+1$ различных вещественных чисел
можно найти возрастающую подпоследовательность из $p+1$ членов
или убывающую подпоследовательность из $q+1$ членов.
\end{problem}


\newpage
\subsection{ПОСЛЕ ПРОМЕЖУТОЧНОГО ФИНИША}

\begin{problem}
На плоскости отмечено бесконечно много точек, никакие три из которых
не лежат на одной прямой. Докажите, что найдется выпуклый ``счетноугольник''
с вершинами в отмеченных точках, то есть такое счетное множество точек,
быть может, неограниченное,
в котором при всех $k$ любые $k$ точек находятся в выпуклом положении.
\end{problem}



\subsubsection{Чашки и крышки (cups and caps)}
\label{sec:cupscaps}

Будем говорить, что точки $(x_1,y_1)$, $(x_2,y_2)$, \dots, $(x_m,y_m)$
образуют $m$-крышку, если
$$
\frac{y_1-y_2}{x_1-x_2}> \frac{y_2-y_3}{x_2-x_3}>\dots>
\frac{y_{m-1}-y_m}{x_{m-1}-x_m}
$$
(в частности, при этом $x_j\ne x_j$). Аналогично, точки образуют $m$-чашку,
если
$$
\frac{y_1-y_2}{x_1-x_2}< \frac{y_2-y_3}{x_2-x_3}<\dots<
\frac{y_{m-1}-y_m}{x_{m-1}-x_m}\,.
$$
%На рисунке изображены ...

\begin{figure}[cb]
\begin{center}
\begin{picture}(430,70)(40,10)
\put(80,60){\circle*{5}}\put(120,30){\circle*{5}}\put(160,60){\circle*{5}}
\put(80,60){\line(4,-3){40}}\put(120,30){\line(4,3){40}}
\put(230,30){\circle*{5}}\put(270,60){\circle*{5}}
\put(310,60){\circle*{5}}\put(350,30){\circle*{5}}
\put(230,30){\line(4,3){40}}\put(270,60){\line(1,0){40}}
\put(310,60){\line(4,-3){40}}
\end{picture}
\end{center}
\caption{Пример 3-чашки и 4-крышки.}
\end{figure}

Пусть $f(k,\ell)$~--- наименьшее натуральное число, для которого множество
$X$ общего положения, в котором $x$-координаты всех точек различны,
обязательно содержит $k$-чашку или $\ell$-крышку, если только в нем не менее
$f(k,\ell)$ элементов.

\begin{problem}
\label{probl:k_cups,l_caps-nerav}
Докажите, что $f(k,\ell)\le C_{k+\ell-4}^{k-2} + 1$.
\end{problem}

\begin{problem}
\label{probl:k_cups,l_caps}
Докажите, что $f(k,\ell)= C_{k+\ell-4}^{k-2} + 1$.
\end{problem}

\begin{problem}
Докажите, что $N(n)\le C_{2n-4}^{n-2} + 1$.
\end{problem}

\begin{problem}
Докажите, что $N(n)\le C_{2n-5}^{n-3} + 2$.
\end{problem}

\subsubsection{Коэффициент неразбиваемости}

\begin{problem}
%Шортлист-96
Существуют ли на плоскости два непересекающихся бесконечных
множества $A$ и $B$ такие, что выполняются два условия:

($i$) Никакие три точки $M:=A\cup B$ не лежат на одной прямой, а
расстояние между любыми двумя точками $M$ не меньше 1.

($ii$) Любой треугольник с вершинами из $A$ содержит точку из
$B$, а любой треугольник с вершинами из $B$ содержит точку из
$A$?
\end{problem}


\begin{problem}
Для каждого натурального числа $n$ найдем максимально возможное
число $k$, обладающее следующим свойством: {\it для любого
множества из $n$ точек общего положения найдется такая раскраска
этих точек в красный и синий цвет, что после удаления любых $k$
точек выпуклые оболочки оставшихся красных и оставшихся синих
точек пересекаются.\/} Докажите, что отношение $k/n$ может быть
сколь угодно близко к $1/2$, если $n$ достаточно велико.
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%ЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦЦ
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{Решения}

\subsection{Одиночный выпуклый многоугольник}

\begin{solution}
%even-odd
Допустим, что это не так, тогда одна из точек является выпуклой
комбинацией трех других, пусть, скажем, $A_1\in\triangle A_2A_3A_4$.
Четность треугольника $XYZ$ будем будем считать остатком по модулю~2
и обозначать ${\cal O}(XYZ)$. Тогда
$$
{\cal O}(A_2A_3A_4) = {\cal O}(A_1A_3A_4)+{\cal O}(A_2A_1A_4)+
{\cal O}(A_2A_3A_1)+1\,,
$$
где последнее слагаемое соответствует точке $A_1$, которая лежит внутри
треугольника $A_2A_3A_4$ и дает вклад в его четность,
но не лежит ни в одном из остальных трех треугольников.
Полученное равенство невозможно, если все четыре четности равны.
Таким образом, наше предположение неверно, и точки лежат в вершинах
выпуклого многоугольника.
\end{solution}

\begin{solution}
%orientation
Допустим, что это не так, тогда одна из точек является выпуклой
комбинацией трех других, пусть, скажем,
$A_{i_1}\in\triangle A_{i_2}A_{i_3}A_{i_4}$.
Не умаляя общности, можно считать, что треугольник $A_{i_2}A_{i_3}A_{i_4}$
ориентирован положительно и $i_2<i_3<i_4$.
Нетрудно проверить, что какой бы ни была величина числа $i_1$ по отношению
к числам $i_2$, $i_3$, $i_4$, все треугольники не могут быть ориентированы
одинаково. Например, если $i_2<i_1<i_3$, то треугольники
$A_{i_2}A_{i_1}A_{i_3}$ и $A_{i_2}A_{i_1}A_{i_4}$ ориентированы
по-разному. Аналогично разбираются другие случаи.
\end{solution}

\begin{solution}
См.\ рис.~\ref{5points}.

\begin{figure}[cb]
\begin{center}
\unitlength=.88\unitlength
\begin{picture}(430,100)(10,10)
\put (40,30){\circle*{5}}  \put (20,70){\circle*{5}}
\put (60,100){\circle*{5}} \put (80,30){\circle*{5}}
\put (100,70){\circle*{5}}
\thicklines
\put (20,70){\line(1,-2){20}} \put (20,70){\line(1,0){80}}
\put (40,30){\line(1,0){40}}  \put (80,30){\line(1,2){20}}
\thinlines
\put (20,70){\line(4,3){40}}  \put (60,100){\line(4,-3){40}}
\put (175,30){\circle*{5}}    \put (175,100){\circle*{5}}
\put (255,30){\circle*{5}}    \put (255,100){\circle*{5}}
\put (215,90){\circle*{5}}
\thicklines
\put (175,30){\line(1,0){80}} \put (175,30){\line(0,1){70}}
\put (175,100){\line(1,0){80}}\put (255,30){\line(0,1){70}}
\thinlines
\put (175,100){\line(4,-1){40}}\put (215,90){\line(2,-3){40}}
\put (330,30){\circle*{5}}     \put (410,30){\circle*{5}}
\put (370,90){\circle*{5}}     \put (360,50){\circle*{5}}
\put (380,50){\circle*{5}}
\thicklines
\put (330,30){\line(1,0){80}}  \put (330,30){\line(3,2){30}}
\put (360,50){\line(1,0){20}}  \put (380,50){\line(3,-2){30}}
\thinlines
\put (330,30){\line(2,3){40}}  \put (370,90){\line(2,-3){40}}
\end{picture}
\caption{Любые пять точек общего положения определяют выпуклый четырехугольник}
%{Any five points in general position determine a convex quadrilateral.}
\label{5points}
\end{center}
\end{figure}
\end{solution}

\begin{solution}
%400 четырехугольников
а) Выберем прямую, не параллельную никакой прямой, проходящей
через две отмеченные точки. Проведем 401 прямую параллельно
выбранной так, чтобы в каждой из 400 полос между соседними
прямыми оказалось ровно по пять точек нашего множества. По
утверждению задачи~\ref{N(4)=5} в каждой полосе мы сумеем найти
выпуклый четырехугольник.

\smallskip
б) Произвольное множество точек общего положения, для которого
можно найти прямую, отделяющую от него четыре точки в выпуклом
положении, будем называть \emph{разбиваемым}, в противном
случае, будем называть множество \emph{неразбиваемым}. Для
доказательства утверждения задачи достаточно проверить, что
любое множество из девяти точек общего положения является
разбиваемым.

Пусть $A$, $B$, $C$~--- точки из данного множества. Угол $\angle
ABC$ назовем пустым, если внутри него нет точек нашего
множества. Имеет место следующая лемма.

\begin{lemma}
Для каждой стороны $AB$ выпуклой оболочки неразбиваемого
множества найдется такая точка $C$ из этого же множества, для
которой оба угла $\angle ABC$ и $\angle BAC$ пустые.
\end{lemma}

Точку $C$, описанную в формулировке леммы, будем называть
\emph{ближайшей} точкой к стороне $AB$.

\begin{figure}
\hbox{}\hskip5cm\special{em:graph ris1.bmp}
\vskip 4cm
\caption{Построение ближайшей точки}
\label{ris1}
\end{figure}

\begin{proof}
Пусть при движении от $A$ к $B$ наше неразбиваемое множество
находится слева. Возьмем луч $AB$ и будем поворачивать его
против часовой стрелки вокруг точки $A$ до тех пор, пока он не
наткнется на какую-нибудь точку нашего множества~--- назовем
ее~$D$. Аналогично будем поворачивать луч $BA$ по часовой
стрелке вокруг точки $B$ до тех пор, пока он не наткнется на
какую-нибудь точку нашего множества~--- назовем ее~$C$. Если
точки $C$ и $D$ совпадают, то они то и суть искомая ближайшая
точка. В противном случае, если внутри треугольника $CDE$
(см.~рис.~\ref{ris1}) нет других точек нашего множества, то
выпуклый четырехугольник $ABDC$ легко может быть отделен от
него, что противоречит неразбиваемости; если же внутри
треугольника $CDE$ есть другие точки нашего множества мы все
равно сможем отделить от него выпуклый четырехугольник. Это
можно сделать следующим способом. Будем поворачивать луч $CB$
против часовой стрелки вокруг точки $C$ до тех пор, пока он не
наткнется на какую-нибудь точку нашего множества, пусть это
будет точка~$F$. Сдвинув немного прямую $CF$, мы получим прямую,
отделяющую от нашего множества выпуклый четырехугольник $ABFC$.
\end{proof}

Очевидно, что одна и та же точка не может быть ближайшей к
разным сторонам.

Вернемся к доказательству того, что любое множество из девяти
точек общего положения разбиваемо. В~силу свойства разбиваемых
множеств, описанного в лемме, выпуклая оболочка неразбиваемого
множества из девяти точек может быть лишь треугольником или
четырехугольником. Разберем эти случаи.

Пусть выпуклая оболочка нашего девятиточечного множества~--- это
четырехугольник $ABCD$; $K$,~$L$, $M$, $N$~--- точки, ближайшие
к его сторонам; $O$~--- точка пересечения диагоналей
(см.~рис.~\ref{ris2}). Не умаляя общности, можно считать, что
девятая точка~$Z$ нашего множества находится внутри треугольника
$AOB$. Тогда один из четырехугольников $ANZK$, $BKZL$ выпуклый и
может быть отделен от нашего множества. Это противоречит
неразбиваемости.

\begin{figure}
\hbox{}\hskip5cm\special{em:graph ris2.bmp}
\vskip 4cm
\caption{Выпуклая оболочка --- четырехугольник}
\label{ris2}
\end{figure}

Пусть теперь выпуклая оболочка нашего девятиточечного
множества~--- треугольник $ABC$; $K$, $L$, $M$~--- точки
ближайшие к его сторонам. Остальные три точки расположны по
одной в треугольниках $AKM$, $BKL$, $CLM$. Действительно, если,
скажем, в треугольнике $AKM$ нет ни одной точки нашего
множества, то сдвинув параллельно прямую $MK$ в направлении от
вершины~$A$, мы сумеем отделить выпуклый четырехугольник $AK?C$.
Пусть в треугольниках $AKM$, $BKL$, $CLM$ расположены
соответственно точки $P$, $Q$,~$R$. Хотя бы один из отрезков
$PQ$, $QR$, $RP$ пересекает ровно два из отрезков $AL$, $BM$,
$CK$ (докажите!). Не умаляя общности, можно считать, что отрезок
$PQ$ пересекает отрезки $BM$ и $CK$ и не пересекает $AL$. Тогда
выпуклый четырехугольник $BKPQ$ можно отделить от остальных
точек прямой, параллельной $AL$.

\begin{figure}
\label{ris3}
\hbox{}\hskip5cm\special{em:graph ris3.bmp}
\vskip 4cm
\caption{Выпуклая оболочка --- треугольник}
\end{figure}


\smallskip
в) Нет, не всегда. Выберем произвольные 1999 точек на
какой-нибудь подходящей выпуклой кривой, скажем, на одной из
ветвей гиперболы (хоть бы даже и $y=1/x$), а последнюю,
двухтысячную точку,~--- в ее центре (в начале координат). Тогда
последняя точка не образует выпуклого четырехугольника ни с
какими из остальных.
\smallskip

г)
\end{solution}

\begin{solution}
%Существование N(n)
Утверждение задачи сразу следует из задач \ref{even-odd},
\ref{orientation}, если воспользоваться теоремой Рамсея.
Достаточно использовать теорему Рамсея в следующей частной
формулировке.

\begin{theorem}[Рамсея]
Для всякого натурального числа $k$ существует натуральное число $R_3(k,k)$,
обладающее следующим свойством: если во множестве точек плоскости общего
положения не меньше $R_3(k,k)$ точек и всевозможные треугольники, с вершинами в
этих точках разбиты на два класса, то найдутся такие $k$ точек,
что все треугольники с вершинами в этих точках принадлежат одному классу.
\end{theorem}

Оценка $N(n)\le R_3(n,n)$ весьма далека от оптимальной. По
поводу чисел Рамсея третьего порядка известно, что $2^{bn^2}\le
R_3(n,n)\le 2^{c^n}$, для некоторых констант $b$ и $c$.
Результаты раздела ``Чашки и крышки'' показывают, что эти числа
слишком велики по сравнению с $N(n)$.
\end{solution}

\begin{solution} %N(5)=9
Пример восьми точек, не определяющих ни одного выпуклого пятиугольника, ---
см.\ на рис~\ref{8points}.

\begin{figure}[tbc]
\begin{center}
\begin{picture}(430,110)(30,10)
\put (150,15){\circle*{5}}  \put (190,30){\circle*{5}}
\put (230,30){\circle*{5}}  \put (270,15){\circle*{5}}
\put (150,100){\circle*{5}} \put (190,85){\circle*{5}}
\put (230,85){\circle*{5}}  \put (270,100){\circle*{5}}
\end{picture}
\end{center}
\caption{Восемь точек, не определяющие ни одного выпуклого пятиугольника}
%{A set of eight points determining no convex pentagon.}
\label{8points}
\end{figure}

\end{solution}

\begin{solution}
а) Следущую конструкцию сообщил нам Ф.\,Петров. Для каждого
четного $n$ построим множество точек~$A_n$, состоящее из
$2^{n/2}$ точек, никакие $n$ из которых не находятся в выпуклом
положении. Построение будем вести по индукции. В качестве базы
для $n=4$ возьмем множество из четырех точек, лежащих в вершинах
невыпуклого четырехугольника. Если множество $A_n$ уже
построено, выберем достаточно малый вектор $\overrightarrow{v}$,
по направлению не совпадающий с прямыми, определяемыми парами
точек из $A_n$, и положим $A_{n+2}=A_n\cup
(A_n+\overrightarrow{v})$. Нетрудно проверить, что множество
$A_{n+2}$ не содержит выпуклых $(n+2)$-угольников.

\smallskip
б) Мы приводим доказательство из \cite{MorrisSoltan},
первоисточник~--- \cite{Erdos1}. Построим множество $X$ из $2^{n-2}$ точек,
в котором никакие $n$ точек не лежат в вершинах выпуклого многоугольника.
Пусть $T_i$, $i=0$, \dots, $n-2$,~---
множество из $C_{n-2}^i$ точек, не содержащее $(i+2)$-крышек и $(n-i)$-чашек.
Такое множество существует в силу результата задачи~\ref{probl:k_cups,l_caps},
мы можем дополнительно потребовать, чтобы все отрезки с концами из $T_i$
имели угловой коэффициент, по модулю не превосходящий~1.

Для $i=0$, \dots, $n-2$ разместим маленькую копию множества $T_i$ в
окрестности точки единичной окружности с радиус-вектором, образующим угол
$\frac\pi4 - \frac{i\pi}{2(n-2)}$ с положительным направлением
вещественной оси. В качестве искомого множества $X$ возьмем объединение
этих множеств $T_i$. Тогда
$$
|X|=\sum_{i=0}^{n-2} C_{n-2}^i=2^{n-2}\,.
$$
Предположим, что $Y\subset X$~--- подмножество точек, расположенных в
вершинах выпуклого многоугольника. Пусть $k$ и $\ell$~--- наименьшее и
наибольшее значение $i$, при котором $Y\cap T_i \ne\emptyset$. Если
$k=\ell$, то $Y$ не содержит ни $(k+2)$-крышек, ни $(n-k)$-чашек.
Если же $k\ne\ell$ и $Y$~--- выпукло, то наша конструкция гарантирует, что

1) $Y\cap T_k$ является крышкой из не более чем $k+1$ точек;

2) $Y\cap T_\ell$ является чашкой из не более чем $n-\ell-1$ точек;

3) $|Y\cap T_i|\le 1$  при $i=k+1$, \dots, $\ell-1$.

Таким образом,
$$
|Y|\le k+1  +  \ell-k-1  + n-\ell-1 \,.
$$

Мы доказали, что никакие $n$ точек из множества $X$ не лежат в вершинах
выпуклого многоугольника.
\end{solution}

\begin{solution}
Посмотрим, может, кто и решит.
\end{solution}


\begin{solution}
Мы приводим решение из \cite{mmo}, задача 66.

В силу утверждения задачи \ref{N(4)=5}, среди любых пяти точек плоскости
общего положения найдутся четыре, образующие вершины выпуклого
четырехугольника. Для каждой из $C_n^5$ групп по пять точек, выбранных
среди данных $n$ точек, отметим четыре точки, образующие выпуклый
четырехугольник. Каждый выпуклый четырехугольник мог быть отмечен не более
$n-4$ раз, поскольку дополнить любые четыре точки до пятерки можно
добавив любую из $n-4$ оставшихся точек. Поэтому всего выпуклых
четырехугольников будет не менее $C_n^5/(n-4)$. Это и есть величина,
указанная в условии.
\end{solution}



\subsection{Пустые выпуклые многоугольники}

\begin{solution}
а) Ясно всякому, кто слышал слово триангуляция. Или рассмотрим треугольник
наименьшей площади с вершинами в данных точках.

б) Мы взяли задачу из \cite{mmo}, задача~99.
Ответ: да.
%Приводим решение из книжки ().
%Пусть $A$ и $B$~--- те из данных точек, расстояние между
%которыми наименьшее. Выберем среди остальных точек третью точку $C$ так,
%чтобы угол $\angle ACB$ был наибольшим. Окружность, проведенная через
%точки $A$, $B$, $C$, искомая. Действительно, отрезок $AB$ делит
%окружность $ABC$ на два сегмента. Если еще какая-то точка $M$
%лежит в том же сегменте, что и $C$, то $\angle AMB > \angle
%ACB$, что противоречит выбору точки~$C$. Допустим, что $M$ лежит
%в другом сегменте, тогда $AMB\ge 180^\circ-\angle ACB$. Заметим,
%что в треугольнике $ABC$ угол $C$~--- наименьший и, в частности,
%острый. Но тогда мы получаем, что угол $\angle AMB$~--- тупой, и
%это опять противоречит выбору точки~$C$.
Рассмотрим выпуклую оболочку всех точек. Это некоторый
многоугольник. Пусть $AB$~--- произвольная сторона этого
многоугольника. Выберем среди оставшихся точек такую точку~$C$,
из которой отрезок $AB$ виден под наибольшим углом. Описанная
окружность треугольника $ABC$~--- это то, что нам требуется.

\end{solution}

\begin{solution}
$H(4)=5$.
\end{solution}

\begin{solution} %H(5)=10
Пример множества из девяти точек, не имеющего ни одного пустого
выпуклого пятиугольника, см.\ на рис.~\ref{9points}.

\begin{figure}
\begin{center}
\begin{picture}(430,160)(40,10)
\put(120,160){\circle*{5}}\put(180,130){\circle*{5}}
\put(240,110){\circle*{5}}\put(340,90){\circle*{5}}
\put(240,70){\circle*{5}} \put(180,50){\circle*{5}}
\put(120,20){\circle*{5}} \put(170,91){\circle*{5}}
\put(190,89){\circle*{5}}
\end{picture}
\end{center}
%\caption{A set of nine points with no empty convex pentagon.}
\caption{Множество из девяти точек, не содержащее пустых выпуклых
пятиугольников}
\label{9points}
\end{figure}
\end{solution}

\begin{solution}
%H(7) не существует
Это решение взято из~\cite{Valtr}. Будем рассматривать только
такие множества, у которых \hbox{$x$-коо}рди\-на\-ты всех точек
различны. Обозначим $x(A)$~--- $x$-координату точки~$A$. Назовем
множество точек $k$-замкнутым сверху, если в нем для любой
$k$-чашки $A_1A_2\dots A_k$ найдется такая точка~$A$, что
${x(A_1)<x(A)<x(A_k)}$, и точка $A$ расположена выше ломаной
$A_1A_2\dots A_k$ (многоугольник $AA_1A_2\dots A_k$ при этом не
обязательно выпуклый). Аналогично (при помощи $k$-крышек)
определяется $k$-замкнутость множества снизу. Множество,
$k$-замк\-ну\-тое и сверху, и снизу, будем называть
$k$-замкнутым.

Для каждого $k\in \mathbb{N}$ построим множество $X_k$, состоящее из
$2^k$ точек, являющееся 4-замкнутым и не содержащее пустых выпуклых
семиугольников (и такое, что $x$-координаты всех его
точек различны). База индукции~--- одноточечное множество.

Пусть множество $X=X_{k-1}$ уже построено. Положим $Y=X_{k-1}+\epsilon$,
где $\epsilon$~--- вектор, у которого достаточно мала $x$-координата и
достаточно велика $y$-координата. Тогда

\begin{itemize}
\item[i)] $x$-координаты точек из множеств $X$ и $Y$ чередуются;

\item[ii)] множество $X$ лежит ниже любой прямой, соединяющей точки из~$Y$;

\item[iii)] множество $Y$ лежит выше любой прямой, соединяющей точки из~$X$.
\end{itemize}

Положим $X_k=X\cup Y$.

\smallskip
1. Проверим, что множество $X_k$ не содержит пустых выпуклых
семиугольников. Допустим, что это не так. Пусть $Z$~--- выпуклый
семиугольник, составленный из точек множества~$X_k$. Обозначим
$X'=A\cap Z$, $Y'=A\cap Z$. Множества $X'$ и $Y'$ непусты, поскольку ни
$X$, ни $Y$ не содержат пустых выпуклых семиугольников. В~силу ii) и~iii)
$X'$~--- чашка, а $Y'$~--- крышка.
Если $X'$ состоит из не менее четырех точек, то в силу 4-замкнутости
сверху множества $X$ (и~опять с учетом ii),~iii)) точка множества~$X$,
осуществляющая это 4-замыкание, лежит внутри семиугольника~$Z$. Аналогично
разбирается случай, когда $Y'$ содержит не менее четырех точек.

\smallskip
2. Проверим, что множество $X_k$ является 4-замкнутым. Пусть
$ABCD$~--- 4-чашка. Если $B\in Y$ (и аналогично, если $A\in Y$),
то обе точки $A$ и $C$ не могут одновременно принадлежать $X$ в
силу~iii). Тогда, если, скажем, $C\in Y$, то в силу выпуклости и
свойства~ii) все четыре точки $A$, $B$, $C$, $D$
принадлежат~$Y$, и в силу 4-замкнутости множества $Y$ мы можем
найти в $Y$ точку, реализующую замыкание этой четверки сверху.
Если же обе точки $B$, $C$ лежат в $X$, то в силу~i) найдется
точка $E\in Y$, $x(B)<x(E)<x(C)$, лежащая выше отрезка $BC$ и
осуществляющая тем самым замыкание нашей 4-чашки сверху.
Аналогично проверяется замкнутость снизу для 4-крышек.

\smallskip
Итак, мы построили семейство множеств $X_k$, состоящих из $2^k$ точек и
не содержащих выпуклых пустых семиугольников.
Теперь нетрудно для любого натурального $n$ построить
множество из $n$ точек, не содержащее пустых выпуклых семиугольников. Для
этого достаточно взять множество $X_k$, $2^k>n$, и удалять из него
последовательно экстремальные точки, до тех пор, пока не останется $n$
точек.

\end{solution}

\begin{solution}
а)
\end{solution}


\subsection{Другие обобщения}

\begin{solution}
Докажем, что $N_d(n)\le N(n)$.
Выберем в $\mathbb{R}^d$ такую двумерную плоскость, чтобы проекции точек нашего
множества точек на совпадали и образовывали множество общего положения.
Если исходное множество (а значит, и его проекция) содержит не менее
$N(n)$ точек, то какие-то $n$ точек проекции образуют выпуклый
$n$-угольник. Тогда соответствующие точки исхдного множества находятся в
выпкулом моложении, поскольку свойство точки ``быть выпуклой комбинацией
других точек'' сохраняется при проектировании.
\end{solution}

\begin{solution}
Ну да, открытая проблема.
\end{solution}

\begin{solution}
Утверждение этой и следующей задачи вместе с доказательствами взяты
из~\cite{Bisztriczky}.

\smallskip
а) Если в какой-то конфигурации, состоящей из пяти овалов,
не нашлось четырех овалов в выпуклом положении, то
любой набор из трех, четырех или всех пяти овалов
в этой конфигурации определяет треугольник.
Это противоречит утверждению следующего пункта задачи.

\smallskip
б) Будем говорить, что два (пересекающихся) овала $X$ и $Y$
\emph{образуют крест}, если оба множества $X\setminus Y$ и
$Y\setminus X$ несвязны. Если овалы не образуют креста, будем
говорить, что они имеют простое пересечение (быть может,
пустое). Если овалы $A_1$, $A_2$, \dots  определяют выпуклый
$k$-угольник, и для всех вершин $A_i$ этого $k$-угольника овалы
$A_i$ и $\conv(\bigcup\limits_{j\ne i} A_j)$ образуют простое
пересечение, то будем говорить, что этот $k$-угольник простой. В
случае простого многоугольника корректно определен порядок
вершин.

Из условия сразу следует, что
\begin{equation}\label{eqn:l-gon}
\mbox{любые $\ell\le m$ овалов из семейства $\Phi$ определяют
$\ell$-угольник.}
\end{equation}

Тогда любые $\ell>m$ овалов $A_1$, $A_2$, \dots, $A_{\ell}$ из семейства
$\Phi$ образуют простой $m$-угольник~$M$. Действительно, если это не так,
то какой-то из овалов-вершин, скажем, $A_1$, разбивает многоугольник $M$
на две части. Так как овалы дизъюнктны, то овал, не являющийся вершиной,
скажем, овал $A_{m+1}$, содержится в одной из половин многоугольника $M$,
что противоречит~(\ref{eqn:l-gon}).

Пусть в семействе $\Phi$ содержится $m+2$ овалов
$A_1$, $A_2$, \dots, $A_{m+2}$, образующих $m$-угольник $M$ с вершинами
$A_1$,~\dots,~$A_m$. Обозначим $M_i=M\setminus A_i$, $1\le i\le m$. Как мы
проверили, $M_i$~--- простой $m$-угольник; одна из вершин этого многоугольника
есть $A_{m+1}$ или $A_{m+2}$. Так как $m\ge 3$, мы можем считать, что
овал $A_{m+1}$ является вершиной каких-то двух из многоугольников $M_i$,
скажем, $M_1$ и $M_j$. При этом $A_{m+2}\subset M_1 \cap M_j$.

Вершины $A_1$ и $A_j$ должны быть соседними в
многоугольнике~$M$, так как иначе $M_1\cap
M_j=\conv(\bigcup\limits_{i\ne1, j}A_i)$ является
($m-1$)-угольником, хотя и содержит $m$ овалов из
семейства~$\Phi$, а это противоречит~(\ref{eqn:l-gon}). Если же
$A_1$ и $A_j$~--- соседние вершины в многоугольнике~$M$, скажем,
$j=2$, то
$$
M_1\cap M_2\subset\conv(\bigcup\limits_{i=3}^{m+1}A_i)
\cup \conv(A_1\cup A_{m+1}) \cup \conv(A_2\cup A_{m+1}),
$$
причем $A_{m+2}$ содержится в одной из этих выпуклых оболочек, что опять-таки
невозможно.
\end{solution}

\begin{solution}
Индукция по $n$ плюс теорема Рамсея с использованием утверждений
задачи~\ref{lem:ovaly}. Нам понадобится следующий вариант теоремы Рамсея:

\begin{theorem}[Рамсея]
Для всяких натуральных чисел $n$, $k$, $\ell$ существует
натуральное число $R_n(k,\ell)$, обладающее следующим свойством:
если в каком-либо множестве не меньше $R_n(k,\ell)$ точек и
всевозможные $n$-наборы точек разбиты на два класса, то либо
найдутся такие $k$ точек, для которых все $n$-наборы принадлежат
первому классу, либо найдутся $\ell$ точек, для которых все
$n$-наборы принадлежат второму классу.
\end{theorem}

База индукции $n=4$~--- это утверждение задачи~\ref{lem:ovaly}~а).
Допустим, что мы уже установили конечность числа $G(n-1)$.
Докажем, что $G(n)\le R_{n-1}(n+1, G(n-1)+1)$.

Возьмем множество $\Omega$, состоящее из $R_{n-1}(n+1, G(n-1)+1)$ овалов,
и разобьем все ($n-1$)-наборы овалов на два класса, в зависимости от того,
определяют ли эти овалы выпуклый ($n-1$)-угольник или нет.
Тогда либо найдется множество $\Omega_1$ из $n+1$ овалов, любые $n-1$ из которых
определяют ($n-1$)-угольник, либо найдутся $G(n-1)+1$ овалов, никакие $n-1$ не
определяют ($n-1$)-угольника. Последнее невозможно по определению числа
$G(n-1)$, а первое также невозможно, если во множестве $\Omega$ никакие
$n$ овалов не определяют $n$-угольника. Действительно, в этом случае во
множестве $\Omega_1$ любые $n$ овалов определяют ($n-1$)-угольник, и, как
легко сообразить, все $n+1$ овалов множества $\Omega_1$ тоже определяют
лишь ($n-1$)-угольник. Теперь размеры множества $\Omega_1$ противоречат
утверждению задачи~\ref{lem:ovaly}~б).
\end{solution}

\begin{solution}
Утверждение задачи сразу следует из теоремы Эрдеша~\ref{Erdos-monoton}.
Действительно, точка $A(y_1, y_2, \dots, y_d)$ лежит между точками
$B(x_1, x_2, \dots, x_d)$ и $C(z_1, z_2, \dots, z_d)$, если при всех
$k$, $1\le k\le d$, последовательность $(x_k, y_k, z_k)$~--- монотонна.

Выпишем все наши $2^{2^{d-1}}+1$ точек в порядке возрастания их первых
координат. По теоеме Эрдеша, найдется подпоследовательность из
$2^{2^{d-2}}+1$ точек, в которой вторые координаты точек изменяются
монотонно. Опять по теореме Эрдеша, в этой подпоследовательности найдется
своя подпоследовательность, в которой монотонно упорядочены третьи
координаты точек. И так далее. Процесс этого многократного применения
теоремы Эрдеша закончится тем, что мы найдем на ($d-1$)-м шаге
последовательность из $2^{2^0}+1=3$ точек с монотонно
изменяющимися координатами. Тогда средняя в этой последовательности точка
лежит между двумя крайними.

Чтобы показать, что оценка в утверждении задачи точная, заметим в дополнение
к теореме Эрдеша, что
для каждой пары чисел $p$ и $q$ нетрудно построить пример
последовательности из $pq$ членов, в которой нет ни возрастающей
подпоследовательности из $p+1$ членов, ни убывающей подпоследовательности
из $q+1$ членов. Например, разобьем числа от 1 до $pq$ на $q$ групп по $p$
последовательных чисел в группе, и расположим эти группы в порядке
убывания их первых чисел.
Пользуясь этим замечанием мы, отталкиваясь от проделанной в первой
части решения декомпозиции, без труда сконструируем множество
из $2^{2^{d-1}}$ точек, ни одна из которых не лежит между двумя другими.
\end{solution}

\begin{solution}
Мы приведем известное рассуждение, использующее алгоритм
Робинсона-Шенстеда-Кнута. Рассмотрим нашу последовательность. Напишем
первое ее число в левой верхней клетке клетчатого листа бумаги.
Будем добавлять новые числа и переставлять имеющиеся по следующему алгоритму:

\begin{description}

\item[Шаг 1.] Возьмем очередное число последовательности.
Назовем его текущим числом.
Верхнюю левую клетку листа назовем текущей клеткой.

\item[Шаг 2.] Если текущая клетка пуста, поставим в нее текущее число и перейдем
к Шагу~1, иначе перейдем к Шагу~3.

\item[Шаг 3.] Если текущее число меньше числа в текущей клетке, передвинемся на
одну клетку вправо, назовем эту клетку текущей и перейдем к шагу 2;
если же текущее число больше числа в текущей клетке, впишем в текущую
клетку вместо имеющегося там числа текущее число, после чего назовем текущим
число, только что удаленное из текущей клетки, сдвинемся на одну
клетку вниз, назовем эту клетку текущей и перейдем к шагу 2.
\end{description}

В результате выполнения этого алгоритма числа нашей последовательности
окажутся расположенными в виде фигуры, которая называется диаграммой Юнга.
Диаграмма Юнга состоит из нескольких горизонтальных рядов клеток,
выровненных по левому краю, причем каждый следующий ряд содержит не больше
клеток, чем предыдущий. Заметим, что если числа знимают $pq+1$ клеток, то
в полученной диаграмме либо первая строка содержит более $q$ клеток, либо
первый столбец~--- более $p$ клеток (в противном случае диаграмма содержалась
бы в прямоугольнике $q\times p$ и состояла бы из не более чем $pq$ клеток).
Оба случая означают наличие требуемой монотонной подпоследовательности.

\input lines.tex
\begin{figure}
\hfil\hbox{\vbox{\lines8
 _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|
|_|_|_|_|_|_|
|_|_|_|_|_|
|_|_|
|_|
|_|}}\hfil
\caption{Диаграмма Юнга}
\end{figure}

\end{solution}

\subsection{После промежуточного финиша}

\begin{solution}
Нам понадобится следующая модификация теоремы Рамсея.

\begin{theorem}
Пусть дано счетное множество $M$ и $k$~--- натуральное число.
Пусть все $k$-элементные подмножества множества $M$ разбиты на
два класса. Тогда существует такое бесконечное подмножество
$L\subset M$, что все $k$-элементные подмножества множества $L$
принадлежат одному классу.
\end{theorem}

Доказательство получается индукцией по $k$ аналогично обычной
теореме Рамсея.

Выберем в нашем множестве счетное подмножество $M$ и пронумеруем
его точки. Разобьем все треугольники с вершинами в точках
множества $M$ на два класса в соответствии с их ориентацией (как
в задаче~\ref{orientation}). По сформулированной теореме Рамсея
для бесконечного подмножества $L\subset M$ все треугольники с
вершинами из $L$ будут ориентированы одинаково, откуда и следует
утверждение задачи.

\end{solution}


\subsubsection{Чашки и крышки (cups and caps)}

\begin{solution}
Мы приводим решение из \cite{MorrisSoltan}, первоисточник~---
\cite{ErdosSzekeres}. Неравенство следует из рекуррентного
соотношения
\begin{equation}
\label{rec-nerav}
f(k,\ell)\le f(k-1,\ell) + f(k, \ell-1) - 1
\end{equation}
и начальных условий $f(k,3)=f(3,k)=k$.

Докажем неравенство~(\ref{rec-nerav}). Пусть множество $X$
состоит из $f(k-1,\ell) + f(k, \ell-1) - 1$ точек. Рассмотрим
всевозможные $(k-1)$-чашки  из множества~$X$. Пусть $Y$~---
множество крайних левых точек этих чашек. Тогда множество
$X\setminus Y$ не содержит ни одной $(k-1)$-чашки. Если в этом
множестве было бы не меньше $f(k-1,\ell)$ точек, то тогда в нем
обязательно нашлась бы $\ell$-крышка. Пусть в множестве
$X\setminus Y$ меньше $f(k-1,\ell)$ точек, тогда в множестве $Y$
не меньше $f(k,\ell-1)$ точек. Если оно при этом не содержит
$k$-чашек, то в нем обязательно найдется $(\ell-1)$-крышка,
обозначим ее
$$
A = \{ (x_1, y_1), (x_2, y_2), \dots, (x_{\ell-1},y_{\ell-1})
\}\,.
$$
Рассмотрим также $(k-1)$-чашку
$$
U= \{ (x_{j_1}, y_{j_1}), (x_{j_2}, y_{j_2}), \dots,
(x_{j_{\ell-1}},y_{j_{\ell-1}}) \}
$$
в множестве $X$, для которой точка $(x_\ell,y_\ell)$ является
крайней левой точкой (так что в наших обозначениях
${j_1=\ell-1}$). Нетрудно видеть, что тогда либо
$(x_{\ell-2},y_{\ell-2})\cup U$~--- $k$-чашка, либо $A\cup
(x_{j_2},y_{j_2})$~--- $\ell$-крышка.
\end{solution}

\begin{solution}
Формула очевидна при $k=3$ или $\ell=3$. Утверждение будем
доказывать по индукции. Допустим, что существует множество $A$
из $C_{k+\ell-5}^{k-3}$ точек, не содержащее ни $(k-1)$-чашек,
ни $\ell$-крышек, и множество $B$ из $C_{k+\ell-5}^{k-2}$ точек,
не содержащее ни $k$-чашек, ни $(\ell-1)$-крышек. Выполним
параллельный перенос этих множеств так, чтобы оказалось, что

1) множество $B$ лежит правее множества $A$, т.\,е.\
$x$-координата любой точки множества $B$ больше $x$-координаты
любой точки множества~$A$;

2) наклон любой прямой, соединяющей любую точку из $A$ с любой
точкой из~$B$ больше наклона любой прямой, проходящей через две
точки из $A$ или две точки из~$B$.

Ясно, что каждая чашка из множества $A\cup B$, содержащая точки
обоих множеств $A$ и $B$, содержит не более одной точки из $B$,
поэтому множество $A\cup B$ не содержит $k$-чашек. Аналогично,
это множество не содержит $\ell$-крышек. Таким образом, $$
f(k,\ell)\ge C_{k+\ell-5}^{k-3} +C_{k+\ell-5}^{k-2}+1=
C_{k+\ell-4}^{k-2}+1\,. $$
\end{solution}

\begin{solution}
Результат задачи сразу следует из очевидного неравенста $N(n)\le
f(n,n)$.

\smallskip
Доказанное утверждение было получено Эрдешем
в~\cite{ErdosSzekeres} и в течение 63 лет было наилучшей
известной оценкой сверху для чисел $N(n)$. Несколько лет назад
появилось сразу несколько статей, где доказывались чуть более
сильные оценки, самая сильная из них и при этом наиболее простая
приводится в следующей задаче (первоисточник~---
\cite{TothValtr98}).
\end{solution}

\begin{solution}
Пусть $A$~--- экстремальная точка множества~$X$. Выберем точку
$B$ вне выпуклой оболочки множества $X$ так, чтобы никакая
прямая, проходящая через какие-нибудь две точки множества
$X\setminus A$, не пересекала отрезок $AB$. Проведем через точку
$B$ произвольную прямую $p$, не пересекающуюся с выпуклой
оболочкой можества $X$. Выполним проективное преобразование~$T$,
отображающее прямую $p$ в бесконечно удаленную прямую, а отрезок
$AB$~--- в луч, идущий из точки $T(A)$ вертикально вниз. Тогда
очевидно, что

1) множество точек $Y\subset X$ находится в выпуклом положении
тогда и только тогда, когда $T(Y)$ находится в выпуклом
положении;

2) множество точек $Z\subset X$, содержащее точку $A$, находится
в выпуклом положении тогда и только тогда, когда $T(Z\setminus
A)$~--- крышка.

Пусть множество $X$ содержит $C_{2n-5}^{n-3}+2$ точек. Тогда
множество $T(X\setminus A)$, в силу утверждения задачи
\ref{probl:k_cups,l_caps-nerav}, содержит $(n-1)$-крышку или
$n$-чашку. Значит, $X$ содержит $n$ точек в выпуклом положении.
\end{solution}


\subsubsection{Коэффициент неразбиваемости}

\begin{solution}
Нет, таких множеств не существует. Действительно, если такие
множества существуют, выберем произвольные десять точек
множества $A$, пусть $S$~--- множество, состоящее из этих десяти
точек и тех точек множества $A$, которые лежат в их выпуклой
оболочке. Тогда в силу утверждения $H(5)=10$ (намек на это
имеется в утверждении задачи \ref{problemH(5)}) во множестве $S$
найдутся пять точек, образующих выпуклый пятиугольник и не
содержащих других точек множества~$A$. Пусть
$B_1B_2B_3B_4B_5$~--- этот пятиугольник. Пусть $C_1$, $C_2$,
$C_3$~--- точки множества $B$, лежащие в треугольниках
$B_1B_2B_3$, $B_1B_3B_4$, $B_1B_4B_5$. Тогда в треугольнике
$C_1C_2C_3$, а значит, и в пятиугольнике $B_1B_2B_3B_4B_5$
содержится точка множества~$A$.

\smallskip
Вот похожее рассуждение, в котором не используются никакие
специальные факты.

\begin{lemma}
Если выполнено условие задачи, то в выпуклой оболочке любых пяти
точек множества~$A$ содержится еще хотя бы одна точка
множества~$A$.
\end{lemma}

\begin{proof}
Если выпуклая оболочка $S$ выбранных пяти точек является
$k$-угольником ($k=3$, 4,~5), то есть, $5-k$ из выбранных точек
лежат внутри~$S$, то мы можем разбить этот $k$-угольник на $8-k$
треугольников с вершинами в этих пяти точках (посчитайте сумму
углов!). Значит, внутри многоугольника $S$ содержится $8-k$
точек множества~$B$. Тогда можно найти $6-k$ непересекающихся
треугольников с вершинами в этих точках, и значит, внутри $S$
есть хотя бы одна ``новая'' точка из множества~$A$.
\end{proof}

Из утверждения леммы сразу следует решение задачи.
Действительно, пусть такие множества существуют. Зафиксируем
какой-нибудь не слишком маленький круг, отметим все точки
множества $A$, лежащие внутри него, и выберем пять точек с
наименьшей площадью выпуклой оболочки (это возможно, так как в
силу отделенности точек друг от друга внутри круга находится
лишь конечное число точек). По лемме, внутри выпуклой оболочки
этих точек найдется еще одна точка множества~$A$. Удалив одну
вершину выпуклой оболочки исходной пятерки точек, мы получим
пять точек с меньшей площадью выпуклой оболочки. Противоречие.

\end{solution}

\begin{solution}
%k/n-> 1/2
Пусть $p$ и $s$~--- произвольные достаточно большие натуральные
числа, выбор которых станет ясен позже. Пусть $n=p N(2s)$. Тогда
в нашем множестве можно выбрать не менее $\frac{(p-1)N(2s)}{2s}$
выпуклых $2s$-угольников, не имеющих общих вершин. В каждом из
этих $2s$-угольников раскрасим вершины попеременно в красный и
синий цвета. Нетрудно проверить, что в каждом $2s$-угольнике
нужно выбросить не менее $s-1$ точек, чтобы выпуклые оболочки
его красных и синих вершин не пересекались. Значит, для того
чтобы  выпуклые оболочки всех красных и синих точек не
пересекались, необходимо выбросить не менее
$\frac{(s-1)(p-1)N(2s)}{2s}$ точек. Поэтому
$$
\frac kn \ge \frac{\frac{(s-1)(p-1)}{2s}N(2s)}{p N(2s)}=
\frac12\cdot\frac{s-1}s\cdot\frac{p-1}p\,.
$$
Это выражение может быть сколь угодно близким к 1/2.
\end{solution}



\begin{thebibliography}{99}


\bibitem{mmo}
Морозова Е.\,А., Петраков И.\,С., Скворцов В.\,А.
Международные математические олимпиады. М.: Просвещение. 1976.

\bibitem{Erdos1}
Erd\H{o}s P., Szekeres G., On some extremum problems in elementary geometry.
Ann. Univ. Sci. Budapest. E\"otv\"os Sect. Math. {\bf 3--4} (1961), 53--62.
Перепечатано в Paul Erd\H{o}s: The Art of Counting. Selected Writings
(J.~Spencer, ed.)

\bibitem{ErdosSzekeres} {\sc Erd\H{o}s P., Szekeres G.},
A combinatorial problem in geometry,
{\it Compositio Math.} {\bf 2} (1935), 463--470.
Reprinted in: {\it Paul Erd\H{o}s: The Art of Counting. Selected
Writings} (J. Spencer, ed.), pp. 3--12, MIT Press, Cambridge, MA, 1973.
Reprinted in: {\it Classic Papers in Combinatorics} (I. Gessel and G.-C.
Rota, eds.), pp. 49--56, Birkh\"auser, Basel, 1987.

\bibitem{MorrisSoltan}
Morris W., Soltan V.
The Erd\H{o}s-Szekeres problem on points in convex position --- a survey.
Bull. AMS  V.~37, No.~4, P. 437--458.

\bibitem{TothValtr98} {\sc T\'oth G., Valtr P.},
Note on the Erd\H{o}s-Szekeres theorem,
{\it Discrete Comput. Geom.} {\bf 19} (1998), 457--459.

\bibitem{Bisztriczky}
{\sc Bisztriczky T., Fejes T\'oth G.},
A generalization of the Erd\H{o}s--Szekeres convex $n$-gon theorem,
{\it J. Reine Angew. Math.} {\bf 395} (1989), 167--170.

\bibitem{Valtr} {\sc Valtr P.},
Convex independent sets and 7-holes in restricted planar point sets,
{\it Discrete Comput. Geom.} {\bf 7} (1992), 135--152.

\end{thebibliography}
\end{document}

\section{Свалка}

1) Table 4.1 shows the known values of $N_d(n)$, where the
respective value is placed at the intersection of column $d$ and
row $n$.

\begin{table}
\begin{tabular}{r|rrrrrrrrrrrrrr}
$n$&   &   &   &    &    &    &    &    &          &    \\
   &   &   &   &    &    &    &    &    &          &    \\
14 &   &   &   &    &    &    &    & 18 &          &    \\ 13 &
&   &   &    &    &    & 17 & 16 &          &    \\ 12 &   &   &
&    &    &    & 15 & 14 &          &    \\ 11 &   &   &   &
&    & 14 & 13 & 12 &          &    \\ 10 &   &   &   &    & 13
& 12 & 11 & 10 &          &    \\
 9 &   &   &   &    & 11 & 10 &  9 &  9 &          &    \\
 8 &   &   &   & 10 &  9 &  8 &  8 &  8 &          &    \\
 7 &   &   & 9 &  8 &  7 &  7 &  7 &  7 &          &    \\
 6 &   & 9 & 7 &  6 &  6 &  6 &  6 &  6 &          &    \\
 5 &  9& 6 & 5 &  5 &  5 &  5 &  5 &  5 &          &    \\
 4 &  5& 4 & 4 &  4 &  4 &  4 &  4 &  4 &          &    \\
 3 &  3& 3 & 3 &  3 &  3 &  3 &  3 &  3 &          &    \\
 2 &  2& 2 & 2 &  2 &  2 &  2 &  2 &  2 &          &    \\
 1 &  1& 1 & 1 &  1 &  1 &  1 &  1 &  1 &      \\   \hline
   &  2& 3 & 4 &  5 &  6 &  7 &  8 &  9 & $\ldots$ & $d$\\
\multicolumn{11}{c}{}\\
\end{tabular}
\caption{Known values of $N_d(n)$ when $d < 10$.}
\end{table}

2) $N_3(6)=9$.

3) $H_3(n)$ не существует при $n\ge 22$.

4) $H_3(6)=9$.

5) Если в множестве $X$ общего положения $k$ точек, и
максимальное расстояние между ними не превосходит $\alpha\sqrt
k$, то $\exists\beta(\alpha)$, такое что во множестве $X$
имеется $\beta \root4\of k$ точек в выпуклом положении.
