Baltic Way 2019

(a) As an auxiliary result, we prove the following. There is no convex quadrilateral $ABCD$ in which $C$ is the closest neighbour of $A$, and $D$ is the closest neighbour of $B$. See Figure below: Convex quadrilateral. Indeed, the diagonals $AC$ and $BD$ cross at a point $P$ by convexity. The Triangle Inequality yields $$AD+BC<(AP+PD)+(BP+PC)=(AP+PC)+(BP+PD)=AC+BD.$$ Since $AC<AD$ by the first assumption, we must have $BC<BD$, contradicting the second assumption.

Now, consider a convex hostile polygon $P_1{P}_2...P_n$. We say a vertex $P_k$ has separation $h\ge 2$ when its closest neighbour is $Q_k=P_{k+h}$. Among all vertices, select one with minimal separation $h$; without loss of generality, we may take it to be $P_1$, thus its closest neighbour is $Q_1=P_{h+1}$. Since $h\ge 2$, the vertex $P_2$ does not belong to the line $P_1{P}_{h+1}$. The closest neighbour of $P_2$ cannot lie on the opposite side of this line according to the auxiliary result proved above, i.e. $Q_2$ is to be found among the vertices $P_1,...,P_{h+1}$. But then $P_2$ will have separation at most $h-1$, which contradicts the minimality of $h$.

(b) Answer: Hostile concave polygons exist for all $n\ge 4$. Start from the type of zig-zag construction given in Figure below, and dislocate the vertices slightly, so as to make all distances unequal (to make each vertex have a unique closest neighbour).