THE WINDMILL (IMO 2011)

Views:
 
Category: Education
     
 

Presentation Description

IMO, Amsterdam 2011

Comments

Presentation Transcript

“The windmill” by Iuliana Parasca:

“The windmill” by Iuliana Parasca International Mathematical Olympiad Amsterdam 2011

Problem:

Problem 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 A Є S. The line rotates clockwise about the pivot until the first time that the line meets some other point belonging to S. This point, B , takes over as the new pivot, and the line now rotates clockwise about B, until it next meets a point of S. This process continues indefinitely.

Show that::

Show that: … we can choose a point A in S and a line l going through A such that the resulting windmill uses each point of S as a pivot indefinitely many times.

Solution:

Solution The idea of this problem is to give the rotating line an orientation, so that we can distinguish its sides as the orange side and the blue side. Notice that whenever the pivot changes from some point T to another point U, after the change, T is on the same side as U was before. Therefore, the number of elements of S on the orange side and the number of those on the blue side remain the same throughout the whole process (except for those moments when the line contains two points in S).

A picture is worth a thousand words:

A picture is worth a thousand words

“An integer can only be odd or even”:

“An integer can only be odd or even” Taking this into account, we shall consider exactly two cases: |S| is odd |S| is even, Where |S| represents the number of points that S contains.

CASE 1.:

CASE 1. |S|=2n+ 1. I claim that through any point T Є S, there is a line that has n points on each side. To see this, choose an oriented line through T containing no other point of S and suppose that it has ( n+r ) points on its orange side. If r=O, then we have established the claim, so we may assume that r≠O . As the line rotates through 180° around T, the number of points of S on its orange side changes by 1 whenever the line passes through a point; after 180 °, the number of points on the orange side is (n-r). Therefore, there is an intermediate stage at which the orange side (and thus, also the blue side) contains exactly n points.

PowerPoint Presentation:

Now select the point A arbitrarily, and choose a line through A that has n points of S on each side to be the initial state of the windmill. I will show that during a rotation over 180°, the line of the windmill visits each point of S as a pivot. To see this, select any point T of S and select a line l through T that separates S into equal halves. The point T is the unique point of S through which a line in this direction can separate the points of S into equal halves (parallel translation would disturb the balance). Therefore, when the windmill line is parallel to l , it must be l itself, and so pass through T.

CASE 2.:

CASE 2. |S|= 2n. Similarly to the odd case, for every T Є S there is an oriented line through T with n-1 points on its orange side and n points on its blue side. Select such an oriented line through an arbitrary A to be the initial state of the windmill.

PowerPoint Presentation:

I will now show that during a rotation over 360°, the line of the windmill visits each point of S as a pivot. To see this, select any point T of S and an oriented line l through T that separates S into two subsets with (n-1) points on its orange and n points on its blue side. Again, parallel translation would change the numbers of points on the two sides, so when the windmill line is parallel to l with the same orientation, the windmill line must pass through T.

To simplify the solution…:

To simplify the solution… Suppose that |S|= 2n+ 1. Consider any line l that separates S into equal halves; this line is unique given its direction and contains some point T Є S. Consider the windmill starting from this line. When the line has made a rotation of 180°, it returns to the same location but the orange side becomes blue and vice versa. So, for each point there should have been a moment when it appeared as pivot, as this is the only way for a point to pass from one side to the other.

PowerPoint Presentation:

Now suppose that |S|= 2n. Consider a line having (n-1) and n points on the two sides; it contains some point T. Consider the windmill starting from this line. After having made a rotation of 180°, the windmill line contains some different point R, and each point different from T and R has changed the color of its side. So, the windmill should have passed through all the points.

authorStream Live Help