APMO

Consider a line $\ell$ on the plane and a point $P$ on it such that $\ell$ is not parallel to any of the $2n$ lines. Rotate $\ell$ about $P$ counterclockwise until it is parallel to one of the $2n$ lines. Take note of that line and keep rotating until all the $2n$ lines are met. The $2n$ lines are now ordered according to which line is met before or after. Say the lines are in order ${\ell }_1,\dots ,{\ell }_{2n}$. Clearly there must be $k\in \{1,\dots ,2n-1\}$ such that ${\ell }_k$ and ${\ell }_{k+1}$ are of different colors.

Now we set up a system of $X$- and $Y$-axes on the plane. Consider the two angular bisectors of ${\ell }_k$ and ${\ell }_{k+1}$. If we rotate ${\ell }_{k+1}$ counterclockwise, the line will be parallel to one of the bisectors before the other. Let the bisector that is parallel to the rotation of ${\ell }_{k+1}$ first be the $X$-axis, and the other the $Y$-axis. From now on, we will be using the directed angle notation: for lines $s$ and $s^{\prime }$, we define $\angle (s,s^{\prime })$ to be a real number in $[0,\pi )$ denoting the angle in radians such that when $s$ is rotated counterclockwise by $\angle (s,s^{\prime })$ radians, it becomes parallel to $s^{\prime }$. Using this notation, we notice that there is no $i=1,\dots ,2n$ such that $\angle (X,{\ell }_i)$ is between $\angle (X,{\ell }_k)$ and $\angle (X,{\ell }_{k+1})$.

Because the $2n$ lines are distinct, the set $S$ of all the intersections between ${\ell }_i$ and ${\ell }_j$ ($i\ne j$) is a finite set of points. Consider a rectangle with two opposite vertices lying on ${\ell }_k$ and the other two lying on ${\ell }_{k+1}$. With respect to the origin (the intersection of ${\ell }_k$ and ${\ell }_{k+1}$), we can enlarge the rectangle as much as we want, while all the vertices remain on the lines. Thus, there is one of these rectangles $R$ which contains all the points in $S$ in its interior. Since each side of $R$ is parallel to either $X$- or $Y$-axis, $R$ is a part of the four lines $x=\pm a,y=\pm b$, where $a,b>0$.



Consider the circle $\mathcal{C}$ tangent to the right of the $x=a$ side of the rectangle, and to both ${\ell }_k$ and ${\ell }_{k+1}$. We claim that this circle intersects $\mathcal{B}$ in exactly $2n-1$ points, and also intersects $\mathcal{R}$ in exactly $2n-1$ points. Since $\mathcal{C}$ is tangent to both ${\ell }_k$ and ${\ell }_{k+1}$ and the two lines have different colors, it is enough to show that $\mathcal{C}$ intersects with each of the other $2n-2$ lines in exactly 2 points. Note that no two lines intersect on the circle because all the intersections between lines are in $S$ which is in the interior of $R$.

Consider any line $L$ among these $2n-2$ lines. Let $L$ intersect with ${\ell }_k$ and ${\ell }_{k+1}$ at the points $M$ and $N$, respectively ($M$ and $N$ are not necessarily distinct). Notice that both $M$ and $N$ must be inside $R$. There are two cases:

(i) $L$ intersects $R$ on the $x=-a$ side once and another time on $x=a$ side; (ii) $L$ intersects $y=-b$ and $y=b$ sides.

However, if (ii) happens, $\angle ({\ell }_k,L)$ and $\angle (L,{\ell }_{k+1})$ would be both positive, and then $\angle (X,L)$ would be between $\angle (X,{\ell }_k)$ and $\angle (X,{\ell }_{k+1})$, a contradiction. Thus, only (i) can happen. Then $L$ intersects $\mathcal{C}$ in exactly two points, and we are done.

Alternative solution:

By rotating the diagram we can ensure that no line is vertical. Let ${\ell }_1,{\ell }_2,\dots ,{\ell }_{2n}$ be the lines listed in order of increasing gradient. Then there is a $k$ such that lines ${\ell }_k$ and ${\ell }_{k+1}$ are oppositely coloured. By rotating our coordinate system and cyclically relabelling our lines we can ensure that ${\ell }_1,{\ell }_2,\dots ,{\ell }_{2n}$ are listed in order of increasing gradient, ${\ell }_1$ and ${\ell }_{2n}$ are oppositely coloured, and no line is vertical.

Let $\mathcal{D}$ be a circle centred at the origin and of sufficiently large radius so that - All intersection points of all pairs of lines lie strictly inside $\mathcal{D}$; and - Each line ${\ell }_i$ intersects $\mathcal{D}$ in two points $A_i$ and $B_i$, say, such that $A_i$ is on the right semicircle (the part of the circle in the positive $x$ half-plane) and $B_i$ is on the left semicircle.

Note that the anticlockwise order of the points $A_i,B_i$ around $\mathcal{D}$ is $A_1,A_2,\dots ,A_n,B_1,B_2,\dots ,B_n$. (If $A_{i+1}$ occurred before $A_i$ then rays $r_i$ and $r_{i+1}$ (as defined below) would intersect outside $\mathcal{D}$.)



For each $i$, let $r_i$ be the ray that is the part of the line ${\ell }_i$ starting from point $A_i$ and that extends to the right. Let $\mathcal{C}$ be any circle tangent to $r_1$ and $r_{2n}$, that lies entirely to the right of $\mathcal{D}$. Then $\mathcal{C}$ intersects each of $r_2,r_3,\dots ,r_{2n-1}$ twice and is tangent to $r_1$ and $r_{2n}$. Thus $\mathcal{C}$ has the required properties. $\square$