Find all natural numbers $n \ge 3$ for which in an arbitrary $n$-gon one can choose $3$ vertices dividing its boundary into three parts, the lengths of which can be the lengths of the sides of some triangle. (Fedir Yudin)
Problem
Source: 2021 Ukraine NMO 11.2
Tags: combinatorial geometry, combinatorics, geometry
01.05.2021 18:54
Answer. Any $n\neq 4$ works. n=4. Take a square to see it fails. n=3. Obviously any triangle works. Let $\mathcal{P}$ be the polygon. Assume $n\ge 5$. It's enough to show that we can always partition any $n$-gon into $3$ parts of length less than $P/2$ where $P$ is the perimeter of the polygon. We can do it by a weak greedy algorithm, that is ; take an arbitrary vertex $A$ and go further as long as the length of the sides we went through is less than $P/2$ in total. Let's say we can't go anymore after some point (which obviously happens) and let $l$ be the first side we can't visit, let its length be $|l|$ and let that "road" be $\xi$, then $$|\xi| +|l|>P/2$$so $$|\mathcal{P}\setminus\{\xi\cup l\}|<P/2$$And we can mark the $3$ endpoints of $\xi$ and $l$ (one in common) . $\mathbb{Q.E.D.}$