\documentclass[12pt,a4paper]{article}
%\usepackage[T2A]{fontenc}
%\usepackage[cp1251]{inputenc}
\usepackage[english]{babel}
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage{epsfig,wrapfig}

\pagestyle{plain}
\advance\textwidth35mm
\advance\textheight55mm
\advance\hoffset-20mm
\advance\voffset-35mm
\let\eps\varepsilon
\let\ds\displaystyle

\def\fig#1{\begin{figure}[!ht]
\centerline{\epsfig{figure=tolpygo-#1.mps}}
\end{figure}
}


\def\prob#1{\par\bigskip\centerline{\bf #1}\par\nopagebreak\smallskip}

\def\answer{\par\textbf{Answer.} }

\begin{document}

\begin{center}
\bf{\Large
Problems on coverings and growth functions}

\it
A.~Tolpygo, B.~Frenkin, M.~Prasolov, I.~Bogdanov

\vskip2em

\bf
Solutions
\end{center}

\prob{A1}

\answer Yes, it is possible.

One of the possible ways is to cover a square by a disk of radius $\frac{\sqrt2}2$, then decrease this radius a bit, and cover the four regions which are uncovered by four small disks.

A different way is presented in the problem statements before problem D1.

\prob{A2, A3}
In the first case the growth of $N(r)$ is quadratic (in terms of part B, $[N(r)] =2$), while in the second case it is cubic.

\prob{B1}
For any $A$, $B$ and a sufficiently large $x$ we have $x^2 > Ax+B$. Thus $[x^2] \ge [x]$ but it is false that $[x^2] \le [x]$. This just means that  $2 > 1$.

\prob{B2, B3}
For instance, the required function can be constructed as follows. Construct a sequence of rapidly increasing intervals (for example, the intervals $[2, 4], [4, 16], [16, 256],\dots, [2^{2^n}, 2^{2^{n+1}}]\ldots$ would fit), and consider first the function $g(x)$ equal to $x^{\frac32}$  on odd intervals, and equal to $x^{\frac52}$  on even intervals.

Obviously, this function grows faster than $x$  but slower than $x^3$. The main its defect is its discontinuity (at points $4, 16, \ldots$) which implies a non-monotonicity. But this can be easily corrected.  Define $f(x)$ at the $r$th interval as $g(x)+A_r$, where the constants $A_r$ are chosen so that the function becomes continuous. Namely, let $A_1= 0, A_2=4^{\frac32} - 4^{\frac52} =  -56$, and so on.

The resulting function satisfies the conditions of the problem. Actually, its graph lies between the graphs of $x$ and $x^3$ as before. Now we show that it is incomparable with $x^2$. Consider an interval $[d,d^2]$, where $d=2^{2^{2n}}$. Then we have $f(d)\leq d^{5/2}$, and hence $f(d^2)\leq d^{5/2}+\left((d^2)^{5/2}-d^{3/2}\right)\leq d^3+d^{5/2}\leq 2(d^2)^{3/2}$. Therefore, if $[f]\geq a$, then $a\geq 5/2$. Analogously, considering the interval $[d,d^2]$ for $d=2^{2^{2n+1}}$, we get $f(d^2)\geq \frac12(d^2)^{5/2}$, wherefore the relation $[f]\leq a$ implies $a\leq 3/2$.

Correspondingly, the constructed function and $x^2$ provide the solution for Problem B2.

\prob{B4}
For instance, the function  $f(x) = \ln x$  fits.

\prob{B5}
For instance, the function $f(x) = 2^x$ fits.  Indeed, we have $f^2  = 4^x = f(2x)$, and the growth of the functions is the same by the definition.

\prob{B6}

\answer Yes, it exists.

It suffices to provide for instance the relation $\ln f(x) = f(x/2)$, or equivalently  $f(2x) = \exp (f(x))$. To get this, take any increasing function on the interval $[1,2]$ such that $f(1)=1$< $f(2)=e=\exp(f(1))$; then our relation determines uniquely the function $f$ n the intervals $[2,4]$, $[4,8]$, and so on. Clearly, we get a desired example.




\prob{C1} 
\answer $\displaystyle M(\varepsilon)=\left\lceil\frac{a}{2\varepsilon}\right\rceil$, $\displaystyle N(\delta) = \left\lfloor\frac{a}{\delta} +1\right\rfloor$.

\prob{C2} The best possible estimate is not required in this problem, so the answer is not unique.

We present one of the possible estimates.

(a) For $M(\varepsilon)$.

Since the disks of radius $\varepsilon$ must cover the whole unit disk, their total area must exceed the area of the unit disk. Hence $\ds M(\varepsilon) > \left(\frac1{\varepsilon}\right)^2$  (respectively, $\ds M(\varepsilon) > \left(\frac1{\varepsilon}\right)^3$ for the cube).

On the other hand, using the construction shown in the Problems section above D1, we can easily see that the whole disk (with a minor ``overcoming'')  can be covered by regular hexagons. Covering these hexagons by disks, we arrive (for a sufficiently small $\varepsilon$) to the estimate $\ds M(\varepsilon) < A\cdot \left(\frac1{\varepsilon}\right)^2  \cdot \frac{2\pi}{3\sqrt{3}}$, where $A$ is an arbitrary constant greater than $1$.

For the ball, the first estimate is quite similar up to replacement of the square by the cube. The second one can't be obtained in this way. But we can cover the ball by small cubes and insert each cube into a ball. This leads to the upper estimate.

(b) For $N(\delta)$.

Suppose that $N$ points form a lattice; for each point, consider a disk of radius $\delta$ with the center in this point. If all these disks do not cover the unit disk, then we can add one more point to the lattice, and it is not maximal.  Hence $\ds N(\delta) > \left(\frac1{\delta}\right)^2$. The other estimates are obtained similarly to the ones above.

\prob{C3} 
Clearly, a maximal $\delta$-lattice is also a $\delta$-net (the respective disks cover the whole figure). On the other hand, a disk of radius $\frac{\delta}2$ can contain not more than one point of a $\delta$-lattice. This immediately implies that if $\varepsilon < \frac{\delta}2$ then $M(\varepsilon) \geq N(\delta). $

Thus $M(\frac{\varepsilon}3) \geq N(\delta) \geq M(\delta)$, and this implies the statement of the problem.

\prob{C4} 
We construct the required figure as an intersection of an infinite number of figures. Actually, let $\Phi_1$ be the disk of radius $2$ with the center at the origin. Furthermore, inscribe a figure $\Phi_2$ into $\Phi_1$ as follows. Let $\Phi_2$ be the union of $8$ disks of radius $\frac12$ (that is, $4$ times less) with centers at $(0, -\frac34 )$; $(0, -\frac14 )$; $(0, \frac14 )$; $(0, \frac34)$, and of $4$ similar disks with centers on the $y$-axis.  (Some of these disks do intersect.)

Next, into each of these disks we inscribe $8$ disks of radius $\frac18$ arranged similarly. Namely, their centers lie on lines passing through the center of the disk in question and parallel to one of the coordinate axes. These  $64$ disks form the figure $\Phi_3$. The figures $\Phi_4, \Phi_5,\dots$ are constructed similarly; let $\Phi$ be the intersection of all these figures.

Obviously the resulting figure can be covered either by a single disk of radius $2$, or by $8$ disks of radius $\frac12$, or so on. On the other hand, all the centers of constructed disks of radius $2^{1-2n}$ form a $2^{-2n}$-lattice in~$\Phi$, and there are $2^{3n}$ such centers.  This determines the dimension of~$\Phi$.

\prob{C5}
\answer The dimension of a (connected) figure can attain each value from $[1,2]$ (on the plane). The dimension can be incomparable with some numbers as well. It can be less than~1 only for a non-connected figure.

\prob{C6}
\answer The dimensions of different helices may be different.

Let us assume first that a helix has finite length. (This is true, for example, when $f(\varphi) = e^{-\varphi}$, since in this case the length of each turn is proportional to the length of the first one, thus the length of the whole helix is the sum of a descending geometrical progression.)

Let $L$ be the length of the whole helix. Since a piece of the helix having length $2r$ obviously can be covered by a disk of radius $r$, the whole helix can be covered by $\frac{L}{2r}$ disks, which means that the dimension is equal to $1$.

On the other hand, if a helix covers a disk densely, then its dimension is greater than $1$. We are left to define what is ``densely''.

To give an example, let us draw concentrical circles of radii $\frac12, \frac13, \ldots \frac1n, \ldots$  in the unit disk. They dissect the disk into concentrical rings. Suppose that the $k$th ring contains $10^k$ turns of the helix arranged uniformly (in this ring). We claim that this is a ``sufficiently dense'' arrangement of turns, that is, the dimension of this helix is greater than $1$.

For the proof we formulate a general

\textbf{Proposition T.} Let $\Phi$ be some figure in a ring, the size of~$\Phi$ being much larger than the width of a helix turn. Then the area of~$\Phi$ is approximately equal to the product of the turn width and the total length of the parts of the helix lying inside~$\Phi$.

\centerline{
\epsfig{figure=tolpygo-1.mps}}

Strictly speaking, this proposition is incorrect; one can easily find some counterexamples. But we will apply it only to the disks and the rings, for which it holds, and can be easily proved.

So, we turn to the dimension of our helix. Consider some small~$\eps$. Choose integer $k$ such that $1/k^2\gg\eps\gg 10^{-k}$, that is, $\eps$ much smaller that the width of $k$th ring, but the turn width~$\delta$ in this ring is much smaller than~$\eps$. Note that such~$k$ can be found if $\eps$ is small enough. Denote by~$\Phi$ the $k$the ring.

Now, apply the Proposition~T to $\Phi$ and to each disk of radius~$\eps$ in the covering. Let $L$ be the length of the piece of the helix lying inside~$\Phi$; then the area of~$\Phi$ is $\ds\pi\left(\frac1{k^2}-\frac1{(k+1)^2}\right)\approx L\delta$. On the other hand, each disk will contain the pieces of helix with total length $\approx \pi\eps^2/\delta$. This means that the number of disks covering the part of a helix inside~$\Phi$ is (almost) at least the ratio of these two values. In other words, these disks have almost the area sufficient to cover the whole~$\Phi$.

From this, we cannot make a conclusion that the dimension of a helix is~2, though~$\Phi$ has a dimension~2: actually, we choose different figures $\Phi$ for different~$\eps$. But, since $k$ grows much slower than~$\eps$, one can easily see that the dimension of $\Phi$ is definitely greater than~1, and this was exactly our goal.





\prob{D1}
{\it Lemma.} Given $N$ polygons lying inside unit disks such that each polygon contains the center of its disk, and the total amount of vertices of polygons does not exceed $6N$. Then the total area of polygons is at most $N\cdot\frac{3\sqrt{3}}2$ (so, this estimate is sharp when the polygons are the regular hexagons).

{\it Proof.} Dissect each polygon into triangles by the radii of its disk. The doubled area of each triangle is not greater than $\sin\alpha$, where $\alpha$ is the angle at the central vertex. So, the doubled total area of given polygons equals to $\sin \alpha_1+\sin\alpha_2+\ldots+\sin\alpha_{n}$, where $\alpha_i$ are the corresponding angles; we have $\alpha_1+\dots+\alpha_n=\pi N$, and $n\leq 6N$. Moreover, adding some zero angles one can assume that $n=6N$. Finally, one can notice that the graph of the function $\sin x$ on $[0,\pi]$ is concave, so the function attains its maximal value when $\alpha_i=\frac{\pi}3$. So we get the maximal area if all polygons are regular hexagons.

\smallskip

{\bf Solution of problem D1.} We will prove the statement for an arbitrary polygon~$T$ with angles not exceeding $2\pi/3$. Suppose that $T$ is covered by $N$ equal disks. Divide this unit square into convex polygons by the following rule: for each disk center, its polygon contains all the points such that this center is the closest center to them (see Figure). The discs are equal, therefore the sides of polygons are the parts of common chords of our disks. Since all points are covered, each polygon lies in a corresponding disk. Moreover, each polygon obviously contains the center of its disk.

\begin{figure}[!ht]
\centerline{\epsfig{figure=tolpygo-2.mps}}
\end{figure}

Now we estimate the average value of the angle of our polygon. The average angle in each vertex of our dissection is not greater than $2\pi/3$ (it can be easily seen separately for the vertices inside $T$, on the sides of~$T$, and for the vertices of~$T$ --- exactly here we use the estimates for the angles of~$T$). It follows easily that the total number of vertices of the polygons does not exceed~$6N$. Hence by the Lemma the total area of the polygons (which is~1) is at most $\ds N\frac{3\sqrt3}2$, and the total area of the disks is $\ds N\cdot \pi\eps^2\geq \frac{2}{3\sqrt3\,\eps^2}=\gamma$, as desired.

\textbf{Remark.} If $T$ is a regular hexagon, then the best way to cover it is to use exactly one disk; all other ways are strictly worse.

With some minimal changes, the proof above is valid for any polygon with at most six sides.


\prob{D2} 

The optimal construction is the following one.

We cover a part of the square by the disks of a larger radius, and the remaining part will be covered by the smaller disks using the method from~D1 (that is, using a covering by the small hexagons). Naturally, to reach an (almost) optimal configuration by this method, we should take the radii $r_1$ and $r_2$ such that $1\gg r_1\gg r_2$.

Cover a unit square by regular hexagon lattice. Denote a side of a hexagon by $a$ and put on each hexagon a disk of radius $r_1$. We wish these disks to intersect but not to cover the whole square; these conditions rewrite as  $\frac{\sqrt{3}}4a<r_1<a$. It remains to cover the rest by the smaller disks.

Now we find the radius $r_1$ for which this configuration is optimal. We see that the total area of the disks is the sum of the total areas of large and of small disks; the latter is $\gamma$ times larger than the area of the parts (``corners'') uncovered by the large disks. We call this latter summand the {\em full} area of the corners (to distinguish it from their {\em total} area).

Thus, neglecting the boungary effect, we can consider only the disks covering of one hexagon; the ratio of their total area to the hexagon area is exactly the total area of all disks.

\fig{8}

First, let $r_1=a\frac{\sqrt3}2$, and then let us increase this radius. When it increases by~$\delta$, the area of the large disks increases approximately by $2\pi r_1\delta$, while the area of six ``corners'' decreases by $6\beta r_1\delta$, hence their {\em full} area decreases by $6\beta r_1\delta\gamma$. Obviously, the total area is minimal when the increment and the decrement become equal, that is, $2\pi r_1\delta=6\beta r_1\delta\gamma$, wherefore $\ds\beta=\frac{2\pi}{6\gamma}=\frac{\sqrt3}2$.

In this case $\ds r_1=a\cdot\frac{\sqrt3}2\cdot \frac1{\cos\left(\frac\pi6-\frac\beta2\right)}$. The total area of the disks can be computed but it has a combersome form.

One can notice that the (presumably) optimal arrangement of the disks with three (or more) different radii can be found in a similar manner.

Unfortunately, the jury does not know the proof for the optimality of this configuration. Perhaps, the participants can fill this gap?


\prob{D3}

\answer 1.

The solution follows from the following

{\it Lemma.} If a unit square is covered by disks of total area $1+\alpha$ then it is possible to cover this square by disks ot total area $1+\frac{\alpha}2$.

{\it Proof.} Assume that a unit square can be covered by the disks of total area ${}<1+\alpha$. We claim first that each figure~$F$ of area~$S$ can also be covered by the disks of total area ${}<S(1+\alpha)$. To prove this, one can cover~$F$ ``almost sharp'' by some small squares, and then cover these squares with the ``non-efficiency'' ${}<1+\alpha$.

Now we are ready to prove the Lemma. Inscribe a disk of area~$\frac\pi4$ into a unit square; then we can cover the remaining figure by the disks of total area $<(1+\alpha)\left(1-\frac\pi4\right)$. Since $\pi>2$, we get the desired covering.

\prob{D4}
Naturally, as in~D1, the radii should be small enough, and the main queation is about the arrangement of the ball centers. By analogy with D1, it is presumably better to take some ``dense'' packing of balls and try to expand it. We  present a dense packing of non-intersecting balls; then it remains to increase their radii to obtain the covering of the whole cube. 

Let the centers of the balls in a ``first layer'' lie in the vertices of a triangular lattice in one plane. The next layer will contain the balls also forming the triangular lattice; moreover, each center in the second layer will form a regular tetrahedron with three centers from the first layer. 

\fig{7}

The third layer is constructed in a same manner from the second one, and so on. Notice here that, having made two first layers, one can construct the third one in two (essentially different) ways; but the density of both coverings will be the same. To visualize his, we remark that if one starts with the first layer in a form of the regular triangle with side~$n$, then we can obtain a pyramid with $n$ layers.

It remains to calculate the ratio of the radii of the  original and the expanded balls.  We mention (without a proof) that this ratio is equal to the ratio of the circumdiameter and the side of a regular octahedron, or $\sqrt2$.

\prob{D5}
It seems that the optimal configuration has a form similar to that in D2. That is, we take the configuration from the previous problem, decrease the radii a bit, and cover the remainng spaceby the balls of a smaller radius.

\prob{D6}
The answer for D6 is the same as for D3. The solution is similar due to the fact that the volume of the ball is greater than half of the volume of the corresponding cube (in 4-dimensional case this is not true, hence one should upgrade the proof a bit).

\textbf{Remark.} Notice that in D4--D5 we provide only some plausible reasonings on an optimal example; conversely, in D6 we show an outline of the full solution.

\prob{D7}
Cover the square as in D1. Part of the square which is covered twice consists of equal figures; we call such a figure {\em a lens}. Cover a hexagon by lenses as in the figure: a hexagon is covered by rhombs, and each rhomb can be covered by a lens.

\fig{6}

Denote by $N$ a number of rhombs in this covering. Each rhomb can be obtain from the initial one by a shift. So, let us shift the covering $N$ times to obtain a square covered $N+1$ times. The correcting of the boundary effect is left to the reader.

\prob{D8}
Jury does not know the solution.


\prob{E1} 
We start with two elementary lemmas.

{\it Lemma 1.} The number of dissection parts equals to $1+a+b+c$ where $a,b$ respectively are numbers of horizontal and vertical lines which intersect the lower square and $c$ is a number of vertices of the upper sheet which lies in the lower square.

{\it Proof} by induction is easy: delete all the horizontal and vertical lines, and then draw them one by one.

{\it Lemma 2.} If a base and the corresponding altitude of triangle are at least $1$ and this triangle lies in the square then its base coincide with the side of the square.

{\it Proof} follows from the fact that if a unit square contains a triangle with area $\geq 1/2$, then this area is~$1/2$; moreover, in this case the triangle and the square have a common side.

\smallskip

\answer The number of parts equals to $4$, $5$ or $6$. Examples are shown in the figure.

\fig{3}

{\bf Solution.} First, notice that each projection of a unit square onto some line has a length between $1$ and $\sqrt2$; this means that $a$ and $b$ can be only $1$ or $2$. Moreover, it is easy to see than $0\leq c\leq 2$. This means, by Lemma~1, that the desired number lies between 3 and 7. We are left to show that the border cases are impossible.

Suppose that the number of parts equales to $3$, thus $a=b=1$ and $c=0$. This means that the lower square is covered by three upper squares (see the left figure below); this contradicts Lemma~2.

The case of $7$ parts is similar in the sense that it follows from the same Lemma~2 (see the right figure below).

\centerline{\epsfig{figure=tolpygo-4.mps}\qquad\epsfig{figure=tolpygo-5.mps}}

\prob{E2}
We will find an approximate estimate for the number of pieces; the further details are left to the reader. We will assume that the upper rectangle is drawn on the plane; so we erase it and then we reconstruct it in several steps. Now we assume that the sides of top (small) rectangle are oriented vertically and horizontally, while the lower rectangle is sloped.

First, we draw the boundary of the upper rectangle; then it will be split into a bit more than two millions parts (almost all of them --- except those on the border --- are the unit squares). Next, we draw the vertical and horizontal lines (of the upper rectangle) one by one. Each line increases the number of parts by the number of its intersections with other lined (drawn up to this moment). Hence, the total increment will equal to the total number of the points of intersection (where the 3- and 4-fold points are considered in an appropriate manner). So, we are to estimate this number. 
There are not more than two millions points of intersection of horizontal and vertical lines with each other. The remaining points are the points of intersection of lines from different sheets. 

Let $\alpha$ be the angle between a horizontal and (some) sloped line. Then a horizontal line (of length $1000$) intersects approximately $1000\sin\alpha$ lower lines of this type, and approximately $1000\cos\alpha$ sloped lines of another type, so all horizontal lines add approximately $2000\cdot 1000(\sin\alpha+\cos\alpha)$ points. Similarly, the vertical lines add approximately $1000\cdot 2000(\sin\alpha+\cos\alpha)$ points. Note that the expression $\sin\alpha+\cos\alpha$ reaches its maximum value $\sqrt2$ when $\alpha=\pi/4$, so the obtained bound for the number of parts is approximately $2\cdot10^6+2\cdot 10^6+2\cdot 2\cdot10^6\sqrt{2}\approx2\cdot4.83\cdot10^6$ parts. It is left to see that the errors in our calculations sum up at less than one million.

\prob{F1}
\answer Figure has a zero volume characteristics if and only if it is bounded.

\prob{F2}
\answer A volume characteristics of the plane and the halfplane  equals to $2$. A volume characteristics of the strip equals to $1$.

\prob{F3}
Denote by $N_1(R)$ and $N_2(R)$ functions corresponding to points $O_1$ and $O_2$. Then $N_1(R+O_1O_2) \ge N_2(R)$ and $N_1(R) \le N_2(R+O_1O_2)$. Thus $[N_1]=[N_2]$.

\prob{F4} 
\answer Yes.

Assume that $\varepsilon>\delta$. Then each disk of radius $\delta$ can be covered by a disk of radius $\varepsilon$. So $N_\delta(R)\ge N_\varepsilon(R)$. (Here, $N_\eps$ and $N_\delta$ denote the two functions defined by the disks of the corresponding radii.)

Conversely, each disk of radius $\epsilon$ can be covered by $A$ disks of radius $\delta$ (for some constant~$A$). Then $N_\delta(R)\le A\cdot N_\varepsilon(R)$, quod erat demonstrandum.

\prob{F5}
\answer $\frac32,2$.

\prob{F6}
\answer A volume characteristics of all of them equals to $2$.

\prob{F7, F8}
If a figure is unbounded and connected then its volume characteristics is at least $1$. Volume characteristics of a figure is at most volume characteristics of the whole plane/space, i.e. $2$ or $3$. These are the only restrictions.

\end{document}
