Maths Olympiad Prep

Library / /95 of 106

Geometry Difficulty 8.8 Shortlist Prove it IMO

Let n3n \geqslant 3 be an integer. Two regular nn-gons A\mathcal{A} and B\mathcal{B} are given in the plane. Prove that the vertices of A\mathcal{A} that lie inside B\mathcal{B} or on its boundary are consecutive.
(That is, prove that there exists a line separating those vertices of A\mathcal{A} that lie inside B\mathcal{B} or on its boundary from the other vertices of A\mathcal{A}.)

Solution

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

Now we separate two cases.

Figure 1
Construction of C\mathcal{C}
Figure 2
Case 1: Translation

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

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

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

For this purpose, let C1,C2C_{1}, C_{2}, and C3C_{3} be three vertices in CL\mathcal{C}_{\mathrm{L}} such that C2C_{2} is between C1C_{1} and C3C_{3}, and t(C1)t\left(C_{1}\right) and t(C3)t\left(C_{3}\right) lie in B\mathcal{B}; we need to prove that t(C2)Bt\left(C_{2}\right) \in \mathcal{B} as well. Let Ai=t(Ci)A_{i}=t\left(C_{i}\right). The line through C2C_{2} parallel to v\vec{v} crosses the segment C1C3C_{1}C_{3} to the right of C2C_{2}; this means that this line crosses A1A3A_{1}A_{3} to the right of A2A_{2}, so A2A_{2} lies inside the triangle A1C2A3A_{1}C_{2}A_{3} which is contained in B\mathcal{B}. This yields the desired result.

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

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

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

Figure 3
Case 2, XX inside B\mathcal{B}
Figure 4
Subcase 2.1: k>1k>1

## Subcase 2.1: k>1k>1.

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

Again, let C1,C2,C3C_{1}, C_{2}, C_{3} be three vertices in CL\mathcal{C}_{\mathrm{L}} such that C2C_{2} is between C1C_{1} and C3C_{3}, and h(C1)h\left(C_{1}\right) and h(C3)h\left(C_{3}\right) lie in B\mathcal{B}. Let Ai=h(Ci)A_{i}=h\left(C_{i}\right). Then the ray XC2X C_{2} crosses the segment C1C3C_{1}C_{3} beyond C2C_{2}, so this ray crosses A1A3A_{1}A_{3} beyond A2A_{2}; this implies that A2A_{2} lies in the triangle A1C2A3A_{1}C_{2}A_{3}, which is contained in B\mathcal{B}.

Figure 5
Subcase 2.2: k<1k<1

## Subcase 2.2: k<1k<1.

This case is completely similar to the previous one. All points from BL\mathcal{B}_{\mathrm{L}} (and hence from CL\mathcal{C}_{\mathrm{L}}) move out from B\mathcal{B} under hh, because they are the nearest points of B\mathcal{B} on the corresponding rays emanated from XX. Assume that C1,C2C_{1}, C_{2}, and C3C_{3} are three vertices in CR\mathcal{C}_{\mathrm{R}} such that C2C_{2} lies between C1C_{1} and C3C_{3}, and h(C1)h\left(C_{1}\right) and h(C3)h\left(C_{3}\right) lie in B\mathcal{B}; let Ai=h(Ci)A_{i}=h\left(C_{i}\right). Then A2A_{2} lies on the segment XC2X C_{2}, and the segments XA2X A_{2} and A1A3A_{1}A_{3} cross each other. Thus A2A_{2} lies in the triangle A1C2A3A_{1}C_{2}A_{3}, which is contained in B\mathcal{B}.

Now, choose a vertex A1A_{1} of A\mathcal{A} such that the vector OAA1\overrightarrow{O_{A} A_{1}} points "mostly outside H1\mathcal{H}_{1}"; strictly speaking, this means that the scalar product OAA1,b1\left\langle\overrightarrow{O_{A} A_{1}}, \overrightarrow{b_{1}}\right\rangle is minimal. Starting from A1A_{1}, enumerate the vertices of A\mathcal{A} clockwise as A1,A2,,AnA_{1}, A_{2}, \ldots, A_{n}; by the rotational symmetry, the choice of A1A_{1} yields that the vector OAAi\overrightarrow{O_{A} A_{i}} points "mostly outside Hi\mathcal{H}_{i}", i.e.,
OAAi,bi=minj[n]OAAj,bi. \begin{equation*} \left\langle\overrightarrow{O_{A} A_{i}}, \overrightarrow{b_{i}}\right\rangle=\min_{j \in[n]}\left\langle\overrightarrow{O_{A} A_{j}}, \overrightarrow{b_{i}}\right\rangle . \tag{1} \end{equation*}
Figure 6

We intend to reformulate the problem in more combinatorial terms, for which purpose we introduce the following notion. Say that a subset I[n]I \subseteq[n] is connected if the elements of this set are consecutive in the cyclic order (in other words, if we join each ii with i+1modni+1 \bmod 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 H\mathcal{H} the indices of vertices of, say, A\mathcal{A} that lie in H\mathcal{H} form a connected set.

To access the problem, we denote
M={j[n]:AjB},Mi={j[n]:AjHi} for i[n]. M=\left\{j \in[n]: A_{j} \notin \mathcal{B}\right\}, \quad M_{i}=\left\{j \in[n]: A_{j} \notin \mathcal{H}_{i}\right\} \quad \text{ for } i \in[n] .
We need to prove that [n]\M[n] \backslash M is connected, which is equivalent to MM being connected. On the other hand, since B=i[n]Hi\mathcal{B}=\bigcap_{i \in[n]} \mathcal{H}_{i}, we have M=i[n]MiM=\bigcup_{i \in[n]} M_{i}, where the sets MiM_{i} are easier to investigate. We will utilize the following properties of these sets; the first one holds by the definition of MiM_{i}, along with the above remark.

Figure 7
The sets MiM_{i}

Property 1: Each set MiM_{i} is connected. \square

Property 2: If MiM_{i} is nonempty, then iMii \in M_{i}.

Proof. Indeed, we have
jMiAjHiBiAj,bi<0OAAj,bi<OABi,bi. \begin{equation*} j \in M_{i} \Longleftrightarrow A_{j} \notin \mathcal{H}_{i} \Longleftrightarrow\left\langle\overrightarrow{B_{i} A_{j}}, \overrightarrow{b_{i}}\right\rangle<0 \Longleftrightarrow\left\langle\overrightarrow{O_{A} A_{j}}, \overrightarrow{b_{i}}\right\rangle<\left\langle\overrightarrow{O_{A} B_{i}}, \overrightarrow{b_{i}}\right\rangle . \tag{2} \end{equation*}
The right-hand part of the last inequality does not depend on jj. Therefore, if some jj lies in MiM_{i}, then by (1) so does ii. \square

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

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

Proof. To prove this property, we proceed on with the investigation started in (2) to write
iMAiMiBiAi,bi<0OBOA,bi<OBBi,bi+AiOA,bi. i \in M^{\prime} \Longleftrightarrow A_{i} \in M_{i} \Longleftrightarrow\left\langle\overrightarrow{B_{i} A_{i}}, \overrightarrow{b_{i}}\right\rangle<0 \Longleftrightarrow\left\langle\overrightarrow{O_{B} O_{A}}, \overrightarrow{b_{i}}\right\rangle<\left\langle\overrightarrow{O_{B} B_{i}}, \overrightarrow{b_{i}}\right\rangle+\left\langle\overrightarrow{A_{i} O_{A}}, \overrightarrow{b_{i}}\right\rangle .
The right-hand part of the obtained inequality does not depend on ii, due to the rotational symmetry; denote its constant value by μ\mu. Thus, iMi \in M^{\prime} if and only if OBOA,bi<μ\left\langle\overrightarrow{O_{B} O_{A}}, \overrightarrow{b_{i}}\right\rangle<\mu. This condition is in turn equivalent to the fact that BiB_{i} lies in a certain (open) half-plane whose boundary line is orthogonal to OBOAO_{B} O_{A}; thus, it defines a connected set. \square

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.