1354C2 The smallest side of the square containing 2*n regular polygon, n odd

Правка en4, от nhantran0, 2020-05-18 21:25:35

Note: This is NOT an official proof of the derived solution, as it is incoherent. It's rather a personal note for my illogical brain. It contains a derivation to the solution and the solution of Educational Codeforces Round 87 C2 at the bottom.

Source: https://math.stackexchange.com/a/458593/496530

From the above observation, 4 points of the polygon must be on the 4 sides of the minimal square. Each of 2 pairs, whose 2 points are on the opposite sides of the square, has the center of the polygon as its midpoint.

Below figures illustrate the minimal square when $$$n=5$$$. Half square on the left, full square on the right.

Recall: $$$n$$$ is odd. Let $$$d$$$ be the length of the longest diagonal.

Consider the point of interest to be $$$P$$$. Let's say $$$P$$$ is $$$k$$$ sides away from R, and $$$n-k$$$ sides away from M measured along the polygon circumference, where $$$k\in [0;n]$$$. Consider the left figure, $$$WU$$$ is the perpendicular bisector of $$$MP$$$, $$$WV$$$ is the perpendicular bisector of $$$RP$$$. Select $$$U$$$ where $$$\measuredangle{MPU}=45^{\circ}$$$. Select $$$V$$$ where $$$\measuredangle{RPV}=45^{\circ}$$$.

When $$$k=\lfloor\frac{n}{2}\rfloor+1$$$, $$$VU$$$ is the side of the minimal square containing the polygon.

Let $$$d=RM$$$ be the diagonal of the polygon.

But, $$$|VU|=d*\sin(\measuredangle{RMU})$$$, $$$|VU|$$$ should be smaller with smaller $$$\measuredangle{RMU}$$$ by using $$$k+1,k+2,..,n$$$. Why do these fail?

Because, when $$$k>\lfloor\frac{n}{2}\rfloor+1$$$, from the way the square was built, some points are outside of the square.

We can visualize these failed cases by considering 1 of them in the figure below where $$$n=9$$$, $$$k=6$$$ i.e. $$$k>\lfloor\frac{n}{2}\rfloor+1$$$:

We can show that the point immediately below the chosen point ($$$K$$$) is out of the square by proving $$$\measuredangle{EKJ}>45^{\circ}$$$.

Proof:

Recall that $$$K$$$ is $$$k$$$ sides away from $$$E$$$ along the polygon circumference. Recall that in failed cases, $$$k>\lfloor\frac{n}{2}\rfloor+1$$$.

$$$\measuredangle{SKE}=90^{\circ}-\frac{1}{2}.\frac{180^{\circ}.k}{n}$$$

$$$\measuredangle{EKJ}=(180^{\circ}-\frac{180^{\circ}}{n}).\frac{1}{2}-\angle{SKE}=\frac{90^{\circ}}{n}.(k-1)$$$

From $$$k>\lfloor\frac{n}{2}\rfloor+1$$$, since $$$n$$$ is odd and $$$k$$$ is integer, therefore $$$k-1>\frac{n}{2}$$$, so:

$$$\measuredangle{EKJ}>\frac{90^{\circ}}{n}.\frac{n}{2}=45^{\circ} \blacksquare$$$

Therefore $$$J$$$ (hence $$$F$$$) will be outside of the bounding square.

Now for the satisfied $$$k$$$:

$$$k=\lfloor\frac{n}{2}\rfloor+1\implies\measuredangle{EKJ}=\frac{90^{\circ}}{n}.\lfloor\frac{n}{2}\rfloor<\frac{90^{\circ}}{n}.\frac{n}{2}=45^{\circ}$$$

This guarantees $$$J$$$ (hence $$$F$$$ and other points in between) will be inside of the bounding square.

End of reasoning.

Begin of derivation:

Let:

  • $$$r$$$ be the radius of the circumscribed circle of the polygon

  • $$$s$$$ be the length of the polygon side

  • $$$\beta$$$ be the angle formed by a radius and a polygon side

  • $$$\theta$$$ be the exterior angle of the polygon

  • $$$m$$$ be the number of sides of the polygon

  • $$$v$$$, $$$u$$$ be the length of the upper and lower segment of the side of the minimal square, separated by the chosen vertex ($$$k$$$ polygon sides away from the top intersection of polygon & minimal square, in second figure: $$$v=PV$$$, $$$u=PU$$$)

  • $$$k=\lfloor\frac{n}{2}\rfloor$$$ which is symmetrical to $$$k=\lfloor\frac{n}{2}\rfloor+1$$$ in the polygon

$$$\theta=\frac{360^{\circ}}{m}=\frac{360^{\circ}}{2n}$$$

$$$r.\cos{\beta}=\frac{s}{2}{\implies}r=\frac{s}{2\cos{\beta}}=\frac{s}{2\cos{(\frac{\pi}{2}-\frac{\theta}{2})}}=\frac{s}{2\sin{(\frac{\theta}{2})}}$$$

$$$v=r.\sin{(\frac{1}{2}.\frac{{\pi}k}{n})}.\sqrt{2}=r.\sin{(\frac{\pi}{2n}.\lfloor\frac{n}{2}\rfloor)}.\sqrt{2}$$$

$$$u=r.\sin{(\frac{1}{2}.\frac{\pi(n-k)}{n})}.\sqrt{2}$$$

$$$ans=v+u$$$

For Educational Codeforces Round 87 C2:

double r = 1.0/(2.0*sin(PI/(2*n)));
double v = r*sin(PI/(2*n)*(n/2))*sqrt(2);
double u = r*sin(PI/(2*n)*(n-n/2))*sqrt(2);
double ans = v + u;

We can further simplify $$$v+u$$$:

$$$v=r\sqrt{2}\sin{(\frac{\pi}{2n}.\frac{n-1}{2})}$$$

$$$u=r\sqrt{2}\sin{(\frac{\pi}{2n}.(n-\frac{n-1}{2}))}$$$

$$$ans=v+u=r\sqrt{2}[\sin{(\frac{\pi}{4}-\frac{\pi}{4n})}+\sin{(\frac{\pi}{4}+\frac{\pi}{4n})}]=\frac{\sqrt{2}}{2\sin{\frac{\theta}{2}}}.2\sin{\frac{\pi}{4}}\cos{\frac{-\pi}{4n}}$$$

$$$\implies ans=\frac{s.\cos{\frac{\pi}{4n}}}{\sin{\frac{\pi}{2n}}}$$$

As a solution to 1354C2:

double ans = cos(PI/(4*n))/(sin(PI/(2*n)));
Теги #geometry

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский nhantran0 2020-05-21 17:45:16 190 Tiny change: 'c{2\pi}{n}.\lfloor\fr' -> 'c{2\pi}{n}\lfloor\fr'
en8 Английский nhantran0 2020-05-20 14:21:03 73
en7 Английский nhantran0 2020-05-19 02:27:21 97 Tiny change: Remove redundant 'Let $d$ be'
en6 Английский nhantran0 2020-05-19 02:20:09 340 Added GeoGebra information
en5 Английский nhantran0 2020-05-18 21:33:41 14 Tiny change: 'mference. Recall that in failed c' -> 'mference. In failed c'
en4 Английский nhantran0 2020-05-18 21:25:35 1960 Tiny change: '\n$\theta=360^{\circ}/{m}$\n\n$r.\' -> '\n$\theta=\frac{360^{\circ}}{2n}$\n\n$r.\' (published)
en3 Английский nhantran0 2020-05-18 19:29:58 3095 Tiny change: 'frac{s}{2}$$\implies$$r=\frac{1}' -> 'frac{s}{2}{\implies}r=\frac{1}'
en2 Английский nhantran0 2020-05-18 14:19:45 409 Tiny change: ' proof for ' -> ' proof for:\n1. '
en1 Английский nhantran0 2020-05-18 09:06:27 170 Initial revision (saved to drafts)