Sharygin 2025 CR P13

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Sharygin 2025 CR P13

G H J

Reveal topic tags

combinatorial geometry

L

G H BBookmark kLocked kLocked NReply

Source: Sharygin 2025

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Gengar_in_Galar

29 posts

Gengar_in_Galar

#1 h Mar 10, 2025, 12:08 PM

Y by

Each two opposite sides of a convex $2n$ -gon are parallel. (Two sides are opposite if one passes $n-1$ other sides moving from one side to another along the borderline of the $2n$ -gon.) The pair of opposite sides is called regular if there exists a common perpendicular to them such that its endpoints lie on the sides and not on their extensions. Which is the minimal possible number of regular pairs?
Proposed by: B.Frenkin

This post has been edited 1 time. Last edited by Gengar_in_Galar, Mar 11, 2025, 9:54 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

60 posts

#2 h Mar 10, 2025, 12:24 PM

Y by

The minimal possible number of regular pairs is \boxed{1}.

We will give a construction for the common perpendicular

Let $f(x):=\left(\frac{x-1}{n-1}\right)^{2}-\frac{1}{2}$ and note that for $1\leq x\leq n$ we have $-\frac{1}{2}\leq f(x)\leq\frac{1}{2}$ . Consider a centrally symmetric polygon with vertices $P_{1},\ldots,P_{2n}$ given by $P_{x}:=(x,f(x))$ and $P_{x+n}:=-P_{x}$ for $1\leq x\leq n$ .

To prove the polygon is convex, it suffices to show that the 2D cross product (cross product $P_{i}P_{i+1}\times P_{i+1}P_{i+2}$ is positive) (i.e., the signed area of the triangle made by any three consecutive vertices) is positive for every set of three consecutive vertices. In other words, if we denote

$\vec{A}=P_{i+1}-P_{i}\quad\text{and}\quad\vec{B}=P_{i+2}-P_{i+1},$
we must show that

$\vec{A}\times\vec{B}>0\quad\text{for all }i,$
where the cross product can be computed via the determinant

$\vec{A} \times \vec{B} = \det\begin{pmatrix} 1 & 1 \\ f(i+1)-f(i) & f(i+2)-f(i+1) \end{pmatrix}.$
For $1\leq x\leq n$ we have

$P_{x}=\left(x,f(x)\right)\quad\text{with}\quad f(x)=\left(\frac{x-1}{n-1}\right)^ {2}-\frac{1}{2}.$
Define

$g(x):=\left(\frac{x-1}{n-1}\right)^{2},$
so that $f(x)=g(x)-\frac{1}{2}$ . For three consecutive vertices $P_{i},P_{i+1},P_{i+2}$ , the vectors corresponding to edges are

$\vec{A}=P_{i+1}-P_{i}=\left(1,\;f(i+1)-f(i)\right)$
and

$\vec{B}=P_{i+2}-P_{i+1}=\left(1,\;f(i+2)-f(i+1)\right).$
Then, the signed area (i.e., the cross product) is given by

$\vec{A} \times \vec{B} = \det\begin{pmatrix} 1 & 1 \\ f(i+1)-f(i) & f(i+2)-f(i+1) \end{pmatrix}.$
Thus,

$\vec{A}\times\vec{B}=f(i+2)-2f(i+1)+f(i).$
Because $f(x)=g(x)-\frac{1}{2}$ , the constant $-\frac{1}{2}$ cancels out in the second difference, so that

$\vec{A}\times\vec{B}=g(i+2)-2g(i+1)+g(i).$
Since

$g(x)=\left(\frac{x-1}{n-1}\right)^{2}=\frac{(x-1)^{2}}{(n-1)^{2}},$
this is a quadratic function in $x$ with leading coefficient

$a=\frac{1}{(n-1)^{2}}.$
For a quadratic function $ax^{2}+bx+c$ , its second finite difference is constant and equal to $2a$ . In our case,

$g(i+2)-2g(i+1)+g(i)=\frac{2}{(n-1)^{2}}.$
Thus, we obtain

$\vec{A}\times\vec{B}=\frac{2}{(n-1)^{2}}>0.$
The polygon is defined to be centrally symmetric by the relation

$P_{x+n}=-P_{x}\quad\text{for }1\leq x\leq n.$
This symmetry implies that the behavior of the second half of the polygon mirrors first half. In particular, the second differences (which measure the turning of the polygon) are the same by symmetry if the vertices are taken in order along the full polygon. Therefore, the cross product is positive between every set of three consecutive vertices in the entire polygon.

Since the cross product for any three consecutive vertices is given by

$P_{t}P_{t+1}\times P_{t+1}P_{t+2}=\frac{2}{(n-1)^{2}}>0,$
the polygon consistently turns in one direction, proving that it is convex.

\subsection*{Alternative Proof}

To show that the polygon defined by the vertices $P_{1},P_{2},\ldots,P_{2n}$ is convex, we will show the 2D cross products $P_{i}P_{i+1}\times P_{i+1}P_{i+2}$ for $i=1,2,\ldots,2n-2$ are positive.

$P_{i}=(i,f(i))=\left(i,\left(\frac{i-1}{n-1}\right)^{2}-\frac{1}{2}\right)$
$P_{i+1}=(i+1,f(i+1))=\left(i+1,\left(\frac{i}{n-1}\right)^{2}-\frac{1}{2}\right)$
$P_{i+2}=(i+2,f(i+2))=\left(i+2,\left(\frac{i+1}{n-1}\right)^{2}-\frac{1}{2}\right)$
Next, we compute the vectors $P_{i}P_{i+1}$ and $P_{i+1}P_{i+2}$ :

$P_{i}P_{i+1}=P_{i+1}-P_{i}=((i+1)-i,f(i+1)-f(i))=(1,f(i+1)-f(i))$
$P_{i+1}P_{i+2}=P_{i+2}-P_{i+1}=((i+2)-(i+1),f(i+2)-f(i+1))=(1,f(i+2)-f(i+1))$
Now, we can compute the cross product $P_{i}P_{i+1}\times P_{i+1}P_{i+2}$ .

$(a,b)\times(c,d)=ad-bc$
Applying it:

$P_{i}P_{i+1}\times P_{i+1}P_{i+2} = \begin{vmatrix} 1 & f(i+1)-f(i) \\ 1 & f(i+2)-f(i+1) \end{vmatrix} = 1 \cdot (f(i+2)-f(i+1)) - 1 \cdot (f(i+1)-f(i))$
This simplifies to:

$f(i+2)-2f(i+1)+f(i)$
The expression is $f(i+2)-2f(i+1)+f(i)$ . This is the second finite difference of the function $f$ , which indicates the concavity or convexity of $f$ .

To show that this expression is positive, we can compute the second derivative of $f(x)$ :

1. $f^{\prime}(x)$ :
$f(x)=\left(\frac{x-1}{n-1}\right)^{2}-\frac{1}{2}$ $f^{\prime}(x)=2\cdot\frac{x-1}{n-1}\cdot\frac{1}{n-1}=\frac{2(x-1)}{(n-1)^{2}}$
2. $f^{\prime\prime}(x)$ :
$f^{\prime\prime}(x)=\frac{2}{(n-1)^{2}}$
Since $f^{\prime\prime}(x)>0$ for all $x$ in the interval $[1,n]$ , this means that $f(x)$ is a convex function on this interval.

Thus, the second finite difference $f(i+2)-2f(i+1)+f(i)>0$ for $1\leq i\leq n-2$ , which implies that the cross product $P_{i}P_{i+1}\times P_{i+1}P_{i+2}>0$ .

Therefore, the polygon is convex.

The pair of edges $P_{n}P_{n+1}\parallel P_{2n}P_{1}$ has a common perpendicular: the $y$ -axis.

\textbf{Claim:} All other pairs $P_{k}P_{x+1}\parallel P_{n+x}P_{n+1+x}$ (for $1\leq x<n$ ) have no common perpendiculars. It suffices to show that the angle $\angle P_{n+x}P_{x}P_{x+1}$ is obtuse.

We should compute the dot product, which should be negative:

$(P_{n+x}-P_{x})\cdot(P_{x+1}-P_{x})=-2P_{x}\cdot(P_{x+1}-P_{x})$ $=-2(x,f(x))\cdot(1,f(x+1)-f(x))$ $=-2x-2f(x)(f(x+1)-f(x))$ $\leq-2+2|f(x)|(|f(x+1)|+|f(x)|)$ $\leq-2+2\cdot\frac{1}{2}\left(\frac{1}{2}+\frac{1}{2}\right)=-1.$
.

This post has been edited 2 times. Last edited by drago.7437, Mar 10, 2025, 1:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

247 posts

#3 h Mar 10, 2025, 12:51 PM

Y by

Funnily enough, this problem was actually already posted on Stack Exchange before the contest ended.

The above solution is quite literally the exact same as the solution posted here (word to word, even!).

This post has been edited 1 time. Last edited by InterLoop, Mar 10, 2025, 1:00 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

60 posts

#4 h Mar 10, 2025, 1:10 PM

Y by

@above , yes you are absolutely right .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

AN1729

#5 h Mar 14, 2025, 3:01 PM

Y by

Combi-Geo : |
Since, I am too bored to latex, I will upload my pdf soln.
(P.S My handwriting is readable : ))

Attachments:

P13-compressed.pdf (370kb)

This post has been edited 2 times. Last edited by AN1729, Mar 14, 2025, 5:27 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

13 posts

HVP

#6 h Yesterday at 1:52 PM

Y by

Well yeah, this is my solution, quite long tho, without ANY type of computing, just purely geometric reasoning.
This is a very beautiful problem, yet it is VERY HARD.

Attachments:

Problem 13 Sharygin Olympiad 24.25.pdf (125kb)

This post has been edited 1 time. Last edited by HVP, Yesterday at 1:56 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a