Hmm... A strange problem. Consider a convex hull of the whole set. If it contains red and blue points then, obviously, we are done. Therefore suppose the convex hull consists of blue points only. Take $A,B,C$ three consecutive vertices on the convex hull. We state there is a balancing $A$ through $A$. Indeed, consider the leftmost line $k$ through $A$ s.t. the right open halfplane contains the same number of red and blue points . The line $k$ exists due to discrete continuity arguments (just rotate $k$ from $AB$ towards to $AC$). We know that $k$ contains a point $D$ from our set. If $D$ is a red point then we are done. If $D$ is a blue point, then there is another line between $AB$ and $k$ satisfying the condition . Contradiction. Since the convex hull contains at least three points we conclude that there are at least three balancing lines for this case. Please, someone read it! I think I missed something

Attachments:

I solved it the same way. So, I missed the same thing as you.

I solved it almost exactly the same way, except I didn't know what a convex hull was so I had to write a page defining the convex hull. Let C be right of A. Label the red points $R_i, i=1,2,...,n $ so that $i > j \Rightarrow \angle CAR_i > \angle CAR_j $ (i.e., counterclockwisely) If we draw all the lines $AR_i $, then the number of red points on the right side of $AR_i $ is $i-1, i=1,2,...,n.$ The number of blue points on the right side of $AR_i $ increases from 1 to at most n-2 as i increases from 1 to n. So $i-1$ starts smaller and ends larger than the number of blue points right of $AR_i $, and $i-1$ also takes on every single value between 0 and n-1, so they have to equal at some point. So this is a balancing line. Do the same thing for B.

So, it means that the problem is really "trivial". I.e. it is just a direct application of well known ideas: convex hull + discrete continuity.

I guess, iff you're experienced. I spent like an hour trying to do it via induction...

tekno10m wrote: I guess, iff you're experienced. I spent like an hour trying to do it via induction... I also tried it via induction. I didn't have much time to do it though, and ended up getting in the base case, which was to show its true for 2 reds and 2 blues. Then, obviously, if you put the red and blue point on the same point of the balancing line, that line still acts as a balancing line. If not, that's where it gets a little wierd. Lets say you put the red on side "A" of the line and the blue on side "B." Rotate your old balancing line about the blue point so that the red point it formerly passed through falls into side "B." If the line next crosses a red point, you have found a new balancing line. If not, you cross a blue point before a red point, then you will have more blues on side B than reds. Therefore, once you hit a red point, rotate the line about that red point so as to move more blues to side A. I conjectured (but was unable to prove) that eventually you will eventually find a new balancing line by this method. Therefore, each balancing line for 2n points has a corresponding balancing line for 2n+2 points, QED. Obviously I dont expect full credit, but hopefully they will give me a point or two for my base case and conjecture. JB

Just a word about balanced lines, about which there are many papers. J. Pach and R. Pinchasi proved that, according to a conjecture of G. Baloglou, for $n$ red points and $n$ blue points in general position in the plane there are at least $n$ balanced lines. And this bound is sharp. J.Pach, R. Pinchasi, 'On the number of balanced lines', Discrete and Computational Geometry, 2001, p. 611-628. Their lemma 1-5 states that for any vertex $v$ of the convex hull of the given set, there is a balanced line passing through $v$. Their argumentation in the proof of this lemma is Myth's one. Pierre.

Myth wrote: So, it means that the problem is really "trivial". I.e. it is just a direct application of well known ideas: convex hull + discrete continuity. Well-known to you, perhaps. But not to most high school students, even olympiad-types. Furthermore, there are so many other techniques that less-experienced students might be led to try. With your level of experience, a glance at the problem suggests discrete continuity, and the convex hull comes soon after. But we don't all have your level of experience! I might also describe #3 in the same terms. #3 uses even simpler well-known ideas - parallel lines, inscribed angles, and cyclic quadrilaterals. But I wouldn't describe it as trivial.

America... What should I do that everyone see I wrote "trivial", not trivial. Indeed, problem is not trivial, but it is absolutely straightforward in some sense. You see that Fedor did exactly the same things as me.

The students more experienced with problem solving that I know all jumped straight to the convex hull. I, for one, spent many hours trying induction, pigeonhole, extremal, contradiction, and even connecting-the-lines (kinda sorta graph theory I guess) while expending many pieces of paper on plots. So I guess this problem gives a huge advantage to experience, arguably much more so than most of the other problems.

I did this for fun. My solution is not fundamentally different than those presented here. Just a slightly different explanation. Consider the convex hull of points. If the convex hull contains both red and blue points, then as we consider the points on the hull in a counterclockwise direction, there must be at least one blue point immediately followed by a red point, and there must be at least one red point immediately followed by a blue point. Lines connecting these pairs of points will be balancing lines. There are at least two such lines. Otherwise, the convex hull is monochrome. In the following, we consider the convex hull to be monochrome blue, but we note that similar arguments would apply if the convex hull were monochrome red. If the convex hull is monocrome blue, we choose one point on the convex hull and divide the half-plane containing all points into $n+1$ sectors, by drawing a series of rays from the chosen point through each red point. Sectors $S_1$ and $S_{n+1}$ must each contain at least one blue point. The remaining sectors may or may not contain blue points. Recall that the total number of blue points is equal to the total number of red points. If we consider $L_1$, we note there is an excess of blue points to the right of the ray. We denote the excess of blue points to the right of line $L_i$ by $K_i$. $(K_1 > 0)$ If we consider $L_n$, we note there is an excess of blue points to the left of the ray. (Or a negative excess of blue points to the right of the ray.) $(K_n < 0)$ Consider each successive line, $L_i$, from $L_2$ through $L_n$. If Sector $S_i$ contains one blue point, the imbalance in $L_i$ will equal the imbalance in line $L_{i-1}$. $(K_i = K_{i-1})$ If Sector $S_i$ contains more than one blue point, the excess of blue points to the right of $L_i$ will increase, compared to the excess of blue points to the right of $L_{i-1}$. $(K_i > K_{i-1})$ However, if Sector $S_i$ contains no blue points, the excess of blue points to the right of $L_i$ will decrease by exactly one, compared to the excess of blue points to the right of $L_{i-1}$. $(K_i = K_{i-1} - 1)$ The value(s) where $K_i = 0$ correspond to a balancing line. Since the sequence, $K_1, K_2, K_3, \ldots, K_n$ is known to go from a positive value at $K_1$ to a negative value at $K_n$, by positive integer steps, zero steps, or steps of negative one, the sequence must pass through 0 at least once. Thus, at least one of the lines is a balancing line. If we choose another point on the convex hull, we are guaranteed to find another (distinct) balancing line. Thus, in every case, there are at least two balancing lines. QED

Attachments:

If you've seen IMO 99 #1 you were probably more than ready to use Convex Hull on this problem.

I experimented for a while with the rotate-the-line method, then succumbed to a very seductive application of the Pigeonhole Principle and induction. And in any case, my line-rotating was restricted to an inductive method that would generate a new balancing line from those in a set of 2n-2 points. I abandoned it because it seemed messy, and I couldn't get it to work. Darn.

I didn't know about convex shells, either, so I just proved it. Then, with the line rotation, I made $ a_0, a_1, ... a_n$ the counts of blue points before, after, and in between the n red points. Then you have the sum of the $a_i$ equal to $n - 1$. Then a balancing line exists through our blue point and the $k + 1^{st}$ red point met in the rotation iff the sum of the $a_i$ for $i$ from $0$ to $k$ is equal to $k$. It does not seem hard, then, to prove that there must be at least one $k$ for which this is true. I did not have time to do it on the USAMO, but I would have liked to. It sounds like if I had scattered the words "finite", "discrete", and "continuity" here and there in my proof, the judges would be happier with my proof. Oh well. I liked this problem anyways. I might have done it the hard way, though. Or is the hard way the inductive proof ... ? (Which I also briefly looked at, then decided that it was too hard. Then I solved it this way) Yeah. I don't see anything wrong with your proof, Myth. On the other hand, I might just be missing something ... oh wait! You forgot to prove that deterministic primality testing only takes $O(n^{O(1)})$ in the worst case! I fill in for your glaring omission here: Theorem: Deterministic primality testing for positive integer n can be computed in $O(n^{O(1)})$ Proof: It has been done; such algorithms exist, and I was standing within about 20 feet of the source code (and the source of the source code) for one such algorithm written in Mathematica, at the NorthWest Science Expo. I got to do that for several hours. That was fun.

Actually, my doubts were concerned only with the fact, that problem is too straightforward (for experienced olympiad students). I see now that it were baseless doubts, since many people did the same things as me.

I solved this problem the same way a very similar problem is solved in Math Olympiad Challenges: Quote: 3.1 Arrange in Order Example 2: Given $2n+2$ points in the plane, no three collinear, prove that two of them determine a line that separates $n$ of the points from the other $n$. I guess I'm just lucky I happened to read that particular section and that that problem stuck in my mind.

I tried induction and wrote a 5 page long solution that really made no sense, but that's ok. I have no idea what a convex hull is....oh well, I still have many more years left.

Quote: 3.1 Arrange in Order Example 2: Given 2n+2 points in the plane, no three collinear, prove that two of them determine a line that separates n of the points from the other n. So basically almost the exact same problem wow.

rrusczyk wrote: Well-known to you, perhaps. But not to most high school students, even olympiad-types. I solved the problem very similar, using convex h. and d. continuity... I think one can easily think of convex hull because you think of it as a trivial case, when one side of the balancing line has no points and the other has the remaining 2n-2... once you get to a convex hull you try some example for small n and see how can you get a balancing line.. making some arguments clear may be the matter of expierience, but the idea isn't.. croatia hasn't got as good results as US but contestants are mostly familiar with those terms (hull and continuity)...

I think the proof given in the AMC website is flawed; it claims that every point on the convex hull lies on a balancing line. But suppose we have the 2 red points (0,0) and (0,1) and the 2 blue points (-1,-1) and (1,-1). Obviously the convex hull is (0,1) (-1,-1) (-1,1). But the point (0,1) is not on any balancing lines (look at the diagram) but it is on the convex hull.

Philip_Leszczynski wrote: I think the proof given in the AMC website is flawed; it claims that every point on the convex hull lies on a balancing line. But suppose we have the 2 red points (0,0) and (0,1) and the 2 blue points (-1,-1) and (1,-1). Obviously the convex hull is (0,1) (-1,-1) (-1,1). But the point (0,1) is not on any balancing lines (look at the diagram) but it is on the convex hull. Err, aren't the lines through (0,1); (-1,-1) and (0,1); (1,-1) both balancing lines? They both have one red and one blue on one side and none on the other...

Lemma. Let $k \ge 3$ be an integer. Then, given any $k$ distinct points in the plane with no three points collinear, there exists a convex polygon, with vertices from the $k$ given points, such that all of the $k$ points lie within the polygon. Proof. We proceed by induction on $k.$ The base case, $k = 3$, is trivial. We simply connect the three points into a triangle. Since every triangle is convex, the claim follows. Now, for the induction hypothesis, assume the claim to be true for some $k = m$, where $m \in \mathbb{N}, m \ge 3.$ We prove the claim true for $k = m + 1.$ Let us label the points $X_1, X_2, ..., X_{m + 1}.$ By the induction hypothesis, there exists a convex polygon, which we will denote by $\oslash$ with vertices from the set $\{X_1, X_2, ..., X_m\}$, that contains all points $X_1, X_2, ..., X_m.$ Now, if the point $X_{m + 1}$ also lies in $\oslash$, then we are done. If $X_{m + 1}$ does not lie in $\oslash$, then consider a line $\gamma$ passing through $X_{m + 1}$ such that $\gamma$ does not intersect $\oslash.$ Note that since $X_{m + 1} \notin \oslash$, such a line $\gamma$ must exist. Now, we rotate $\gamma$ couterclockwise until it first intercepts a vertex $X_p$ of $\oslash.$ We continue to rotate $\gamma$ counterclockwise until it intercepts a vertex $X_q$ of $\oslash$, such that $X_q$ is the last vertex that $\gamma$ intercepts during this rotation (until it once again intercepts $X_p$ after rotating through $180^{\circ}$). Denote by $S$ the sequence of consecutive vertices of $\oslash$ that connect $X_p$ and $X_q$, where $S$ lies on the opposite side of line $X_pX_q$ as $X_{m + 1}.$ It follows that all vertices of $\oslash$ that are not $X_p, X_q$ or in $T$ are contained within the lines $X_{m + 1}X_p$ and $X_{m + 1}X_q.$ Therefore, $X_{m + 1}X_pTX_q$ is a convex polygon that contains all $m + 1$ points. Therefore we have shown the claim true for $k = m + 1.$ This completes the induction. Now, since $n \ge 2$, there are at least $2 \cdot 2 = 4$ given points. Therefore, by our Lemma, there must exist a convex polygon, which we will denote by $\otimes$, with vertices from the $2n$ given points, such that all of the $2n$ points lie within $\otimes.$ We label these vertices (in the order that they appear in $\otimes$) $P_1, P_2, ..., P_i$, where $i \in \mathbb{N}, i \le 2n.$ We now consider two cases: Case 1: $P_1, P_2, ..., P_i$ are all the same color. WLOG, assume that these points are all red. Then the adjacent vertices $P_1$ and $P_2$ are both red. Now, consider the line $P_1P_2.$ We rotate this line about $P_1$ in the direction such that $P_2$ is rotated into $\otimes.$ Let $Q$, where $Q$ is one of the given $2n$ points, be the first blue point that the line $P_1P_2$ intercepts during this rotation. Then the line $P_1Q$ divides the plane into two regions, one of which contains only red points (among which is $P_2$), and the other contains the remaining of the given $2n$ points (other than $P_1$ and $Q$, of course). Since the first region contains only red points, it follows that the second region, which contains the point $P_i$, contains more blue points than red points. Now, we continue rotating the line $P_1P_2$ in the same direction until it intercepts $Q*$, where $Q*$ is one of the $2n$ given points, and $Q*$ is the last blue point that the line $P_1P_2$ will intercept during its rotation, until $P_1P_2$ intercepts $P_i.$ Then the line $P_1Q*$ divides the plane into two regions, one of which contains only red points (among which is $P_i$), and the other contains the remaining of the given $2n$ points (other than $P_1$ and $Q*$, of course). Therefore, during this rotation, the line $P_1Q$ divides the plane into two regions. The region containing the point $P_i$ has more blue points than red points. Then, the line is further rotated to $P_1Q*.$ The line $P_1Q*$ divides the plane into two regions, where the region containing $P_i$ contains more red points than blue points. Therefore, by the principle of continuity, there must exist a blue point $R \in \otimes$, such that the line $P_1R$ divides $\otimes$ into two regions, with each region containing an equal number of red and blue points. Hence, there exists a balancing line passing through $P_1.$ Similarly, we can show that there exists a balancing line passing through $P_2$, and in general, through all of the $P_k$'s. Since we have shown that there exist at least two balancing lines, this concludes Case 1. Case 2: The set $\{P_1, P_2, ..., P_i\}$ contains both red and blue elements. Consider the longest consecutive sequence of red vertices on $\otimes.$ Since the vertices of $\otimes$ are not all red, it follows that the first and last red vertex in this sequence must be adjacent to a blue vertex. Therefore, $\otimes$ must contain at least two pairs of consecutive vertices that are opposite in color. Suppose these pairs of adjacent vertices are $(P_a, P_b), (P_c, P_d)$ where $P_a, P_c$ are red and $P_b, P_d$ are blue. Note that these pairs are distinct, since if $P_a = P_c$ and $P_b = P_d$, then it follows that $\otimes$ has only two vertices, absurd. Now, since the pairs $(P_a, P_b)$ and $(P_c, P_d)$ are distinct, the two lines $P_aP_b$ and $P_cP_d$ are also distinct. In addition, since the $P_i$'s are simply vertices of a convex polygon, $\otimes$, that encloses the given $2n$ points, it follows that the each of the lines $P_aP_b$ and $P_cP_d$ divides the plane into two regions, one of which fully contains $\otimes.$ Therefore each of these lines divides the plane into two regions, one of which contains the remaining $2n - 2$ points (other than the two in the line itself), and the other containing none of the given points. Clearly these $2n - 2$ points are comprised of $n - 1$ red points and $n - 1$ blue points, i.e., an equal number of red and blue points. Therefore, the lines $P_aP_b$ and $P_cP_d$ are both balancing lines. Since we have shown that there exist at least two balancing lines, this concludes Case 2. Since we have considered all cases, the proof is complete.

Actually good cg problem?? Let $S$ be the set of all of the points. Also, given a line $\overline{PQ}$ (where the order of vertices matters) and a point $X$ not on that line, say $X$ is to the "left" of $\overline{PQ}$ if it is on the left half-plane from the perspective of an ant at $P$ looking towards $Q$, and say it is to the "right" otherwise. Consider the convex hull of $S$. If it contains points of both colors, then any line drawn from a red point to a blue point is clearly balancing. Since there are at least two of these, the result is true in this case. Hence suppose that the convex hull of $S$ contains points of only one color. WLOG let this color be blue. I will now prove the following key claim: Claim: For every blue point $B$ on the convex hull of $S$, there exists at least one balancing line passing through $B$. Proof: Consider the $n$ red points, none of which are on the convex hull. Number these points $R_1,R_2,\ldots,R_n$ such that $R_i$ is to the left of $\overline{BR_j}$ if and only if $i<j$. Also define a function $f$ such that $f(i)$ is equal to the number of blue points to the left of $\overline{BR_i}$ minus the number of red points to the left of $\overline{BR_i}$. It is evident that the line $\overline{BR_i}$ is balancing if and only if $f(i)=0$. Consider the difference between consecutive values of $f$. Since there is exactly one red point to the left of $\overline{BR_{i+1}}$ and not to the left of $\overline{BR_i}$ (namely $R_i$), it follows that $f(i)-f(i+1)$ is at most $1$ for all $i$; that is $f(i)$ decreases by at most $1$ when $i$ increases by $1$. Now, note that $f(1)>0$, since there are no red points to the left of $\overline{BR_1}$, but there must be at least one blue point (else $R_1$ lies on the convex hull), and by similar reasoning $f(n)<0$. Hence there must be some value $1 \leq x \leq n$ such that $f(x)=0$, otherwise $f(i)$ decreases by at least $2$ when $i$ increases by $1$. (This is known as discrete continuity/discrete IVT). To finish, note that the number of points on the convex hull of $S$ is at least $3$, hence there are at least $2$ balancing lines for $S$, as desired. $\blacksquare$

Consider the convex hull of the $2n$ points. It must consist of at least $3$ points such that any 3 are not collinear. First consider when it consists of both red and blue points. WLOG assume there must be at least 2 red points. Call these 2 red points $R_1$ and $R_2$. Then, the 2 balancing lines are $R_1B$ and $R_1B$, where $B$ is any blue point on the convex hull. For both $R_1B$ and $R_2B$, the other $2n-2$ points all lie on one side of the line, so $R_1B$ and $R_2B$ are indeed balancing. Now consider when all the points on the convex hull is one color. WLOG let the color be red. Label the points on the convex hull $R_1, R_2, \dots, R_i$ $(i \ge 3)$. Focus on $R_1$. Then, label the blue points $B_1, B_2, \dots B_n$ such that $R_1B_j$ is to the left of $R_1B_{j+1}$ for all $j$. For all $R_1B_j$, let $X_j$ denote the number of blue points to the left of $R_1B_j$ subtracted from the number of red points to the left of $R_1B_j$. We know that $R_1B_1 \ge 1$ and $R_1B_n \le -1.$ Moreover, if $X_{j+1} < X_j$, $X_{j+1}$ must be at most 1 less than $X_j$ since there are no blue points between $B_j$ and $B_{j+1}$. By the intermediate value theorem, there exists an $X_{\ell}$ such that $X_{\ell}=0.$ Then $A_1B_{\ell}$ is the desired balancing line. A similar process can be done for $R_2$, so we have another balancing line and we are done. (In fact, every red line on the convex hull is part of a balancing line).

POV: you spend 1 hour proving the existence of a convex hull

Consider the convex hull of the points. If both red and blue points exist on the convex hull, then we are done because taking an adjacent red/blue pair produces a balancing line. Otherwise, WLOG suppose only blue points are on the convex hull. Taking one such point, we can continuously sweep clockwise by taking red points inside the convex hull. Initially, one side of the line will have at least one blue points and no red points, and at the end, the same side of the line will contain $n-1$ red points, but at most $n-2$ blue points. Since the number of red points on this side of the line increases by exactly $1$ each time we take a new line, and the number of blue points on that side cannot decrease, one of the lines drawn will be a balancing line. This works for all points on the boundary, and since our convex hull consists of at least $3$ points, we will have at least $2$ balancing lines, as desired.

CASE 1: One can notice That if any blue and red point have not points on one of it's sides this mean the line between them is a balancing line (as on the other side we will have $n-1$ blue points and $n-1$ red). CASE 2: Now we consider the case in which all the points are inside a polygon with all vertices being one color (assume WLOG it's blue). Now consider a line that is pivoting at any vertex and rotating till reaching the other vertex of the polygon (convex hull) passing through every point in side the polygon. and let $x$ be the number of red points. minus the number of blue points on one side of the line. In other words every time the line passes through a blue point $x$ will increase by $1$, and decrease by $1$ if it passes through a red point. Firstly we have that $x=1$ and when the line reaches the other vertex of the polygon it will be equal to $-1$. So when $x$ will be equal to zero, we have a balancing line. Now repeating this process on all the other vertices of the polygon (convex hull) then we will have balancing lines equal to the number of the vertices.

If the convex hull is not monochromatic, the result is true by considering any dichromatic edge of the convex hull. Otherwise, take a line $\ell$ through two (say) consecutive blue points on the convex hull, and rotate $\ell$ counterclockwise until it touches a red point; call this line $\ell_0$. We keep track of the difference $D$ between the number of red and blue points on the side that originally contained the edge containing $\ell$. In particular, $D$ must be negative to begin (as there are no red points on that side by assumption). Now, we rotate $\ell$, stopping to compute $D$ every time $\ell$ hits another red point. In particular, any difference $D$ increases by at most $1$ every time we hit a new red point. In particular, the last such line $\ell$ will have $D$ nonnegative. So by continuity, there exists a point in between where $D=0$ precisely. We have demonstrated that there exists a balancing line through some vertex of the convex hull. As there are at least two such vertices, we are done.

A beautiful combinatorial question! I believe these are the kinds of problems that are best for problem-solving as they do not require prerequisites. As for the solution after you find the concept of a "convex hull", it is quite trivial.