Let n be an integer greater than 1. Suppose 2n points are given in the plane, no three of which are collinear. Suppose n of the given 2n points are colored blue and the other n colored red. A line in the plane is called a balancing line if it passes through one blue and one red point and, for each side of the line, the number of blue points on that side is equal to the number of red points on the same side. Prove that there exist at least two balancing lines.
Problem
Source: USAMO 2005, problem 5, Kiran Kedlaya
Tags: geometry, induction, discrete continuity, pigeonhole principle, minimal maximal principal
21.04.2005 13:37
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:

21.04.2005 13:55
I solved it the same way. So, I missed the same thing as you.
21.04.2005 15:38
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 Ri,i=1,2,...,n so that i>j⇒∠CARi>∠CARj (i.e., counterclockwisely) If we draw all the lines ARi, then the number of red points on the right side of ARi is i−1,i=1,2,...,n. The number of blue points on the right side of ARi 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 ARi, 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.
21.04.2005 15:43
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.
21.04.2005 16:04
I guess, iff you're experienced. I spent like an hour trying to do it via induction...
21.04.2005 17:09
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
21.04.2005 17:26
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.
21.04.2005 20:04
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.
21.04.2005 20:16
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.
21.04.2005 20:35
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.
21.04.2005 21:02
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 S1 and Sn+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 L1, 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 Li by Ki. (K1>0) If we consider Ln, 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.) (Kn<0) Consider each successive line, Li, from L2 through Ln. If Sector Si contains one blue point, the imbalance in Li will equal the imbalance in line Li−1. (Ki=Ki−1) If Sector Si contains more than one blue point, the excess of blue points to the right of Li will increase, compared to the excess of blue points to the right of Li−1. (Ki>Ki−1) However, if Sector Si contains no blue points, the excess of blue points to the right of Li will decrease by exactly one, compared to the excess of blue points to the right of Li−1. (Ki=Ki−1−1) The value(s) where Ki=0 correspond to a balancing line. Since the sequence, K1,K2,K3,…,Kn is known to go from a positive value at K1 to a negative value at Kn, 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:

21.04.2005 21:04
If you've seen IMO 99 #1 you were probably more than ready to use Convex Hull on this problem.
22.04.2005 01:20
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.
22.04.2005 10:29
I didn't know about convex shells, either, so I just proved it. Then, with the line rotation, I made a0,a1,...an the counts of blue points before, after, and in between the n red points. Then you have the sum of the ai equal to n−1. Then a balancing line exists through our blue point and the k+1st red point met in the rotation iff the sum of the ai 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(nO(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(nO(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.
22.04.2005 11:21
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.
24.04.2005 00:03
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.
25.04.2005 06:44
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.
26.04.2005 06:29
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.
29.04.2005 12:58
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)...
13.12.2005 05:38
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.
13.12.2005 08:41
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...
15.11.2014 02:56
Lemma. Let k≥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∈N,m≥3. We prove the claim true for k=m+1. Let us label the points X1,X2,...,Xm+1. By the induction hypothesis, there exists a convex polygon, which we will denote by ⊘ with vertices from the set {X1,X2,...,Xm}, that contains all points X1,X2,...,Xm. Now, if the point Xm+1 also lies in ⊘, then we are done. If Xm+1 does not lie in ⊘, then consider a line γ passing through Xm+1 such that γ does not intersect ⊘. Note that since Xm+1∉⊘, such a line γ must exist. Now, we rotate γ couterclockwise until it first intercepts a vertex Xp of ⊘. We continue to rotate γ counterclockwise until it intercepts a vertex Xq of ⊘, such that Xq is the last vertex that γ intercepts during this rotation (until it once again intercepts Xp after rotating through 180∘). Denote by S the sequence of consecutive vertices of ⊘ that connect Xp and Xq, where S lies on the opposite side of line XpXq as Xm+1. It follows that all vertices of ⊘ that are not Xp,Xq or in T are contained within the lines Xm+1Xp and Xm+1Xq. Therefore, Xm+1XpTXq 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≥2, there are at least 2⋅2=4 given points. Therefore, by our Lemma, there must exist a convex polygon, which we will denote by ⊗, with vertices from the 2n given points, such that all of the 2n points lie within ⊗. We label these vertices (in the order that they appear in ⊗) P1,P2,...,Pi, where i∈N,i≤2n. We now consider two cases: Case 1: P1,P2,...,Pi are all the same color. WLOG, assume that these points are all red. Then the adjacent vertices P1 and P2 are both red. Now, consider the line P1P2. We rotate this line about P1 in the direction such that P2 is rotated into ⊗. Let Q, where Q is one of the given 2n points, be the first blue point that the line P1P2 intercepts during this rotation. Then the line P1Q divides the plane into two regions, one of which contains only red points (among which is P2), and the other contains the remaining of the given 2n points (other than P1 and Q, of course). Since the first region contains only red points, it follows that the second region, which contains the point Pi, contains more blue points than red points. Now, we continue rotating the line P1P2 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 P1P2 will intercept during its rotation, until P1P2 intercepts Pi. Then the line P1Q∗ divides the plane into two regions, one of which contains only red points (among which is Pi), and the other contains the remaining of the given 2n points (other than P1 and Q∗, of course). Therefore, during this rotation, the line P1Q divides the plane into two regions. The region containing the point Pi has more blue points than red points. Then, the line is further rotated to P1Q∗. The line P1Q∗ divides the plane into two regions, where the region containing Pi contains more red points than blue points. Therefore, by the principle of continuity, there must exist a blue point R∈⊗, such that the line P1R divides ⊗ into two regions, with each region containing an equal number of red and blue points. Hence, there exists a balancing line passing through P1. Similarly, we can show that there exists a balancing line passing through P2, and in general, through all of the Pk's. Since we have shown that there exist at least two balancing lines, this concludes Case 1. Case 2: The set {P1,P2,...,Pi} contains both red and blue elements. Consider the longest consecutive sequence of red vertices on ⊗. Since the vertices of ⊗ are not all red, it follows that the first and last red vertex in this sequence must be adjacent to a blue vertex. Therefore, ⊗ must contain at least two pairs of consecutive vertices that are opposite in color. Suppose these pairs of adjacent vertices are (Pa,Pb),(Pc,Pd) where Pa,Pc are red and Pb,Pd are blue. Note that these pairs are distinct, since if Pa=Pc and Pb=Pd, then it follows that ⊗ has only two vertices, absurd. Now, since the pairs (Pa,Pb) and (Pc,Pd) are distinct, the two lines PaPb and PcPd are also distinct. In addition, since the Pi's are simply vertices of a convex polygon, ⊗, that encloses the given 2n points, it follows that the each of the lines PaPb and PcPd divides the plane into two regions, one of which fully contains ⊗. 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 PaPb and PcPd 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.
08.04.2021 00:43
Actually good cg problem?? Let S be the set of all of the points. Also, given a line ¯PQ (where the order of vertices matters) and a point X not on that line, say X is to the "left" of ¯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 R1,R2,…,Rn such that Ri is to the left of ¯BRj 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 ¯BRi minus the number of red points to the left of ¯BRi. It is evident that the line ¯BRi 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 ¯BRi+1 and not to the left of ¯BRi (namely Ri), 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 ¯BR1, but there must be at least one blue point (else R1 lies on the convex hull), and by similar reasoning f(n)<0. Hence there must be some value 1≤x≤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. ◼
03.05.2021 00:03
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 R1 and R2. Then, the 2 balancing lines are R1B and R1B, where B is any blue point on the convex hull. For both R1B and R2B, the other 2n−2 points all lie on one side of the line, so R1B and R2B 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 R1,R2,…,Ri (i≥3). Focus on R1. Then, label the blue points B1,B2,…Bn such that R1Bj is to the left of R1Bj+1 for all j. For all R1Bj, let Xj denote the number of blue points to the left of R1Bj subtracted from the number of red points to the left of R1Bj. We know that R1B1≥1 and R1Bn≤−1. Moreover, if Xj+1<Xj, Xj+1 must be at most 1 less than Xj since there are no blue points between Bj and Bj+1. By the intermediate value theorem, there exists an Xℓ such that Xℓ=0. Then A1Bℓ is the desired balancing line. A similar process can be done for R2, 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).
18.01.2022 02:37
POV: you spend 1 hour proving the existence of a convex hull
09.06.2022 04:13
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.
14.12.2023 16:36
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.
27.02.2024 04:53
If the convex hull is not monochromatic, the result is true by considering any dichromatic edge of the convex hull. Otherwise, take a line ℓ through two (say) consecutive blue points on the convex hull, and rotate ℓ counterclockwise until it touches a red point; call this line ℓ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 ℓ. In particular, D must be negative to begin (as there are no red points on that side by assumption). Now, we rotate ℓ, stopping to compute D every time ℓ 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 ℓ 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.
30.09.2024 19:47
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.