Bulgarian Spring Tournament

Question

We call n lines in the plane three-way if they can be separated into three nonempty sets, X, Y, Z. Every two lines from the same set are parallel to each other, no two lines from different sets are parallel to each other, and no three lines intersect at a point. By S_n we denote the maximum number of regions into which n three-way lines can divide the plane. As a region we consider a connected part of the plane, not necessarily finite, whose boundaries are defined by three-way lines. What is the largest n for which S_n < 128? (Konstantin Delchev)

Accepted Answer

We will derive a general formula for the number of regions. Let the three sets have the number of elements |X| = x, |Y| = y and |Z| = z, respectively. The first two divide the plane into a total of (x+1)(y+1) regions. Each line of the third set intersects the others at x+y points and is divided into x+y+1 parts. Each of them divides one of the already obtained areas into two. Thus we get a general formula: S_x,y,z = (x+1)(y+1) + z(x+y+1) = x + y + z + xy + xz + yz + 1. We note that n = x + y + z. Furthermore, we have that 3(xy + yz + zx) (x + y + z)^2 = n^2 (equivalent to (x - y)^2 + (y - z)^2 + (z - x)^2 0). So S_x,y,z n^2/3 + n + 1 which is less than 128 for n = 18 (actually, S_6,6,6 = 127, i.e. S_18 = 127). Also, S_6,6,7 = 140, so S_n > 128 for n 19. Therefore, the answer is 18.