3n lines are drawn on the plane (n>1), such that no two of them are parallel and no three of them are concurrent. Prove that, if 2n of the lines are coloured red and the other n lines blue, there are at least two regions of the plane such that all of their borders are red. Note: for each region, all of its borders are contained in the original set of lines, and no line passes through the region.
Problem
Source:
Tags: combinatorial geometry, combinatorics, geometry
26.05.2015 02:26
It's easy to see that the number of regions formed by the red lines is n(2n+1)+1, each blue line cuts exactly 2n+1 of those regions, then after putting n blue lines, there is at least one region with red border. But, if there were only one, all the blue lines cut different regions, and in particular they don't intersect, that's impossible, so there are at least two. In fact, there are at least n regions with red border, because the first blue line cuts 2n+1 regions, but the second must intersect the other blue line in some region, so it cuts at most 2n regions with red border, and the same happens for the other n−2 blue lines. So, in total they cut at most n(2n+1)+1−n regions with red border. The result is still true if we suppose that each blue line is in general position respect to the red lines, but not necessarily respect to the others blue lines. In fact, if two blue lines are parallel, they cut the same two unbounded regions with red border.
31.05.2015 06:03
Never mind I'm dumb
07.01.2019 13:37
Zaratustra wrote: In fact, there are at least n regions with red border, because the first blue line cuts 2n+1 regions, but the second must intersect the other blue line in some region, so it cuts at most 2n regions with red border, and the same happens for the other n−2 blue lines. So, in total they cut at most n(2n+1)+1−n regions with red border. The result is still true if we suppose that each blue line is in general position respect to the red lines, but not necessarily respect to the others blue lines. In fact, if two blue lines are parallel, they cut the same two unbounded regions with red border. Can anyone assert whether the above is true? I seem to have some doubts about it, but I'm waiting for the assertion first.
13.10.2021 22:01
It's easy to show (induction!) that 3n lines generate {3n+1 \choose 2} + 1 different regions. Let's say that a region is good if all of its borders are red, and lets try to count the number of bad regions. Let's focus on a blue line, which is cut into exactly 3n (induction!) segments. Each one of these segments touch exactly two regions, making them bad regions. Since there are n blue lines, we have n \cdot 3n \cdot 2 = 6n^2 bad regions. However, whenever two blue lines meet, they count neighboring regions twice at their intersection. We should remove such regions. There are {n\choose2} such blue-blue intersections, and they are associated to 4 regions, which gives 2n(n-1) = 2n^2-2n. So, the number of bad regions is at most 6n^2-(2n^2-2n) = 4n^2+2n The minimum for the number of good regions is therefore {3n+1 \choose 2} + 1 - (4n^2 + 2n)= \frac{9n^2}{2} + \frac{3n}{2} + 1 - (4n^2 + 2n) = \frac{n^2}{2} - \frac{n}{2} + 1 Which is at least 2 for n \geq 2