Let $n \geq 4$, and consider a (not necessarily convex) polygon $P_1P_2\hdots P_n$ in the plane. Suppose that, for each $P_k$, there is a unique vertex $Q_k\ne P_k$ among $P_1,\hdots, P_n$ that lies closest to it. The polygon is then said to be hostile if $Q_k\ne P_{k\pm 1}$ for all $k$ (where $P_0 = P_n$, $P_{n+1} = P_1$). (a) Prove that no hostile polygon is convex. (b) Find all $n \geq 4$ for which there exists a hostile $n$-gon.
Problem
Source: 2019 Baltic Way P15
Tags: geometry, combinatorial geometry
Pathological
24.11.2019 19:13
(a) Define the length of a diagonal $P_i P_j$ for $1 \le i < j \le n$ to be $\min(j- i, n-(j-i)).$ We will show that no convex polygon $P_1P_2 \cdots P_n$ is hostile. Call a diagonal $P_i P_j$ tasty if either $Q_i = P_j$ or $Q_j = P_i.$ Consider the tasty diagonal of minimum length. WLOG it's $P_i P_j$ and has length $j- i,$ for $1 \le i < j \le n.$ Suppose that $Q_i = P_j.$ If $j = i+1$, we win. Else consider $Q_{i+1}.$ If it is $P_k$, where $i \le k \le j$, then clearly $P_{i+1} Q_{i+1}$ is a tasty diagonal which has length less than $P_i P_j.$ Hence, we must have that $P_{i+1} Q_{i+1}$ intersects $P_i Q_i$ in its interior. But then notice by the Triangle Inequality applied twice that $P_i Q_i + P_{i+1} Q_{i+1} > P_i Q_{i+1} + P_{i+1} Q_i.$ This clearly contradicts the fact that $P_i Q_i < P_i Q_{i+1}$ and $P_{i+1} Q_{i+1} < P_{i+1} Q_i.$ The case where $Q_j = P_i$ is analogous (or just reverse the labels of the $P_i$'s and use the above argument). $\square$ (b) I think there exists a hostile polygon for all $n \ge 4.$ It's pretty easy to construct this by using polygons which "zigzag" a lot. $\square$
Samusasuke
21.08.2020 03:23
@above Indeed!. here are all examples for $n\geq 4$ attached (don't know how to include in the text)
Attachments:
