discrete.tex

\csname @openrightfalse\endcsname
\chapter{Discrete geometry}

In this chapter, we consider geometrical problems with a strong combinatoric flavor.
No special prerequisite is needed.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Round circles in 3-sphere}\label{Round circles}

\begin{pr}
Suppose that $\mathcal{C}$ is a finite collection of pairwise linked round circles in the unit 3-sphere. 
Prove that there is an isotopy of $\mathcal{C}$ that moves all of them into great circles.
\end{pr}


\parit{Semisolution.}
For each circle in $\mathcal{C}$, consider the plane containing it.
Note that the circles are linked 
if and only if 
the corresponding planes intersect at a single point inside the unit sphere $\mathbb{S}^3\subset \RR^4$.

Consider the collection of circles formed by the intersections of the planes with the sphere of radius $R\ge 1$.
Rescale the sphere and pass to the limit as $R\to\infty$.  
This way we get the needed isotopy.\qeds

This problem was discussed 
by Genevieve Walsh \cite{walsh}.
The same idea was used by Michael Freedman and  Richard Skora to show that any link made from pairwise not linked round circles is trivial; 
in particular, Borromean rings cannot be realized by round circles
\cite[see Lemma 3.2 in ][]{freedman-skora}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Box in a box}\label{box-in-box}

\begin{pr}
Suppose a rectangular parallelepiped with sides $a,b,c$ 
lies inside another rectangular parallelepiped with sides $a',b',c'$. 
Show that 
\[a'+b'+c'\ge a+b+c.\]

\end{pr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Piercing the cube}\label{Piercing the cube}

\begin{pr}
Let $\Pi$ be a $k$-plane that passes thru the center of a unit $n$-cube $Q$.
Show that $k$-area of the intersection $\Pi\cap Q$ is at least 1.
\end{pr}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Harnack's circles}\label{Harnack}

\begin{pr}
Prove that a smooth algebraic curve of degree $d$ in $\RP^2$ consists of at most $n=\tfrac12\cdot(d^2-3\cdot d+4)$ connected components.
\end{pr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Two points on each line}\label{2pts-on-line}

\begin{pr}
Construct a set in the Euclidean plane that intersects each line at exactly 2 points. 
\end{pr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Balls without gaps}
\label{Balls without gaps}

\begin{pr}
Let $B_1,\dots,B_n$ be balls  
of radii $r_1,\dots,r_n$ 
in a Euclidean space.
Assume that no hyperplane divides the balls into two
non-empty sets without intersecting at least one of the balls. 
Show that the balls
$B_1,\dots,B_n$ can be covered by a ball of radius
$r=r_1+\dots+r_n$.

\end{pr}

\subsection*{Covering lemma}

\begin{pr}
Let $\{B_i\}_{i\in F}$ be any finite collection of  balls in $\RR^m$. 
Show that there is a subcollection of pairwise disjoint balls $\{B_i\}_{i\in G}$, $G\subset F$
such that
\[\vol \left(\bigcup_{i\in F}B_i\right)\le 3^m\cdot \vol \left(\bigcup_{i\in G}B_i\right).\]
\end{pr}



{

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

\begin{wrapfigure}{r}{27 mm}
\vskip0mm
\centering
\includegraphics{mppics/pic-902}
\end{wrapfigure}

\subsection*{Kissing number\easy}\label{pr:Kissing number}


Let  $W_0$ be a convex body in $\RR^m$.
We say that $k$ is the \index{kissing number}\emph{kissing number} of $W_0$ (briefly $k=\mathop{\rm kiss}W_0$)
if $k$ is the maximal integer such that there are $k$ bodies $W_1,\dots,W_k$ such that 
(1) each $W_i$ is congruent to $W_0$,
(2) $W_i\cap W_0\not=\emptyset$ for each $i$ 
and (3) no pair $W_i,W_j$ has common interior points.

}

As you may have guessed from the diagram, the kissing number of the round disk in a plane is $6$.

\begin{pr}
Show that for any convex body $W_0$ in $\RR^m$ we have that
$$\mathop{\rm kiss}W_0\ge \mathop{\rm kiss}B,$$
where $B$ denotes the unit ball in $\RR^m$.
\end{pr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Monotonic homotopy}
\label{mono-homotopy}




\begin{pr}
Let $F$ be a finite set and $h_0,h_1\: F\to\RR^m$ be two maps.
Consider $\RR^m$ as a subspace of $\RR^{2\cdot m}$.
Show that there is a homotopy  $h_t\:F\z\to\RR^{2\cdot m}$ from $h_0$ to $h_1$ such that  the function 
$t\z\mapsto |h_t(x)-h_t(y)|$
is monotonic for any pair $x,y\in F$.
\end{pr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Facet cover}\label{Facet cover}

\begin{pr}
Show that any facet of a convex polyhedron can be covered by the remaining facets.
\end{pr}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Cube}\label{Cube}

\begin{pr}
Half of the vertices 
of an $m$-dimensional cube
are colored in white and the other half in black.
Show that the cube has at least $2^{m-1}$ edges connecting vertices of different colors. 
\end{pr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Geodesic loop}\label{Geodesic loop}

\begin{pr}
Show that the surface of a cube in $\RR^3$
does not admit a geodesic loop with a vertex as the base point.
\end{pr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Right and acute triangles}\label{Right and acute triangles}

\begin{pr}
Let $x_1,\dots,x_n\in\RR^m$
be a collection of points such that any triangle $[x_ix_jx_k]$ is right or acute.
Show that $n\le 2^m$.
\end{pr}

\subsection*{Upper approximant}\label{One-sided approximants}

\begin{pr}
Let $\mu$ be a Borel probability measure on the plane.
Show that given $\eps>0$, there is a finite set of points $S$ that intersects every convex figure of measure at least $\eps$.
Moreover, we can assume that $|S|$ --- the number of points in $S$, depends only on $\eps$ (in fact, one can take $|S|=\lceil\tfrac1{\eps^5}\rceil$).
\end{pr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Right-angled polyhedron\thm}\label{Right-angled polyhedron}

A polyhedron is called {}\emph{right-angled} if all its dihedral angles are right.

\begin{pr}
Show that in all sufficiently large dimensions, there is no compact convex hyperbolic right-angled polyhedron. 
\end{pr}

Here is a summary of the Dehn--Sommerville equations that can help.

Let $P$ be a \index{simple polyhedron}\emph{simple} Euclidean $m$-dimensional polyhedron;
that is, exactly $m$ facets meet at each vertex of $P$.
Denote by $f_k$ the number of $k$-dimensional faces of $P$;
the array of integers $(f_0,\dots f_m)$ is called the $f$-vector of $P$.

Choose a linear function $\ell$ that takes different values on the vertices of~$P$.
The \index{index of vertex}\emph{index} of a vertex $v$ 
is defined as the number of edges $[vw]$ of $P$ such that $\ell(v)>\ell(w)$. 
The number of vertices of index $k$ will be denoted by $h_k$.
The array of integers $(h_0,\dots h_m)$ is called the $h$-vector of $P$.

Each $k$-face of $P$ contains a unique vertex that maximizes $\ell$.
If the vertex has index $i$,
then $i\ge k$, and then it is the maximal vertex of exactly $\tbinom i k$
faces of dimension $k$.
This observation can be packed in the following polynomial identity:
\[\sum_k h_k\cdot (t+1)^k=\sum_k f_k\cdot t^k.\]

This identity implies that the $h$-vector does not depend on the choice of $\ell$.
Changing the sign of $\ell$, we get that, the $h$-vector is the same for the reversed order;
that is,
\[h_k=h_{m-k}\quad\text{for all}\quad k.
\leqno({*})\]

The identities $({*})$ for all $k$ are called the Dehn--Sommerville equations.
They give a complete list of linear equations for $h$-vectors (and therefore $f$-vectors) of simple polyhedrons.
For more on the subject, see \cite[Chapter 9]{gruenbaum}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Real roots of random polynomial\easy}\label{Real roots of random polynomial}

Consider the \index{moment curv}\emph{moment curve} $\gamma_n\:t\mapsto(1,t,\dots,t^n)$  in $\RR^{n+1}$.
Let 
\[\ell_n=\length \tfrac{\gamma_n}{|\gamma_n|}.\]

\begin{pr}
Show that $\tfrac{\ell_n}{\pi}$ is the expected number of real roots of a polynomial of degree $n$ with independent normally distributed real coefficients.
\end{pr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Space coloring\easy}\label{Space coloring}

\begin{pr}
Let $A$ be a set of colored points in $\mathbb{R}^d$.
We are allowed to color any line containing at least $k$ already colored points.
Suppose that in a finite number of steps, we can color any point in $\mathbb{R}^d$.
What is the minimal number of points in $A$ as a function of $d$ and $k$?
\end{pr}





\section*{Semisolutions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\parbf{Box in a box.} 
Let $\Pi$ be a parallelepiped
with dimensions $a$, $b$, and $c$.
Denote by $v(r)$ the volume of the $r$-neighborhood of $\Pi$,
 
Note that for all positive $r$ we have
\[v_{\Pi}(r)=w_3(\Pi)+w_2(\Pi)\cdot r+w_1(\Pi)\cdot r^2+w_0(\Pi)\cdot r^3,\leqno({*})\]
where 
\begin{itemize}
\item $w_0(\Pi)=\tfrac43\cdot \pi$ is the volume of the unit ball,
\item $w_1(\Pi)=\pi\cdot (a+b+c)$,
\item $w_2(\Pi)=2\cdot(a\cdot b+b\cdot c+c\cdot a)$ is the surface area of $\Pi$,
\item $w_3(\Pi)=a\cdot b\cdot c$ is the volume of $\Pi$,
\end{itemize}

Let $\Pi'$ be another parallelepiped
with dimensions $a'$, $b'$ and~$c'$.
If $\Pi\subset \Pi'$,
then $v_{\Pi} (r)\le v_{\Pi'}(r)$ for any $r$.
For $r\to\infty$, these inequalities imply
\[a+b+c\le a'+b'+c'.\qedsin\]

\parit{Alternative proof.}
Note that the average length of the projection of $\Pi$ to a line is
$\Const\cdot(a+b+c)$ for some $\Const>0$.
(In fact, $\Const=\tfrac12$, but we will not need it.)

Since $\Pi\subset \Pi'$,
the average length of the projection of $\Pi$
cannot exceed the average length of the projection of $\Pi'$.
Hence the statement follows.
\qeds

The problem was discussed by Alexander Shen \cite{shen}.

A formula analogous to $({*})$
holds for an arbitrary convex body $B$ of arbitrary dimension $m$.
It was discovered by Jakob Steiner \cite{steiner}.
The coefficient $w_i(B)$ in the polynomial (with different normalization constants)
appears under different names, most commonly
\emph{intrinsic volumes} and
\emph{quermassintegrals}.
Up to a normalization constant,
they can also be defined as the average 
area of the projections of $B$ to the $i$-dimensional planes.
In particular, 
if $B'$ and $B$ are convex bodies such that $B'\subset B$,
then $w_i(B')\le w_i(B)$ for any $i$.
This generalizes our problem quite a bit.
Further generalizations lead to the theory of \index{mixed volumes}\emph{mixed volumes} \cite{burago-zalgaller}.

The equality $w_1(\Pi)=\pi\cdot (a+b+c)$ still holds for all parallelepipeds, not only rectangular ones.
In particular, if one parallelepiped 
lies inside another then the sum of all edges of the first one cannot exceed the sum for the second.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Piercing the cube.}
Observe that there is an odd increasing 1-Lipschitz function $\phi\:\RR\to(-\tfrac12,\tfrac12)$ that pushes the measure with the density $e^{-\pi x^2}$ to the Lebesgue measure on $(-\tfrac12,\tfrac12)$.

We can assume that $Q=\set{(x_1,\dots,x_n)\in \RR^n}{|x_i|\le \tfrac12}$.
Applying $\phi$ to each coordinate,
we get a 1-Lipschitz diffeomorphism from $\RR^n$ to the interior of $Q$ that pushes the measure with the Gauss density 
$\rho(x_1,\dots,x_n)=e^{-\pi (x_1^2+\dots+x_n^2)}$ to the Lebesgue measure on $Q$.

Note that the inverse image $\Pi'=\phi^{-1}(\Pi)$ is a symmetric $k$-surface in~$\RR^n$.
Since $\phi$ is $1$-Lipschitz, we get that the area of $\Pi\cap Q$ cannot be smaller than the $\rho$-weighted $k$-area of $\Pi'$.
Moreover, we have equality for coordinate $k$-planes.

Denote by $S_r$ the sphere of radius $r$ in $\RR^n$ centered at the origin.
Note that $\Pi'\cap S_r$ intersects each great $(n-k-1)$-sphere in $S_r$.
By Crofton's formula, we get that $(k-1)$-area of $\Pi'\cap S_r$ cannot be smaller than $(k-1)$-area of the great $(k-1)$-sphere in $S_r$.
By the coarea formula, the $\rho$-weighted $k$-area of $\Pi'$ cannot be smaller than $\rho$-weighted $k$-area of a $k$-plane that passes thru the origin --- hence the result.
\qeds

The problem was posed by Anton Good
and solved by Jeffrey Vaaler \cite{vaaler}.
The presented solution was found by Arseniy Akopyan, Alfredo Hubard, and Roman Karasev \cite{akopyan-hubard-karasev};
note that it proves the following more general statement:
\textit{If $f\:Q \to \RR^{n-k}$ is an odd continuous map, such that $Z = f^{-1}\{0\}$ is smooth $k$-surface, then the $k$-area of $Z$ is at least 1.}
The map $\RR^n\to Q$ was first used by Gilles Pisier \cite[p. 182]{pisier}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Harnack's circles.}
Let $\sigma\subset \RP^2$ be an algebraic curve of degree~$d$.
Consider the complexification $\Sigma\subset \CP^2$ of~$\sigma$.
Without loss of generality, we may assume that $\Sigma$ is regular.

Note that all regular complex algebraic curves of degree $d$ in $\CP^2$
are isotopic to each other in the class of regular algebraic curves of degree~$d$.
Indeed, the set of equations of degree $d$ that correspond to singular curves has real codimension 2.
It follows that the set of equations of degree $d$ that correspond to regular curves is connected.
Therefore, one can construct an isotopy from one regular curve to any other by changing continuously the parameters of the equations.

In particular, it follows that all regular complex algebraic curves of degree $d$ in $\CP^2$ have the same genus,
denote it by $g$.
Perturbing a singular curve formed by $d$ lines in $\CP^2$,
we can see that 
\[g=\tfrac12\cdot(d-1)\cdot(d-2).\]

The real curve $\sigma$ forms the fixed point set in $\Sigma$ by the complex conjugation.
In particular $\Sigma\setminus\sigma$ has at most two connected components.
Therefore, the number of components of $\sigma$ cannot exceed $g+1$.
\qeds

This problem is a background for Hilbert's 16th problem.
The inequality was originally proved 
by Axel Harnack using a different method \cite{harnack}.
The idea to use complexification is due to Felix Klein \cite{klein}.
In fact any number of connected components up to $g+1$ is realizable, with one exception:
if $d$ is odd, then $\sigma$ has at least one connected component. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Two points on each line.}
Take any complete ordering of the set of all lines 
so that each beginning interval has cardinality less than continuum.

Assume we have a set of points $X$ of cardinality less than continuum such that each line intersects $X$ in at most $2$ points.

Choose the least line $\ell$ in the ordering that intersects $X$ 
in $0$ or $1$ point.
Note that the set of all lines intersecting $X$ at two points has cardinality less than continuum.
Therefore we can choose a point on $\ell$ and add it to $X$ so that the remaining lines are not overloaded.

It remains to apply the well-ordering principle.
\qeds

This problem has an endless list of variations.
The following problem looks similar but far more involved;
a solution follows from the proof of Paul Monsky that a square cannot be cut into triangles with equal areas \cite{monsky}.

\begin{pr}
Subdivide the plane into three everywhere dense sets $A$, $B$, and $C$ such that each line meets exactly two of these sets.
\end{pr}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Balls without gaps.} 
Assume the mass of each ball is proportional to its radius.
Denote by $z$  the center of mass of the balls.
It is sufficient to show the following.
\begin{cl}{$({*})$}
The ball $B(z,r)$ contains all $B_1,\dots,B_n$.
\end{cl}

Assume this is not the case.
Then there is a line $\ell$ thru $z$, 
such that the orthogonal projection of a ball $B_i$ to $\ell$ 
does not lie completely inside the projection of $B$.
(This observation reduces the problem to the one-dimensional case.)

Note that the projection of all balls $B_1,\dots,B_n$ has to be connected and it contains a line segment longer than $r$ on one side from $z$. 
In this case, the center of mass of the balls projects inside of this segment --- a contradiction.
\qeds

The statement was conjectured by Paul Erdős.
The solution was given by Adolph and Ruth Goodmans
[see \ncite{goodman-goodman} and also \ncite{hadwiger}].

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

\parbf{Covering lemma.} 
The required collection $\{B_i\}_{i\in G}$ is constructed using the \emph{greedy algorithm}. 
We choose the balls one by one;
on each step we take the largest ball that does not intersect those which we have chosen already.

\medskip

Note that each ball in the original collection $\{B_i\}_{i\in F}$ intersects a ball in $\{B_i\}_{i\in G}$ with a larger radius.
Therefore 
\[\bigcup_{i\in F}B_i\subset \bigcup_{i\in G}3\cdot B_i,\leqno({*})\]
where $3\cdot B_i$ denotes the ball concentric to $B_i$ and three times larger radius.
Hence the statement follows.
\qeds

The constant $3^m$ can be improved slightly \cite{domotorp}.
For $m=1$ the optimal constant is $2$.
Possibly, for any $m$, the optimal constant is $2^m$;
it can not be smaller, an example can be found among collections of unit balls that contain a fixed point.

The inclusion $({*})$ is called the \emph{Vitali covering lemma}.
The following statement is called the \emph{Besicovitch covering lemma};
it has a similar proof.

\begin{pr}
For any positive integer $m$, there is a positive integer $M$ such that 
any finite collection of balls $\{B_i\}_{i\in F}$ in $\RR^m$ 
contains a subcollection $\{B_i\}_{i\in G}$
such that (1) center of any ball in $\{B_i\}_{i\in F}$ lies inside one of a ball from $\{B_i\}_{i\in G}$
and (2) the collection $\{B_i\}_{i\in G}$ can be subdivided into $M$ subcollections of pairwise disjoint balls.
\end{pr}

Both lemmas were used to prove the so-called \emph{covering theorems} in measure theory,
which state that ``undesirable sets'' have vanishing measures.
Their applications overlap but aren't identical, the \emph{Vitali covering theorem} works for nice measures in arbitrary metric spaces while the \emph{Besicovitch covering theorem} works in nice metric spaces with arbitrary Borel measures.

More precisely, Vitali works in arbitrary metric spaces with a \index{doubling measure}\emph{doubling measure} $\mu$;
the latter means that 
\[\mu [2\cdot B]\le C\cdot \mu B\] 
for a fixed constant $C$ and any ball $B$ in the metric space.
On the other hand, Besicovitch works for all Borel measures in the so-called \emph{directionally limited} metric spaces \cite[see 2.8.9 in][]{federer};
these include Alexandrov spaces with curvature bounded below.




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



\parbf{Kissing number.}
Set $n=\mathop{\rm kiss} B$.
Let $B_1,\dots, B_n$ be copies of the ball $B$ that touch $B$ and don't have common interior points.
For each $B_i$ consider the vector $v_i$ from the center of $B$ to the center of $B_i$.
Note that $\measuredangle(v_i,v_j)\ge \tfrac\pi3$ if $i\ne j$.

For each $i$,
consider the supporting hyperplane $\Pi_i$
of $W$
with the outer normal vector $v_i$.
Denote by $W_i$ the reflection of $W$ with respect to $\Pi_i$.

\begin{wrapfigure}{r}{43 mm}
\vskip-0mm
\centering
\includegraphics{mppics/pic-903}
\vskip-2mm
\end{wrapfigure}

Note that $W_i$ and $W_j$ have no common interior points if $i\ne j$;
the latter gives the needed inequality.
\qeds

The proof is given by 
Charles Halberg, 
Eugene Levin, 
and Ernst Straus 
\cite{halberg-levin-straus}.
It is not known if the same inequality holds for the orientation-preserving version of the kissing number.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Monotonic homotopy.}
Note that we can assume
that $h_0(F)$ and $h_1(F)$ both lie in the coordinate $m$-spaces of $\RR^{2\cdot m}=\RR^m\times \RR^m$;
that is,
$h_0(F)\z\subset\RR^m\times\{0\}$
and $h_1(F)\subset  \{0\}\times\RR^m$.

Direct calculations show that the following homotopy is monotonic
\[h_t(x)=\bigl(h_0(x)\cdot \cos\tfrac{\pi\cdot t}2
\,,\,
 h_1(x)\cdot\sin\tfrac{\pi\cdot t}{2}\bigr).\qedsin\] 
\medskip

This homotopy was discovered by Ralph Alexander \cite{ralexander}.
It has a  %wide?
number of applications, 
one of the most beautiful is given 
by K\'aroly Bezdek 
and Robert Connelly \cite{bezdek-connelly};
they proved the Kneser--Poulsen  
and Klee--Wagon conjectures in the two-dimensional case.

The dimension $2\cdot m$ is optimal;
that is, for any positive integer $m$,
there are two maps $h_0,h_1\:F\to \RR^m$ that cannot be connected by a monotonic homotopy $h_t\:F\to\RR^{2\cdot m-1}$.
The latter was shown by Maria Belk and Robert Connelly \cite{belk-connelly}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Facet cover.}
Choose a convex polyhedron $P$ and its facet $F$.
Denote by $\Pi$ the hyperplane of $F$.

For each point $p\in F$ consider the maximal ball $B_p\subset P$ that contains~$p$.
Note that $B_p$ touches another facet of $P$ at some point $q$.

Show that the restriction of the partially defined map $q\mapsto p$ to any other facet $F'$ can be extended to a distance-preserving map $F'\to \Pi$.
By construction union of all such images cover $F$.
\qeds

This problem was considered by Igor Pak and Rom Pinchasi \cite{pak-pinchas};
the presented proof was given by Arseniy Akopyan \cite{akopyan-2012}.
A slightly different version of this problem made it to the All-Russian olympiad of 2012 \cite[№ 116774]{problems}.

In the three-dimensional case,
a more involved, but straightforward solution can be built on the fact that orthogonal projection of a convex figure can be covered by the figure itself.
The latter statement is not as simple as one might think  \cite[see][and the references therein]{kos-toroscik}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Cube.}
Consider the cube $[-1,1]^m\subset \RR^m$.
Any vertex of this cube has the form $\bm{q}=(q_1,\dots,q_m)$,
where  $q_i=\pm1$.

For each vertex $\bm{q}$,
consider the intersection of the corresponding hyperoctant with the unit sphere;
that is, consider the set
\[V_{\bm{q}}=\set{(x_1,\dots,x_m)\in\mathbb{S}^{m-1}}{q_i\cdot x_i\ge 0\ \text{for each}\ i}.\]

Let $\mathcal{A}\subset\mathbb{S}^{m-1}$ be the union of all the sets $V_{\bm{q}}$ for black $\bm{q}$.
Note that 
\[\vol_{m-1}\mathcal{A}=\tfrac12\cdot\vol_{m-1}\mathbb{S}^{m-1}.\]

By the spherical isoperimetric inequality,
\[\vol_{m-2}\partial\mathcal{A}
\ge \vol_{m-2}\mathbb{S}^{m-2}.\] 

It remains to observe that
\[\vol_{m-2}\partial\mathcal{A}
=
\tfrac k{2^{m-1}}\cdot\vol_{m-2}\mathbb{S}^{m-2},\]
where $k$ is the number of edges of the cube with one black end and the other in white.
\qeds

The problem was suggested by Greg Kuperberg.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Geodesic loop.}
Let $\gamma$ be a geodesic from vetrex to vertex;
denote by $v$ its midpoint.

Show that there is symmetry of the cube that fixes $v$, reverts $\gamma$, and moves all the vertices of the cube.
Conclude that the endpoints of $\gamma$ are different.
\qeds

I learned this problem from Jaros{\l}aw K\k{e}dra; 
it was rediscovered independently by
Diana Davis,
Victor Dods,
Cynthia Traub,
and Jed Yang \cite{DDTY}.
The presented solution is taken from the paper of Serge Troubetzkoy \cite{troubetzkoy}.
This idea can be used to solve the following harder problems.

\begin{pr}
Show the same for the surface of the $n$-dimensional cube, $n\ge 4$.
\end{pr}

\begin{pr}
 Show the same for the surface of the tetrahedron, octahedron, and icosahedron.
\end{pr}

For the dodecahedron such loops exist;
\begin{figure}[!ht]
\vskip0mm
\centering
\includegraphics{mppics/pic-905}
\end{figure}
a development of one example is on the diagram.
Vertices of an inscribed tetrahedron are circled.
A classification of all such loops is found by Jayadev S. Athreya, David Aulicino, and W. Patrick Hooper \cite{athreya-aulicino-hooper}.

These and related problems are discussed by Dmitry Fuchs \cite{fuchs-2016}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Right and acute triangles.}
Denote by $K$ the convex hull of $\{x_1,\z\dots,x_n\}$.
Without loss of generality, we can assume that $\dim K=m$. 

\begin{wrapfigure}{o}{35 mm}
\vskip-0mm
\centering
\includegraphics{mppics/pic-907}
\end{wrapfigure}

Note that for any distinct points $x_i$, $x_j$,
and any interior point $z$ in $K$,
we have 
\[\measuredangle \hinge{x_i}{x_j}z<\tfrac\pi2.\leqno({*})\]
Indeed, if $({*})$ does not hold, then $\langle x_j-x_i,z-x_i\rangle<0$.
Since $z\in K$ we have $\langle x_j-x_i,x_k-x_i\rangle\z<0$ for some vertex $x_k$.
That is, $\measuredangle \hinge{x_i}{x_j}{x_k} > \tfrac\pi2$ --- a contradiction.

Denote by $h_i$ the homothety with center $x_i$ and coefficient $\tfrac12$.
Set $K_i=h_i(K)$.

Let us show that $K_i$ and $K_j$ have no common interior points.
Assume the contrary; 
that is, \[z=h_i(z_i)=h_j(z_j);\]
for some interior points $z_i$ and $z_j$ in $K$.
Note that 
\[
\measuredangle\hinge{x_i}{x_j}{z_j}
+
\measuredangle\hinge{x_j}{x_i}{z_i}
=
\pi,
\]
which contradicts $({*})$.

Note that $K_i\subset K$ for any $i$;
it follows that 
\begin{align*}
\tfrac n{2^m}\cdot \vol K
&=\sum_{i=1}^n\vol K_i\le\vol K.
\end{align*}
Hence the result follows.
\qeds

The problem was posted by Paul Erdős \cite{erdos}
and solved by Ludwig Danzer and Branko Grünbaum \cite{danzer-gruenbaum}.

Grigori Perelman noticed that the same proof works for a similar problem in Alexandrov spaces \cite{perelman-Erdos}.
The latter led to interesting connections with the crystallographic groups \cite{lebedeva};
in particular, it gives an approach to the following open problem.

\begin{pr}
Let $\Gamma\acts\RR^n$ be an effective properly discontinuous isometric action.
Denote by $m$ the number of maximal finite subgroups $\Gamma$ up to conjugation. 
Is it true that $m\le 2^n$?
\end{pr}


Surprisingly, the maximal number of points that make only acute triangles grows exponentially with $m$ as well.
The latter was shown by Paul Erdős and Zolt\'an Füredi \cite{erdos-fueredi} using the \index{probabilistic method}\emph{probabilistic method}.
Later, an elementary constructive argument was found and improved by Dmitriy Zakharov,
\texttt{grizzly} (an anonymous mathematician),
Bal{\'a}zs Gerencs{\'e}r, and Viktor Harangi
\cite{zakharov,grizzly,gerencser-harangi};
the current lower bound is $2^{m-1}+1$, which is exponentially optimal.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Upper approximant.}
We assume that the measure is given by a distribution.
The general case is done by a straightforward modification.

Cut the plane by two lines into 4 angles of equal measure.
Let $p$ be the intersection point of the two lines.
Note that every convex set avoiding $p$ is fully contained in three angles out of the four.
In particular, its measure cannot exceed $\tfrac34$.

Apply this construction recursively for the restriction of the measure to each triple of angles.
After $n$ steps we get a $(1+\z\dots+4^{n-1})$-point set 
that intersects each convex figure $F$ of measure $(\tfrac34)^n$.
\qeds

This is a stripped version of a theorem proved by Boris Bukh and Gabriel Nivasch \cite{bukh-nivasch}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Right-angled polyhedron.}
Let $P$ be a right-angled hyperbolic polyhedron of dimension $m$.
Note that $P$ is simple; 
that is, exactly $m$ facets meet at each vertex of $P$.

From the projective model of the hyperbolic plane, 
one can see that for any simple compact hyperbolic polyhedron, there is a simple Euclidean polyhedron with the same combinatorics. 
In particular, the Dehn--Sommerville equations hold for $P$.

Denote by $(f_0,\dots f_m)$ and $(h_0,\dots h_m)$ the $f$- and $h$-vectors of $P$.
Recall that 
\begin{align*}
h_i&=h_{m-i},
\\
f_1&=h_1+2\cdot h_2+\dots+m\cdot h_m,
\\
f_2&= h_2+3\cdot h_3+\dots+\tbinom m 2\cdot h_m.
\end{align*}
Observe that $h_i\ge 1$; together with the identities above it implies that
\[f_2> \tfrac{m-2}4\cdot f_1.
\leqno({*})\]

Since $P$ is hyperbolic, each 2-dimensional face of $P$ has at least 5 sides.
It follows that
\[f_2\le \tfrac{m-1}5\cdot f_1.\]
The latter contradicts $({*})$ for $m\ge 6$.
\qeds

This is the core of the proof of nonexistence of compact hyperbolic Coxeter's polyhedrons of large dimensions 
given by Ernest Vinberg \cite{vinberg, vinberg-strong}.

Playing a bit more with the same inequalities, 
one gets the nonexistence of right-angled hyperbolic polyhedrons,
in all dimensions starting from~$5$.
In the $4$-dimensional case,
there is a regular right-angled  hyperbolic polyhedron with \index{120-cells}\emph{120-cells} --- a $4$-dimensional uncle of the dodecahedron.

The following related question is open:

\begin{pr}
Let $m$ be a large integer.
Is there a cocompact properly discontinuous isometric action  on the $m$-dimensional Lobachevsky space that is generated by finite order elements (for example, involutions)?
\end{pr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Real roots of random polynomial.}
Choose a polynomial 
\[p(t)=a_0+\dots+a_n\cdot t^n.\]
Consider the hyperplane $\Pi$ in $\RR^{n+1}$ defined by the equation 
\[a_0\cdot x_0+\dots+a_n\cdot x_n=0.\]
Note that the number of real roots of $p$ equals the number of intersections of $\Pi$ with the moment curve.

It remains to apply the spherical Crofton formula.
\qeds

The observation is due to Alan Edelman and Eric Kostlan \cite{edelman-kostlan}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbf{Space coloring.}
The answer is $\binom{d+k-1}{d}$.

Choose $d+k-1$ hyperplanes in $\RR^d$ in general position.
Let $A$ be the set of all $\binom{d+k-1}{d}$ intersection points of every $d$-tuple of the chosen hyperplanes. 
Show that starting with $A$ one can color every point in $\RR^d$.

To prove the lower bound, note that $\binom{d+k-1}{d}$ is the dimension of the space of polynomials $p\:\RR^d\to\RR$ of total degree at most $k-1$.
Therefore, if $A$ has less than $\binom{d+k-1}{d}$ points, then there is a non-zero polynomial $p$ of degree at most $k-1$ such that $A$ lies in its zero-set $Z$.
Observe that if a line does not lie in $Z$, then it has at most $k-1$ common points with $Z$.
Therefore, it is impossible to color a point outside of $Z$.
\qeds

This is a problem of Ivan Mitrofanov and Fedor Petrov \cite[№ 10]{kanel-belov};
a three-dimensional version of this problem appeared at the 28$^\text{th}$ Annual Vojtěch Jarník International Mathematical Competition, Category II \cite{vjimc}.

The problem illustrates the so-called \emph{polynomial method};
for more on the subject check the book of Lary Guth \cite{guth2016}.