|
|
|
<a href="https://www.youtube.com/watch?v=M64HUIJFTZM">Youtube</a><br>
<a href="https://artofproblemsolving.com/wiki/index.php?title=2011_IMO_Problems/Problem_2">aops</a><br>
<a href="https://www.math.leidenuniv.nl/~desmit/pop/2011_imo_final6.pdf">imo_final6.pdf</a> (page 5)
<p>2011 IMO Problems/Problem 2 Let <span class="math inline">𝒮</span> be a finite set of at least two points in the plane. Assume that no three points of <span class="math inline">𝒮</span> are collinear. A <em>windmill</em> is a process that starts with a line <span class="math inline">𝓁</span> going through a single point <span class="math inline"><em>P</em> ∈ 𝒮</span>. The line rotates clockwise about the pivot <span class="math inline"><em>P</em></span> until the first time that the line meets some other point belonging to <span class="math inline">𝒮</span>. This point, <span class="math inline"><em>Q</em></span>, takes over as the new pivot, and the line now rotates clockwise about <span class="math inline"><em>Q</em></span>, until it next meets a point of <span class="math inline">𝒮</span>. This process continues indefinitely. Show that we can choose a point <span class="math inline"><em>P</em></span> in <span class="math inline">𝒮</span> and a line <span class="math inline">𝓁</span> going through <span class="math inline"><em>P</em></span> such that the resulting windmill uses each point of <span class="math inline">𝒮</span> as a pivot infinitely many times.</p>
<p>Solution. Choose a coordinate system so that all points in <span class="math inline">𝒮</span> have distinct x-coordinates. Number the points <span class="math inline"><em>P</em><sub><em>i</em></sub> = (<em>x</em><sub><em>i</em></sub>,<em>y</em><sub><em>i</em></sub>)</span> of <span class="math inline">𝒮</span> by increasing x-coordinates: <span class="math inline"><em>x</em><sub>1</sub> < <em>x</em><sub>2</sub> < … < <em>x</em><sub><em>N</em></sub></span>.</p>
<p>In order to divide the set <span class="math inline">𝒮</span> into two halves, define <span class="math inline"><em>n</em></span> so that N=2n+1+d where d=0 for an odd number of points and d=1 for an even number of points.</p>
<p>Start the "windmill" process with the line <span class="math inline">𝓁</span> going vertically through the point <span class="math inline"><em>P</em><sub><em>n</em> + 1</sub></span>. Attach a down-up direction to this line so that we can color all points as follows: Points to the left of <span class="math inline">𝓁</span> (with lower x-coordinates) are blue, the pivot point on <span class="math inline">𝓁</span> is white and point to the right of <span class="math inline">𝓁</span> (with higher x-coordinates) are red. We have now <span class="math inline"><em>n</em></span> blue points, one white point and n+d red points.</p>
<p>After processing the "windmill" by 180 degrees, the line <span class="math inline">𝓁</span> goes vertically up-down. Now, points with lower x-coordinates are to the right of <span class="math inline">𝓁</span> and colored red; points with higher x-coordinates are to the left of <span class="math inline">𝓁</span> and colored blue.</p>
<p>Note that at each pivot exchange, the old pivot point enters the same side of <span class="math inline">𝓁</span> 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 <span class="math inline"><em>P</em><sub><em>n</em> + <em>d</em></sub></span>.</p>
<p>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.</p>
<p>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.</p>
<p>Variation question: Is it necessary to start with the initial pivot and windmill line in this exact configuration (depending on the odd/even number S?) i.e. the solution given splits the set S exactly in half (for odd S) or as close to half as possible (for even S). Can the initial line be more "off center"?</p>
<p>Is it possible to solve the problem with, say, (n-2) points on one side of the initial line? What is the maximum possible difference between the sum of points on either side that meets the conditions of the answer (i.e. each point is a windmill pivot infinitely often?)</p>
<p>(I’m assuming that you’ve read the windmill solution and are familiar with the concepts, like the invariance in the number of points on one side, existence of line given any point, and uniqueness of line given direction.)</p>
<p>The difference between the number of points is crucial to the solution, because it guarantees the existence of the line given any point.</p>
<p>As an extreme example, if we’re given n points, and we consider a line going through 1 pivot point, has 0 points on 1 side, and n-1 points on the other, it is clear that this line cannot intersect the (interior of the) convex hull of the points. In particular, if the convex hull interior contains a point, then no such line can touch this point, and so this point cannot ever be the pivot. In particular, with n=4 points, then the line with 0 points on 1 side and 3 points on the other, will not work for the case where the convex hull is a triangle, and the other point is inside. This shows that a difference of 3 points isn’t enough.</p>
<p>—–</p>
<p>Now, let’s consider the case where we have a difference of 2 points. This necessitates that there are n=2k+1 points, and the line has 1 pivot point, k-1 points on one side, and k+1 points on the other.</p>
<p>Claim: For any arrangement of n=2k+1 points, and any given point <span class="math inline"><em>P</em></span>, there exists a line which has <span class="math inline"><em>k</em></span> points on one side, and <span class="math inline"><em>k</em></span> points on the other.</p>
<p>Proof: This is shown in the solution to the windmill problem.</p>
<p>Claim: For any arrangement of n=2k+1 points, and any given point P, there exists a line which has k-1 points on one side, and k+1 points on the other.</p>
<p>Poof: Take the line in the solution in the windmill problem, and let it rotate past 1 point. We now have k-1 points on one side, and k+1 points on the other.</p>
<p>Claim: Given a oriented direction (not parallel to the vector defined by 2 points), there is a unique line that passes through 1 point, and has k-1 points on one side and k+1 points on the other. Note that the "oriented direction" means that a line with k+1 points "on top" is different than a line with k-1 points "on top".</p>
<p>Proof: Take the line and slowly move it across all of the points. At some stage, we must have exactly k-1 points on one side, it passes through 1 pivot point, and hence has k+1 points on the other side.</p>
<p>Claim: Such a line satisfies the conditions of the windmill problem.</p>
<p>Proof: Repeat the solution. All that we needed was A) Existance of line through any given point and B) Uniqueness of line given direction, which was shown above.</p>
<p>**Corollary:** For odd <span class="math inline"><em>n</em></span>, we could use a difference of 2 points.</p>
<p>Hence, the answer to your question is 2.</p>
<p>—–</p>
<p>Note: Where this argument breaks down for larger differences, is that we cannot guarantee the existence of a line which has <span class="math inline"><em>k</em> − 2</span> points on one side, and <span class="math inline"><em>k</em> + 2</span> points on the other. What this means is that as we rotate a line through this point, it toggles between having <span class="math inline"><em>k</em>, <em>k</em></span> points and <span class="math inline"><em>k</em> − 1, <em>k</em> + 1</span> points. Can you find such a configuration where there isn’t a line with <span class="math inline"><em>k</em> − 2, <em>k</em> + 2</span> fo a given point?</p>
<p>Similarly, for <span class="math inline"><em>n</em> = 2<em>k</em></span> even, there is a configuration where the line though the point always has <span class="math inline"><em>k</em> − 1, <em>k</em></span> points.</p> |
|
Czhang271828
Posted 2022-5-19 16:15
kuing
Posted 2022-5-19 16:20
abababa
Posted 2022-5-19 16:39
……
