37th Iranian Mathematical Olympiad

First note that there are totally $\left(\genfrac{}{}{0ex}{}{3n+1}{2}\right)+1$ regions formed by these lines. So we have to prove that there are at most $\left(\genfrac{}{}{0ex}{}{3n+1}{2}\right)+1-\frac{(n-1)(n-2)}{2}=4n^2+3n$ bi-colored regions.

Consider an arbitrary point $X$ on the plane as "the infinity point", such that $X$ is neither inside of any of the finite regions nor any of the $3n$ lines. On each of the $3n$ lines, choose two points as the line's endpoints such that all the intersection points of a line, lie between its two endpoints. Now connect $X$ to all of the endpoints with curved segments in a way that these segments don't intersect at any point except $X$. Color a segment as the color of its corresponding line.

Consider a table in which each of the rows corresponds a bi-colored region, one column corresponds the point $X$, and each of the other columns corresponds a point which is the intersection of a red and a blue line. Write 1 in the intersection of a row and a column, if the column's point lies on the region corresponding the row, and write 0 otherwise.

Now we count the sum of the numbers in two ways. Obviously $X$ lies on $6n$ segments. So it is on at most $6n$ bi-colored regions. Note that these regions are the infinite regions we initially had. An intersection of a red and a blue line is exactly on 4 bi-colored regions. Note that there are exactly $2n\times n=2n^2$ such points. So the sum of the numbers written is at most $$4\times 2n^2+6n=8n^2+6n.$$

On the other hand, it's easy to find that the sum of the numbers in a row corresponding to a bi-colored (finite or infinite) region is at least 2. So if there are $k$ bi-colored regions, we have $$8n^2+6n\ge 2k\Rightarrow 4n^2+3n\ge k$$ as desired.