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"

(Created page with "Let S be a finite set of at least two points in the plane. Assume that no three points of S are collinear. A windmill is a process that starts with a line l going through a singl...")
 
(Graph)
 
(8 intermediate revisions by 6 users not shown)
Line 1: Line 1:
−
Let S be a finite set of at least two points in the plane. Assume that no three points of S are collinear. A windmill is a process that starts with a line l going through a single point P ∈ S. The line rotates clockwise about the pivot P until the first time that the line meets some other point belonging to 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 S. This process continues indefinitely.
+
__TOC__
−
Show that we can choose a point P in S and a line l going through P such that the resulting windmill uses each point of S as a pivot infinitely many times.
+
 
 +
==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.  
 +
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==
 +
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==
 +
 
 +
{{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"