International Mathematical Olympiad

We start with finding a regular $n$-gon $\mathcal{C}$ which (i) is inscribed into $\mathcal{B}$ (that is, all vertices of $\mathcal{C}$ lie on the perimeter of $\mathcal{B}$); and (ii) is either a translation of $\mathcal{A}$, or a homothetic image of $\mathcal{A}$ with a positive factor. Such a polygon may be constructed as follows. Let $O_A$ and $O_B$ be the centers of $\mathcal{A}$ and $\mathcal{B}$, respectively, and let $A$ be an arbitrary vertex of $\mathcal{A}$. Let $\overrightarrow{O_{B}C}$ be the vector co-directional to $\overrightarrow{O_{A}A}$, with $C$ lying on the perimeter of $\mathcal{B}$. The rotations of $C$ around $O_B$ by multiples of $2\pi /n$ form the required polygon. Indeed, it is regular, inscribed into $\mathcal{B}$ (due to the rotational symmetry of $\mathcal{B}$), and finally the translation/homothety mapping $\overrightarrow{O_{A}A}$ to $\overrightarrow{O_{B}C}$ maps $\mathcal{A}$ to $\mathcal{C}$.

Now we separate two cases.

Construction of $\mathcal{C}$ Case 1: Translation

Case 1: $\mathcal{C}$ is a translation of $\mathcal{A}$ by a vector $\vec{v}$. Denote by $t$ the translation transform by vector $\vec{v}$. We need to prove that the vertices of $\mathcal{C}$ which stay in $\mathcal{B}$ under $t$ are consecutive. To visualize the argument, we refer the plane to Cartesian coordinates so that the $x$-axis is co-directional with $\vec{v}$. This way, the notions of right/left and top/bottom are also introduced, according to the $x$- and $y$-coordinates, respectively.

Let $B_{\mathrm{T}}$ and $B_{\mathrm{B}}$ be the top and the bottom vertices of $\mathcal{B}$ (if several vertices are extremal, we take the rightmost of them). They split the perimeter of $\mathcal{B}$ into the right part ${\mathcal{B}}_{\mathrm{R}}$ and the left part ${\mathcal{B}}_{\mathrm{L}}$ (the vertices $B_{\mathrm{T}}$ and $B_{\mathrm{B}}$ are assumed to lie in both parts); each part forms a connected subset of the perimeter of $\mathcal{B}$. So the vertices of $\mathcal{C}$ are also split into two parts ${\mathcal{C}}_{\mathrm{L}}\subset {\mathcal{B}}_{\mathrm{L}}$ and ${\mathcal{C}}_{\mathrm{R}}\subset {\mathcal{B}}_{\mathrm{R}}$, each of which consists of consecutive vertices.

Now, all the points in ${\mathcal{B}}_{\mathrm{R}}$ (and hence in ${\mathcal{C}}_{\mathrm{R}}$) move out from $\mathcal{B}$ under $t$, since they are the rightmost points of $\mathcal{B}$ on the corresponding horizontal lines. It remains to prove that the vertices of ${\mathcal{C}}_{\mathrm{L}}$ which stay in $\mathcal{B}$ under $t$ are consecutive.

For this purpose, let $C_1,C_2$, and $C_3$ be three vertices in ${\mathcal{C}}_{\mathrm{L}}$ such that $C_2$ is between $C_1$ and $C_3$, and $t\left(C_1\right)$ and $t\left(C_3\right)$ lie in $\mathcal{B}$; we need to prove that $t\left(C_2\right)\in \mathcal{B}$ as well. Let $A_i=t\left(C_i\right)$. The line through $C_2$ parallel to $\vec{v}$ crosses the segment $C_1{C}_3$ to the right of $C_2$; this means that this line crosses $A_1{A}_3$ to the right of $A_2$, so $A_2$ lies inside the triangle $A_1{C}_2{A}_3$ which is contained in $\mathcal{B}$. This yields the desired result.

Case 2: $\mathcal{C}$ is a homothetic image of $\mathcal{A}$ centered at $X$ with factor $k>0$. Denote by $h$ the homothety mapping $\mathcal{C}$ to $\mathcal{A}$. We need now to prove that the vertices of $\mathcal{C}$ which stay in $\mathcal{B}$ after applying $h$ are consecutive. If $X\in \mathcal{B}$, the claim is easy. Indeed, if $k<1$, then the vertices of $\mathcal{A}$ lie on the segments of the form $XC$ ($C$ being a vertex of $\mathcal{C}$) which lie in $\mathcal{B}$. If $k>1$, then the vertices of $\mathcal{A}$ lie on the extensions of such segments $XC$ beyond $C$, and almost all these extensions lie outside $\mathcal{B}$. The exceptions may occur only in case when $X$ lies on the boundary of $\mathcal{B}$, and they may cause one or two vertices of $\mathcal{A}$ stay on the boundary of $\mathcal{B}$. But even in this case those vertices are still consecutive.

So, from now on we assume that $X\notin \mathcal{B}$.

Now, there are two vertices $B_{\mathrm{T}}$ and ${\mathcal{B}}_{\mathrm{B}}$ of $\mathcal{B}$ such that $\mathcal{B}$ is contained in the angle $\angle B_{\mathrm{T}}X{B}_{\mathrm{B}}$; if there are several options, say, for $B_{\mathrm{T}}$, then we choose the farthest one from $X$ if $k>1$, and the nearest one if $k<1$. For the visualization purposes, we refer the plane to Cartesian coordinates so that the $y$-axis is co-directional with $\overrightarrow{B_{\mathrm{B}}{B}_{\mathrm{T}}}$, and $X$ lies to the left of the line $B_{\mathrm{T}}{B}_{\mathrm{B}}$. Again, the perimeter of $\mathcal{B}$ is split by $B_{\mathrm{T}}$ and $B_{\mathrm{B}}$ into the right part ${\mathcal{B}}_{\mathrm{R}}$ and the left part ${\mathcal{B}}_{\mathrm{L}}$, and the set of vertices of $\mathcal{C}$ is split into two subsets ${\mathcal{C}}_{\mathrm{R}}\subset {\mathcal{B}}_{\mathrm{R}}$ and ${\mathcal{C}}_{\mathrm{L}}\subset {\mathcal{B}}_{\mathrm{L}}$.

Case 2, $X$ inside $\mathcal{B}$ Subcase 2.1: $k>1$

## Subcase 2.1: $k>1$.

In this subcase, all points from ${\mathcal{B}}_{\mathrm{R}}$ (and hence from ${\mathcal{C}}_{\mathrm{R}}$) move out from $\mathcal{B}$ under $h$, because they are the farthest points of $\mathcal{B}$ on the corresponding rays emanated from $X$. It remains to prove that the vertices of ${\mathcal{C}}_{\mathrm{L}}$ which stay in $\mathcal{B}$ under $h$ are consecutive.

Again, let $C_1,C_2,C_3$ be three vertices in ${\mathcal{C}}_{\mathrm{L}}$ such that $C_2$ is between $C_1$ and $C_3$, and $h\left(C_1\right)$ and $h\left(C_3\right)$ lie in $\mathcal{B}$. Let $A_i=h\left(C_i\right)$. Then the ray $X{C}_2$ crosses the segment $C_1{C}_3$ beyond $C_2$, so this ray crosses $A_1{A}_3$ beyond $A_2$; this implies that $A_2$ lies in the triangle $A_1{C}_2{A}_3$, which is contained in $\mathcal{B}$.

Subcase 2.2: $k<1$

## Subcase 2.2: $k<1$.

This case is completely similar to the previous one. All points from ${\mathcal{B}}_{\mathrm{L}}$ (and hence from ${\mathcal{C}}_{\mathrm{L}}$) move out from $\mathcal{B}$ under $h$, because they are the nearest points of $\mathcal{B}$ on the corresponding rays emanated from $X$. Assume that $C_1,C_2$, and $C_3$ are three vertices in ${\mathcal{C}}_{\mathrm{R}}$ such that $C_2$ lies between $C_1$ and $C_3$, and $h\left(C_1\right)$ and $h\left(C_3\right)$ lie in $\mathcal{B}$; let $A_i=h\left(C_i\right)$. Then $A_2$ lies on the segment $X{C}_2$, and the segments $X{A}_2$ and $A_1{A}_3$ cross each other. Thus $A_2$ lies in the triangle $A_1{C}_2{A}_3$, which is contained in $\mathcal{B}$.

Now, choose a vertex $A_1$ of $\mathcal{A}$ such that the vector $\overrightarrow{O_A{A}_1}$ points "mostly outside ${\mathcal{H}}_1$"; strictly speaking, this means that the scalar product $⟨\overrightarrow{O_A{A}_1},\overrightarrow{b_1}⟩$ is minimal. Starting from $A_1$, enumerate the vertices of $\mathcal{A}$ clockwise as $A_1,A_2,\dots ,A_n$; by the rotational symmetry, the choice of $A_1$ yields that the vector $\overrightarrow{O_A{A}_i}$ points "mostly outside ${\mathcal{H}}_i$", i.e., $$\begin{array}{c}⟨\overrightarrow{O_A{A}_i},\overrightarrow{b_i}⟩=\underset{j\in [n]}{\min }⟨\overrightarrow{O_A{A}_j},\overrightarrow{b_i}⟩.\end{array}\text{\hspace{1em}(1)}$$

We intend to reformulate the problem in more combinatorial terms, for which purpose we introduce the following notion. Say that a subset $I\subseteq [n]$ is connected if the elements of this set are consecutive in the cyclic order (in other words, if we join each $i$ with $i+1\mathrm{mod}n$ by an edge, this subset is connected in the usual graph sense). Clearly, the union of two connected subsets sharing at least one element is connected too. Next, for any half-plane $\mathcal{H}$ the indices of vertices of, say, $\mathcal{A}$ that lie in $\mathcal{H}$ form a connected set.

To access the problem, we denote $$M=\left\{j\in [n]:A_j\notin \mathcal{B}\right\},M_i=\left\{j\in [n]:A_j\notin {\mathcal{H}}_i\right\}\text{ for }i\in [n].$$ We need to prove that $[n]\backslash M$ is connected, which is equivalent to $M$ being connected. On the other hand, since $\mathcal{B}={\bigcap }_{i\in [n]}{\mathcal{H}}_i$, we have $M={\bigcup }_{i\in [n]}{M}_i$, where the sets $M_i$ are easier to investigate. We will utilize the following properties of these sets; the first one holds by the definition of $M_i$, along with the above remark.

The sets $M_i$

Property 1: Each set $M_i$ is connected. $\square$

Property 2: If $M_i$ is nonempty, then $i\in M_i$.

Proof. Indeed, we have $$\begin{array}{c}j\in M_i⟺A_j\notin {\mathcal{H}}_i⟺⟨\overrightarrow{B_i{A}_j},\overrightarrow{b_i}⟩<0⟺⟨\overrightarrow{O_A{A}_j},\overrightarrow{b_i}⟩<⟨\overrightarrow{O_A{B}_i},\overrightarrow{b_i}⟩.\end{array}\text{\hspace{1em}(2)}$$ The right-hand part of the last inequality does not depend on $j$. Therefore, if some $j$ lies in $M_i$, then by (1) so does $i$. $\square$

In view of Property 2, it is useful to define the set $$M^{\prime }=\left\{i\in [n]:i\in M_i\right\}=\left\{i\in [n]:M_i\ne \varnothing \right\}.$$

Property 3: The set $M^{\prime }$ is connected.

Proof. To prove this property, we proceed on with the investigation started in (2) to write $$i\in M^{\prime }⟺A_i\in M_i⟺⟨\overrightarrow{B_i{A}_i},\overrightarrow{b_i}⟩<0⟺⟨\overrightarrow{O_B{O}_A},\overrightarrow{b_i}⟩<⟨\overrightarrow{O_B{B}_i},\overrightarrow{b_i}⟩+⟨\overrightarrow{A_i{O}_A},\overrightarrow{b_i}⟩.$$ The right-hand part of the obtained inequality does not depend on $i$, due to the rotational symmetry; denote its constant value by $\mu$. Thus, $i\in M^{\prime }$ if and only if $⟨\overrightarrow{O_B{O}_A},\overrightarrow{b_i}⟩<\mu$. This condition is in turn equivalent to the fact that $B_i$ lies in a certain (open) half-plane whose boundary line is orthogonal to $O_B{O}_A$; thus, it defines a connected set. $\square$

Now we can finish the solution. Since $M^{\prime }\subseteq M$, we have $$M=\bigcup _{i\in [n]}{M}_i=M^{\prime }\cup \bigcup _{i\in [n]}{M}_i,$$ so $M$ can be obtained from $M^{\prime }$ by adding all the sets $M_i$ one by one. All these sets are connected, and each nonempty $M_i$ contains an element of $M^{\prime }$ (namely, $i$). Thus their union is also connected.