Points $ A_1,A_2, ... ,A_n$ inside a circle and points $ B_1,B_2,...,B_n$ on its boundary are positioned so that the segments $ A_1B_1,A_2B_2, ... ,A_nB_n$ do not intersect. A bug can go from point $ A_i$ to $ A_j$ if the segment $ A_iA_j$ does not intersect any segment $ A_kB_k$, $ k \neq i, j$. Prove that the bug can go from any point $ A_p$ to any point $ A_q$ in a finite number of steps.
Problem
Source: Russia 1994
Tags: combinatorics unsolved, combinatorics
08.10.2008 00:23
A point may see another point if the segment between them is not intersected by an existing chord (seeing is mutual). Suppose a point $ X$ (connected by chord to a point $ W$) may see a point $ Y$; then we claim that $ X$ also sees the other endpoint $ Z$ of the chord containing $ Y$. The region defined by $ \overline{WX}, \overline{YZ}$ and the non-overlapping arcs that connect them is convex. Thus if a chord intersects the line $ \overline{XZ}$ it’s endpoints must be on both arcs, but then $ X$ may not see $ Y$, contradiction. So it is not important if the bug jumps to an $ A$ or a $ B$ (if it jumps to a $ B_k$, instead change it so that it jumps to the corresponding $ A_k$). Now any endpoint $ A_i$ also sees at least one other endpoint of another chord (consider the point closest to $ A_i$, traveling along the circle). Suppose from $ A_iB_i$ we may see $ A_jB_j$, and now we delete $ A_jB_j$. Suppose further that [only after this deletion] $ A_iB_i$ may see $ A_kB_k$. Then we claim that $ A_jB_j$ saw $ A_kB_k$ before it was deleted, which follows similarly from the convexity argument above. Then we just continuously delete chords (which corresponds to the bug jumps), and since there is a finite number of chords eventually any chord may be seen from any starting point.