We construct a planar graph with vertices the intersection points of the lines and an edge between two vertices if and only if the vertices are consecutive intersection points in one of those lines. We have $V = \binom{n}{2}$ vertices and $E = n(n-2)$ edges and so we have $F = 1 + E - V = \cdots = \binom{n-1}{2} \leqslant n^2/2$ bounded faces. We colour some of the lines blue independently at random with probability $p$. We call a face bad if all its edges are colour blue. Let X be the number of coloured lines minus the number of bad faces. Then $EX \geqslant np - p^3n^2/2$. Choosing \[ p = \sqrt{\frac{2}{3n}}\] we obtain $EX \geqslant (2/3)^{3/2} \sqrt{n}$. So there is a colouring of the lines such that the number of coloured lines minus the number of bad faces is at least $(2/3)^{3/2} \sqrt{n}$. We decolour at list one line from each bad face. We now have no bad faces and at least $(2/3)^{3/2} \sqrt{n}$ coloured lines. Unfortunately this is less than $1$. Probably some counting of the number of triangular faces will do the trick but I have not yet tried it.

Not sure if I made any mistake. Call the $\binom{n}{2}$ intersections, well, points. Then each line will have $n-1$ points. We call 2 points (on a line) neighbors if there are no other points on the line segment joining those 2. Then each finite region has to be a convex polygon whose any pair of neighboring vertices are, well, neighbors. Now start by coloring any line blue, and all points are uncolored (neither red nor blue). Suppose there is an uncolored line which does not pass through any red points. Color that line blue. Now consider each of the intersections that line makes with the other blue lines. For each intersection point $X$ of the 2 blue lines $l_1,l_2$, color it blue (it was originally uncolored). Now consider the neighbors of $X$ on $l_1,l_2$, call them $A_1,A_2$ on $l_1$ and $B_1,B_2$ on $l_2$ (if there is only 1 neighbor, let the other point be an uncolored dummy). If neither $A_1$ nor $A_2$ is blue, we colour them both red. Else if neither $B_1$ nor $B_2$ is blue, we colour them both red. Otherwise, we colour the uncolored ones (out of the 4 points) red. Anyway, we would have colored at most 2 points red. Once we have done this for all the intersection points, proceed back to the start of this paragraph until no such line exists. Now to show it works. Suppose there is a finite region polygon $P_1...P_m$ with all blue boundaries (with $P_{m+1}=P_1$). Then all the points must be blue. Consider the first point colored blue, WLOG let it be $P_2$. Suppose the previous line to be colored blue is $P_1P_2$. Then $P_2P_3$ has to be colored blue before that, and $P_3P_4$ has to be uncolored (otherwise $P_3$ will be colored blue first). So $P_3$ is uncolored. Then if $P_1$ is blue, $P_3$ will be colored red by our coloring algorithm. $P_1$ has to be uncolored and by our coloring algorithm at least one of $P_1,P_3$ will be colored red. Note that no blue line will pass through a red point. Thus there are no finite region with blue boundaries. Now suppose $k$ lines are blue. By our algorithm, each blue point intersection will introduce at most 2 red points. Since we can't color any more lines blue, those red points will cover the remaining lines. Thus $2\binom{k}{2}\geq n-k\implies k\geq \sqrt{n}$ exact. Note: this works for all $n$, provided there is no mistake.

I assume there is a (deterministic) rule to color the lines in the wanted way, but nevertheless the probabilistic argument is nice. Reminds me of a statistical mechanics approach I tried a stategy to color the regions alternatively in two colors (i.e. if a region is painted in color 1, its neighbours are painted in color 2), and then to color in blue only the lines, which touch odd/even number of 1-colored finite regions. I haven't finished the analysis, because I don't have time, but I assume the solution uses some similar logic scheme.

Here was my partial solution at the IMO. Let $c = \frac{1}{\sqrt[3]{6e}}$. We'll show the bound $c \sqrt n$. The main core of the proof is the following lemma. Lovasz Local Lemma Consider several events, each occurring with probability at most $p$, such that each event is independent fexcept for at most $d$ of them. If \[ epd \le 1 \] then there is a nonzero probability that no events happen. Split the $n$ lines into $c \sqrt n$ groups of size $\frac{\sqrt n}{c}$ each, arbitrarily. We are going to select one line from each of the groups at random to be blue. For each of the regions $R_1$, $R_2$, \dots, $R_m$ we will consider an event $A_k$ meaning ``three of the lines bounding $R_k$ are blue''; we designate these lines beforehand. We will show there is a nonzero probability that no events occur. The probability of $A_k$ is clearly at most $\left( \frac{c}{\sqrt n} \right)^3$. For each $R_k$, we have three groups to consider. Each group consists of $\sqrt n$ lines. Each line is part of at most $2n-2$ regions. Hence $A_k$ depends on at most $3 \cdot \sqrt n \cdot (2n-2)$ events. Thus, \[ e \left( \frac{c}{\sqrt n} \right)^3 \left( 3 \cdot \sqrt{n} \cdot (2n-2) \right) < 6ec^3 = 1 \] and we are done by LLL.

Here's a proof for no blue triangular regions:

The issue is with non-triangular blue regions, this process does not ensure that these regions do not exist (though for any of these regions, there must exist a vertex/intersection from which none of the "closest" lines in one direction are red, but since the selection of the blue lines did not happen in that order, it is possible). I can't really figure out how to resolve this issue though.

Suppose we can color maximum $k$ out of $n$ lines in blue. It would mean color each other line of the $n-k$ lines in blue, creates a blue finite region. Hence such a line is forbidden according to some region containing all except that one blue lines as boundary. Look to the $\binom{k}{2}$ intersection points of blue lines (B-intersection points) and the $4$ regions it belongs to. When only one uncolored line is in such a region, we will assign a value to the intersection point, to remember we don't may color a neighbour. When the region contain $r$ intersection points of $2$ blue lines at its boundary, we will asign a value of $\frac{1}{r}$ to each such intersection point. Hence for each forbidden line, at least $1$ will be added to the values of all B-intersection points. If the value of one B-intersection point is $\le 2$ (*), we have the total is $\le 2 \binom{k}{2}$. Hence as there are $n-k$ forbidden lines, $n-k \le 2* \binom{k}{2} \Rightarrow k \ge \sqrt{n}$ as we wanted. Now we yet prove (*): Suppose it isn't true, than at least one of the $4$ interiors of the B-intersection has a value $> 0.5$ , so equal to $1$. But this will mean the neighbouring interiors will have a part of that forbidden line, so no other line in that interior will be forbidden. So the total value will be maximum $1+0+1+0$ in that case, which proves it. EDIT: I think it solves the trouble colinhy had.

IMO2018 wrote: Note: Results with $\sqrt{n}$ replaced by $c\sqrt{n}$ will be awarded points depending on the value of the constant $c$. So there is a proof that yields the statement with constant $c=1$. I see no reason why this bound should be tight. Why not $c=2$ with bound $2\sqrt{n}$? And why is it a square root? Why not $n^{2/3}$ or $n^{3/4}$? Why not $n/(\log^{100}n)$? If the bound $\sqrt{n}$ is not tight (which I strongly suspect) then the problem is a bad olympiad problem. It awards points if you come close to some artificial threshold that the problem author was able to reach, but that is not inherent in the problem structure.

manuel153 wrote: IMO2018 wrote: Note: Results with $\sqrt{n}$ replaced by $c\sqrt{n}$ will be awarded points depending on the value of the constant $c$. So there is a proof that yields the statement with constant $c=1$. I see no reason why this bound should be tight. Why not $c=2$ with bound $2\sqrt{n}$? And why is it a square root? Why not $n^{2/3}$ or $n^{3/4}$? Why not $n/(\log^{100}n)$? If the bound $\sqrt{n}$ is not tight (which I strongly suspect) then the problem is a bad olympiad problem. It awards points if you come close to some artificial threshold that the problem author was able to reach, but that is not inherent in the problem structure. First: it's not because a bound on a problem isn't tight that makes it a bad problem. There are several olympic problems regarding the probabilistic method that have beautiful solutions, although they the bounds to be proven aren't tight, for example. Second: maybe the answer is a square root because one can proof that the answer is at order of square root, in the assynthotic sense. If that's the case, $n^{2/3}$ or $n^{3/4}$ will unsharp the inequality a lot! Third: How'll be the criterion? If the examination bank doesn't like the estimate, then they'll wipe out the contestant's solution? I'm really confused!

post deleted due to being irrelevant.

manuel153 wrote: IMO2018 wrote: Note: Results with $\sqrt{n}$ replaced by $c\sqrt{n}$ will be awarded points depending on the value of the constant $c$. So there is a proof that yields the statement with constant $c=1$. I see no reason why this bound should be tight. Why not $c=2$ with bound $2\sqrt{n}$? And why is it a square root? Why not $n^{2/3}$ or $n^{3/4}$? Why not $n/(\log^{100}n)$? If the bound $\sqrt{n}$ is not tight (which I strongly suspect) then the problem is a bad olympiad problem. It awards points if you come close to some artificial threshold that the problem author was able to reach, but that is not inherent in the problem structure. I understand this the following way. The upper bound is in fact $\sqrt{n}$. However partial points will be awarded depending on the value of the constant $c$, where $c<1$. This makes the problem easier and that is why the full points can only be awarded for $c=1$.

The original short listed problem asked $c=\frac{1}{\sqrt2}$ but provided the solution for $c=1$. The bound is not tight, Po-Shen Loh showed a bound of $\sqrt{n\ln n}$.

Here's another Lovasz Local Lemma proof of the bound $\Omega\left(n^{\frac{1}{2}-\epsilon}\right)$: Colour each line blue independently with probability $p=cn^{-\frac{1}{2}-\epsilon}$ for $c<\frac{1}{e}$. Let $E_k$ be the event that region $k$ has all sides blue. Then $P(E_k)\le p^3$. Since each region shares a line with $O(n)$ regions, we may bound the degree of the dependency graph on the $E_i$ by $d=n^{\frac{3}{2}+3\epsilon}-1$ for sufficiently large $n$. So $ep^3(d+1)<1$ and so by the LLL no event $E_i$ occurs with probability at least $\left(1-\frac{1}{d+1}\right)^{|R|}>e^{-Kn^{\frac{1}{2}-3\epsilon}}$ for some small enough constant $K>0$, where $|R|=O(n^2)$ is the number of regions. Fix $\delta>0$. The probability that the number of blue lines is smaller than $(1-\delta)pn$ is at most $e^{-\delta^2 np/3}$ by a Chernoff bound. Union bounding, the probability that the number of blue lines is smaller than $(1-\delta)np$ or the probability that some event occurs is at most $1-e^{-Kn^{\frac{1}{2}-3\epsilon}}+e^{-\delta^2np/3}=1-e^{-Kn^{\frac{1}{2}-3\epsilon}}+e^{-\delta^2cn^{\frac{1}{2}-\epsilon}/3}$ which is smaller than $1$ for $n$ large enough. Hence with positive probability no region has all sides blue, and at least $(1-\delta)cn^{\frac{1}{2}-\epsilon}$ blue lines exist.

malcolm wrote: The probability that the number of blue lines is not between $(1-\delta)n^\frac{2}{3}$ and $(1+\delta)^\frac{2}{3}$ is at most $2e^{-\delta^2 n/3}$ by Chernoff. I do not think this is true; if you take, say, $\delta=\frac{1}{2}$, well the probability that the number of blue lines is zero is given by $(1-\frac{1}{n^{\frac{1}{3}}})^n$, which is around $e^{-n^\frac{2}{3}}$, already larger than what you are claiming.

Youre' right - it should be $2e^{-\delta^2np/3}$, which breaks the argument. Unfortunately it seems the best this kind of argument can achieve is $\Omega\left(n^{\frac{1}{2}-\epsilon}\right)$.

v_Enhance wrote: The bound is not tight, Po-Shen Loh showed a bound of $\sqrt{n\ln n}$. Maybe (more likely quite possibly) my good friend Po-Shen has read this http://www2.math.technion.ac.il/~room/ps_files/coloringlines.pdf, where Theorem 1 provides precisely that bound; moreover, the paper refers to an older bound that would yield $\sqrt{n}$, and it seems makes no region having completely blue boundary, be it finite (bounded) or not! Am I the only one to think that yet another result from an extremely recent article (it cites a work published in 2012) was used in a 2014 IMO problem? I would appreciate any expert, or pertinent feed-back.

very nice problem i solve it in 4 hour and 30 minutes for problem 4! my proof: 1- use extremal and give maximum blue line(x) 2- in a regions if has just one not blue line write on intersect of blue line $1/t$ .(t is the number of intersect blue lines) 3- double count the $\sum \frac{1}{t}$ 4- we find \[n-x\leq 2.\binom{x}{2}\Rightarrow \sqrt{n}\leq x\] done

mavropnevma wrote: v_Enhance wrote: The bound is not tight, Po-Shen Loh showed a bound of $\sqrt{n\ln n}$. Maybe (more likely quite possibly) my good friend Po-Shen has read this http://www2.math.technion.ac.il/~room/ps_files/coloringlines.pdf, where Theorem 1 provides precisely that bound; moreover, the paper refers to an older bound that would yield $\sqrt{n}$, and it seems makes no region having completely blue boundary, be it finite (bounded) or not! Am I the only one to think that yet another result from an extremely recent article (it cites a work published in 2012) was used in a 2014 IMO problem? I would appreciate any expert, or pertinent feed-back. Well, of course Po-Shen is involved But as the following quote implies, the Jury was not in fact aware of the research paper: Po-Shen Loh wrote: Nice find about the research paper from 2012, btw. None of us had been aware of it. As far as I know, the IMO problem proposer did not communicate any knowledge of a bound stronger than order sqrt{n}. The existence of the paper only makes me more enthusiastic in the problem. It confirms my hunch that this problem had a nice flavor. Pulling the connection back the other way, it shows that the IMO 2014 community independently selected a problem that was of interest to contemporary combinatorics researchers. If we can pull this off again, but come with better timing, then IMO 20XY will author a research paper too. Here is a comment explaining why the choice $c=1$ is in fact not completely artificial. Po-Shen Loh wrote: On the other hand, the sqrt{n} bound asked in the question is natural for a different reason: it is the limit of any argument based upon a greedy argument, and is also achievable via traditional Olympiad-style arguments. (That is why it was a problem proposal for the IMO. I didn't propose the original problem; credit goes to Austria.) One can construct a family of n lines, and a selection of about sqrt{n} of them to color blue, such that one cannot color any more lines blue without making a fully blue region (it's a maximal blue set). So, any "pure greedy" argument which starts by taking an arbitrary maximal set of lines must fail: it could accidentally have started with this particularly bad maximal set, which only has size about sqrt{n}. Indeed, one would have found a local maximum, but the global maximum would be quite a bit higher. On supporting the selection of this problem: Po-Shen Loh wrote: My motivation for supporting this for the IMO was that it would present people with an Olympiad combinatorics problem that was solvable using traditional Olympiad arguments, but would open up a discussion afterward, and indeed, the problem can now take on a life of its own as interested people (contestants, bystanders, coaches) continue to investigate into the truth. At the same time, I hope that by working on the problem (especially in attempting to improve the bound, or to prove a matching upper bound), students might be able to sample a taste of research, and so problem #6 of this year's IMO will be somewhat of a bridge from the Olympiad world to the research world. And finally, we think we can get $n^{2/3}$: Po-Shen Loh wrote: I was intrigued by the fact that the correct asymptotic on the shortlist problem was unknown, and during the problem selection days, I managed to quickly push it above sqrt(n) using some results on hypergraph independent sets (therefore showing that it is not tight). I am working on an upper bound, and so far a simple random distribution of lines appears to give an n^{2/3} polylog upper bound, but there are details to work out, and so I'm not 100% confident of that statement. I do not claim that sqrt{n log n} is optimal; rather, it simply shows that there is even more to the problem. (These comments are from my Facebook.)

Thanks for the comprehensive answer. So maybe Terence Tao will turn this into one of the "polymath projects" he inaugurated with the grasshopper problem from IMO 2009, Germany ...

As a reply to Mr Po-Shen-Loh's comment that existence of a paper is good in terms of the fact that the problem is relevant and actually investigated in research. I couldn't agree more to this if there was no specific mention of the problem. So if the problem was related but not the same as the one on the IMO. But in this way I disagree, this problem introduced, admittedly small, chance of giving certain students enormous advantage over their peers and I can't consider that as a good thing. Of course I agree this was not intentional and that the problem wouldn't be selected given someone on the Jury knew about the paper (although I am unsure of this after reading Mr Loh's reply) but I attempted to find the paper myself (without looking to the link provided) (ok I had advantage of knowing I can find it) and it took me about 5 minutes to find it. I am sad about the fact that no one in the jury/committee spent 5 minutes trying to check if it is original (I do understand they have better things to do but once selected this should be done...), especially as the question seems quite easy and familiar (not the complete problem but the setting) as now it seems they don't value originality of the problems as much as it should be valued (imo) and I don't believe there were no better suited (?possibly NT?) problems for Q6. The problem itself is quite nice and I kind of like the scoring bit although it might not have been necessary for that to be put explicitly in the text. Students should attempt to solve the problem and in a natural course they should get some weaker bounds which then jury should reward appropriately. This way it is simply telling the students we have a solution in mind for you to find which we reward and if you find something else it is due to luck (how your solution compares to intended one) and not the quality of your argument that you will get the points. If someone uses a really nice argument that gives a different type of bound shouldn't he get some points regardless of this not being of the type $c \sqrt{n}$? Will this be done in practice I am unsure, marking schemes for questions 0 mod 3 are utterly ridiculous...

Is this correct?... Given $n$ blue lines with $m$ finite areas, the maximum number of black lines required to obtain a configuration satisfying the problem is $m$ (one for splitting each finite area). Now we need to find an upper bound for the number of finite areas possible given $n$ blue lines. Note that given $n$ lines, adding an $(n+1)th$ line will result in at most $n-1$ more finite areas ($n$ intersection points, at most $n-1$ finite areas on each side). By induction we can prove the upper bound of $(n-2)(n-1)/2$ finite areas given $n$ lines, so given $(n^2 -3n +2)/2 + n$ lines, at least $n$ can be blue and satisfy the problem condition.

We will sequentially color lines blue, and after each blue coloring, we color every line which can no longer be colored blue (ie will create a completely blue finite region) red. Then after the $d$th blue line, as long as the number of red lines is less than $n-d$, we can draw another blue line. Suppose at the end of the process we have $k$ blue lines. Then, for the $n-k$ red lines, each one must be part of a finite region which is all blue besides the edge which is on the line. Now, for each red line, consider such a region, and pair it with a vertex of the region which is one away counterclockwise from the edge on the red line. Of course, this point must be a blue-blue intersection. However, for each blue-blue intersection, if there are more than $2$ red lines associated with it, then two of them correspond to polygons which share one of the four rays from the intersection. Then, these two polygons also share the line which intersects the ray first after the blue-blue intersection. However, this first line is one of the red lines which corresponds to the blue-blue vertex, so these two polygons actually have the same red line as an edge, which is a contradiction. Thus, each blue-blue intersection is chosen at most twice, which tells us that $2\binom{k}{2}\ge n-k\implies k^2\ge n\implies k\ge\sqrt{n}$, as desired.

Hopefully this is right. Clearly, any set of general position lines $\ell$ will form finite region(s) as a polygon with $\le|\ell|$ sides. Let the non-blue lines be red. Suppose that for the case with some $n$, we have colored $k$ lines blue, and that it is impossible to color any more, without violating the conditions. So, we have $n-k$ red lines. [asy][asy] dot((0,0)); dot((3,0)); dot((1.5, 2.7)); draw((0,0)--(1.5, 2.7), blue); draw((3,0)--(1.5, 2.7), blue); draw((0,0)--(3, 0), red); [/asy][/asy] The case $n=3$ is shown. Consider one finite region. Each red line is the side of an otherwise entirely blue finite region ($k$ was taken to be maximal). For every such line $L$, We can select one region it is a side of it. Then, take a counterclockwise vertex one away from $L$. We can call $L$ the fork of this vertex. It is easy to see that an intersection of two blue lines can consist of at most $2$ forks. There are $\binom{k}{2}$ intersections, so \begin{align*} n-k &\le 2\binom{k}{2}\\ \implies n-k &\le k^2 -k \\ \implies \sqrt{n} &\le k,\\ \end{align*}as needed. $\blacksquare$ Remark: Yeah, I know, the diagram is trivial. I just kept it there to practice Asymptote. Remark:[On motivation] The motivation to count intersections comes mainly from trying to bound the number of blue segments, so that the result is proven.

v_Enhance wrote: Here was my partial solution at the IMO. Let $c = \frac{1}{\sqrt[3]{6e}}$. We'll show the bound $c \sqrt n$. The main core of the proof is the following lemma. Lovasz Local Lemma Consider several events, each occurring with probability at most $p$, such that each event is independent fexcept for at most $d$ of them. If \[ epd \le 1 \]then there is a nonzero probability that no events happen. Split the $n$ lines into $c \sqrt n$ groups of size $\frac{\sqrt n}{c}$ each, arbitrarily. We are going to select one line from each of the groups at random to be blue. For each of the regions $R_1$, $R_2$, \dots, $R_m$ we will consider an event $A_k$ meaning ``three of the lines bounding $R_k$ are blue''; we designate these lines beforehand. We will show there is a nonzero probability that no events occur. The probability of $A_k$ is clearly at most $\left( \frac{c}{\sqrt n} \right)^3$. For each $R_k$, we have three groups to consider. Each group consists of $\sqrt n$ lines. Each line is part of at most $2n-2$ regions. Hence $A_k$ depends on at most $3 \cdot \sqrt n \cdot (2n-2)$ events. Thus, \[ e \left( \frac{c}{\sqrt n} \right)^3 \left( 3 \cdot \sqrt{n} \cdot (2n-2) \right) < 6ec^3 = 1 \]and we are done by LLL. can you explain why the probability of Ak is at most of that? and, i remember LLL needs ep(d+1)<=1

Call a finite region with exactly one red edge dangerous. Say a red line supports a region if the region is dangerous and the line is an edge to that region, and say that it supports a blue intersection $b_1 \cap b_2$ if that point is a vertex of a region supported by that line. Fix the $n$ lines in general position and consider a coloring which uses a maximal number $k$ of blue lines. I will prove that no matter how we choose these edges, there will be at least $\sqrt{n}$ blue lines for sufficiently large $n$. By maximality, every red line supports at least one region and thus at least one intersection, otherwise we can recolor it blue. The key claim is now the following: Claim: Two adjacent regions which contain a blue intersection $b_1 \cap b_2$ cannot both be dangerous. Proof: Suppose that our regions are $\mathcal{R}_1,\mathcal{R}_2$, and WLOG let their common edge be $b_1$. Suppose $r_1$ supports $\mathcal{R}_1$ and $r_2$ supports $\mathcal{R}_2$, and WLOG let $r_1 \cap b_1$ be closer to $b_1 \cap b_2$ than $r_2 \cap b_1$. Then $\mathcal{R}_2$ has $r_1$ as an edge, but also has $r_2$, so it has two edges and thus isn't dangerous: contradiction. $\blacksquare$ Thus, every intersection is supported by at most two lines, so there are at most $2\binom{k}{2}=k^2-k$ red lines (since every red line is supports some intersection). On the other hand, there are exactly $n-k$ red lines, so $$k^2-k \geq n-k \implies k^2 \geq n \implies k \geq \sqrt{n},$$which is the desired bound. $\blacksquare$ Remark: I haven't looked very closely, but without the claim we can get $c=(1/2)^{1/2}$ (maybe $\varepsilon$ smaller) just by using $4\binom{k}{2}$ instead of $2\binom{k}{2}$. At some point I think I got $c=(2/3)^{1/2}$ with the same approach and the use of Euler Characteristic by eliminating unbounded regions, but I think I was just tripping. If we commit to the approach detailed in this problem, one might see that we need to bound the number of supporting lines per intersection to $2$ on average, and $4$ is the naive bound. I have no clue how I stumbled upon the main claim (to me, it felt like it just fell out of the sky), but it's an interestingly (combo-)geometrical idea in a solution that doesn't really use the geometry part of combinatorical geometry much elsewhere.

Greedy greedy Let's be greedy. If adding a blue line loses, then there must be a region with all blue lines except one. Then for any pair of blue lines, consider the danger coefficient that is the sum over all such regions containing the intersection of the blue lines (ones that have a single red line) where for any two regions of consideration that share the same line, we only consider the one that maximizes the danger coefficient, of the reciprocal of the the number of edges minus two. I claim the danger coefficient of a pair of blue lines is always at most 2. Notice at most four regions contain the intersection of the two lines. Now, consider the four rays extending out the intersection, and let the lines intersecting these rays closest to the intersection be $a, b$ on the first line and $c, d$ on the second line. These can be undefined if in an infinite region. $a = c$ is possible. Then if one region is a triangle, $a = c$ is red. Then by definition, the $b, c$ and $a, d$ regions don't meet the danger criteria since they contain the same red line as the triangle, so the maximum is $1 + 1 \leq 2$. Otherwise, if no triangles are bordered, then $\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2} \leq 2$, so we are done with the claim. Now, the number of banned lines (prevented from adding to the set) is at most the number of such valid regions (with the added criteria that two regions that ban the same line can be ignored), then since we chose the maximum reciprocal in the first claim, we can now sum the danger coefficient over all pairs of blue lines. If a line is indeed banned, then it must hold at least a value of one in the reciprocal sum from summing the danger coefficient part over only the region that successfully banned the line (this is where the maximum reciprocal on top of the criteria comes in), so it follows that with there are less than $\sqrt{n}$ lines in the set, then $$\text{number of banned lines} \leq \sum_{\text{pair of blue lines}} \text{danger coefficient} < 2{\sqrt{n} \choose 2} + \sqrt{n} = n$$, finishing since we can add another line to the chosen set. Notice that without the criteria to exclude regions that ban the same line with less of a contribution to the danger coefficient, the same proof fails. For example, given everything except $y = -1$ are blue lines, the configuration $y = x, y = -x, y = -1, y = 4+2x, y = 4-2x, y = 3-0.0001x$ would make the danger coefficient $1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{3}$ at $(0, 0)$.

For given set consider coloring of maximal number $k$ of lines with no blue-bounded finite regions. Each region has at least one uncolored side - if it is exactly one we call this line magical for given region. Claim. If two regions adjacent by a side have common corner, obtained by intersection of two blue lines, then at least one of them hasn't a magical line. Proof. Assume the opposite. Let $\ell_1,\ell_2$ denote blue side-lines ($\ell_1$ is a common side of regions). Then the magical line, which intersect $\ell_1$ nearer to $\ell_1 \cap \ell_2$ is included in both regions, so one region has two magical lines, contradiction $\Box$ Thus for every intersection of blue lines is assigned at most two magical lines, and there are $n-k$ uncolored lines at all, so $$k^2-k=2\binom k2\geq n-k\implies k\geq \sqrt n \text{ } \blacksquare$$

Very nice problem Let a line be grey if it is not blue, Assume that after coloring $k$ lines blue, it is impossible to color any more lines blue. Call a finite region $cyan$ if every line defining its border is blue, except for one. This means that there must be at least $n-k$ cyan regions since every grey line borders a cyan region. Each point which is the intersection of two blue lines can be the vertex of at most two cyan regions. So, the number of cyan regions is at most $2 \cdot \binom{k}{2}$. Thus, we get the following inequality \[ n-k \leq 2 \cdot \binom{k}{2} \implies k \geq \sqrt{n} \]

blackbluecar wrote: Each point which is the intersection of two blue lines can be the vertex of at most two cyan regions. No that's not true. Here's a counter-example (your grey is pink here).

Wait, how so many ppl did the exact same mistake? Am I missing something here? :thonk:

@above the definition is actually more subtle; the intersection point $A$ must be exactly counterclockwise of the red edge, not necessarily just adjacent; so in your picture, there are only two regions. But I agree, that statement needs to be given more care. Color blue lines greedily until we cannot color any more; suppose that there are $k$ blue lines at this point. Then, each remaining red line must border a region that otherwise has all its edges blue. Now the trick is to double count the number of such regions. On one hand, there are obviously at least $n-k$ such regions; however, we can upper bound the number of such regions by looking at the intersection points $A$ of two blue lines. In order to create a one-to-one mapping between points and regions, we can define a signature region of $A$ to be a semi-blue region, which has a red edge immediately clockwise to $A$. On the other hand, only regions bounded by the counterclockwise one of the lines passing through $A$ (where we look at the acute angle) work; thus, for every point $A$, there are at most two regions. This gives us the inequality $$n-k \leq 2{k \choose 2} \iff k \geq \sqrt n.$$

First color the blue lines greedily until it is impossible to color another line blue. If all lines are blue, then we win. Otherwise, there must exist a region $\mathcal{R}$ with exactly one edge that is not blue. Draw a vertex at each intersection of blue lines, and label each region the reciprocal of $2$ less than the number of edges of that region. Now, perform the following process: for each vertex $A$, consider the regions containing $A$, and for each two adjacent regions, write ``$A$" on the region(s) with the larger label. The sum of the labels corresponding to the regions with ``$A$" written on them and containing an edge which is not blue is the number that $A$ is labeled with. Let $f(A)$ be the label on vertex $A$. Lemma: The label on each vertex is always a positive number at most $2$. Proof. At most $4$ regions that are considered for a given vertex $A$, so we do a simple casework. Clearly, we cannot have three regions with ``$A$" stamps have label $1$. If exactly two region labels with an ``$A$" stamp are both 1s, then we greedily make $2$ of the opposite regions triangles, but this forces $f(A) \le 1+1=2$. If exactly one region labels with an ``$A$" stamp is labelled $1$, then note that the only other region with an ``$A$" stamp is possibly the region opposite to it, but that must have label less than $1$ by our assumption, and so $f(A)<2$. Finally, if none of the regions are labelled $1$, then we are okay since all of them are at most $\frac{1}{2}$. Hence we are done. Claim: Let $S$ be the set of lines that were eventually illegible to be colored blue in the first greedy process. Then, $|S| \le \sum_{A} f(A)$. Proof. This is clear from the definition of $f$; we essentially use the reciprocal as a way to count for all vertices of a region while only extracting a weight of about $1$. By the lemma and claim, we have \[ n-k \le |S| \le \sum_A f(A) \le 2 \binom{k}{2} = k^2-k, \]and thus $k \ge \sqrt{n}$, which finishes. Remark: I found this to be more instructive than the usual double counting approach, because of the way in which the reciprocal structure of the labelling system seemed to go well with the greedy algorithm (which was used in many other solutions). A problem that can be solved with a similar invariant is Shortlist 2012 C7, where the reciprocal \[ \frac{1}{\deg v + 1} \]is the invariant used. However, the work required to use it is actually rather minimal, since the key claims hold by linearity of expectation.

Just color lines blue until we cannot. Let's say we've colored $k$ lines. Call a region with all but one edge blue almost bad. For each uncolored line, if all the regions that border it have at least two uncolored edges, then we can color this line without running into issues, contradiction. Thus, there are at least $n-k$ almost bad regions. For each almost bad region, consider the point most directly counter-clockwise of the uncolored edge, but on actually on the edge. This must be an intersection of two blue lines. Let's say this region belongs to this intersection. We claim that at most two almost bad regions belong to one intersection. Otherwise, there will be two adjacent regions belonging to one intersection. Let these regions be $1$, $2$, where $2$ is counter-clockwise of $1$ then it is evident that the region at 2 must be a triangle. This means that the region counter-clockwise of $3$ cannot belong to the intersection. If the region clockwise of $1$ belongs to the intersection then $2$ cannot, so this is true. Thus, we have \[n-k\le k(k-1)\]which implies $k\ge \sqrt{n}$ as desired.

Greedily color lines until we can't color any more lines. FTSOC we have colored $m < \sqrt{n}$ lines blue. Then color the rest of the non-blue lines purple. Let a region be blue-ish if all lines bordering it are blue except for one. Note that all purple lines must pass through at least one blue-ish region, otherwise we could paint it blue, contradiction. Also since two purple lines can't pass through the same blue-ish region we find that there are at least $n - m$ regions. We also note that the intersection of any two given blue lines can be a part of at most two blue-ish regions, so the amount of blue-ish regions is at most $2 \cdot \binom{m}{2} = m(m-1)$, so we get $m^2 - m \geq n - m \implies m \geq \sqrt{n}$.