IMO 2013 problem 2. For some reason aops doesn't have anything under IMO 2013 in the contests sections at the moment. You can find the solution on the IMO official website: http://www.imo-official.org/problems/IMO2013SL.pdf . It is on page 23

I'm reposting the problems right now since the contests page is screwed up.

The key is that you can draw two lines to separate two points - draw two parallel lines very close to the two points. Now I claim that the answer is $\boxed{2013}$. To show that we need at least $2013$ lines, throw a blue point somewhere and draw a circle and place 4026 points on the arc so that consecutive point have different colors. Each line must intersect all $4026$ arcs, so we require at least $2013$ lines. Now I claim that we can succeed in $2013$ lines. If the convex hull of these points have a red point, draw one line to separate that point, pair the other $2012$ red points into $1006$ pairs, then draw $2012$ lines to separate them into a group. We used $2013$ lines. If the convex hull of these points does not have a red point, Separate two consecutive blue points on the convex hull with just one line, then pair the other $2012$ blue points into $1006$ pairs, then draw $2012$ lines to separate them into a group. Therefore, we conclude that our answer is $2013$.

First, I will show $k \ge 2013$. Have all $4027$ points arranged in a circle with red and blue points alternating, but for two consecutive blue points on the circle. Call the arcs in counterclockwise order containing the red points as $R_1, \cdots, R_{2013}$ and the arcs in counterclockwise order containing the blue points as $B_1, \cdots, B_{2013}$ where one of the $B_k$ contains both consecutive blue points. Each of the $k$ lines hits at most two different arcs, and each arc needs to be intersected by at least one line. We have $4026$ arcs so we need at least $2013$ lines. Next, I claim $2013$ lines are sufficient. Define a process of shearing as taking two parallel lines such that there are exactly two points contained within those two lines, hence separating those two points. The two lines can be arbitrarily close, as a side note. Take the convex hull of all $4027$ points. If the convex hull contains one or more red points, then separate some red point with a line. Then shear the $1006$ pairs of the remaining $2012$ red points. Observe this ensures that the arrangement is good. Hence, we can do with $2013$ lines in this case. Else, if there are no red points on the convex hull, take two consecutive blue vertices and separate them from the rest of the arrangement with a line. We are left with $2012$ blue and $2013$ red points. Shear the $1006$ pairs of the remaining $2012$ blue points, like in the previous case, using $2012$ lines. A total of $2013$ lines work in both cases, so we are done.

We will proves a general result that for $n$ red points and $n+1$ blue points then $k\geq n$ Indeed, consider a configuration with $n$ red points and $n+1$ blue points placed alternatively on a circle. A line will be refered as good if it go through the space between two points. Now, by noticing that a good line can go through at most two spaces between two points, hence the number of good line is \[ \left\lfloor \frac{2n+1}{2}\right\rfloor = n \]Now, we will contruct a configuration that satisfies the conditions. We will do this by induction So, the base case $n=1$ is trivial. Assume that the statement holds for all $k<n$. Let $d$ be the number of domains that contains points with different colors. Construct a convex hull of $2n+1$ given points. Consider an vertice $A$ of the convex hull and its adjacent $B$. Case 1: $A$ and $B$ has the same color (red for example), consider a line through $A$ and the distance from the points to $AB$. Now, consider another line that also go through $A$ clockwisely and it will stop when it hits a blue pints that is closest to $AB$. It is easy to see that the domain this line go through will contains all res points, hance $d$ decrease by $1$. By keep doing the above process, there will be a points that $d$ reaches $0$, and the problem is solved. Case 2: $A$ and $B$ has the different colors, then we consider a vertice $C$ adjacent to $A$ or $B$. Then, there must be two vertices with the same color. Repeat the above process. Done Hence, we can always divide the configuration into domains that contains all same colors. We have that $n$ red points, by induction hypothesis will be divided by $\left\lfloor\frac{n}{2}\right\rfloor$. For $n+1$ blue points, it will be divided by $\left\lfloor\frac{n+1}{2}\right\rfloor$. But \[\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{n+1}{2}\right\rfloor=n \]$\blacksquare$

Nice problem! IMO 2013/2 wrote: A configuration of $4027$ points in the plane is called Colombian if it consists of $2013$ red points and $2014$ blue points, and no three of the points of the configuration are collinear. By drawing some lines, the plane is divided into several regions. An arrangement of lines is good for a Colombian configuration if the following two conditions are satisfied: i) No line passes through any point of the configuration. ii) No region contains points of both colors. Find the least value of $k$ such that for any Colombian configuration of $4027$ points, there is a good arrangement of $k$ lines. Proposed by Ivan Guo from Australia. Answer: $k=2013$ is the desired minimum. To see $k \geqslant 2013$, toss a blue point anywhere; from the remaining $4026$ points, construct a regular polygon inscribed in a circle with vertices coloured alternatingly. Each of the $4026$ arcs must be intersected by at least one line; since each line can have at most $2$ intersections, we get the desired bound. To see that this is sufficient, we consider the more general result. Claim: Given $m$ blue and $n$ red points, with $m \in \{n, n+1\}$ we require at least $\left \lfloor \frac{m+n}{2}\right \rfloor$ lines. (Proof) Induct on $k=m+n$. Base cases are trivial; for induction step, we consider two cases: Case 1: $m=n$. Select a line which separates one of the points from the rest; apply the induction hypothesis for the remaining points to conclude. Case 2: $m=n+1$. Let $\mathcal{P}$ be the convex hull of this set. If all vertices of $\mathcal{P}$ are blue then take a line which separates two of them from the rest and apply induction hypothesis for the remaining points. Suppose $R$ is a red point on it, let $\ell$ be a line passing through $R$ which has all of $\mathcal{P}$ on a single half-plane. Take a point $O$ sufficiently far from $\mathcal{P}$ on line $\ell$. Rotate $\ell$ about $O$ and evaluate the difference between the number of red and blue points. Initially this difference is $1$ and finally it is $n-m=-1$. Thus, by discrete IVT, at some intermediate position $\ell'$ of $\ell$, this value is exactly zero. Then there is a region between $\ell$ and $\ell'$ with $s$ red and $s$ blue points and another with $n-s$ red and $n-s+1$ blue points. Evidently, by induction hypothesis we require $$\left \lfloor \frac{s+s}{2} \right \rfloor+\left \lfloor \frac{(n-s)+(n-s+1)}{2} \right \rfloor=n,$$so this case is also satisfied. Hence, our induction is complete. For $m=2014, n=2013$ the result follows. $\blacksquare$

To show that you can do it with 2013 points, why can't you just start with two blue points and a red point (separated with one line) and then add loads of pairs of points (one blue, one red, separated by one line)?

I guess this works, though a bit different than above.

The answer is $k \ge 2013$. To see that $k = 2013$ is necessary, consider a regular $4026$-gon and alternatively color the points red and blue, then place the last blue point anywhere in general position (it doesn't matter). Each side of the $4026$ is a red-blue line segment which needs to be cut by one of the $k$ lines, and each line can cut at most two of the segments. Now, we prove that $k = 2013$ lines is sufficient. Consider the convex hull of all the points. If the convex hull has any red points, cut that red point off from everyone else by a single line. Then, for each of the remaining $2012$ red points, break them into $1006$ pairs arbitrarily, and for each pair $\{A, B\}$ draw two lines parallel to $AB$ and close to them. If the convex hull has two consecutive blue points, cut those two blue points off from everyone else by a single line. Then repeat the above construction for the remaining $2012$ blue points. The end.

And... my solution is the same as v_Enhance... Main motivation for the solution was simply to experiment with small cases. I took advantage of the "no lines collinear" condition by connecting two points together and realized I could move it ever so slightly to the sides to guarantee two lines contain two points.

I claim that our answer is $\boxed{k = 2013}$. It is easy to see that $k$ is at least 2013 by arranging some $2013$ red points and $2013$ blue points in an alternating color scheme around a circle. Note how any two adjacent points around the circle are of different color, and must be separated. Each line can separate at most two pairs of adjacent vertices, hence a least $\tfrac{4026}{2} = 2013$ lines are required. Then we prove that $k = 2013$ lines is sufficient. Consider the convex hull $\mathcal{C}$ of the set of $4027$ points. If there exists a red point in $\mathcal{C}$, then remove it with a line. Then, there are $2012$ red points left in the configuration. For any pair of red points, we can single them out with two parallel lines infinitely close to each other. For the $1006$ remaining pairs, we need $2012$ lines to complete this "singling out" process, hence a total of $2012 + 1 = 2013$ lines is sufficient in this case. If there are no red points in $\mathcal{C}$, then we may use a line to remove some two consecutive blue points in $\mathcal{C}$. Then, we repeat the singling out process described in the previous case on the remaining $1006$ pairs of blue points, hence a grand total of $2012 + 1 = 2013$ lines is also sufficient in this case. Thus, a total of $k = 2013$ lines is sufficient and necessary, and we are done. $\blacksquare$

Let $N=2013$. We claim the answer is $N$. This is achieved by taking a $2N+1$-gon, with alternating blue and red vertices; of course, we will have two adjacent blue vertices. Draw $N$ parallel lines, splitting the circle into a bunch of regions, each of which has 2 vertices of one color. The last region will have just 1 blue vertex, however. This shows we need at least $N$ lines. Now we show that in any Colombian configuration, we can finish in at most $N$ lines. Consider the convex hull of all the points. Case 1: There are no red points on the boundary of the convex hull. So there are two adjacent blue vertices on the boundary, now make a line separating them into their own region. Now we have $N-1$ blues, and $N$ reds. So switch the colors and finish by induction. Case 2: There is at least one red point on the boundary of the convex hull. Then make a line separating this into its own region. Now we have $N-1$ reds, $N+1$ blues. The key idea is to now take 2 arbitrarily close parallel lines to get a tiny region containing only two red points; we can do this since no 3 points are collinear. Repeat this process for all $(N-1)/2$ pairs (each of which are arbitrarily selected), so we use $N-1$ lines. In total, we used $(N-1)+1=N$ lines.

We claim the least value of $k$ is $2013$. First, we can take the convex hull of the $4027$ points. For the vertices that are part of the perimeter of the convex hull, If a blue is connected to a blue, or a red is connected to a red, disconnect. Repeat. After that, if a vertex on the perimeter of the convex hull doesn't have another point it is connected to, then connect it to an adjacent vertex of the opposite color. Within the points that have not been paired up, do the same thing. Then, just apply this same process to the points inside the convex hull. If we have any leftover points of different color, just do the same thing as before with the convex hulls. After that we only have one vertex left (red), but we can just leave it. After all the specified edges are drawn, just take a parallel line extremely close to that edge, so we say byebye to this problem.

We claim the answer is $2013$. To see that $2013$ may be necessary, simply take $2013$ red points around a circle, then put $1$ blue point in each of the arcs between them. Then, we'll have one blue point left, and we double up one of the arcs. Then, each line that passes through the circle cuts it at two points which we will mark black. Two colored points on different sides of a black point are then in different regions. Since we know that there must be at least $2 \cdot 2013$ black points in order to surround a red point, the bound is proven. Now, we prove that $2013$ is sufficient. We will induct down. Take the convex hull of the points; if there are two adjacent blue points on the convex hull, then evidently by taking a line that gets arbitrarily close to the line between the blue points, we can separate the configuration into $2$ blue points on one half, and $2012$ blues and $2013$ reds on the other half. From here, we induct down while switching the roles of the blue and red. As a result, assume that we can't find two adjacent blue points on the convex hull. The only thing we actually need from this is that some red point is on the convex hull, so we can separate it from the rest of the configuration with one line. Now arbitrarily pair off the remaining $2012$ red points. Consider two red points $R_1, R_2$, and let $\ell = \overline{R_1R_2}$. Evidently no blue point can lie on $\ell$, so assume that the closest blue point to $\ell$ is $d$ away. Then we can simply draw two lines $\ell_1$ and $\ell_2$ both parallel to $\ell$, such that they are on opposite sides of $\ell$ and are both a distance $\epsilon$ away from $\ell$, where $\epsilon < d$. This just works lmfao

Consider $n+1$ blue and $n$ red points $(x_{i},y_{i})$. Let $P$ be a point such that $P(x,y)$ is not any of the $\binom{2n+1}{2}$ lines created by the points and $x<\min\{x_{i}\},y<\min\{y_{i}\}$. Consider an angular sorting of the points with respect to the angle created by $P$ and the points with the positive $X$ axis. For each of the $2n$ points $P_{1},\ldots,P_{2n}$, draw a line from $P$ to $P_{i}$. Since no $3$ points are collinear, we will get $2n$ distinct lines. From this construction, it is easy to see that the lines from $P$ to the red points separate the points with the same color. These $n$ lines $L_{1},\ldots, L_{n+1}$ would be sufficient, however, the lines cannot pass through any of the marked points. To make the $n$ lines not pass through any of the marked points, consider the $2n$ points. If $\theta=\min\{\angle P_{i}PP_{i+1}\}$, then we can simply rotate all lines $L_{i}$ by $\theta/2$ in the same direction. Then all the points with same color are still separated and none of the lines pass through any of the marked points.

The answer is $2013.$ Claim: (Generalization) For configurations consisting of $k$ red points and $k$ blue points or $k$ red points and $k+1$ blue points, there exists a good arrangement of $k$ lines. Proof. Proven by strong induction. The base cases are trivial. Suppose it is true for $(k,k)$ and $(k,k+1)$. If there are $k+1$ red and $k+1$ blue points, then considering the convex hull, we can draw a line to separate one point, wlog assume red, form the other $2k+1$, whence by assumption for the remaining $k$ red and $k+1$ blue one can draw $k$ lines to form a colombian configuration, meaning there exists $k+1$ lines forming a good arrangement for $k+1$ red and $k+1$ blue points. Now suppose there are, wlog, $k+1$ red and $k+2$ blue points. If there exists a blue point on the convex hull, then there must exist an edge of the hull with both endpoints blue or one red, one blue. As a result, separating these two points and inducting gives a good arrangement of $k+1$ lines. If there is only red points on the convex hull, then if $k+1$ is odd we can separate one red point away (and if even don't separate). Then, for the remaining $k$ red points, we can pair them by drawing two arbitrarily close parallel lines with only a pair of red points inside. As a result, there exists a good arrangement of $k+1$ lines. $\blacksquare$ Claim: There exists a configuration requiring $2013$ lines. Proof. Consider a regular $4027$ gon with the vertices alternating in color. Note that no two red points are consecutive. Moreover, excluding the one edge with two blue endpoints, every other edge of the $4027$ gon must be intersected by a line in a good arrangement. Indeed, if not, then the two endpoints are not separated, contradiction. Hence, since there are $4026$ such mixed-endpoint edges, and each line can obviously only intersect at most twice, this configuration requires at least $2013$ lines. $\blacksquare$

Solved with Jeffrey Chen We claim that if a configuration has $n$ red points and $n+1$ blue points, the least value of $k$ is $n$. To do this, we consider a convex $2n$-gon with alternating colors (indexed $P_i$ from $i=1,2,\ldots 2n$, and place the blue point anywhere that maintains Colombianity. Then, note that since each pair of adjacent points of the convex polygon $P_iP_{i+1}$ are of different colors, they must be separated. Therefore, for all $i$ there must exist some line which intersects $P_iP_{i+1}$. In total, there are $2n$ such segments that must be intersected. Additionally, since the $2n$-gon is convex, at most 2 segments can be intersected by any line. Thus, we clearly need at least $\frac{2n}{2}$ lines in order to make this Colombian configuration good. So $k\geq n$. Now, we show that all configurations have a good arrangement with $n$ lines. $\textbf{Claim 1: }$ For any configuration of $2n+1$ red and blue points, there exists some collection of $n$ lines which separate them into monochromatic regions $\textbf{Proof: }$ We proceed with induction on $n$. The base cases of $n=0,1$ are trivial. For the inductive step, consider the convex hull of the $2n+1$ total points. If $P_iP_{i+1}$ is monochromatic, draw the line $\varepsilon$ into the hull from $P_iP_{i+1}$, and applying the inductive hypothesis finishes. Otherwise, we must have that the convex hull is a $2m$-gon with alternating colors. We now consider the point $Q$ which minimizes the distance to a line $P_iP_{i+1}$ as $d_M$. WLOG $Q$ is red, $P_i$ is red, and $P_{i+1}$ is blue. By extension, $P_{i+2}$ is also red. We may then draw a pair of lines which are $d_M+\varepsilon$ away from lines $P_iP_{i+1}$ and $P_{i+1}P_{i+2}$. This puts $(P_i,Q), (P_{i+1}), (P_{i+2})$ into their own regions. Thus, we have removed four points with 2 lines, at which point by the inductive hypothesis we are done. Now, our induction is complete $\square$. The desired claim is clearly a subcase of Claim 1, so we have shown that $k\geq n$ and $k\leq n$. Thus, $k=n$ and the answer is 2013.

The answer is $2013$ lines. To see why $2013$ is required, consider a convex polygon with $4027$ vertices where every alternate vertex is colored blue (except for one pair, since there are more blue vertices than red ones). It is easy to see why $2013$ lines are required here. Now to show that every configuration requires at most $2013$ lines, we define $f(x, y)$ to be the value of $k$ for $x$ red vertices and $y$ blue vertices. I claim that $f(m, n) = f(m-2, n) + 1 = f(m, n-2) + 1$. We shall proceed by induction. The base case is $f(1, 2) = 1$. Let $f(m, n) = t$ for some $m,n$ where $m \not \equiv n \pmod{2}$. Consider the convex hull of the configuration. If there are two consecutive vertices of the same color in the convex hull, just remove them (separate them from the rest of the set) with the help of a line, and observe that $f(m, n) \leq f(m-2, n) + 1$ or $f(m, n) \leq f(m, n-2) + 1$ and we're all good. Otherwise suppose there are no two consecutive vertices of the same color in the convex hull, so they alternate between red and blue. Call each consecutive pair in this convex hull which are of different colors 'friends'. Suppose there are $k$ blue and $k$ red vertices in this convex hull. Then remove every pair of friends from the rest of the set with a line, and use one line to separate each pair of friends, such that each of these lines also separates another pair of friends. Clearly we will require $k + \left \lceil \frac{k}{2} \right \rceil \leq \frac{3k + 2}{2}$ lines to do this, and we are left with $m-k$ red points and $n-k$ blue points in the inside of the convex hull. By our hypothesis, it is sufficient to show that $f(m, n) \leq f(m-k, n-k) + 2k$, but here we can see that $f(m, n) \leq f(m-k, n-k) + \frac{3k+2}{2} < f(m-k, n-k) + 2k$, so we are done. Thus $f(m, n)$ increases by at most one everytime we add two points of the same color, and since $f(1, 2) = 1$, we quickly see that $f(2013, 2014) \leq 2013$, which completes this proof.

If there exists a red point on the convex hull, we separate the red point. Otherwise, there are two consecutive blue points on the convex hull, we separate the blue points. Both with only one line. Then, no matter which we chose, the color has 2012 points left, so for each pair of points, we draw two parallel lines to separate them, so we used 2013 lines. To prove that $2013$ is necessary just take the configuration with a circle and 4026 alternately colored points and its center.

Claim $n$ on WLOG $n, n+1$ of red, blue points, necessary by alternating on a circle. Induct. If $n$ even, pair all red points directly and place two lines infinitesimally close on either side of each pair segment. If $n$ odd take red on convex hull, cut it off, then pair as before. If no red on convex hull, cut off an edge with two blue points, and induct down by swapping colors. Base cases are trivial. Hence answer is $n$.

The answer is k=2013. Lower bound: put the 4027 points around a circle in an alternating fashion. There are 4026 pairs of consecutive points on the circles that are coloured differently and every line intersects at most 2 of the segments joining this pairs. Therefore at least 2013 lines are needed. upper bound: search for a triangle made up of 3 red points thar doesn't contain any blue points in its interior. If it exists. Choose 3 Lines parallel to the sides of this triangle and very close to it such that this 3 points well be isolated from all of the blue points. Then pair up the remaining red points and for each pair draw 2 parallel lines containing the 2 points and no other points in the configuration and we isolated all of the red points using 2013 lines. If such triangle doesn't exist and there is a red point in the convex hull of the configuration then draw a line that separates it from the other points of the configuration and pair up the remaining red points similar to before, using only 2013 lines. If the convex hull is made up entirely of blue points then there are at most 2011 blue points in the convex hull of the red points. If there is a red point that is strictly inside this convex hull then it is possible to triangulate the red points into 2012 triangles and we necessarily have a red triangle with no interior blue points. So Assume that the red points are in a convex position. Let us induct on n that given 2n+1 red points in a convex position and 2n-1 blue points, then there exists a red triangle with no interior blue points. Base: n=2 is clear. Assume that the statement is true for n-1. We have a (2n+1)-gon. Cut off a quadrilateral of the polygon. It contains at least 2 blue points because it is made up of two non-intersecting red triangles. The remaining (2n-1)-gon has at most 2n-3 points in its interior so it contains a red triangle with no blue interior points, and this triangle is a triangle of the original (2n+1)-gon, so we are done.

Kind of silly The answer is $k=2013$. To prove that $2013$ lines are sufficient, consider the convex hull of the points. If it contains two consecutive blue points then draw a line which cuts off only those two blue points and induct down. Otherwise it contains a red point; cut it off and pair the $2012$ remaining red points into $1006$ pairs, and then draw $2$ lines for each pair which form a narrow region only containing that pair. To prove that $2013$ lines are necessary, place the points in alternating fashion along a circle, except for two consecutive blue points. Each line drawn intersects the circle at two points, so after drawing $k$ lines we form at most $2k$ arcs along the circle. Each arc should contain points of only one color, but it is clear that $4026$ arcs are necessary, so we're done. $\blacksquare$

Solved with SatisfiedMagma. Solution: The answer is $k = 2013$. First of all we show that this is bare minimum and the rest of the solution will showcase an inductive proof that this indeed works. We start with the upper bound. Arrange $4026$ points in a regular polygon such that adjacent points are of opposite color. Place the remaining blue point anywhere. Since each line cuts the polygon at most twice, its obvious it would take $2013$ lines. It's about time we give a construction. The first case will be by induction and other one will be via an explicit construction. The idea is to consider the convex hull of all the points. Replace $2013$ by $2n+1$. As an induction hypothesis, assume that there is a construction for $2k+1$ points. We now wish to show that there is a construction for $2k+3$ points with $k$ lines as well, with of course $k+2$ blue points and $k+1$ red points. The base case $k=1$ is trivial. Therefore we now consider $k \ge 2$. If the convex hull has only blue points, then pick any two of them and separate them out and consider the rest of $k$ blue points $k+1$ red points. But applying induction hypothesis, we have a "Colombian configuration" of $k$ lines separating for the $2k+1$ points. Add one last line which partitions the separated out blue points. If there is one blue and one red point on convex hull, then after separating them out, we would have $k+1$ blue points and $k$ red points which is precisely the induction hypothesis. If convex hull as only red points, then we give an explicit construction and not rely on induction at all! Then pick one red point and separate it out. Now you are left with $2012$ red points and $2014$ blue points. Since no three points are collinear, then we can make lines clubbing all red points such that they don't enclose blue points. These will take $2012$ lines. Finally add one last line to partition the separated point in beginning. The solution is complete. $\blacksquare$

Solved with sman96 and Jbmm2004 we first prove that we have to use at least $2013$ lines. We consider a regular $4026$ gon with alternating blue and red coloring. Every line we draw can intersect at most $2$ sides of that polygon. But we have to intersect each and every side, therefore , we need at least $2013$ lines. We use a trick to separate two points from the rest of the configuration. Consider the convex hull that surrounds the configuration. Case - $1$: the convex hull contains at least $1$ red point. We use one line to separate it from the rest of the configuration. and then use the pairing trick to separate the rest of the $2012$ points pairwise. Case - $2$: there exists no red point in the convex hull. we use one line to separate $2$ blue points [ a convex hull must contain at least 3 points ] and then use the pairing trick to separate the rest of the $2012$ points pairwise. So, we are done. (literally we) $\blacksquare$

The answer is $k=2013$. This is necessary: for example, consider the Columbian configuration of the points arranged in a circle, alternating color (except for one pair of two adjacent blue points). At each of the $4026$ arcs connecting two points of opposite color, there must be a line that passes through that arc in order to separate those two points, so we need at least $2013$ lines in this configuration. To construct, we do casework on whether the convex hull of all $4027$ points contains a red point: If so, we pick a red point on the convex hull; since it is on the convex hull, we can draw one line that separates that point from the other $4026$ points. Then, we split the remaining $2012$ points into pairs, and for each pair of points, we draw a pair of parallel lines arbritrarily close to the line passing through both points. Due to the collinearity condition, no other point, red or blue, will lie in the region between these two lines. If not, we pick the convex hull of the red points, which will contain no blue points; this convex hull has at most $2013$ sides, so we extend each side into a line, shift it by some $\epsilon$ and are done too.

Let $f(x,y)$ be the answer with $x$ red points and $y$ blue points. The claim is that $f(x+1,x)=f(x,x+1)=x$ and $f(x,x)=x$. Let's first prove that $f(x,x)\le x$; that is, we can always draw a good arrangement of $x$ lines. Notice that $f(1,1)=1$. We use strong induction. Consider an oriented line $\ell$ not passing through any points and rotate it $180^{\circ}$ about some fixed point $P$ not collinear with any two points and inside the convex hull. Let $d$ be the number of blue minus the number of red points to the left of $\ell$; then clearly $d\to -d$ and at some point the given monovariant is equal to $0$. Hence we have reduced to proving $f(a,a)\le a$ and $f(b,b)\le b$ where $a+b=x$ which is true. Now we prove that $f(x,x+1)\le x$ by the same logic. Notice that $f(1,2)=1$. Define $\ell$, $P$, and the monovariant $d$ the same way. To reduce down, we need $d=0$ or $d=1$. In addition the monovariant will transform $d\to 1-d$. This works; thus we reduce to $f(a,a)\le a$ and $f(b,b+1)\le b$ with $a+b=x$. It suffices to give a construction proving $f(x,x+1)=f(x,x)=x$. Take a convex polygon with $2x$ vertices and alternate vertices. Any drawn line increases the number of "regions" along the boundary of the polygon by at most $2$ (since it adds two endpoints). Hence we need at least $x$ lines. The last point can be placed anywhere. We want $f(2013,2014)=2013$. $\blacksquare$

Solved with Jack_w.

The answer is $2013$. Lower bound: Suppose the points all lie on a circle with alternating colors (except for one pair of adjacent blue points). There are $4026$ pairs of adjacent points of different colors, but each line can separate at most two pairs, giving the desired bound. Upper bound: We take two cases. If there is a red point on the convex hull, use a line to break off this point, then break off each of the remaining $1006$ pairs of red points with pairs of lines. If there is no red point on the convex hull, use a line to break off a pair of adjacent blue points, then break off each of the remaining $1006$ pairs of blue points with pairs of lines.

We claim that the configuration with $n$ red points and $n+1$ blue points needs at least $n$ lines, and the minimum $n$ can always be achieved. We will proceed with induction. The base case is trivial. Just draw a line going through the two blue points. The red point lies on one side of the line. Let the red point be a distance $d$ away from that line. Now move the line $\frac{d}{2}$ units towards the red point. Base case complete Now for the inductive step. Assuming the configuration for $k-1$ red and $k$ blue points can be solved with at least $k-1$ lines, we can examine a configuration with $k$ red and $k+1$ blue points. Now things depend on the parity of $k.$ Case 1: k is even Pair up red points. For every pair, the following process works: 1. Draw the line between the two points. 2. "Duplicate" the line. 3. if the closes points to the line on the two halve planes it creates have distances $d_1$ and $d_2$ to the line, we move the lines a distance $\frac{d_1}{2}$ and $\frac{d_2}{2}$ in the respective directions. Doing this over all pairs, we "isolate" each pair of points from the blues, using exactly $k$ lines in the process, as there is a $1-1$ (or rather "2-2") correspondence. Case 2: Consider the convex hull of the points. If a red point exists on the convex hull, we draw a line that divides a red point on the convex hull from the rest of the dots. Then the paring argument of Case 1 works. If there is no red point on the convex hull, there are two consecutive blue points on the polygon that makes the convex hull. We can draw a line that divides two blue points from the rest of the diagram. What remains on the side with red points is $k$ red points and $k-1$ blue ones, and by the inductive hypothesis we can use $k-1$ lines to solve the diagram. (The colors are reversed from the inductive hypothesis but that is fine) Therefore, the induction is complete and in the context of this problem, we find that $k\ge 2013.$