%\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$, $i2$.
\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_2n$ 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$ точек в выпуклом положении.