%\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}{Definition}[subsection]
\newtheorem*{lemma}{Lemma}
\theoremstyle{plain}
\newtheorem*{theorem}{Theorem}
%\renewcommand{\proofname}{Proof}
%\renewcommand{\refname}{References}
%\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{Convex Polygons}
\author{S. Berlov, K. Kokhas}
%\date{{\small Версия 0.07}}
\begin{document}
\maketitle

%\title{Convex Polygons}
%\author{S.~Berlov, K.~Kokhas}
%\date{{\small Draft 0.04}}
%\begin{document}
%\maketitle

\section{Problems}

%This series of problems comprises, primarily, the contents of survey
%\cite{MorrisSoltan}. Pictures come from electronic version of this
%paper on the AMS server.
%
%КК: текст выше -- не нужно печатать в условиях.

We say that points are \emph{in general position} in the plane if no three
of them are on a line; we say that points are \emph{in convex position} if
they form a convex polygon.

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


\subsection{Single Convex Polygon}

\begin{problem}
\label{even-odd}
Let $X$ be any finite set of points in general position in the plane.
For $A$, $B$, $C\in X$, triangle $ABC$ is called
\emph{even}, if the number of points of $X$ inside $ABC$ is even and
\emph{odd} otherwise.
Let $A_1$, $A_2$, \dots, $A_n$ be points of $X$.  Prove that if
all triangles with these points as vertices have the same parity
(i.e., either all are even or all are odd) then points
$A_1$, $A_2$, \dots, $A_n$ are in convex position.
\end{problem}

\begin{problem}
\label{orientation}
Let $A_1$, $A_2$, $A_3$, \dots be any finite set of points in
general position in the plane. We say that triangle $A_iA_jA_k$, $i<j<k$,
is \emph{well-oriented} if its vertices come clockwise in the above
order; otherwise we say that the triangle is \emph{maloriented}.
Prove that for any positive integer $n$ points
$A_{i_1}$, $A_{i_2}$, \dots, $A_{i_n}$ are in convex position
if and only if all triangles
$A_{i_p}A_{i_q}A_{i_r}$, $i_p< i_q < i_r$ have the same orientation.
\end{problem}

Let $N(n)$ be the smallest positive integer such that for any set
of points in general position in the plane with at least $N(n)$ points
%KK                                        containing?
there always exists $n$ points forming a convex $n$-gon.
The problem of determination of $N(n)$ or at least finding a
reasonable estimates of it is known as the
\emph{Erd\H{o}s-Szekeres problem}.

\begin{problem}
\label{N(4)=5}
Prove that $N(3)=3$, $N(4)=5$.
\end{problem}

\begin{problem}
Prove that if we have 2000 points in general position in the plane
then we can form at least 400 disjoint convex quadrangles. Can you form
more? How about 500?
\end{problem}

\begin{problem}
Prove, drawing on results of problems \ref{even-odd}, \ref{orientation},
that $N(n)$ exists for any $n>2$.
\end{problem}

\begin{problem}
Prove that $N(5)>8$. In fact $N(5)=9$, but it seems that a prove of this
would be too technical.
\end{problem}

\begin{problem}
a) Prove that $N(n)$ grows exponentially, i.\,e.\ there exists
$\alpha\in\mathbb{R}$ such that
$N(n)>\alpha^n$ for all $n$.

b) Prove that $N(n)\ge 2^{n-2}+1$.
\end{problem}

\begin{problem}
Open question: by the conclusion of the previous problem $N(6)\ge 17$.
Is it true that $N(6)=17$?
\end{problem}


\begin{problem}
%(\cite{mmo}, problem 67)
A number $n>4$ points in general position in the plane are marked.
Prove that one can find at least $n(n-1)(n-2)(n-3)/120$
convex polygons with vertices in marked points.
\end{problem}



\subsection{Empty Convex Polygons}

Let $H(n)$ be the smallest positive integer such that in any set
of at least $H(n)$ points in general position in the plane
one can always find $n$ points that form a convex
$n$-gon with no other points of the set inside.

\begin{problem}
a) Prove that $H(3)=3$.

b) %(\cite{mmo}, problem 99)
Consider $n>3$ points in general position in the plane.
Is it true that there always exists a circle that has at least three of
given points on its circumference and no other given points inside?
\end{problem}

\begin{problem}
Find $H(4)$.
\end{problem}

\begin{problem}
\label{problemH(5)}
Prove that $H(5)\ge 10$. By the way, $H(5)=10$.
\end{problem}

\begin{problem}
Prove that for $n\ge 7$ \ there exists no $H(n)$.
\end{problem}

\begin{problem}
a) Prove that $H(6)\ge 20$.

b) Open question: does $H(6)$ exist?
\end{problem}




\subsection{Other Generalizations}

\subsubsection{Other Dimensions}

\begin{problem}
Prove that for all $n$ in any big enough set of points in general
position in $\mathbb{R}^d$ there always exist $n$ points
in convex position.
\end{problem}

\smallskip
By $N_d(n)$ denote the smallest number of points for which the above
statement holds.

\begin{problem}
Open question: is it true that $N_3(n)$ grows exponentially?
\end{problem}

\subsubsection{Ovals instead of points}

By an \emph{oval} we mean a closed convex bounded set of points in the
plain; we consider collections of pairwise nonoverlapping ovals.
We say that three ovals are non-collinear if none of them is a subset of
the convex hull of the other two; more generally, we say that
$n$ ovals are in \emph{convex position} if none of them is a subset
of the convex hull of the others.
We say that a set of ovals determines a (convex) $k$-gon if
$k$ of them are in convex position (we call them vertices) and
others lie in the convex hull of these $k$ ovals.

\begin{problem}
\label{lem:ovaly}
a) Show that for any five ovals any three of which are non-collinear some
four are in convex position.

b) Suppose $m\ge3$. Prove that if in a set $\Phi$ of ovals any $k\ge m$
ovals determine only a $m$-gon then $\Phi$ consists of at most
$m+1$ ovals.
\end{problem}

By $G(n)$ denote the smallest positive integer such that for any set
of at least $G(n)$ ovals any three of which are non-collinear
one can always find $n$ ovals in convex position.
Obviously, $G(n)\ge N(n)$. The previous problem suggests that
%KK тут тоже suggest
$G(4)=N(4)=5$. One can show that $G(5)=N(5)=9$.
Whether or not $G(n)=N(n)$ for $n\ge 4$ is an open question.

\begin{problem}
Prove that $G(n)$ is finite for all $n$.
\end{problem}


\subsubsection{Abstract Convexity}

A rectangular parallelepiped in $\mathbb R^3$ with edges parallel to
coordinate axes is called \emph{standart}. The intersection of two
standart parallelepipeds, unless empty, is standart again.
Thereby the class of standart parallelepipeds is similar to that
of all convex sets. The implied convex structure, however, differs
a lot from the usual one. For example, the next result states
that a polyhedron convex with respect to this structure cannot
have too many vertices.

Consider three points $x$, $y$, $z\in\mathbb R^3$. We say that $x$
lies between $y$ and~$z$ if $x$ belongs to any standart
parallelepiped that contains both $y$ and~$z$.

\begin{problem}
a) Prove that out of any 17 points in $\mathbb R^3$ at least one lies
between two others.

b) Prove that among any $2^{2^{d-1}}+1$ points in $\mathbb R^d$ at least
one lies between two others. For $2^{2^{d-1}}$ points it is not true.
\end{problem}

The following theorem (Erd\H{o}s) fits ideologically to the context:

\begin{problem}
\label{Erdos-monoton}
In any sequence of $pq+1$ different real numbers one can find an
increasing subsequence of length $p+1$ or a decreasing subsequence of
length $q+1$.
\end{problem}

\newpage
\subsection{}

\begin{problem}
Now let us mark infinitely many points in general position in the plane.
Prove that there exists a convex "infinitegon" with vertices at marked
points, i.e., such a (countable) infinite subset that for
all $k$ any $k$ points of it are in  convex position.
\end{problem}

\subsubsection{Cups and Caps}
\label{sec:cupscaps}

We say that points $(x_1,y_1)$, $(x_2,y_2)$, \dots, $(x_m,y_m)$
form an $m$-cap, if
$$
\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}
$$
(in particular this implies $x_i\ne x_j$). Similarly, points form an
$m$-cup, if
$$ \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{Examples of 3-cup and 4-cap.}
\end{figure}

Let $f(k,\ell)$ be the smallest positive integer such that any set
$X$ of at least $f(k,\ell)$ points in general position, $x$-coordinates of
which are all different, always contains a $k$-cup or an $\ell$-cap.

\begin{problem}
\label{probl:k_cups,l_caps-nerav}
Prove that $f(k,\ell)\le \binom{k+\ell-4}{k-2} + 1$.
\end{problem}

\begin{problem}
\label{probl:k_cups,l_caps}
Prove that $f(k,\ell)= \binom{k+\ell-4}{k-2} + 1$.
\end{problem}

\begin{problem}
Prove that $N(n)\le \binom{2n-4}{n-2} + 1$.
\end{problem}

\begin{problem}
Prove that $N(n)\le \binom{2n-5}{n-3} + 2$.
\end{problem}

\subsubsection{Indivisibility Coefficient}

\begin{problem}
%Шортлист-96
Do there exists two disjoint finite sets $A$ and $B$ in the plane
such that the following two conditions hold:

($i$) No three points of the set $M:=A\cup B$ are on a line,
and the distance between any two points of $M$ is at least 1.

($ii$) Any triangle with vertices belonging to set $A$ contains
a point from $B$ and any triangle with vertices belonging to set $B$
contains a point from $A$?
\end{problem}


\begin{problem}
For any positive integer $n$ find maximum possible $k$ such that
{\it any $n$ points in general position in the plane can be painted in
red and blue in such a way that after any $k$ points are removed convex
hulls of remaining red and blue points overlap.\/}
Prove that the ratio $k/n$ can be arbitrary close to $1/2$ if $n$ is
sufficiently large.
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{Solutions}

\subsection{Single Convex Polygon}

\begin{solution}
%even-odd
Assume the converse, then one of the points is a convex combination of
three others, for example, $A_1\in\triangle
A_2A_3A_4$.  We consider parity of triangle $XYZ$ to be a
modulo 2 reminder and denote it by ${\cal O}(XYZ)$.  Then
$$
{\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\,,
$$
where the last term corresponds to the point $A_1$ that lies inside triangle
$A_2A_3A_4$ and contributes to its parity but does not lie inside any
of the other three triangles. The equality above can not be satisfied
if all four parities are equal; thus  our assumption was
wrong and the points are in convex position.
\end{solution}

\begin{solution}
%orientation
Assume the converse, then one of the points is a convex combination of
three others, say, $A_{i_1}\in\triangle A_{i_2}A_{i_3}A_{i_4}$.
Without loss of generality we may assume that triangle
$A_{i_2}A_{i_3}A_{i_4}$ is well-oriented and $i_2<i_3<i_4$.  It can be
easily checked that no matter how $i_1$ is related to $i_2$, $i_3$, $i_4$,
all the triangles can not have the same orientation.  For example, if
$i_2<i_1<i_3$ then triangles $A_{i_2}A_{i_1}A_{i_3}$ and
$A_{i_2}A_{i_1}A_{i_4}$ have different orientation; other cases can be
dealt with similarly.
\end{solution}

\begin{solution}
See\ fig.~\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 четырехугольников
(a) Choose a line not parallel to any line passing through two
marked points.  Draw 401 lines parallel to the chosen line in
such a way that there is exactly five of our points in each of
400 strips. By~\ref{N(4)=5} we can choose a convex quadrangle in each
strip.

\smallskip
(b) We call a set of points in general position
\emph{splittable} if there exists a line that cuts four
points in convex position off it, otherwise we call the set
\emph{nonsplittable}. To solve the problem it suffices to show that
any nine-point set is splittable.

Let $A$, $B$, $C$ be points of the given set. We call angle $\angle
ABC$ empty if it contains no points of our set. Then the following
lemma holds.

\begin{lemma}
For each side $AB$ of the convex hull of a nonsplittable set
there exists a point $C$ from this set such that both angles
$\angle ABC$ and $\angle BAC$ are empty.
\end{lemma}

Such (unique) point $C$ will be called \emph{the closest} point
to side$AB$.

\begin{figure}
\hbox{}\hskip5cm\special{em:graph ris1.bmp}
\vskip 4cm
\caption{Construction of the closest point}
\label{ris1}
\end{figure}

\begin{proof}
Let our nonsplittable set lie to the left of us when we move from
point $A$ to point $B$. Take ray $AB$ and start turning it
counterclockwise around point $A$ until it hits a point of our set
which we call point~$D$.  Similarly start turning ray $BA$ clockwise
around point $B$ until it hits a point of our set which we call point~$C$.
If points $C$ and $D$ coincide then this is the point we are
looking for. Otherwise if there are no other points of our set inside
triangle~$CDE$ (see~fig.~\ref{ris1}) then convex quadrangle $ABDC$ can
be cut off the set which contradicts its nonsplittability;
if there are other points of our set inside $CDE$ we can still cut a
convex quadrangle off the set; to do so, proceed as follows.
Start turning ray $CB$ counterclockwise around point $C$ until it
hits a point of our set which we call point~$F$.
Shifting line $CF$ a little gives us a line cutting convex
quadrangle $ABFC$ off our set.  \end{proof}

It is obvious that the same point can't be the
closest to different sides.

Turn back to the proof of splittability of any nine-point set.
By the property of splittable sets derived in the above lemma, the
convex hull of a nonsplittable nine-point set can only be either
triangle or quadrangle. Consider both these cases.

Let the convex hull of our nine-point set be quadrangle $ABCD$;
let $K$,~$L$, $M$, $N$ be the points closest to its sides and
$O$ be the intersection point of its diagonals (see~fig.~\ref{ris2}).
Without loss of generality we may assume that the ninth point~$Z$
of our set lies inside triangle $AOB$.  Then one of quadrangles
$ANZK$ and $BKZL$ is convex and can be cut off our set. This
contradicts nonsplittability.

\begin{figure}
\hbox{}\hskip5cm\special{em:graph ris2.bmp}
\vskip 4cm
\caption{Quadrangle as the convex hull}
\label{ris2} \end{figure}

Now let triangle $ABC$ be the convex hull of our nine-point set;
let points $K$, $L$, $M$ be points closest to its sides.
The other three points lie one in each triangle $AKM$, $BKL$, $CLM$.
Indeed, if, say, triangle $AKM$ contains no points of our set then a
parallel shift of line $MK$ away from point~$A$ cuts convex quadrangle
$AK?C$ off the set.  Let triangles $AKM$, $BKL$, $CLM$
contain points $P$, $Q$,~$R$, respectively. At least one of the
segments $PQ$, $QR$, $RP$ intersects exactly two of the segments $AL$,
$BM$, $CK$ (prove it!). Without loss of generality assume that segment
$PQ$ intersects segments $BM$ and $CK$ and does not intersect segment
$AL$.  Then convex quadrangle $BKPQ$ can be cut off by a line parallel
to $AL$.

\begin{figure}
\label{ris3}
\hbox{}\hskip5cm\special{em:graph ris3.bmp}
\vskip 4cm
\caption{Triangle as the convex hull}
\end{figure}


\smallskip
(c) No, not necessarily. Choose any 1999 points on an appropriate
convex curve, such as one of the branches of a hyperbola
(say, $y=1/x$) and the last point in its center (in the origin).
Then this last point forms no convex quadrangle with any three of
the others.  \smallskip

(d) We have no idea.
\end{solution}

\begin{solution}
%Существование N(n)
The statement follows immediately from problems \ref{even-odd},
\ref{orientation} by Ramsey theorem. It suffices to draw on the
following special case of the theorem.

\begin{theorem}[Ramsey]
For any positive integer $k$ there exists a positive integer $R_3(k,k)$
with the following property: if there is a set of at least $R_3(k,k)$
points in general position in the plane and all triangles with
vertices at these points are split into two classes then there
exist $k$ points such that all triangles with vertices in them
belong to one class.  \end{theorem}

Lower bound $N(n)\le R_3(n,n)$ is quite far from the optimal.
What is known about Ramsey numbers of order three is that
$2^{bn^2}\le R_3(n,n)\le 2^{c^n}$ for some constants $b$ and $c$.
Results of section  ``Cups and caps'' suggest that these numbers are
too large compared to $N(n)$.
\end{solution}

\begin{solution} %N(5)=9
Figure~\ref{8points} gives an example of eight points determining no
convex pentagon.

\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}
(a) F.~Petrov has suggested the following construction. For every
even $n$ construct a set~$A_n$ of $2^{n/2}$ points such that no $n$
of them are in convex position. The construction develops inductively.
As the base of induction for $n=4$ consider a set of four points
that are vertices of a non-convex quadrangle. If set $A_n$ is
already constructed, choose small enough vector $\overrightarrow{v}$
not collinear with any of the lines determined by points of $A_n$ and
define $A_{n+2}=A_n\cup (A_n+\overrightarrow{v})$. It can be
easily checked that set $A_{n+2}$ contains no convex $(n+2)$-gons.

\smallskip
(b) We cite the proof from  \cite{MorrisSoltan},
which has its source in \cite{Erdos1}. Construct a set $X$ of $2^{n-2}$
points no $n$ of which are vertices of a convex polygon.
Let $T_i$, $i=0$, \dots, $n-2$, be a set of $\binom{n-2}i$ points
containing no $(i+2)$-caps or $(n-i)$-cups. Such a set exists by the
result of problem~\ref{probl:k_cups,l_caps} and in addition we can
demand that all segments with endpoints from $T_i$ have slopes
less than or equal to one in absolute value.

For $i=0$, \dots, $n-2$ place a small copy of set $T_i$ in the
neighborhood of the point of the unit circle that has angle
$\frac\pi4 - \frac{i\pi}{2(n-2)}$ with the real axis.
Set $X$ is then the union of these sets $T_i$. Then
$$
|X|=\sum_{i=0}^{n-2} \binom{n-2}i=2^{n-2}\,.
$$
Assume that $Y\subset X$ is a subset of points in convex position.
Let $k$ and $\ell$ be maximum and minimum values of $i$ such that
$Y\cap T_i \ne\emptyset$. If $k=\ell$ then $Y$ contains no
$(k+2)$-caps and no $(n-k)$-cups. If instead $k\ne\ell$ and $Y$ is
convex then our construction guarantees that

1) $Y\cap T_k$ is a cap of at most $k+1$ points;

2) $Y\cap T_\ell$ is a cup with at most $n-\ell-1$ points;

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

Therefore,
$$
|Y|\le k+1  +  \ell-k-1  + n-\ell-1 \,.
$$

We have proved that no $n$ points of $X$ are in convex position.
\end{solution}

\begin{solution}
We see if anyone can solve it; we can not.
\end{solution}


\begin{solution}
We cite the solution from \cite{mmo}, problem 66.

By problem \ref{N(4)=5}, for every five points in general position in
the plane one can choose four point in convex position.
For each of $\binom n5$ groups of five points chosen among given
$n$ points mark four points in convex position.
Any convex quadrangle was marked at most $n-4$ times since any four
points can be completed to a set of five in $n-4$ ways only.
Therefore we will end up with at least $\binom n5/(n-4)$ points; this
is exactly what is stated.
\end{solution}


\subsection{Empty Convex Polygons}

\begin{solution}
(a) It is clear for everyone who knows what triangulation means. Or
consider the triangle with the smallest area with vertices in given
points.

(b) We took the problem from \cite{mmo}, problem~99.
Answer: yes.
Consider the convex hull of all points; it is a polygon.
Let $AB$ be a side of this polygon. Choose the point (call it
point~$C$) for which angle $ACB$ is maximum possible; then the
circumcircle of triangle $ABC$ is what we are looking for.

\end{solution}

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

\begin{solution} %H(5)=10
Figure~\ref{9points} shows a set of nine points forming no empty convex
pentagon.

\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.}
\label{9points}
\end{figure}
\end{solution}

\begin{solution}
%H(7) не существует
This solution comes from~\cite{Valtr}. Consider only sets where
$x$-coordinates of all points are different.
By  $x(A)$ denote $x$-coordinate of point~$A$. We call a set of
points  $k$-closed from above for each
$k$-cup $A_1A_2\dots A_k$ in it there exists a point~$A$ such that
${x(A_1)<x(A)<x(A_k)}$ and $A$ lies above broken line $A_1A_2\dots A_k$
(polygon $AA_1A_2\dots A_k$ here need not be convex).
Similarly (employing $k$-caps) we define sets $k$-closed from below.
We call a set $k$-closed if it is $k$-closed both from above and from
below.

For each $k\in \mathbb{N}$ construct a set $X_k$ consisting of
$2^k$ points that is  4-closed and has no empty convex heptagons
(and such that $x$-coordinates of all its points are different).
induction base is the one-point set.

Suppose $X=X_{k-1}$ is already constructed. Let
$Y=X_{k-1}+\epsilon$ where $\epsilon$ is a vector with small enough
$x$-coordinate and large enough $y$-coordinate.  Then

\begin{itemize}
\item[(i)] $x$-coordinates of points of sets $X$ and $Y$ alternate;

\item[(ii)] set $X$ lies below any line connecting points of~$Y$;

\item[(iii)] set $Y$ lies above any line connecting points of~$X$.
\end{itemize}

Assign $X_k=X\cup Y$.

\smallskip
1. Check that set $X_k$ contains no empty convex heptagons.
Assume the converse. Let $Z$ be a convex heptagon of points from~$X_k$.
Denote $X'=A\cap Z$, $Y'=A\cap Z$. Sets $X'$ and $Y'$ are nonempty
since neither $X$ nor $Y$ contains empty convex heptagons.
By (ii) and~(iii) $X'$ is a cup and $Y'$ is a cap.  If set $X'$
consists of at least four points, then by the fact that $X$ is
4-closed from above (and again drawing on  (ii),~(iii)) the point of
set~$X$ that makes this 4-closing lies inside heptagon~$Z$.
The case when  $Y'$ has at least four points is considered
similarly.

\smallskip
2. Check that set $X_k$ is 4-closed. Let $ABCD$ be a
4-cup. If $B\in Y$ then points $A$ and $C$ can not belong to
$X$ simultaneously by~(iii). Now if, say, $C\in Y$, then by
convexity all four points $A$, $B$, $C$, $D$ belong to~$Y$ and
because set $Y$ is 4-closed we can find a point in $Y$ that
closes this quadruple from above.
Similar considerations work if $C\in Y$. If instead both points
$B$, $C$ are in $X$ then by~(i) there exists a point $E\in
Y$, $x(B)<x(E)<x(C)$ that lies above segment $BC$ and thus closing our
4-cup from above.  Similarly you can check that 4-cups are
closed from below.

\smallskip
Therefore we have constructed a family of sets $X_k$ consisting of
$2^k$ points and containing no empty convex heptagons.  Now one
can easily construct a set of $n$ points containing no empty convex
heptagons for any positive integer $n$. To do this it suffices to take
set $X_k$, $2^k>n$ and remove from it one by one its extremum points until
only $n$ points are left.

\end{solution}

\begin{solution}
(a)
\end{solution}


\subsection{Other Generalizations}

\begin{solution}
Let us prove that $N_d(n)\le N(n)$.
In $\mathbb{R}^d$ choose a two-dimensional plane in such  a way
that projections of points from our set onto it do not coincide
and form a set in general position.
If the original set (and hence its projection)
contains at least $N(n)$ points then some $n$ points of the projection
form a convex $n$-gon. Now corresponding points of the original set are
in convex position since the property of a point
``to be a convex combination of other points'' is preserved under
projection.  \end{solution}

\begin{solution}
Uhu, an open question.
\end{solution}

\begin{solution}
The statements of this and the following problems, together
with the proofs are taken from~\cite{Bisztriczky}.

\smallskip
(a) If a configuration of five ovals has no four ovals in convex
position then any set of three, four or all five ovals in the
configuration determines a triangle. That contradicts to the
statement of the next point of the problem.

\smallskip
(b) We say that two (overlapping) ovals $X$
and $Y$ \emph{form  a cross} if both sets $X\setminus Y$ and
$Y\setminus X$ are disconnected. If ovals do not form a cross, we
say that they have simple overlapping (possibly empty).
If ovals $A_1$, $A_2$, \dots determine a convex $k$-gon and for all
vertices $A_i$ of this $k$-gon ovals $A_i$ and
$\conv(\bigcup\limits_{j\ne i} A_j)$ have simple overlapping
then we say that this $k$-gon is simple.  For the case of a simple
polygon the order of vertices is well defined.

It follows directly from the hypothesis that
\begin{equation}\label{eqn:l-gon}
\mbox{any $\ell\le m$ ovals from family
$\Phi$ determine an $\ell$-gon.}
\end{equation}

Now any $\ell>m$ ovals $A_1$, $A_2$, \dots, $A_{\ell}$ of family
$\Phi$ form a simple $m$-gon~$M$. Indeed, otherwise one
of the vertex ovals, say, $A_1$, splits polygon $M$ into two parts.
Since the ovals are disjoint, a nonvertex oval, say, oval
$A_{m+1}$ is contained in one of the halves of polygon~$M$ which
contradicts~(\ref{eqn:l-gon}).

Let family $\Phi$ have $m+2$ ovals
$A_1$, $A_2$, \dots, $A_{m+2}$ that form an $m$-gon $M$ with vertices
$A_1$,~\dots,~$A_m$. Denote $M_i=M\setminus A_i$, $1\le
i\le m$. As we have checked $M_i$ is a simple $m$-gon; on of its
vertices is either $A_{m+1}$ or $A_{m+2}$.  Since $m\ge 3$ we may
assume that oval $A_{m+1}$ is a vertex of two polygons from $M_i$,
say, $M_1$ and $M_j$. In this case $A_{m+2}\subset M_1 \cap M_j$.

Vertices $A_1$ and $A_j$ must be adjacent in polygon~$M$,
since otherwise $M_1\cap M_2=\conv(\bigcup\limits_{i\ne1, j}A_i)$
is an ($m-1$)-gon, even though it contains $m$ ovals from family~$\Phi$,
but this contradicts~(\ref{eqn:l-gon}). Now if
$A_1$ and $A_j$ are adjacent vertices of polygon~$M$, say, for
$j=2$, then
$$ 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}), $$
and $A_{m+2}$ is contained in one of these convex hulls, which is again
impossible.
\end{solution}

\begin{solution}
Proof is the induction on $n$ with making use of Ramsey theorem and
the statement of problem~\ref{lem:ovaly}. We will need the following
version of Ramsey theorem:

\begin{theorem}[Ramsey]
For any positive integers $n$, $k$, $\ell$ there exists a positive
integer $R_n(k,\ell)$ with the following property: if a set contains at
least $R_n(k,\ell)$ points and all $n$-subsets of points are split into
two classes than either there exist $k$ points for which all
$n$-subsets are in the first class or there exist $\ell$ points
for which all $n$-subsets are in the second class.
\end{theorem}

Induction base $n=4$ is the statement of problem~\ref{lem:ovaly}~(a).
Suppose that we have already proved that $G(n-1)$ is finite.
Let us prove that $G(n)\le R_{n-1}(n+1, G(n-1)+1)$.

Consider a set $\Omega$ consisting of $R_{n-1}(n+1, G(n-1)+1)$ ovals
and split all its ($n-1$)-subsets of ovals into two classes depending
on whether or not these ovals determine a convex ($n-1$)-gon.
Then either there exists a set $\Omega_1$
of $n+1$ ovals any $n-1$ of which determine a ($n-1$)-gon or there
exist $G(n-1)+1$ ovals no $n-1$ of which determine a ($n-1$)-gon.
The latter is impossible by definition of number $G(n-1)$
and the former is impossible too if no $n$ ovals from set $\Omega$
determine an $n$-gon. Indeed, in this case any $n$ ovals of set
$\Omega_1$ determine an ($n-1$)-gon and, as it is easy to figure
out, all $n+1$ ovals of set $\Omega_1$ only determine an ($n-1$)-gon.
Now the size of set $\Omega_1$ contradicts the statement of
problem~\ref{lem:ovaly}~(b).
\end{solution}

\begin{solution}
The statement of the problem follows immediately from Erd\H{o}s
theorem~\ref{Erdos-monoton}.  Indeed, point $A(y_1,
y_2, \dots, y_d)$ lies between points $B(x_1, x_2, \dots, x_d)$ and
$C(z_1, z_2, \dots, z_d)$ if for all $k$, $1\le k\le d$,
sequence $(x_k, y_k, z_k)$ is monotonic.

Arrange our $2^{2^{d-1}}+1$ points in increasing order of their first
coordinates. By Erd\H{o}s theorem there exists a subsequence of
$2^{2^{d-2}}+1$ points second coordinates of which are monotonic.
Again by Erd\H{o}s theorem there exists a subsequence in this
subsequence with monotonic third coordinates, and so on.
After applying Erd\H{o}s theorem $d-1$ times we will end up with a
sequence of $2^{2^0}+1=3$ points with monotonic coordinates; then
the midpoint of these lies between two endpoints.

To show that the bound in the statement of the problem is exact
note, in addition to Erd\H{o}s theorem, that for any pair of numbers
$p$ and $q$ one can easily construct an example of a sequence
of length $pq$ that has neither increasing subsequence of length
$p+1$ no decreasing subsequence of length $q+1$.  For example,
split all numbers from 1 to $pq$ onto $q$ groups of $p$ consecutive
numbers each and arrange these groups in order of decreasing first
terms. Making use of this note we can, drawing on the decomposition
above, easily construct a set of $2^{2^{d-1}}$ points none of
which lies between two others.
\end{solution}

\begin{solution}
We present a well known argument employing Robinson-Shensted-Knuth
algorithm. Consider our sequence. Write down its first term in the
upper left square of a sheet of the grid paper. Now we add new terms and
rearrange those that have been written earlier according to the
following algorithm:

\begin{description}

\item[Step 1.] Take a term of the sequence and call it current
number. Call the upper left square of the sheet current square.

\item[Step 2.] If the current square is empty, fill it with the
current number and switch to Step~1, otherwise switch to Step~3.

\item[Step 3.] If the current number is smaller than the number in
the current square, move one square to the right, call this new
square current and switch to Step 2; if current number more than that
in the current square, write current number in the current square,
call current the number just removed from there, move one square
down, call this new square current and switch to Step 2.
\end{description}

After this procedure is completed terms of our sequence will be
arranged in a figure called Young diagram.
Young diagram consists of several horizontal rows of squares aligned
along their leftmost squares where each new row contains at most as
many squares as the previous one. Note that if
the numbers occupy $pq+1$ squares then in the resulting diagram
either the first row has more than $q$ squares or the first column has
more than $p$ squares (otherwise the diagram would fit into rectangle
$q\times p$ and would consist of at most $pq$ squares). Both cases
mean that there exists a required subsequence.

\input lines.tex
\begin{figure}
\hfil\hbox{\vbox{\lines8
 _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|
|_|_|_|_|_|_|
|_|_|_|_|_|
|_|_|
|_|
|_|}}\hfil
\caption{A Young diagram}
\end{figure}

\end{solution}

\subsection{After the Semifinal}

\begin{solution}
We need the following refinement of Ramsey theorem.

\begin{theorem}
Let $M$ be a countable set and $k$ be an integer.
Let all $k$-element subsets of $M$ be split into two classes.
Then there exists an infinite subset $L\subset M$ such that all
$k$-element subsets of $L$ belong to the same class.
\end{theorem}

The proof involves induction on $k$ and is done similarly to
the usual Ramsey theorem.

In our set choose a countable subset $M$ and enumerate its points.
Split all triangles with vertices in points of $M$ into two classes
according to their orientation (as in problem~\ref{orientation}). By
the refined Ramsey theorem for an infinite subset $L\subset M$ all
triangles with vertices from $L$  will have the same orientation
which proves the statement of the problem.

\end{solution}


\subsubsection{Cups and Caps}

\begin{solution}
We cite the solution from \cite{MorrisSoltan}, with the original source
in \cite{ErdosSzekeres}. The inequality follows from
recurrence relation
\begin{equation}
\label{rec-nerav}
f(k,\ell)\le f(k-1,\ell) + f(k, \ell-1) - 1
\end{equation}
and initial conditions $f(k,3)=f(3,k)=k$.

Let us prove inequality~(\ref{rec-nerav}). Let a set
$X$ consist of $f(k-1,\ell) + f(k, \ell-1) - 1$ points.
Consider all possible $(k-1)$-cups from set~$X$.
Let $Y$ be the set of leftmost points of these cups.
Then set $X\setminus Y$ has no $(k-1)$-cups. If this set
contained at least $f(k-1,\ell)$ points then it would have an
$\ell$-cap. Suppose set $X\setminus Y$ contains less than
$f(k-1,\ell)$ points, then set $Y$ contains at least $f(k,\ell-1)$
points. If it has no $k$-cups then it must have an $(\ell-1)$-cap,
which we denote by
$$
A = \{ (x_1, y_1), (x_2, y_2), \dots, (x_{\ell-1},y_{\ell-1})
\}\,.
$$
Besides consider $(k-1)$-cup
$$
U= \{ (x_{j_1}, y_{j_1}), (x_{j_2}, y_{j_2}), \dots,
(x_{j_{\ell-1}},y_{j_{\ell-1}}) \}
$$
in set $X$ for which point $(x_\ell,y_\ell)$ is the leftmost
point (so in our notation ${j_1=\ell-1}$). It can easily be
seen that either $(x_{\ell-2},y_{\ell-2})\cup U$ is a $k$-cup or
$A\cup (x_{j_2},y_{j_2})$ is an $\ell$-cap.
\end{solution}

\begin{solution}
The formula is obvious for $k=3$ or $\ell=3$. We prove the
formula by induction. Suppose that there exists a set $A$
of $\binom {k+\ell-5}{k-3}$ points that contains neither
$(k-1)$-cups nor $\ell$-caps and set $B$ of
$\binom{k+\ell-5}{k-2}$ points that contains neither $k$-cups nor
$(\ell-1)$-caps. Consider parallel translations of these sets
such that

1) set $B$ lies to the right of set $A$, i.e., $x$-coordinate of any
point of $B$ is greater than that of any point of~$A$;

2) the slope of each line connecting a point of
$A$ with a point of~$B$ is greater than the slope of each line
connecting two points of $A$ or two points of~$B$.

Clearly each cup from set $A\cup B$ that contains points from both
sets $A$ and $B$ contains at most one point from $B$,
thus set $A\cup B$ has no $k$-cups.
Similarly, this set has no $\ell$-caps.  Therefore
$$ f(k,\ell)\ge \binom{k+\ell-5}{k-3} +\binom{k+\ell-5}{k-2}+1=
\binom{k+\ell-4}{k-2}+1\,.
$$
\end{solution}

\begin{solution}
This result follows immediately from the obvious inequality
$N(n)\le f(n,n)$.

\smallskip
The statement proved above was first obtained by Erd\H{o}s
in~\cite{ErdosSzekeres} and for 63 years it was the best known upper
bound for numbers $N(n)$. A few years ago several papers appeared
almost simultaneously where slightly stronger bounds were proved, of
which the strongest and still the simplest is presented in the next
problem (source \cite{TothValtr98}).
\end{solution}

\begin{solution}
Let $A$ be an extremum point of~$X$. Choose a point $B$ outside the
convex hull of $X$ in such a way that no line passing through any two
points of set $X\setminus A$ crosses segment $AB$.
Through point $B$ draw any line $p$ that does not cross the convex hull
of set $X$. Carry out projective transformation~$T$ that
maps line $p$ into the infinitely distant line and segment~$AB$ into a
ray going straight down from point $T(A)$. Then obviously

(1) set $Y\subset X$ is in convex position if and only if set $T(Y)$
is in convex position;

(2) set $Z\subset X$ containing point $A$ is in convex position if and
only if $T(Z\setminus A)$ is a cap.

Let set $X$ contain $\binom{2n-5}{n-3}+2$ points. Then the set
$T(X\setminus A)$ according to the statement of
\ref{probl:k_cups,l_caps-nerav} contains an $(n-1)$-cap or an
$n$-cup. Therefore $X$ contains $n$ points in convex position.
\end{solution}


\subsubsection{Indivisibility Coefficient}

\begin{solution}
No, there exist no such sets. Indeed, if they do, choose any ten points
from set $A$ and let $S$ be the set of these ten points and all points
of set $A$ that lie in their convex hull. Then since $H(5)=10$
(see \ref{problemH(5)}) there exist five points in set $S$
that form a convex pentagon and having no other points of set~$A$
inside. Denote by $B_1B_2B_3B_4B_5$ such a pentagon.
Let $C_1$, $C_2$, $C_3$ be points of set $B$ contained in triangles
$B_1B_2B_3$, $B_1B_3B_4$ and $B_1B_4B_5$, respectively. Then there
exists a point from set $A$ that lies in triangle $C_1C_2C_3$ and hence
in pentagon $B_1B_2B_3B_4B_5$.

\smallskip
Here is a similar consideration drawing on no special facts.

\begin{lemma}
If the hypothesis of the problem is satisfied then the convex hull of any
five points of set $A$ contains at least one other point of set~$A$.
\end{lemma}

\begin{proof}
If the convex hull $S$ of five chosen points is a $k$-gon ($k=3$,
4,~5), that is, if $5-k$ of the chosen points lie inside~$S$, then we
can split this $k$-gon into $8-k$ triangles with vertices
at these five points (sum up the angles!). Thus there are $8-k$ points
of set~$B$ inside polygon~$S$. Then we can find $6-k$
nonoverlapping triangles with vertices at these points
and hence there is at least one 'new' point of set~$A$
inside~$S$.
\end{proof}

The statement of the problem follows immediately from the lemma.
Indeed, suppose such sets exist. Fix a big enough circle, mark all
points of set~$A$ inside it and choose five points with the smallest
area of their convex hull (this is possible since only
finitely many points fit into the circle because
points are isolated from each other).
By the lemma there exists one more point of~$A$ inside the convex hull
of these five points. Removing one of the vertices from the convex hull
of five original points gives us five points with smaller area of
their convex hull. Contradiction.

\end{solution}

\begin{solution}
%k/n-> 1/2
Let $p$ and $s$ be any large enough positive integers (to be chosen
later).  Suppose $n=p N(2s)$.  Then we can choose at
least $\frac{(p-1)N(2s)}{2s}$ convex $2s$-gons from our set that have
no common vertices. We color vertices of each of these $2s$-gons
into red and blue alternately. It can be easily checked that
one must remove at least $s-1$ vertices from each of
these $2s$-gons in order to convex hulls of its blue and red vertices
not to overlap.  Thus for convex hulls of red and blue points not to
overlap one must remove at least
$\frac{(s-1)(p-1)N(2s)}{2s}$ points.  Therefore
$$
\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\,.
$$
This expression can be arbitrarily close to 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$ точек в выпуклом положении.
