## Task 2.

A web is a finite set of lines in general position (i.e., any two lines intersect, but no three lines pass through the same point). The lines of the web divide the plane into regions whose sides are segments or rays. A maze is a web in which each line is colored, like a wall, with one side red and the other side blue. Two regions sharing a common vertex that have both red and blue sides at that point are called connected. Ants move through the maze and can only move from the region they are in to a region that is connected to it. For a web $S$, define $k(S)$ as the maximum number of ants that can be placed in each maze on $S$ such that no two ants can meet by moving through the maze.

For $n \in \mathbb{N}$, determine all possible values of $k(S)$ where $S$ is a web of $n$ lines.
## Solution.

By induction, we show the fact that $n$ lines in general position in a plane divide that plane into $\frac{n(n+1)}{2}+1$ regions. The claim is obvious for $n=0$. When adding the $n$-th line, each of the existing $n-1$ lines is intersected exactly once, thereby increasing the number of regions by $n$. Using the induction hypothesis, we see that $n$ lines generate $\frac{n(n-1)}{2}+1+n=\frac{n(n+1)}{2}+1$ regions.

![](https://cdn.mathpix.com/cropped/2024_05_30_fcf49bda6fab77cc12a3g-11.jpg?height=374&width=1200&top_left_y=1087&top_left_x=428)

Notice that the intersections are exactly $\binom{n}{2}$. Each intersection reduces the number of ants that can meet by at most one, so no matter how the lines are colored, we can always place at least $\binom{n+1}{2}+1-\binom{n}{2}=n+1$ ants.

To show that the answer for any arrangement is exactly $n+1$, we will construct a maze in which more than $n+1$ ants cannot be placed. For any arrangement, introduce a coordinate system in the plane such that no line is parallel to the $x$- or $y$-axis. Then each line determines a left and a right half-plane, with the right half-plane being the one that contains the part of the $x$-axis for very large positive values. Color the left side of each line red and the right side blue.

Assign to each region the number of lines that lie to the left of that region. We claim that regions with the same assigned number are mutually connected.

Consider any region $A$ with an assigned number $k \in \{0,1, \ldots, n\}$. If this region is not unbounded towards the positive $y$-axis, then there exists a vertex with the highest ordinate. This vertex is also a vertex of another region with the same assigned number. Indeed, the line that was to the left of the lower region ceases to be to the right of the upper region, and the one that was to the right of the lower region now becomes to the left of the upper region. All other lines are in the same position relative to these two regions. Therefore, from any region with label $k$, we can reach a region with label $k$ that is not bounded above. There are exactly $n+1$ such regions because above all intersections, we can draw a line parallel to the $y$-axis that intersects each of the given lines exactly once.