Note that two regions share a common segment or half-line only if they also share a vertex. Furthermore, every pair of lines forms exactly one vertex and there are $ 1 + \binom{n + 1}{2}$ regions. Let $ v_R$ be the number of vertices of region $ R$ and denote $ V = \sum v_R$. Noticing that each intersection adds four vertices to $ V$ and that each line intersects every other line in distinct points, there $ v = 4\binom{n}{2}$, and this is $ \le$ the number of sides with double counting (it would be $ =$, but we have the unbounded regions). Finally, we observe that every side is counted exactly twice, so there are at least $ 2\binom{n}{2}$ sides. Suppose there were more than $ \frac {n(n + 1)}{3}$ colored regions. Since no side is counted twice here, there are exactly $ \frac {2n(n + 1)}{3}$ sides counted. But this is $ > 2\binom{n}{2}$; contradiction. This seems to make the bound seem relatively weak, so I probably screwed up somewhere. It's late though, so I don't have time to check. EDIT: The above is flawed in two ways. Firstly, I only proved there are at least $ 2\binom{n}{2}$ sides with double counting, when I need an upper bound rather than zero bound. It turns out there are *exactly* $ 2\binom{n}{2} + 2n$ sides. Furthermore, the last inequality I used isn't actually true. I have a solution now, but unfortunately once again it's late and I don't have time to type it up. It rests on the lemma that there are always exactly three regions with 2 sides. It's worth noting that the desired bound is 2/3 the total number of regions, so this may lead to a nicer proof.

Now that it's morning and I'm more sane, here's my solution: Lemma: There are always $ 2n$ unbounded regions. Proof: Induction. Note that all other regions have the same number of vertices and sides and unbounded regions have one more side than vertex; hence the total side sum count is exactly $ 2\binom{n}{2}+2n=n(n+1)$ as I noted above. Lemma: There are always exactly three regions with two sides. Proof: They must be unbounded; induction by considering cases of what unbounded regions the $ n+1$th line cuts through. So suppose we have chosen $ \frac{n(n+1)}{3}$ regions and none share a side; we want to prove that this consumes more than the number of sides itself. To do this, we use a weighted average. Let $ x$ be the number of regions with exactly three sides; if we can show that $ 6+3x+4(\frac{n(n+1)}{3}-x-3)> n(n+1)$, or rearranging, $ 3x<n(n+1)-18$. Assume for the sake of contradiction $ 3x\ge n(n+1)-18$. However, $ 3x$ is simply the number of total edges we can have in summing over all the 3-regions, with $ n(n+1)$ edges total; we conclude that we can have at most $ 18$ edges in the sum of all other regions. Since there are always exactly 3 regions with 2 sides, we can have at most $ 12$ edges for 4+-sided ones, or at most 3 regions with more than 3 sides. Lemma: For all $ n\ge 5$, there are at least 4 4+-sided regions. Proof: Induction; use casework similar to our second lemma. We can check $ n=3$ and $ n=4$ by hand.

fwolth wrote: Lemma: There are always exactly three regions with two sides. If we have five lines in the form of a regular pentagon, are there not five such regions? Also, the first lemma has a very simple explanation: imagine zooming out so far that all of the pairwise intersections of the lines appear to collapse to a single point.

Hmmm this is true. Let's try this then. Since no three lines concur and no two are parallel, there are $ \binom{n + 1}{2} + 1$ regions formed, so it suffices to prove that we have fewer than $ 2/3$ of the regions colored. Now imagine the following process: Pick an arbitrary region and take one region bordering it and call them group $ G_1$. Repeat until we can no longer do so. Then we will have a number of groups $ G_k$ and various one-region "pockets" not included in any group but bordered by regions in groups (we cannot have more than two bordering regions in a pocket or we could make a group of them). Clearly, only one of the two regions in each group can be colored. If we can show that we can select the groups in a way such that there are more groups than pockets, then we're done. To do this, we prove the stronger statement that in any connected bipartite graph where every vertex has at least degree two (lemma: the graph resulting by interpreting regions as vertices is bipartite. proof: no odd cycles, assume there was one, but each line passes through cycle twice, contradiction) we can remove pairs of adjacent vertices until fewer than a third of them are left. Noticing the degree-two condition means that the subgraph of lesser order in the bipartite representation has at least half the number of vertices as the one with larger order, it suffices to show that for each vertex on the subgraph of smaller order, we can pick one of the vertices it's connected to on the other side so that we don't pick the same vertex for any two vertices. This is possible because if at any given point we come on a vertex so that all of the vertices (let there be $ v$ of them) it's connected to on the opposite side are already taken, then we would have to have at least $ v$ on the original vertex's side to have no choice, all connected to only that vertex's $ v$ connections. If either the graph isn't connected or there are more vertices on the original vertex's subgraph, contradiction. Otherwise, some connection preventing the original vertex is obligated by another similar situation; however, we can repeat the same logic for this with the same two cases. We clearly cannot have the second cause every time or this would be circular reasoning This concludes the proof. The last part seems a bit imprecise; I'll try to find a better argument.

fwolth wrote: Lemma: There are always $ 2n$ unbounded regions. This is essentially all you need to solve the problem. If we "zoom out" as JBL said (or equivalently, place everything in a sufficiently large circle) then the unbounded regions form a $2n$-cycle. If $S\subseteq F$ is the set of colored faces, then $S$ can have at most half of this cycle and thus at most $\frac{1}{2}(2n)=n$ unbounded faces (of degree at least two); everything else in $S$ has at least three edges. It immediately follows that \[ 3|S| - n \le \sum_{f\in S}\deg{f} \le |E| = n^2, \]as desired. By Theorem 2(3) here, the bound is tight for infinitely many $n$ (just include the line at infinity to get the $n$ boundary triangles, and note that no two triangles share a side).