Croatian Mathematical Olympiad

Let a path be any line $A_i{A}_j$ and a wall be any line $A_k{B}_k$. We say that a path and a wall intersect if the path goes through an inner point of the wall. A path is good if there is no wall to intersect it, and a wall is irrelevant if it does not intersect any path.

Claim 1. For any $i\in \{1,2,\dots ,n\}$ there exists at least one good path from point $A_i$.

Proof. We will prove the claim for point $A_1$, and it holds analogously for all points $A_i$. Define the distance between a point $A$ and a wall $w$ as $$\underset{T\in w}{\min }|AT|.$$ Since all walls are mutually disjoint, we know that none of the walls $\overline{A_2{B}_2},\dots ,\overline{A_n{B}_n}$ contain point $A_1$. Let $\overline{A_k{B}_k}$ be the wall closest to $A_1$. We claim that the path $A_1{A}_k$ is good. If we assume the contrary, that means that there exists a wall which intersects $A_1{A}_k$, but then this wall is closer to $A_1$ than wall $\overline{A_k{B}_k}$, which is a contradiction. $\square$

Claim 2. There exists at least one irrelevant wall.

Proof. Without loss of generality, we can assume that points $A_1,A_2,\dots ,A_k$ are the vertices of the convex hull of $\{A_1,A_2,\dots ,A_n\}$, and that they are labelled clockwise in that order as the vertices of polygon $P=A_1{A}_2\dots A_k$. If the wall $w_1=\overline{A_1{B}_1}$ is irrelevant, we are done. Therefore, assume that $w_1$ intersects some path. That means that this wall goes through the inner points of polygon $P$, and since the walls are mutually disjoint, we conclude that $w_1$ must also intersect a path which is the side of $P$, because it cannot pass through any of the vertices of $P$ except $A_1$. Let $C$ be the intersection of wall $w_1$ and a side of $P$. Consider the arc $\text{overarc}{A}_{1}C$ (clockwise from point $A_1$ to point $C$), and note that it contains points $A_2,\dots ,A_l$. We can repeat this inference for wall $A_2{B}_2$. Since all walls are mutually disjoint, its corresponding arc is strictly smaller than the arc of $w_1$. Therefore, if all of the walls $\overline{A_2{B}_2},\dots ,\overline{A_{l-1}{B}_{l-1}}$ are relevant, then wall $\overline{A_l{B}_l}$ must surely be irrelevant. $\square$

Finally, we prove the problem statement by mathematical induction on $n$. The claim obviously holds for $n=1$. Assume the claim holds for some positive integer $n$. For $n+1$ it follows from Claim 2 that there exists a point $A_i$ such that the wall $\overline{A_i{B}_i}$ is irrelevant. By the inductive assumption, we can conclude that the claim holds for all points except possibly point $A_i$. However, by Claim 1, point $A_i$ is connected by a good path with at least one of the remaining points, which proves the claim for $n+1$.