Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2011 IMO Problems/Problem 2"
(Graph)
 
(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 +
__TOC__
 +
 +
==Problem==
 
Let <math>\mathcal{S}</math> be a finite set of at least two points in the plane. Assume that no three points of <math>\mathcal S</math> are collinear. A ''windmill'' is a process that starts with a line <math>\ell</math> going through a single point <math>P \in \mathcal S</math>. The line rotates clockwise about the ''pivot'' <math>P</math> until the first time that the line meets some other point belonging to <math>\mathcal S</math>. This point, <math>Q</math>, takes over as the new pivot, and the line now rotates clockwise about <math>Q</math>, until it next meets a point of <math>\mathcal S</math>. This process continues indefinitely.  
 
Let <math>\mathcal{S}</math> be a finite set of at least two points in the plane. Assume that no three points of <math>\mathcal S</math> are collinear. A ''windmill'' is a process that starts with a line <math>\ell</math> going through a single point <math>P \in \mathcal S</math>. The line rotates clockwise about the ''pivot'' <math>P</math> until the first time that the line meets some other point belonging to <math>\mathcal S</math>. This point, <math>Q</math>, takes over as the new pivot, and the line now rotates clockwise about <math>Q</math>, until it next meets a point of <math>\mathcal S</math>. This process continues indefinitely.  
 
Show that we can choose a point <math>P</math> in <math>\mathcal S</math> and a line <math>\ell</math> going through <math>P</math> such that the resulting windmill uses each point of <math>\mathcal S</math> as a pivot infinitely many times.
 
Show that we can choose a point <math>P</math> in <math>\mathcal S</math> and a line <math>\ell</math> going through <math>P</math> such that the resulting windmill uses each point of <math>\mathcal S</math> as a pivot infinitely many times.
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
Choose a coordinate system so that all points in <math>\mathcal S</math> have distinct x-coordinates. Number the points <math>P_i=(x_i,y_i)</math> of <math>\mathcal S</math> by increasing x-coordinates: <math>x_1<x_2<\ldots<x_N</math>.
 +
 
 +
In order to divide the set <math>\mathcal S</math> into two halves, define <math>n</math> so that <math>N=2n+1+d</math> where <math>d=0</math> for an odd number of points and <math>d=1</math> for an even number of points.
 +
 
 +
Start the "windmill" process with the line <math>\ell</math> going vertically through the point <math>P_{n+1}</math>.  Attach a down-up direction to this line so that we can color all points as follows: Points to the left of <math>\ell</math> (with lower x-coordinates) are blue, the pivot point on <math>\ell</math> is white and point to the right of <math>\ell</math> (with higher x-coordinates) are red.  We have now <math>n</math> blue points, one white point and <math>n+d</math> red points.
 +
 
 +
After processing the "windmill" by 180 degrees, the line <math>\ell</math> goes vertically up-down.  Now, points with lower x-coordinates are to the right of <math>\ell</math> and colored red; points with higher x-coordinates are to the left of <math>\ell</math> and colored blue.
 +
 
 +
Note that at each pivot exchange, the old pivot point enters the same side of <math>\ell</math> where the new pivot point came from.  This means that throughout the "windmill" process, the number of blue points and the number of red points stay constant, respectively: We still have <math>n</math> blue points, one white point and <math>n+d</math> red points.  This means that the current pivot point is <math>P_{n+d}</math>. 
 +
 
 +
Note that all blue and all red points changed their color from the start of the "windmill" process.  This implies that every point was a pivot at some stage of the rotation.
 +
 
 +
For every 180 degrees of "windmill" rotation, the same argument applies: all colored points must change their color and hence be a pivot at some stage.  Infinitely many rotations imply infinitely many color changes.  This completes the proof.
 +
 
 +
==Interactive Graph==
 +
See [https://www.desmos.com/calculator/eec1g1zfh9 here]
 +
(By u/basuboss on reddit)
  
 
==See Also==
 
==See Also==
−
*[[IMO Problems and Solutions]]
+
 
 +
{{IMO box|year=2011|num-b=1|num-a=3}}
 +
 
 +
==Weblinks==
 +
* [http://bernikr.github.io/windmill/ A interactive visualization of the Problem]
 +
 
 +
* [https://www.youtube.com/watch?v=M64HUIJFTZM/ A video solution]

Latest revision as of 22:19, 26 November 2023

Problem

Let $\mathcal{S}$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal S$ are collinear. A windmill is a process that starts with a line $\ell$ going through a single point $P \in \mathcal S$. The line rotates clockwise about the pivot $P$ until the first time that the line meets some other point belonging to $\mathcal S$. This point, $Q$, takes over as the new pivot, and the line now rotates clockwise about $Q$, until it next meets a point of $\mathcal S$. This process continues indefinitely. Show that we can choose a point $P$ in $\mathcal S$ and a line $\ell$ going through $P$ such that the resulting windmill uses each point of $\mathcal S$ as a pivot infinitely many times.

Solution

Choose a coordinate system so that all points in $\mathcal S$ have distinct x-coordinates. Number the points $P_i=(x_i,y_i)$ of $\mathcal S$ by increasing x-coordinates: $x_1<x_2<\ldots<x_N$.

In order to divide the set $\mathcal S$ into two halves, define $n$ so that $N=2n+1+d$ where $d=0$ for an odd number of points and $d=1$ for an even number of points.

Start the "windmill" process with the line $\ell$ going vertically through the point $P_{n+1}$. Attach a down-up direction to this line so that we can color all points as follows: Points to the left of $\ell$ (with lower x-coordinates) are blue, the pivot point on $\ell$ is white and point to the right of $\ell$ (with higher x-coordinates) are red. We have now $n$ blue points, one white point and $n+d$ red points.

After processing the "windmill" by 180 degrees, the line $\ell$ goes vertically up-down. Now, points with lower x-coordinates are to the right of $\ell$ and colored red; points with higher x-coordinates are to the left of $\ell$ and colored blue.

Note that at each pivot exchange, the old pivot point enters the same side of $\ell$ where the new pivot point came from. This means that throughout the "windmill" process, the number of blue points and the number of red points stay constant, respectively: We still have $n$ blue points, one white point and $n+d$ red points. This means that the current pivot point is $P_{n+d}$.

Note that all blue and all red points changed their color from the start of the "windmill" process. This implies that every point was a pivot at some stage of the rotation.

For every 180 degrees of "windmill" rotation, the same argument applies: all colored points must change their color and hence be a pivot at some stage. Infinitely many rotations imply infinitely many color changes. This completes the proof.

Interactive Graph

See here (By u/basuboss on reddit)

See Also

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

Weblinks

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_IMO_Problems/Problem_2&oldid=206001"