Let $n\ge3$ be an integer. Two regular $n$-gons $\mathcal{A}$ and $\mathcal{B}$ are given in the plane. Prove that the vertices of $\mathcal{A}$ that lie inside $\mathcal{B}$ or on its boundary are consecutive. (That is, prove that there exists a line separating those vertices of $\mathcal{A}$ that lie inside $\mathcal{B}$ or on its boundary from the other vertices of $\mathcal{A}$.)
Problem
Source: IMO Shortlist 2017 G6
Tags: IMO Shortlist, geometry, Simple Statement
me9hanics
10.07.2018 15:26
Wow, sounds so simple yet isn't trivial..
Wizard_32
11.07.2018 11:02
Any solution?
SHARKYKESA
13.07.2018 10:59
We solved this problem during our training. Here, we refer to a polygon as both the interior and its boundary. We try to find a regular $n$-gon $\mathcal{C}$ inscribed in $\mathcal{B}$ which is either a translation or a positive dilation of $\mathcal{A}$. We construct it as follows: Let $O_A$ and $O_B$ be the centres of $\mathcal{A}$ and $\mathcal{B}$ respectively, and let $A$ be an arbitrary vertex of $\mathcal{A}$. Let the ray originating from $O_B$ in the same direction to the vector $O_A A$ intersect $\mathcal{B}$ at $C$. Rotating $C$ about $O_B$ with angle $\dfrac{2\pi}{n}$ yields a regular $n$-gon $\mathcal{C}$, which is a dilation/translation of $\mathcal{A}$, so we're done. [asy][asy] import graph; size(6.cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ real xmin = -1.5, xmax = 0.5, ymin = -0.4, ymax = 1.4; /* image dimensions */ pen uuuuuu = rgb(0.26666666666666666,0.26666666666666666,0.26666666666666666); pen qqffff = rgb(0.,1.,1.); pair O_B = (-0.5997940967676232,0.4861842206353406), O_A = (-0.11264301360819354,0.33984682648720516), A = (-0.44239278521538944,0.8919278834962218), C = (-0.9538478522156285,1.0789560384687427); /* draw figures */ draw((-1.079918702174105,-0.21244823816121508)--(-0.08372180682202204,-0.18633071656022412), linewidth(.5) + red); draw((-0.08372180682202204,-0.18633071656022412)--(0.19928072447723078,0.7691795903030363), linewidth(.5) + red); draw((0.19928072447723078,0.7691795903030363)--(-0.6220109876296579,1.3335999149443825), linewidth(.5) + red); draw((-0.6220109876296579,1.3335999149443825)--(-1.4125997116895617,0.7269205526507238), linewidth(.5) + red); draw((-1.4125997116895617,0.7269205526507238)--(-1.079918702174105,-0.21244823816121508), linewidth(.5) + red); draw((-0.739601583717616,0.19683858634161325)--(-0.17037494786665455,-0.30061818360309456), linewidth(.5) + green); draw((-0.17037494786665455,-0.30061818360309456)--(0.4786352588932256,0.08702592179194764), linewidth(.5) + green); draw((0.4786352588932256,0.08702592179194764)--(0.3105189898654669,0.8240599244093376), linewidth(.5) + green); draw((0.3105189898654669,0.8240599244093376)--(-0.4423927852153894,0.8919278834962218), linewidth(.5) + green); draw((-0.4423927852153894,0.8919278834962218)--(-0.739601583717616,0.19683858634161325), linewidth(.5) + green); draw(O_A--(-0.4423927852153894,0.8919278834962219), linewidth(.5),EndArrow(6)); draw(O_B--C, linewidth(.5),EndArrow(6)); draw(C--(-1.2729622241499092,0.3326356548947962), linewidth(.5) + qqffff); draw((-1.2729622241499092,0.3326356548947962)--(-0.6617811241849898,-0.2014858297495154), linewidth(.5) + qqffff); draw((-0.6617811241849898,-0.2014858297495154)--(0.035063940809158596,0.21472932219269109), linewidth(.5) + qqffff); draw((0.035063940809158596,0.21472932219269109)--(-0.14544322409674773,1.0060859173699883), linewidth(.5) + qqffff); draw((-0.14544322409674773,1.0060859173699883)--C, linewidth(.5) + qqffff); /* dots and labels */ dot(O_B,linewidth(2.pt) + uuuuuu); label("$O_B$", (-0.5873860309431387,0.5099104004047209), NE * labelscalefactor,uuuuuu); dot(O_A,linewidth(2.pt) + uuuuuu); label("$O_A$", (-0.09989420143119244,0.363075511997508), NE * labelscalefactor,uuuuuu); dot(A,linewidth(2.pt) + uuuuuu); label("$A$", (-0.43174104923149315,0.9151746924086287), NE * labelscalefactor,uuuuuu); dot(C,linewidth(2.pt) + uuuuuu); label("$C$", (-0.9427264608885934,1.1031233495698614), NE * labelscalefactor,uuuuuu); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] Let $d$ denote the mapping of $\mathcal{C}$ to $\mathcal{A}$, and let the centre of this dilation be $O$ with factor $\lambda > 0$. Note that if the dilation was a translation of $\mathcal{A}$, then by applying a dilation on $\mathcal{A}$ with centre $O_B$ and factor of $1-\epsilon$ for sufficiently small positive $\epsilon$ will create a smaller polygon $\mathcal{A}'$, and preserve the vertices already inside or outside $\mathcal{B}$, so we can then assume the polygons are $\mathcal{A}'$ and $\mathcal{C}$ instead. We will show the vertices of $\mathcal{C}$ that were already in $\mathcal{B}$ are consecutive upon $d$ being applied. If $O \in \mathcal{B}$, then if $\lambda < 1$, then for each of the vertices $A$ of $\mathcal{A}$ lie on the segment $OC$, where $C$ is the corresponding vertex to $A$ on $\mathcal{C}$, which lie in $\mathcal{B}$, so we're done in this case. If $\lambda > 1$, $A$ lies on the extension of $OC$, which lie outside $\mathcal{B}$, so we're done in this case. Thus, we can assume $O \not \in \mathcal{B}$. Case 1: $\lambda > 1$ Let $X$ and $Y$ be two vertices of $\mathcal{B}$ such that $XOY$ contains $\mathcal{B}$. If there are multiple choices for this, choose the two vertices farthest from $O$. For ease of understanding, consider the plane to be the Cartesian plane, with $XY$ parallel to the $y$-axis. Also, WLOG $O$ lies to the right of $XY$. Let $\mathcal{B}_R$ denote the set of perimeter points of $\mathcal{B}$ to the right of $XY$, and $\mathcal{B}_L$ denote the set of perimeter points of $\mathcal{B}$ to the left of $XY$. Thus, the vertices of $\mathcal{C}$ are also split into set $\mathcal{C}_R \subset \mathcal{B}_R$ and $\mathcal{C}_L \subset \mathcal{B}_L$. We have all the points from $\mathcal{B}_L$ (including $\mathcal{C}_L$) move out from $\mathcal{B}$ under $d$ since they are the farthest points of $\mathcal{B}$ on the corresponding rays from $O$. Thus, it suffices to show the vertices of $\mathcal{C}_R$ which remain in $\mathcal{B}$ are consecutive. Let $C_1$, $C_2$, $C_3$ be 3 vertices in $\mathcal{C}_R$ such that $C_2$ lies in between $C_1$ and $C_3$ and both $d(C_1)$ and $d(C_3)$ lie in $\mathcal{B}$. Let $A_i = d(C_i)$. Thus, the ray $OC_2$ intersects $C_1C_3$ beyond $C_2$, so intersects $A_1A_3$ beyond $A_2$. Therefore, $A_2$ lies in triangle $C_2 A_1 A_3$, so $A_2$ lies in $\mathcal{B}$. Thus, proven in this case. Case 2: $\lambda < 1$ We will apply the same logic as before, except have $X$ and $Y$ as the closest satisfying points to $O$ instead of furthest. All the points in $\mathcal{B}_R$ move out from $\mathcal{B}$ under $d$ since they are the closest points of $\mathcal{B}$ on the corresponding rays from $O$. Thus, it suffices to show the vertices of $\mathcal{C}_L$ remain in $\mathcal{B}$. Again, let $C_1$, $C_2$, $C_3$ be points in $\mathcal{C}_L$ such that $C_2$ lies in betwen $C_1$ and $C_3$ and both $h(C_1)$ and $h(C_3)$ lie in $\mathcal{B}$, with $A_i = h(C_i)$. Then $A_2$ lies ons egment $OC_2$, and since the intersection of $OC_2$ and $C_1C_3$ lies on $OC_2$, we must have $A_2$ inside $C_2A_1A_3$, so $A_2$ is inside $\mathcal{B}$. Thus, proven in this case. Therefore, the vertices of $\mathcal{A}$ that remain inside $\mathcal{B}$ are consecutive.
gvole
29.12.2021 18:59
What's the motivation behind considering the polygon which is a homothetic image of $\mathcal{A}$ whose vertices are in $\mathcal{B}$?
Siddharth03
19.05.2023 00:39
Hehe, mass point geo and convexity go brr A very nice problem! Lemme share a completely different solution I came up with :
In this proof, whenever I say similar, I mean directly similar
Let $R(\mathcal{A})$ denote the region covered by $\mathcal{A}$, i.e. boundary and interior. Let $D_{\mathcal{A}}(A,B)$ denote the number of sides between $A$ to $B$ while going counterclockwise on $\mathcal{A}$ Lemma 1: Let $ABC$ be a triangle formed by 3 vertices of $\mathcal{A}$. Let $A',B'$ be vertices of $\mathcal{A}$ on the other side of $B$ w.r.t. $AC$ such that the vertices $A,A',C',C$ are in order ($A$ can be the same as $A'$ and $C$ can be the same as $C'$). Consider the point $B'$ so that $\triangle ABC \sim \triangle A'B'C'$. Then $B' \in R(\mathcal{A})$.
Assume WLOG, $\triangle ABC$ is oriented counterclockwise.
Note that as $A,B,C$ are vertices of $\mathcal{A}$, $\angle BAC = a\alpha$ where $\alpha = \frac{180^{\circ}}{n}$ and $a = D_{\mathcal{A}}(B,C)$.
Therefore, $\angle B'A'C' = \angle BAC = a\alpha$. So, $A'B'$ intersects $\mathcal{A}$ again at a vertex $B_0$ where $D_{\mathcal{A}}(B_0,C') = a$.
Also, as $\angle C'B_0A' = \angle C'BA' \leq \angle CBA = \angle C'B'A'\implies B' \in \overline{AB_0}\implies B' \in R(\mathcal{A})$.
In what follows, we shall mainly use the following 2 well-known results about mass points: Theorem 1: Let $\Delta_1,\Delta_2,\dots,\Delta_k$ be $k$ similar triangles and let $\lambda_1,\lambda_2,\dots,\lambda_k$ be $k$ real numbers summing up to $1$. Then $\lambda_1\Delta_1+\lambda_2\Delta_2+\dots+\lambda_k\Delta_k$ is also similar to each $\Delta_i$ Theorem 2: Let $A_1,A_2,\dots,A_k$ be any $k$ points. Then, for any point $X$; $X$ can be represented as $\lambda_1A_1+\lambda_2A_2+\dots+\lambda_kA_k$ where the $\lambda_i$'s are non-negative reals summing up to $1$ iff $X$ is contained in the convex hull of $A_1,A_2,\dots,A_n$ Now, returning to the main problem, observe that it suffices to show that there do not exist distinct vertices $A,B,C,D$ of $\mathcal{B}$ (in order) so that $A,C\in R(\mathcal{A})$ but $B,D\not\in R(\mathcal{A})$. FTSOC, assume that such 4 points exist. Lemma 2: We can WLOG assume that $A,C$ are on the boundary of $\mathcal{A}$.
Let $\overleftrightarrow{AC}$ intersect $\mathcal{A}$ at $A',C'$ where $A',A,C,C'$ are in order. Let the homothety at center $O$ and ratio $k$ taking $A,C$ to $A',C'$ respectively be $\mathcal{H}$. Let $\mathcal{H}$ take $B$ to $B'$, $D$ to $D'$ and $\mathcal{B}$ to $\mathcal{B}'$. Observe that as $O\in R(\mathcal{A}), k = \frac{A'C'}{AC} \geq 1$ and as $\mathcal{A}$ is convex, $B',D'\not\in R(\mathcal{A})b$.
Now, observe that after replacing $\mathcal{B}$ by $\mathcal{B}'$; $A',B',C',D'$ satisfy exactly what we assumed about $A,B,C,D$ plus $A',C'$ are on the boundary of $\mathcal{A}$. So, we can work with $A',B',C',D'$ and get a contradiction instead of working with $A,B,C,D$
WLOG, let $\square ABCD$ be oriented in counterclockwise sense. Let $b_1 = D_{\mathcal{B}}(A,C), b_2 = D_{\mathcal{B}}(C,A)$. Let the halfplanes determined by $\overleftrightarrow{AC}$ containing $B,D$ be $\mathcal{L},\mathcal{R}$ respectively. Let $A$ be on side $A_0A_1$ and let $C$ be on side $C_0C_1$ in $\mathcal{C}$ (It's fine if either of $A,C$ are the endpoints of these sides) such that $A_0,C_0\in L\cup\{A,C\}$ and $A_1,C_1\in R\cup\{A,C\}$ Let $a_1 = D_{\mathcal{A}}(A_0,C_0), a_2 = D_{\mathcal{A}}(C_1,A_1)$. As $b_1 + b_2 = n = a_1+a_2+2$ we can now make the following two cases : 1. $a_1\geq b_1$ or $a_2\geq b_2$ 2. $b_1 = a_1+1, b_2 = a_2+1$ WLOG, let the side length of $\mathcal{A}$ be $1$ and let $A_0A = a, C_0C = c$.
1. $a_1\geq b_1$ or $a_2\geq b_2$
WLOG, assume $a_1\geq b_1$. We shall prove that $B\in R(\mathcal{A})$ which would be a contradiction.
Then, there are 2 vertices $X,Z\in \mathcal{L}\cup\{A,C\}$ of $\mathcal{A}$, so that $D_{\mathcal{A}}(X,Z) = b_1$.
Also, as $A,B,C$ are vertices of $\mathcal{B}$, we can also choose $Y$ from one of the vertices of $\mathcal{A}$ from $X$ to $Z$ s.t. $\triangle XYZ \sim \triangle ABC$.
Now, consider points $B_1,B_2,B_3,B_4$ so that $\triangle A_0B_1C_0 \sim\triangle A_1B_2C_0 \sim\triangle A_0B_3C_1 \sim\triangle A_1B_4C_1 \sim\triangle XYZ \sim\triangle ABC$.
By Theorem 1, we have that $B_1,B_2,B_3,B_4\in R(\mathcal{A})$.
Now, in the cartesian plane, $(a,c)$ belongs to the convex hull of the four points $(0,0),(1,0),(0,1),(1,1)$. So, by Theorem 2 we can choose non-negative reals $\lambda_1,\lambda_2,\lambda_3,\lambda_4$ summing up to 1 so that $\lambda_1(0,0) + \lambda_2(1,0) + \lambda_3(0,1) + \lambda_4(1,1) = (a,c)$.
What this implies is that if $\triangle PQR = \lambda_1\triangle A_0B_1C_0+\lambda_2\triangle A_1B_2C_0+\lambda_3\triangle A_0B_3C_1 +\lambda_4\triangle A_1B_4C_1$, then $P\equiv A,R\equiv C$ and also as Theorem 1 implies $\triangle PQR\sim \triangle ABC$, $Q\equiv B$.
$\therefore B = Q = \lambda_1B_1 + \lambda_2B_2 + \lambda_3B_3 + \lambda_4B_4$ and hence $B$ in the convex hull of $B_1,B_2,B_3,B_4$ by Theorem 2.
$\therefore$ As $B_1,B_2,B_3,B_4 \in R(\mathcal{A})$, their convex hull is also contained in $R(\mathcal{A})$ and hence $B\in R(\mathcal{A})$ a contradiction.
2. $b_1 = a_1+1, b_2 = a_2+1$
As $(A_0A+C_0C) + (AA_1+CC_1) = 2$, WLOG, let $A_0A+C_0C = a+c \geq 1$.
What the condition $b_1 = a_1+1, b_2 = a_2+1$ says is that the diagonal $AC$ in $\mathcal{B}$ corresponds to both of the diagonals $A_0C_1$ and $A_1C_0$ in $\mathcal{A}$.
So, we can choose vertices $B_1,B_2$ of $\mathcal{A}$ so that $\triangle A_0B_1C_1 \sim\triangle A_1B_2C_0 \sim\triangle ABC$.
Also, by Lemma 2, we can also choose $B_3\in R(\mathcal{A})$ so that $A_1B_3C_1\sim ABC$.
Now, the condition $a+c\geq 1$ implies that in the cartesian plane, $(a,c)$ is in the convex hull of $(0,1),(1,0),(1,1)$.
So, just as in Case 1 we get that there are non-negative reals summing up to $1$ so that $(a,c) = \lambda_1(0,1) + \lambda_2(1,0) + \lambda_3(0,1)$ which in similar fashion implies that $B$ is in the convex hull of $B_1,B_2,B_3$ implying that $B\in R(\mathcal{A})$, a contradiction and we are done!
(lmk if there are any typos)
awesomeming327.
14.06.2024 21:22
Yet another different proof... Let $\mathcal{A}$ and $\mathcal{B}$ denote closed sets defining the interior of the polygon as their boundaries. Let $\mathcal{A}'$ and $\mathcal{B}'$ be open sets that are $\mathcal{A}$ and $\mathcal{B}$ with boundaries removed, respectively. Throughout the rest of this proof, we will take indices $\pmod n$. After translating $\mathcal{B}=B_1B_2\dots B_n$ so that its center $B$ coincides with the center $A$ of $\mathcal{A}=A_1A_2\dots A_n$, we see that by rotational symmetry, we can positively dilate the translated polygon at $A$ so that it is inscribed in $\mathcal{A}$. Call this polygon $\mathcal{C}=C_1C_2\dots=C_n$ where there exists either a positive homothety centered at $O$, or a translation, that takes $C_i$ to $B_i$ for each $i$. Let the factor of this homothety be $k$. WLOG, let $C_i\in A_iA_{i+1}$. Note that there are three different cases, and we will look at the case of translation first. We define a function $f_T(X)$ for any point $X$ on $\mathcal{A}$'s boundary that returns an interval that is defined as follows: draw a line $\ell_X$ through $X$ parallel to $AB$. Note that $\ell_X\cap \mathcal{A}$ is a line segment, so represent this as a closed interval $[a_T(X),b_T(x)]$ where $X$ is zero and $A\to B$ is the positive direction. Note that $B_i\in \mathcal{A}$ if and only if $AB\in f_T(B_i)$. Now we look at the case of a homothety with factor $k\neq 1$. Define $f_H(X)$ for any point $X$ on $\mathcal{A}$'s boundary in a similar fashion: draw line $OX$ which intersects $\mathcal{A}$ in a line segment $X_1X_2$ where $X_1$ is closer to $O$ than is $X_2$. Now, let our interval be \[[a_H(x),b_H(x)]=\left[\frac{OX_1}{OX},\frac{OX_2}{OX}\right]\]where $B_i\in\mathcal{A}$ if and only if $k\in f_H(B_i)$. We have created two indicator functions and these functions have the properties necessary for us to prove what we needed. We claim that $a_T(X)\le 0\le b_T(X)$ and $a_H(X)\le 1\le n_H(x)$. These are obvious since $X$ is on $X$ is on $X_1X_2$ and $\ell_X\cap\mathcal{A}$. We also claim that when we take each function as $X$ moves around the polygon counterclockwise, there is one contiguous subdomain in which the function is non-decreasing and one contiguous subdomain in which the function is non-increasing. This is obvious by convexity. Now that we have proved properties of the functions, note that if $AB>0$ then $AB>a_T(X)$. Therefore, $AB\in f_T(X)$ if and only if $AB\le b_T(X)$. By the nature of $b_T$, this is one contiguous segment of the $\mathcal{A}$'s boundary. The other four proceeds similarly, and so we are done.