
Problem 1. Given an integer $n \geq 3$, determine the smallest positive number $k$ such that any two points in any $n$-gon (or at its boundary) in the plane can be connected by a polygonal path consisting of $k$ line segments contained in the $n$-gon (including its boundary).

(David Hruška)


Solution. The following example shows that at least $m$ segments are needed for any $2 m$-gon, $m \geq 2$ :

![](https://cdn.mathpix.com/cropped/2024_04_17_ea42bc7e448a11d39c22g-01.jpg?height=425&width=1016&top_left_y=884&top_left_x=520)

FiguRE 1. Example for $m=5$

Indeed, a polygonal path connecting the marked vertices must intersect all the $m-1$ dashed line segments and hence it must at least $m$ times cross the vertical line. Since no two of these intersections can belong to the same line segment (WLOG no segment lies at the vertical line), we conclude that the path must contain at least $m$ line segments. It is clear that there is a $2 m+1$-gon which needs at least $m$ line segments as well. Hence, $k \geq\left\lfloor\frac{n}{2}\right\rfloor$ (obviously also for $n=3$ ).

Now we prove that this number is always sufficient. Denote the given $n$-gon by $P$ and the given points $A$ and $B$. Fix a triangulation of $P$ and a consider a triangle $T$ containing $A$. Cutting $P$ along the sides of $T$ produces the triangle and at at most three disjoint polygons. Let us take the union of one containing $B$ (if $B \in T$ we are done) with $T$ and replace $P$ by this new polygon. Doing the same for the point $B$ we can assume that $A$ and $B$ lie in triangles with two sides belonging to the boundary of the $r$-gon for some $r \leq n$. Let us call the pairs of sides $A$-sides and $B$-sides, respectively. Then let us connect $A$ by a line segment with the common vertex of the $A$-sides, analogously for $B$ and $B$-sides. These two vertices can be connected by a polygonal path $p$ starting at $A$ and ending at $B$ which has at most $\left\lfloor\frac{r}{2}\right\rfloor$ line segments - sides of the $r$-gon. Now we connect $A$ with the second vertex of $p$ and the penultimate vertex of $p$ with $B$. That gives a polygonal path contained in $P$ with the same number of vertices and hence also the desired upper bound.

Sketch of an alternative proof of the upper bound. Consider again a triangulation of $P$. The triangulation has $n-2$ triangles. We observe that if points $A$ and $B$ belong to different triangles, which is the only interesting case, they can be connected by a polygonal path with vertices in different triangles and with every segment except for the first one and the last one crossing a triangle (without having an endpoint in it) which is crossed by no other of the segments. It follows that the number $k$ of segments used satisfies the inequality $(k+1)+(k-2) \leq n-2$ and hence $k \leq\left\lfloor\frac{n}{2}\right\rfloor$.
