Difference between revisions of "2005 USAMO Problems/Problem 5"

Latest revision as of 13:55, 2 September 2024

Problem

(Kiran Kedlaya) 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.

Solution

Solution 1

Consider the convex hull of the the $2n$ points, or the points that would form the largest convex polygon. If the points in the convex hull contain both red and blue points, then there must be at least 2 edges of the graph of the convex hull such that the edge connects a blue and a red point. Drawing a line through those points would give a balancing line, as we have n-1 blue points and n-1 red points on one side, and 0 points on the other.

Therefore it suffices to show that there exist at least 2 balancing lines when the convex hull is colored all the same color.

Pick a random point on the convex hull, and without loss of generality we can say it is blue (if there are no red we can change all the colors, and end up with an equivalent setup). Consider a line going through it and not any other points. As we rotate the line clockwise, we encounter the red points in some order. Let the ith point encountered be $R_i$ . Let $b_i$ and $r_i$ be the number of points encountered before $R_i$ . Then $r_i=i-1$ .

Define a sequence $f(i)=b_i-r_i$ . Then $f(1)=b_i-(1-1)=b_i\geq0$ $f(n)=b_n-(n-1)=b_n-n+1\leq0$ , because we can only encounter up to n-1 blue points. Thus, $f(i)$ goes from negative to positive as $i$ goes from 1 to $n$ . We can also see that $f(i)$ can only increase by one for each change in i, so we know $f(i)$ must be 0 for some value of $i$ . Take the first $f(i)$ where $f(i) = 0$ . Since $f(i-1)$ must have been positive, the ith point must have been red. Thus there is a balancing line for every point on the convex hull. Since a polygon must have at least 3 vertices, there must be at least $3>2$ balancing lines for the set of points when the convex hull is all the same color, and the statement is true as we desired.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Solution 2

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 another 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.

By Ywgh1

@@ Line 1: / Line 1: @@
-== Problem 5 ==
+== Problem ==
-Let <math>n</math> be an integer greater than 1. Suppose <math>2n</math> points are given in the plane, no three of which are collinear. Suppose <math>n</math> of the given <math>2n</math> points are colored blue and the other <math>n</math> 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.
+(''Kiran Kedlaya'') Let <math>n</math> be an integer greater than 1. Suppose <math>2n</math> points are given in the plane, no three of which are collinear. Suppose <math>n</math> of the given <math>2n</math> points are colored blue and the other <math>n</math> 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.
+== Solution ==
+===Solution 1===
+Consider the convex hull of the the <math>2n</math> points, or the points that would form the largest convex polygon. If the points in the convex hull contain both red and blue points, then there must be at least 2 edges of the graph of the convex hull such that the edge connects a blue and a red point. Drawing a line through those points would give a balancing line, as we have n-1 blue points and n-1 red points on one side, and 0 points on the other.
+Therefore it suffices to show that there exist at least 2 balancing lines when the convex hull is colored all the same color.
+Pick a random point on the convex hull, and without loss of generality we can say it is blue (if there are no red we can change all the colors, and end up with an equivalent setup). Consider a line going through it and not any other points. As we rotate the line clockwise, we encounter the red points in some order. Let the ith point encountered be <math>R_i</math>. Let <math>b_i</math> and <math>r_i</math> be the number of points encountered before <math>R_i</math>. Then <math>r_i=i-1</math>.
+Define a sequence <math>f(i)=b_i-r_i</math>. Then <math>f(1)=b_i-(1-1)=b_i\geq0</math>
+<math>f(n)=b_n-(n-1)=b_n-n+1\leq0</math>, because we can only encounter up to n-1 blue points.
+Thus, <math>f(i)</math> goes from negative to positive as <math>i</math> goes from 1 to <math>n</math>. We can also see that <math>f(i)</math> can only increase by one for each change in i, so we know <math>f(i)</math> must be 0 for some value of <math>i</math>. Take the first <math>f(i)</math> where <math>f(i) = 0</math>. Since <math>f(i-1)</math> must have been positive, the ith point must have been red. Thus there is a balancing line for every point on the convex hull. Since a polygon must have at least 3 vertices, there must be at least <math>3>2</math> balancing lines for the set of points when the convex hull is all the same color, and the statement is true as we desired.
+{{alternate solutions}}
+=== Solution 2 ===
+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 <math>n-1</math> blue points and <math>n-1</math> 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 another vertex of the polygon (convex hull) passing through every point in side the polygon. and let <math>x</math> 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 <math>x</math> will increase by <math>1</math>, and decrease by <math>1</math> if it passes through a red point.
+Firstly we have that <math>x=1</math> and when the line reaches the other vertex of the polygon  it will be equal to <math>-1</math>.
+So when <math>x</math> 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.
+By Ywgh1
+== See Also==
+{{USAMO newbox|year=2005|num-b=4|num-a=6}}
+{{MAA Notice}}

2005 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search