This post marks the official opening of the mini-polymath3 project to solve a problem from the 2011 IMO. I have decided to use Q2, in part to see how the polymath format would cope with a more geometrically themed problem.
Problem 2. Letbe a finite set of at least two points in the plane. Assume that no three points of
going through a single point
. The line rotates clockwise about the pivot
until the first time that the line meets some other point
belonging to
Show that we can choose a point
The comments to this post shall serve as the research thread for the project, in which participants are encouraged to post their thoughts and comments on the problem, even if (or especially if) they are only partially conclusive. Participants are also encouraged to visit the discussion thread for this project, and also to visit and work on the wiki page to organise the progress made so far.
This project will follow the general polymath rules. In particular:
- All are welcome. Everyone (regardless of mathematical level) is welcome to participate. Even very simple or “obvious” comments, or comments that help clarify a previous observation, can be valuable.
- No spoilers! It is inevitable that solutions to this problem will become available on the internet very shortly. If you are intending to participate in this project, I ask that you refrain from looking up these solutions, and that those of you have already seen a solution to the problem refrain from giving out spoilers, until at least one solution has already been obtained organically from the project.
- Not a race. This is not intended to be a race between individuals; the purpose of the polymath experiment is to solve problems collaboratively rather than individually, by proceeding via a multitude of small observations and steps shared between all participants. If you find yourself tempted to work out the entire problem by yourself in isolation, I would request that you refrain from revealing any solutions you obtain in this manner until after the main project has reached at least one solution on its own.
- Update the wiki. Once the number of comments here becomes too large to easily digest at once, participants are encouraged to work on the wiki page to summarise the progress made so far, to help others get up to speed on the status of the project.
- Metacomments go in the discussion thread. Any non-research discussions regarding the project (e.g. organisational suggestions, or commentary on the current progress) should be made at the discussion thread.
- Be polite and constructive, and make your comments as easy to understand as possible. Bear in mind that the mathematical level and background of participants may vary widely.
Have fun!
The polymath blog 
[…] just opened the research thread for the mini-polymath3 project over at the polymath blog. I decided to use Q2 of this […]
Pingback by Mini-polymath3 discussion thread « What’s new — July 19, 2011 @ 8:01 pm |
Could you start off with a random point in the plane and prove it doesn’t work, if you can’t prove that then the opposite holds.
Comment by Richard McCart — August 22, 2011 @ 3:52 am |
Connecting the dots: At the point where the pivot changes we create a line that passes through the previous pivot and a new pivot – like a side of a polygon.
Comment by Gal — July 19, 2011 @ 8:07 pm |
Nice. We need only to consider the times when to points are connected – this gives us a path, and after some time this path will come back to some already visited point. So there is a cycle. If only we could find a cycle which spans all the points, the question is solved… That may be some useful simplification.
Comment by Garf — July 19, 2011 @ 8:23 pm |
Isn’t there always a cycle that spans all the points? The problem imposes restrictions on the cycles we can choose, right?
Comment by Gal — July 19, 2011 @ 8:37 pm |
For example, the restriction on how the next pivot is chosen (geometrically: comment 9). Are there any other restrictions? Can we start with a complete graph and all cycles on that graph and just discard the ones that don’t follow the restrictions to converge on the ones that do?
Comment by Gal — July 19, 2011 @ 8:56 pm |
The line must sweep out a full rotation (and only one full rotation) of 2π during the traversal of S. I feel like this is intimately related to proving that there is a starting angle for any point P in S such that all of S is then traversed. I’m trying to show this by induction. Base case (|S|=2) is obvious. Let |S| = n, take S’ = S U {Q}, and start with some windmill traversal of S.
Case A: Q is unreachable. Therefore we just traverse S, taking 2π to do so by induction.
Case B: Q is reachable at some angle Ω0 from P0 in S
– Case 1: the next point to be reached is the same as before (e.g. S_k -> Q -> S_{k+1} -> S_{k+2} instead of S_k -> S_{k+1 -> S_{k+2}). Previously, the radians traversed by the line for this transition was A1 + A2. Now it’s (A1-Ω0) + Ω0 + Ω1 + (A_2 – Ω1) = A1+A2. Then we proceed through S, taking the remainder of 2π remaining.
– Case 2: We go through Q again. This is effectively the same thing, but now you segment the angle few more times: (A_1 – Ω0) + Ω0 + Ω1 + Ω2 + … + (A_2 – Ω1 – Ω2 – ….)
– Case 3: We go to a different point in S (having trouble here).
Comment by CLH — July 19, 2011 @ 9:31 pm |
Or like an edge of a graph, and each edge leads to another edge. We want to show that there’s a circuit that visits every vertex at least once. Ideas?
Comment by Anonymous — July 19, 2011 @ 8:28 pm |
Is it me, or you can get a partition of the set of directed edges on this graph into admissible cycles (i.e., cycles generated by the windmill process) ? You juste have to reverse the time if necessary…
Comment by Garf — July 19, 2011 @ 8:37 pm |
I believe this is true. It proves that it’s enough to find a cycle that visits each vertex at least once; there are no “rho” processes with an initial segment that doesn’t repeat.
Comment by Austin — July 19, 2011 @ 8:43 pm |
If the points form a convex polygon, it is easy.
Comment by Anonymous — July 19, 2011 @ 8:08 pm |
Yes. Can we do it if there is a single point not on the convex hull of the points?
Comment by Thomas H — July 19, 2011 @ 8:09 pm |
Say there are four points: an equilateral triangle, and then one point in the center of the triangle. No three points are collinear.
It seems to me that the windmill can not use the center point more than once! As soon as it hits one of the corner points, it will cycle indefinitely through the corners and never return to the center point.
I must be missing something here…
Comment by Jerzy — July 19, 2011 @ 8:17 pm |
This isn’t true – it will alternate between the centre and each vertex of the triangle.
Comment by Joe — July 19, 2011 @ 8:21 pm |
No, you’re not right. Let the corner points be A, B, C, clockwise, M the center. If you start in M, you first hit say A, then C, then M, then B, then A.
Comment by Thomas H — July 19, 2011 @ 8:21 pm |
Ohhh… I misunderstood the problem. I saw it as a half-line extending out from the last point, in which case you would get stuck on the convex hull. But apparently it means a full line, so that the next point can be “behind” the previous point. Got it.
Comment by Jerzy — July 19, 2011 @ 8:31 pm |
Yeah, so it’s an infinite line extending in both directions and not just a ray. I’m thinking spirograph rather than convex hull.
Comment by Dan Hagon — July 19, 2011 @ 8:44 pm |
Yeah, Spirograph seems to be worth a try…
Comment by Manjunath Mc — July 20, 2011 @ 6:09 am |
The first point and line P_0, l_0 cannot be chosen so that P_0 is on the boundary of the convex hull of S and l_0 picks out an adjacent point on the convex hull. Maybe the strategy should be to take out the convex hull of S from consideration; follow it up by induction on removing successive convex hulls.
-Haggai
Comment by Haggai Nuchi — July 19, 2011 @ 8:08 pm |
More specifically, remove the subset of S which forms the convex hull to get S_1; remove the new convex hull to get S_2, and repeat until S_n is convex. Maybe a point of S_n is a good place to start.
Comment by Haggai Nuchi — July 19, 2011 @ 8:10 pm |
Can we just assume by induction that we have proved the result for all the “inner points”
. The base case would be that $S = S_1$, i.e., it forms a convex polygon.
Comment by Srivatsan Narayanan — July 19, 2011 @ 8:37 pm |
I hope this hasn’t been said already, but this seems close to me. Consider one convex hull $$\{ p1, p2, …\}$$ inside another $$\{q1, …\}$$, and suppose that a line pivoting on $$p_i$$ needs to sweep out some angle $$\alpha$$ to reach $$p_{i+1}$$. Then I think that even if there are points $$q_{j_1}, q_{j_2}, …$$ between $$p_i$$ and $$p_{i+1}$$, the line keeps advancing until it starts to pivot on $$p_{i+1}$$. If this could be extended to many hulls then we may be done.
Comment by Anonymous — January 19, 2012 @ 7:59 pm |
(apologies for doing my latex wrong). I just wanted to clarify, though, that a line advances if it passes over the sector with center![[q_i]](https://s0.wp.com/latex.php?latex=%5Bq_i%5D&bg=ffffff&fg=000000&s=0&c=20201002)
and boundary equal to the starting point of ![[\ell]](https://s0.wp.com/latex.php?latex=%5B%5Cell%5D&bg=ffffff&fg=000000&s=0&c=20201002)
and angle ![[\alpha]](https://s0.wp.com/latex.php?latex=%5B%5Calpha%5D&bg=ffffff&fg=000000&s=0&c=20201002)
. Once the whole sector is on the other side of ![[\ell]](https://s0.wp.com/latex.php?latex=%5B%5Cell%5D&bg=ffffff&fg=000000&s=0&c=20201002)
, then I believe we will have hit ![[q_{i+1}]](https://s0.wp.com/latex.php?latex=%5Bq_%7Bi%2B1%7D%5D&bg=ffffff&fg=000000&s=0&c=20201002)
Comment by Anonymous — January 19, 2012 @ 8:05 pm |
Trivial observation: If we start with a point on the convex hull of S and a line
that is “tangent” to the convex hull then we will only iterate over the points from the convex hull.
Comment by Nemanja — July 19, 2011 @ 8:08 pm |
Minor typo in the problem statement: I assume the last line should be “each point of *S* as a pivot…” [Corrected, thanks – T.]
Comment by Jerzy — July 19, 2011 @ 8:14 pm |
It looks to me like we could take the convex hull of all the points and ignore all the points that are in the interior. Then the windmill process would work its way through the exterior points in an infinite cycle while never passing through the interior hence missing all the interior points and allowing them to be ignored.
Comment by Kristal — July 19, 2011 @ 8:15 pm |
To be specific choose one of the points not in the interior of the convex hull and a line which doesn’t
pass through the interior of the convex hull.
Comment by Kristal — July 19, 2011 @ 8:28 pm |
I think I started with the same misunderstanding as you. Don’t imagine rotating a half-line extending out (in one direction) from the new point, but rather a full line extending out in both directions.
Comment by Jerzy — July 19, 2011 @ 8:33 pm |
I don’t follow. Take three points forming an equilateral triangle, and a fourth in the middle (interior of the triangle, not on the boundary of the triangle). Start with one of the vertices of the triangle as a pivot for the line $l$. Then $l$ rotates clockwise until it hits another triangle vertex (thus laying over an ‘edge’ of the triangle), and switches its pivot to the new vertex. When does $l$ ever pivot around the interior point?
Comment by -- — July 19, 2011 @ 9:35 pm |
EDIT: I follow now. In the above setup, it suffices to start with the interior point as initial pivot. I misunderstood the question.
Comment by -- — July 19, 2011 @ 9:43 pm |
Trivial observation: It is easy to see for n=2 and n=3. Actually this can easily be generalized to any convex polygon.
First non-trivial case: A triangle with a point in the middle?
Comment by rweba — July 19, 2011 @ 8:15 pm |
A triangle with an interior point can be dealt with be making sure the interior point is the second pivot we would then form a cycle involving all 4 points which will repeat.
Comment by Paul — July 19, 2011 @ 8:20 pm |
One should start say with a point in the middle and there any line will do.
Comment by Anonymous — July 19, 2011 @ 8:21 pm |
choose one of the points of the triangle and choose a line through the point that does not pass through the interior of the triangle then the windmill process should cycle through the vertices of the triangle.
Comment by Kristal — July 19, 2011 @ 8:24 pm |
It looks like some kind of subdivision in cells occurs (i.e. a subdivision in convex polygons whose vertices are visited counter-clockwise)…
Comment by Garf — July 19, 2011 @ 8:32 pm |
Angles: If we connect every two dots, then the next pivot is the one that forms the smallest angle in relation with the current pivot.
Comment by Gal — July 19, 2011 @ 8:15 pm |
… in the direction of rotation of our line L.
Comment by Gal — July 19, 2011 @ 8:17 pm |
A possible line of enquiry might be to consider how adding additional points effects an already established “windmill” this might lead to an inductive solution if adding new points can be related to already established cases.
Comment by Paul — July 19, 2011 @ 8:16 pm |
One can start with any point (since every point of S should be pivot infinitely often), the direction of line that one starts with however matters!
Comment by Anonymous — July 19, 2011 @ 8:19 pm |
In other words, we can start with any point and ‘just’ need to choose a second point through which will we draw a line.
Comment by Nemanja — July 19, 2011 @ 8:28 pm |
Perhaps even the line does not matter! Is it possible to prove that any point and any line will do?
Comment by Anonymous — July 19, 2011 @ 8:31 pm |
No, if you start with two points on the convex hull (ordered in the right way) you stay on the convex hull.
Comment by Thomas H — July 19, 2011 @ 8:35 pm |
It is not possible, two consecutive points on convex hull will not do.
Comment by Nemanja — July 19, 2011 @ 8:37 pm |
Sure a choice of line is important. Imagine S is a cet of vertices of a convex polygone P (triangle, say) plus one point inside P.
Comment by Zhecka — July 19, 2011 @ 8:42 pm |
Only the starting point matters. By the problem statement, it appears that the initial angle is irrelevant to the existence of a pivot point P* from which all of S is traversed. Every point in S is a pivot point, but only with a specific range of starting angle (e.g. those consistent with the cycle generating S). The union of these intervals must necessarily be [0,2π), and thus we can assume WLOG that the starting angle is 0 (and thus we single out a specific point — or points in the case of |S| = 2).
Comment by Anonymous — July 19, 2011 @ 8:50 pm |
In fact all points must be achievable within a single full rotation of the line, from a starting P*. Thus the different ways of traversing a subset of S correspond not only to different starting points/angles, but also to different segmentations of [0,2π).
Comment by CLH — July 19, 2011 @ 8:57 pm |
Sure. I meant a choice of line is important if you fix a starting point. It was exactly the reply to the parental comment saying that probably we can start with any conficuration “starting point + starting line”.
Comment by Zhecka — July 19, 2011 @ 8:59 pm |
I don’t really see this. Could you give this a bit more justification? It seems to me that if only the point matters, we are reduced to only n-1 distinct cases (n being the size of the set S). But we have a lot more cases than this.
Comment by Seungly Oh — July 19, 2011 @ 9:06 pm |
It might be fun to use projective duality: the space of unoriented lines in the plane is diffeomorphic to the projective plane minus a point, i.e. the open Möbius strip, which I’ll call M. Every point p of S corresponds to a line m_p in M, and every line l passing through p in the plane corresponds to a point n_l on m_p in M. So the projective dual windmill process tracks the position of a point on the arrangement of lines in M dual to the points of S. The process begins with n_l on a line m_p and I suppose the clockwise direction tells us which direction we progress along m_p. I think the goal is then to show that there exists a starting point on the arrangement such that the trace of the projective dual windmill “curve” will hit every single line in this arrangement…?
Comment by jc — July 19, 2011 @ 8:23 pm |
In this comment, I’ll give a few more details on the geometry I have in mind.
I think a pretty picture for M can be taken by starting with the picture of RP^2 as a sphere with antipodal points identified and then removing the North pole (see e.g. http://en.wikipedia.org/wiki/Duality_%28projective_geometry%29#Mapping_the_sphere_onto_the_plane ). The mapping between a pair of antipodal points on this sphere and lines in the plane is as follows: first place the sphere so that it lies tangent to the plane, e.g. let the plane be the z=0 plane in 3D and let the sphere be a unit sphere centered at (0,0,1). Now a point in RP^2 is a pair of antipodal points, which defines a line passing through the center of the sphere. There is a unique plane through the center of the sphere which is perpendicular to this line. This plane intersects the z=0 plane in a line (except if the original point in RP^2 was the North pole!). Points in the plane z=0 are mapped to geodesics on the sphere by the reverse of this procedure (a point in the plane defines a unique line through the origin of the sphere, which has a perpendicular plane, which yields a great circle).
Comment by jc — July 19, 2011 @ 10:48 pm |
I think that winding a line clockwise around a point in the z=0 plane is thus mapped to a point traveling in a clockwise direction on a great circle on the sphere (as viewed from above). This is well defined because none of the great circles pass through the North pole.
So the set S in the z=0 plane is mapped to an arrangement of great circles on the sphere, and the clockwise rule yields an orientation on each great circle in this arrangement. We just need an argument now to find a directed cycle on this arrangement.
Comment by jc — July 19, 2011 @ 10:51 pm |
It seems that a good place to start is with the set, A, of ordered pairs of points, with each ordered pair representing a “transition” from one pivot point to the next. Each member of A would be a vertex in a directed graph containing an edge from each “transition” to its successor “transition”.
One would then need to show that a cycle exists in this graph for which every point participates in at least one (actually two) of the vertices.
Comment by Justin W Smith — July 19, 2011 @ 8:26 pm |
The question here is how to translate the inherent geometrical properties that are required to prove the statement into properties of the graph. (Since obviously it isn’t true for all graphs)
Comment by Joe — July 19, 2011 @ 8:30 pm |
There must be n/2 distinct cycles since the number of points to the left or right of the line remains constant throughout the process. (Correct me if I’m wrong.)
Comment by Justin W Smith — July 19, 2011 @ 8:50 pm |
Ok. I think the solution might involve this observation, with the observation that every point participates in a “splitting” lines (one with n/2 points on one side).
Comment by Justin W Smith — July 19, 2011 @ 8:55 pm |
This seems to be incorrect. Consider A=(0,2), B=(3,2), C=(3,0), D=(0,0), E=(2,1). Start with ED pivoting around D; this divides the other points into two (A,B) and one (C). The next line is DC, which leaves A,B,E all on one side.
Comment by Austin — July 19, 2011 @ 9:13 pm |
If you start with DE turning around D and the next line is DC it means that you start with “DE+\epsilon”, that is you should also count the point (E) at the side of (A,B). In the seim vein, turning CD around Cyou should count (D) on the one side and (A,B,E) on the other. So the number of points persists the same.
Comment by Zhecka — July 19, 2011 @ 9:29 pm |
I’m not sure but as no three points are collinear, one can always find a line which splits the points into two sets whose number of elements differ at most one?
Comment by Anonymous — July 19, 2011 @ 8:27 pm |
That is surely true. How could this help us?
Comment by Thomas H — July 19, 2011 @ 8:28 pm |
Something like one can find this no matter how we choose the first point. Then in some time the windmill must be parallel to the line through these points. This line must be unique or else it splits the points such that number of elements differ at least two.
Comment by Anonymous — July 19, 2011 @ 8:41 pm |
It appears that the number of points to the “left” or “right” of the line is constant through the entire process!
Comment by Justin W Smith — July 19, 2011 @ 8:47 pm |
I think this solves the problem. Start with a line which separates the points into two parts of roughly same size (their cardinal differ by at most one, not counting the point to which the line is attached). Then run the process until the line is “upside-down”, and so has turn by exactly $\pi$. Every point has gone from the right of the line to the left of the line (easy to see is the number of point is odd, you have to be a bit more crafty if it is even), and no point can go from left to right or right to left without touching the line. Add the previous remarks (the process will always come back to its initial configuration), and every point will be visited infinitely often.
Comment by Garf — July 19, 2011 @ 9:14 pm |
Very nice! Don’t we run into problems with a convex hull though? Take a square with a point in the middle (M) and pass the diagonal of the square (not through M) – it seems to me M is never visited (though I may be wrong here). I think we should be more specific in our initial choice of line, maybe?
Comment by Gal — July 19, 2011 @ 9:23 pm |
No. This example is false :)
Comment by Gal — July 19, 2011 @ 9:28 pm |
Yes, it seems to be a correct solution!
Comment by Zhecka — July 19, 2011 @ 9:35 pm |
This seems to be right, but there something I don’t understand. Please see if you can help me with it:
Start with a square and a point inside it (M): start with a tangent to the square (your solution demands a more equal division of points, I know). When we get to the opposite vertex of the square all points moved from one side of the line to the other, but not all points have been visited (M will never be visited). The argument is almost exactly the same, so it seems that the equal division of points plays a crucial role, but I don’t understand what role exactly. Can we pin it down precisely?
Comment by Gal — July 19, 2011 @ 9:42 pm |
I f I understand well your example : the problem is that you must give an orientation to the line. Then, left and right are define with respect to this orientation : if the line has made half a turn, then left and right are reversed. In your example, I think most of the point move from, say, the part et the top of the line to the part at the bottom of the line, but always stay at the right of the line.
Comment by Garf — July 19, 2011 @ 9:47 pm |
Got it! Kind of like a turn number in topology. Thanks! :)
Comment by Gal — July 19, 2011 @ 9:50 pm |
My bachelor thesis supervisor said that one can’t use the word cardinal if we talk about finite sets. One has to use the words “number of elements”.
Comment by Anonymous — July 19, 2011 @ 9:46 pm |
I’m trying to understand why the initial line must split the points into two (almost)-equal sets.
I guess it’s so that when it rotates 180 degrees, the line is guaranteed to be back in the same place again, i.e. dividing it into the same two equal sets, so each point must have switched from right to left… so the line must have visited each point.
If instead you start the line tangent to the convex hull, with all non-pivot points to its right, then when it rotates 180 degrees it will STILL have all non-pivot points to its “right”. Yes?
Comment by Jerzy — July 19, 2011 @ 9:49 pm |
That’s it.
Comment by Garf — July 19, 2011 @ 9:50 pm |
Cool. One more thing I’m trying to understand:
If there are an even number of non-pivots, there is exactly one vertical line that passes through a pivot that divides the remaining points in half. So when the line rotates 180 degrees, it’ll have to pass through that point again.
But if there are an odd number of non-pivots, then there are two choices of pivot point for the vertical line separating the non-pivots into almost-halves. Does it matter which one you use? Do you need to specify anything like “the side with one extra point is the side that will get hit next”? Or does that not matter?
In other words, when there are an odd number of non-pivots, and then the line hits a 2nd point so it’s on two points at once, you could either have equal points on either side, or you could have k on one side and (k-2) on the other side. Does this cause a problem that requires an appropriate choice of initial pivot and rotation-direction?
Comment by Jerzy — July 19, 2011 @ 10:06 pm |
And that is the difference between the odd and even cases. Anyway, the choice of the starting point (between the two possible choices, say, A and B) does not matter : if you start from A, then after half a turn you will be on point B, so the two choices of starting point (with the given starting orientation) belong to the same orbit.
Comment by Garf — July 19, 2011 @ 10:28 pm |
We could perhaps consider “layers” of convex hulls (polygons) .. like peeling off an onion. If our line doesn’t start at the “core” (innermost) polygon then I feel it’ll get stuck in the upper layers and never reach the core.
Comment by Varun — July 19, 2011 @ 8:27 pm |
I think that is a good start, thanks Varun!
Comment by A — July 19, 2011 @ 8:46 pm |
This was suggested by Haggai Nuchi (comment 4). But it’s hard to keep track of the process since it keeps switching between multiple layers in a seemingly arbitrary fashion (in fact, we are looking for a windmill that does exactly this).
Comment by Srivatsan Narayanan — July 19, 2011 @ 8:48 pm |
[…] Minipolymath3 project: 2011 IMO […]
Pingback by International Mathematical Olympiad IMO2011 Amsterdam | problemas | teoremas — July 19, 2011 @ 8:29 pm |
The windmill process defines a function f from the set of all pairs of points to itself, with the condition that f(ab)=bc for some c.
Is it true that for any such function we can find a permutation a_1,a_2,…a_n such that f(a_i,a_{i+1}) = a_{i+1} a_{i+2} ?
Comment by Anonymous — July 19, 2011 @ 8:39 pm |
No, e.g.: f(ab)=ba and f(ba) = ab. The geometric properties of f seem crucial.
Comment by Srivatsan Narayanan — July 19, 2011 @ 8:51 pm |
But even if f(ab)=ba and f(ba)=ab, there may be some other cycle that works. For example, if n=3, we might have f(ac)=cb, f(cb)=bc, f(bc)=ca, f(ca)=ac. So your counterexample isn’t actually a counterexample (yet).
Comment by Austin — July 19, 2011 @ 8:55 pm |
The counterexample is f(a b) = (b a) for all pairs (a,b).
Comment by Thomas H — July 19, 2011 @ 8:58 pm |
On the other hand, if n=3, then we could have cycles aba, bcb, cac, which would form a counterexample. This is definitely “ungeometric,” since the cycles are too short (ac and ca are actually the same line). But if n=5, then we could have cycles abcda, acea, bedb — another counterexample, and this one survives the preceding objection. So I’m ready to agree that geometry matters.
Comment by Austin — July 19, 2011 @ 9:03 pm |
No. For instance, consider the f that simply swaps the points in the pair you hand it: f(ab) = ba, f(ba) = ab, for all choices of a,b.
Comment by g — July 19, 2011 @ 8:53 pm |
We don’t need it to be a permutation, just a sequence which contains each point at least once (possibly with repetition).
Comment by Austin — July 19, 2011 @ 8:53 pm |
Since the points are in general position, you could define “the wheel of p”, w(p) to be radial sequence of all the other points p’!=p around p. Then, every transition from a point p to q will “set the windmill in a particular spot” in q. This device tries to clarify that the new point in a windmill sequence depends (only) on the two previous points of the sequence.
Comment by Anonymous — July 19, 2011 @ 8:41 pm |
Yes. Geometry constrains the possible lists of w(P_1), w(P_2), etc., but I wonder if the geometry actually matters.
Suppose we associate to each p an *arbitrary* radial sequence consisting of all p’ != p. Does the conclusion of the problem still hold, or are there counterexamples?
Comment by Austin — July 19, 2011 @ 8:48 pm |
Never mind, this is what comment #17 is suggesting.
Comment by Austin — July 19, 2011 @ 8:51 pm |
A question: Does the windmill process eventually form a cycle?
Comment by Seungly Oh — July 19, 2011 @ 8:48 pm |
Yes, see comment #2 and replies.
Comment by Austin — July 19, 2011 @ 8:49 pm |
I think so: the function f from comment #17 is a permutation on the pairs of points.
Comment by Thomas H — July 19, 2011 @ 8:50 pm |
I guess it should, since there are infinite many iterations and only finite options.
Comment by Seungly Oh — July 19, 2011 @ 8:50 pm |
By the way, if we get as S the four following points: vertices of an equilateral triangle T and its center, what will be a cooresponding windmill that passes each point infinitely often? It seems that after wa fall on one of the vertices of T we will never return to its center.
Comment by Zhecka — July 19, 2011 @ 8:49 pm |
I’ve just found the answer in brunch 3.
Comment by Zhecka — July 19, 2011 @ 8:51 pm |
Suppose that all but two points lie on the convex hull of the points. Start with the two points (ab) not on the convex hull. Then, since the function f in #17 is a permutation, f^(k)(ab) = (ab), for some k. Also, it seems “clear” that all points on the convex must have been visited (but how to see that formally?)
Comment by Thomas H — July 19, 2011 @ 8:56 pm |
Pick a smallest angle PQR and take the pair to be Q and PQ.
Comment by Anonymous — July 19, 2011 @ 9:05 pm |
Consider the first time the line rotates past Q but misses it. Let S be the pivot and T be the pivot before S.
Suppose Q’ is the point such that angle STQ’ is less than STQ. Then is it feasible to prove that angle PQ’R must be smaller than PQR, thus deriving a contradiction?
Comment by Anonymous — July 19, 2011 @ 9:21 pm |
Can someone give me *any* other example where the windmill cycles without visiting all the points? The only one I can come up with is: loop over the convex hull of S.
Comment by Srivatsan Narayanan — July 19, 2011 @ 9:08 pm |
Place many equidistant points on a circle, and also take the center. Then, start with the line which uses two points adjacent points on the convex hull, but in the different order than you did previously (i.e., so that it does *not* just loop over the convex hull).
Comment by Thomas H — July 19, 2011 @ 9:11 pm |
Let me check that I got the example correctly: is this “a point inside a regular polygon”? Isn’t it established in an early comment that the example of a point inside an equilateral triangle indeed visits *all* the points? Can you clarify the difference here?
Comment by Srivatsan Narayanan — July 19, 2011 @ 9:19 pm |
I wanted to place many more points on the unit circle — say 100. Also, even with the equilateral triangle and the point inside, it depends on how you start — you may not visit all points.
Comment by Thomas H — July 19, 2011 @ 9:21 pm |
take a regular pentagon (ABCDE) for example. In the “star” formed by connecting all the vertices, place an extra point on the center of the star. and begin your windmill from the line AC (with A as the first pivot). I believe that the lines here stay strictly outside the center of the star.
Comment by Seungly Oh — July 19, 2011 @ 9:19 pm |
Okay, but the *points* this loops around do form the convex hull though (or have I misunderstood?). Can we find an example where we have a cycle, not visiting all points, where the *points that are visited* do not form a convex set?
Comment by Joe — July 19, 2011 @ 9:25 pm |
forgive my lack of rigor in the following statement: I believe that there can injected “harmless” points, where the overall covered area by the rotating line is essentially same (or vary by measure of epsilon). In my experiment, you are able to inject such points in the interior of the pentagon. Thus the points do not form a convex polygon. Does that make any sense? Of course, I may be wrong in this.
Comment by Seungly Oh — July 19, 2011 @ 9:34 pm |
Say you have an equilateral triangle ABC with a smaller equilateral triangle DEF sitting inside ABC. (For simplicity assume DEF has its sides parallel to that of ABC and has the same orientation). Take point G to be somewhere inside DEF. Now Start the line AC with pivot at A (so that the next point it’ll hit is F). You’ll visit all points except G.. so the set of visited points(i.e. A,B,C,D,E,F) does not form a convex polygon.
Comment by Varun — July 19, 2011 @ 9:43 pm |
I am sure I am making a mistake, but my windmill seems to “drift off” to the convex hull in the second step. Can you list a few initial vertices that the windmill is supposed to visit so that I can track the error?
Comment by Srivatsan Narayanan — July 19, 2011 @ 9:26 pm |
okay. in order of the vertices serving as pivot, I have: A, B, E, A, D, E, C, D, B, etc..
Comment by Seungly Oh — July 19, 2011 @ 9:29 pm |
Yes, I am happy with this example. Although it still does use the points only on the convex hull, it definitely at least sweeps inside as well. Thanks!
Comment by Srivatsan Narayanan — July 19, 2011 @ 9:44 pm |
Moreover is there an example where the space which is not “swept” by the lines (as the windmill goes on) is unbounded? (we know that that space contains all the points that are not picked, and for the convex hull example it is just the interior of the polygon)
Comment by Joel — July 19, 2011 @ 9:22 pm |
I do not believe that this is possible. Since the rotation is unstopped and always counterclockwise, the line will inevitably sweep through the unbounded space outside the convex hull of the points when a full rotation has taken place.
Comment by Seungly Oh — July 19, 2011 @ 9:25 pm |
I believe Joel hopes to show that the area *not swept* is always bounded (or get a counterexample).
Comment by Srivatsan Narayanan — July 19, 2011 @ 9:28 pm |
I think it is always bounded and lies inside the convex hull. I believe that is graphically obvious. But how does this help?
Comment by Seungly Oh — July 19, 2011 @ 9:36 pm |
Oh yes, it does seem so. And yes, I am not sure it would help either.
Comment by Srivatsan Narayanan — July 19, 2011 @ 9:40 pm |
Take a large number of points on a circle, plus another point at the center of the circle. Take your initial point on the circle, and second point some distance away (e.g. a quarter of the way around). Now perturb some of the points so that they lie just inside the circle. It seems clear to me that the windmill will miss the center point and yet will hit some of the points not on the convex hull.
Comment by Haggai Nuchi — July 19, 2011 @ 9:28 pm |
@Thomas @Seungly @Haggai Thank you all for your examples. I haven’t understood them fully yet; I’ll think about them for some time and get back if I have questions.
Comment by Srivatsan Narayanan — July 19, 2011 @ 9:39 pm |
I think that there may be a notion of “innermost point” stripping consecutive convex hulls, and it may be possible to stay outside any particular convex hull, which can (it seems to me) be treated as an overgrown point.
Actually there may be a proof there in taking the convex hull and treating the internal structure as a single point and showing you can do that, then growing that point into the second level convex hull with a single point inside.
Or alternatively growing outwards – solving for the internal structure first (which seems possibly cleaner) – though as I post this there are some other neat comments out there for different approaches.
Comment by Mark Bennet — July 19, 2011 @ 9:58 pm |
Let’s say you start with the vertical line which has n/2 points on the right, and n/2 points on the left. You turn it — eventually it will be vertical again. Now n/2 points are on the left and n/2 points on the right, but the left and right have reversed. You have only switched points 1 by 1, so to say — so you must have visited each point at least once?
Comment by Thomas H — July 19, 2011 @ 9:19 pm |
I believe this is a solution (see my comment to #14), although this needs some polishing (I guess there is an odd / even number of point distinction to do).
Comment by Garf — July 19, 2011 @ 9:31 pm |
Right — I’m sorry, I didn’t see your solution there! :)
Comment by Thomas H — July 19, 2011 @ 9:33 pm |
This implies the windmill is unique, correct? For any orientation there is only one line (up to irrelevant translation over a range containing no points) dividing the points in half.
Actually I guess it would imply the windmill is unique for an even number of points and there are two distinct windmills for an odd number of points.
Comment by Andrew L — July 19, 2011 @ 9:37 pm |
I don’t see why a good windmill must have half points in each side.
Comment by Joel — July 19, 2011 @ 9:42 pm |
Ah, so. I’ll shut up now. :-)
Comment by Andrew L — July 19, 2011 @ 9:45 pm |
Maybe it’s possible in *some* cases to get a good windmill with less than half the points on each side, but having half the points on each side will *guarantee* a good windmill?
Comment by Jerzy — July 19, 2011 @ 9:52 pm |
Yes, I think this solves it.
Suppose it doesn’t get a point a. Then a is always at the same side of the line, but it starts in the right and ends in the left, contradiction.
Comment by Joel — July 19, 2011 @ 9:39 pm |
Using the terminology from comment #18, the average angle formed at p by two consecutive points in its “wheel” is pi/(n-1), right? And the windmill can’t cycle until it’s turned through a total angle of pi, at least. Is there a pigeonhole argument?
Comment by Austin — July 19, 2011 @ 9:22 pm |
Building on comment 10, we could try to induct on the number N of points. Suppose we know there is always a conforming windmill of N points; given N+1 points, show that you can choose one point to label the “newcomer” so that a conforming windmill of the remaining N points must extend to a conforming windmill of the N+1 points.
Comment by Andrew L — July 19, 2011 @ 9:22 pm |
I’ve added the solution at comment #14 to the wiki as the first completed solution (although some additional details could do with being filled in there; please feel free to do so!). This solution appeared 74 minutes after the mini-polymath project started, which is a respectable time. Congratulations to all participants, and hope you enjoyed the project. :-)
Of course, there could still be alternate solutions and other loose ends. (For instance, it would be curious to see whether there is a nice proof using the projective duality language from comment #12, or whether the induction strategy can be made to work; there is also the question of whether the cycles are completely classified by the number of points to the left and right of a line.)
Comment by Terence Tao — July 19, 2011 @ 9:50 pm |
It looks like the cycles are indeed classified by the number of points to the left and to the right. Let us take two lines with this same invariant (but not the same orientation, otherwise the problem is trivial). Then, run the windmill from the first line until the orientation is the same that the second line. At this instant the two lines must coincide (otherwise, they would not have the same number of points on each side).
Comment by Garf — July 19, 2011 @ 10:01 pm |
p.s. While your experiences are still fresh, please post any comments, suggestions, or reflections you have on the project at the discussion thread:
http://terrytao.wordpress.com/2011/07/19/mini-polymath3-discussion-thread/
Comment by Terence Tao — July 19, 2011 @ 10:04 pm |
Following Justin Smith’s comments:
For simplicity, suppose there are an odd number of points. For each point, there is at least one line which passes through that point and which splits the complementary set of points in half. Furthermore, given any slope, there exists at most one point through which that line cuts the points in half. (Think of moving the line with a fixed slope through space.)
Now, using Justin’s comment, note that as you sweep a line throw the windmill process then (whenever it is not touching two points) the number of points on each of its two sides are constant.
So, starting at any point, and using a line which cuts the complementary set of points in half, should do the trick. You must pass through all possible slopes, and at the same time must (almost always) cut the set of points in half, and thus must hit all possible points.
Note in particular, this shows that a half sweep of the windmill will actually hit all the points, when the number of points is odd.
When the number is even, a similar statement should hold.
——
Follow-up: Let n be the number of points. Let (p,q) be a partition of n-1. Let m be a slope. Label the half-planes cut out by a line of slope m sides 1 and 2. If you shift the line, keeping the slope constant, keep the same labeling on half-planes.
There either exists exactly one point for which a line with slope m through that point has p points in the half-plane 1 and q points in the half-plane 2, OR there is no such point, but the line does pass through two points at one, and the two half planes partition the remaining points into (p-1,q) or (p,q-1).
So the problem with a point on the convex hull is that there are lines which give the partition (0,n-1), and interior points don’t have this property.
Comment by Pace P. Nielsen — July 19, 2011 @ 10:00 pm |
In particular, note that Justin’s invariant is more than an invariant, it characterizes each of the cycles. In other words, the cycles are in direct correspondence with partitions of n-1. The (0,n-1) partition corresponds to the outer-hull cycle.
Comment by Pace P. Nielsen — July 19, 2011 @ 10:31 pm |
I just realize that I’m way too late because this took me a while to write and the problem has apparently been solved in the mean time, but anyway, Here is a reformulation of the problem:
Let $S=\{s_1 , …, s_n\}$. For each $j\ne k$, let $\alpha_{j,k}\in (-\pi/2,\pi/2]$ be the angle that the line through $s_j$ and $s_k$ makes with some fixed line, say the $x$-axis. The sign of this angle depends on whether the line is going top-left to right-bottom (positive) or top-right to left-bottom (negative).
For each $j$, no two $\alpha_{j,k}$ for two different $k$ are equal due to the hypothesis that no three points are collinear, so $\alpha_{j,k}$ can be put in ascending order, that is, define $b_j: \{ 1, …, n-1 \} \to \{ 1, …, n \} \setminus \{j\}$ such that $\alpha_{j,b_j(1)}<\alpha_{j,b_j(2)} < … < \alpha_{j,b_j(n)}$.
I will call such a family of mappings $b_1,…,b_n$ a windmill plan, because it contains all the information needed to describe the windmill process. This process assigns to an ordered pair of distinct indices $(k,l)$ the new pair $(l,b_l(\tau(b_l^{-1}(k)))$. $\tau:\{1,…,n-1\}\to \{1,…,n-1\}$ is the cyclic shift map which maps $n-1$ to $1$ and any other $j$ to $j+1$. So the reformulated assertion is if there exists a pair $(k,l)$ such that if we repeatedly apply the process to it (obtaining pairs $(k_0,l_0),(k_1,l_1),…,(k_m,l_m)$ until we return at this pair, then $\{k_1,…,k_m\}=\{1,…,n\}$.
The question is what we gained from this reformulation. We could consider the statement for an abstractly given windmill plan, but it's most probably not true, because properties of windmill plans will be needed. So it might be worthwile to characterize those windmill plans which come from actual sets of points. I have no idea if that is an easy task, but if such a characterization was available, the problem would be known to be equivalent to an entirely combinatorial problem.
Comment by Florian — July 19, 2011 @ 10:02 pm |
How could we show that no point is isolated i.e. every point is eventually a pivot?
Comment by Marvin Martel — July 19, 2011 @ 10:13 pm |
[…] mini-polymath3 was today. Here is the research thread. The wiki is here. There is a discussion thread […]
Pingback by Mini-polymath3 « Euclidean Ramsey Theory — July 19, 2011 @ 11:12 pm |
[…] 20-July-2011: Tao choose problem number 2 for the mini-polymath. It was a geometric/combinatoric question about a “windmill” […]
Pingback by International Maths Olympiad 2011 « viXra log — July 20, 2011 @ 7:45 am |
I have an idea, but I’m not sure about it.
Connect all the dots. Now there is a biggest convex polygon such that all the other points are in side of this polygon. Delete this. Ten again there will be a biggest convex polygon. Delete it too. Continue this till one, two or three points are remaining. I feel like any line through these points will do. But couldn’t prove it.
Comment by stsamster — July 20, 2011 @ 3:24 pm |
I think that maybe it would help to think instead of each transition from point to point, e.g. P1 to P2 to P3 to think of transitions between pairs of points, e.g. (P1,P2) to (P2,P3) to (P3,P4) where the first coordinate is the old point and the second coordinate is the new point. Note: (P1,P2) is a different point-pair from (P2,P1) in this definition. In such a case, each transition from one point-pair to the next is unique since the orientation of the line is specified and the line rotates in one direction. One can then compose a graph where the nodes are point-pairs and the edges are transitions. By this construction each node has exactly one outgoing edge. Since transitions always occur and the graph is finite, a cycle will ultimately emerge via the transitions. The question then reduces to whether or not one can have one point-pair that is reached by two different point-pairs. e.g. Can we geometrically have transitions P1 to P2 to P3 and P4 to P2 to P3 while none of the points are colinear?
Comment by Richard G. — July 21, 2011 @ 1:50 pm |
[…] This post marks the official opening of the mini-polymath3 project to solve a problem from the 2011 IMO. I have decided to use Q2, in part to see how the polymath format would cope with a more geometrically themed problem. Problem 2. Let be a finite set of at least two points in the plane. Assume that no three points of are collinear. A windmill is a process that starts with a line going through a single point $ … Read More […]
Pingback by Minipolymath3 project: 2011 IMO (via The polymath blog) « Metroplex Math Circle — July 21, 2011 @ 3:14 pm |
I think solution 14 can be generalized by picking any orientaion for starting line (instead of one that divides points roughly in half). Then we won’t need the fact that a line exists that divides points roughtly in half.
To do this we need to show two things which seem to be easy generalizations of arguments made in 14 :
1. Suppose we pick any starting orientation, and it divides the plane such that nL points are on its left, and nR points are on its right. Then this division of points is maintained through out the windmill process.
2. If a line L through point p divides the plane such that there are nL points on its left, and nR points on the right, then no other line passing through another point and parallel to L can make the same division of points
Comment by aravi — July 22, 2011 @ 5:50 am |
Some of the ideas above are based on repeatedly removing the convex hull of S. I think I’ve found a counterexample:
Let A be the point (0.01, 0.99)
Let B be the point (-0.01, 0.99)
Let C be the origin (0, 0)
Let X0 be the point (0, 1)
Let X1, X2, .., XN be more points on the unit circle below the line AB. N is large
The convex hull is {X0, X1, …, XN}. Once removed, points A, B, C remain
The windmill starting with a nearly horizontal line through B that is about to hit A will go around the circle but will never reach C.
Comment by Takaki — July 23, 2011 @ 10:08 am |
thanks, now I can see that the two conditions I gave are not sufficient. Simplest counterexample is probably 4 points A,B,C,D, with ABC making a triangle and D inside the triangle. Then a starting point A with starting orientation parallel to BC will never reach D.
Looks like we need one more conditon: The starting orientation that divides points into nL and nR should be such that for every other point P, there exists a line through P that can divide the points into nL and nR.
This starting orientation should be nL = nR because of this case:
Consider N points, with N-1 of them uniformly distributed on a circle, and one point C in the middle of the circle.
Then any line through C will divide points into half (i.e nL=nR ).
Comment by aravi — July 28, 2011 @ 4:40 am |
Am I wrong, or would any S that is the set of vertices from any convex polygon provide a sufficient set to satisfy these conditions? Even a set with any 2 points would suffice.
Comment by The Janitor — August 8, 2011 @ 1:06 am |
Is the line l of finite length ?
Comment by Ravi — October 22, 2011 @ 11:24 pm |
Could someone draw a depiction of the problem? I am having problems visualizing it.
Comment by alex — November 15, 2011 @ 7:22 pm |
IMO comment 14 is not a complete solution. It may well be correct, but there is a gap. There is an assumption, perhaps using spatial intuition, that when the line has rotated by pi it will have returned to the original, central pivot. This may be true but it requires a proof. The pivot point changes and can move back and forth to points on both sides as well as the central point. How do we know that, after the rotation by pi, it hasn’t moved so far to the left or right that the central point can’t be the pivot? I have struggled to find a proof, or at least some idea pointing in that direction, but I haven’t managed it.
Comment by David Holland — January 14, 2012 @ 12:14 pm |
Okay, I think I can fill in the gaps. Let us first suppose that we choose the orientation so the line l is vertical and also assume that it only goes through the single point P of S. Suppose we count a points of S on the left and b on the right of the line. WLOG we can suppose as we rotate the line clockwise the first point we come to Q in S is on the right (otherwise switch the orientation by pi). At the moment the line goes through both P and Q there are are still a points of S on the left but b-1 on the right as Q has been removed. Now rotate a small enough angle clockwise about Q so the line now only goes through the one point Q of S. This can be done as S is finite. Now we have again a points of S on the left and b on the right of the line. If we now imagine rotating the plane anticlockwise so that the line through Q is vertical, we see that the number of points on either side of the line is preserved at every stage of a windmill. As has been pointed out, we can choose our original line so that either a=b or |a-b|=1. In the simpler case where a=b, we can see after a rotation through pi we have got a vertical line through some P’ in S with a points of S on either side. Hence P’=P, since we can also achieve the new vertical line by sliding the old one to the left or the right (or not moving it) until we hit P’, but if P’ is not P we would have changed the number of points on both sides by at least one.
Thus in this case we return to point P each rotation by pi, so the windmill goes through P infinitely often. But, as noted earlier, at any other stage of the windmill with the line going through a point Q we have the very same properties, so the windmill goes through every point visited infinitely often. Appealing to geometry, a point of S can only switch sides of the line if the line has at some point gone through it (okay, this might be another gap but it seems reasonable). So in this case all the points of S have been visited after a rotation through pi. Hence the result follows in the case a=b.
In the other case, we can suppose WLOG that b=a+1 (otherwise again switch orientation by pi). So after the rotation through pi we have a vertical line through some P’ in S with b points on the left and a on the right. This is equivalent to sliding our original line to the right until it hits the first point of S. Now do the rotation through pi again and we have a vertical line through some P’’ with a points of S on the left and b on the right — but then P’’ must be P by the sideways sliding argument again. So in this case we return to P after a rotation through 2pi. Applying similar arguments as in the previous case, the windmill visits every point of S infinitely often as required.
Comment by David Holland — January 14, 2012 @ 3:55 pm |
To deal with the second gap in the proof, where it is assumed that every point is visited after a rotation by pi, first consider the case when a=b. If a point is not visited by the windmill, WLOG it is on the left of the line initially (otherwise change orientation by pi). But then at each stage of the windmill, when a new pivot is visited, this point remains on the left as we consider the frame of reference of the line (imagine rotating the plane anticlockwise by an equal amount as the line has rotated clockwise to keep the line vertical). But we know that after the rotation by pi, every point on the left of the line initially is now on the right — again considering the frame of reference of the line. The unvisited point can’t be both on the left and on the right. This contradiction shows that every point of S is visited in this case. Now consider the remaining case, WLOG that b=a+1. After the rotation by pi the vertical line goes through P’, the next point to the right of P in S. All a points on the left of the line initially are on the right of the line after the rotation by pi, so by the same argument as before they must all have been visited by the windmill in between. All points but P’ on the right initially end up on the left so they also must have been visited. But P and P’ were also visited, so it is still true that the windmill visits every point of S after a rotation by pi.
Comment by David Holland — January 16, 2012 @ 10:16 am |
Just encountered this site, and this problem, it’s wonderfully distracting.
Anyway, It occurs to me that there are two ways to alter the original problem that may be interesting. In the descriptions that follow, “left” and “right” are relative to looking at the line perpendicularly.
First way: points are allowed to be collinear. When the line turns to meet additional points, the new pivot is now the nth from the left if the original was the nth from the right. Any points outside the (new,old) pivot pair are counted as used, while points between the (new,old) pair are not. The new pivot and old pivot need not be distinct.
Second way: a ray is used. When a point intersects with the ray, that point becomes the new pivot. At a pivot change, the ray reverses direction (so if it was infinite to the left, it’s now infinite to the right – and vice-versa).
I believe the original proof still works for the first modification, but it easily fails for the second. However, during my brief thoughts, I have so far failed to think of an example where the second can’t also be solved.
Comment by twio — February 14, 2012 @ 1:24 pm |
sorry for my English,I have just a remark on this problem,I just tried to see this problem in dimension three (in the space), so I remarked that all points on a sphere verify the condition :each three point are not collinear,it means that there is a plane passing through each set of three points.Now if we consider starting point P and a plane witch contain it .then we can do the same procedure and try to meet all remaining points.the problem is to define the movement of our plane such that:
in the second step is to consider the stereographic projection and see the behaviour of the movement of our line(it will be a line after projection and try to conclude).
Comment by mkhida — March 28, 2012 @ 2:09 pm |
Lemma 1:
Let set A have this property
Let T be a triangle whose vertexes are in A, and has the remaining points in A in its interior.
Assume T exists for any A (A has no 3 co-linear points, so this should be easy to prove)
Let P be a point outside of T
A union P has this property
Proof of Lemma 1:
Let circle C circumscribe T
Let L be the line that is windmilling through A
Let I be the intersection of C and L
As L turns clockwise, its angle increases, and I moves clockwise
Both the angle and the location of I are continuas.
In order for a cycle to occur in A, L must be at all angles, and intersect C at all points
(Otherwise it would need to jump or move counter-clockwise to reach the original state)
L must intersect P (See Lemma 2)
Let B be the pivot point of L prior to it hitting P.
Let C be the point that L would hit following B, if not for P
The distance between L and C decreases as L pivots around P, until L intersects with C.
L cannot intersect with another point first, or else it would have done so if P were not there as well
The cycle resumes as it would if not for the presence of P, until it has hit all points in A, and repeats.
QED
(I’m not entirely convinced the last two lines of this are necessarily true.)
Lemma 2:
Assume line L intersects circle C at point I.
Assume the angle of L is continuas, increasing, and will hit all angles.
Assume I will be at all points on C, and is continuas.
Assume point P is outside of C
L intersects P
Proof of Lemma 2:
Let C` go through P, and have the same center as C.
Let I` be the intersection of L and C`
Let Z be the distance between I` and P
If I were to move along C at a constant angle, we can see that Z will decrease until it reaches 0;
If the angle of L were to increase, with a constant I, we can see that Z will decrease until it reaches 0;
As both the angle L, and the posistion of I are continuas, when they both increase, Z will decrease until it reaches 0
Main Proof
Let T(A) represent a triangle whose vertices are in set A, and which surrounds all other points in A.
Select a subset A of S, of size 3, such that T(A) does not surround a member of S.
We can see that A has the described property
Add a point P, that is a member of S, to A, such that T(A) does not surround a member of S which is not in A.
A still has the described property.
Repeat until A=S
QED
Comment by brandon — April 2, 2012 @ 5:21 am |
brandon wrote:
Let set A have this property
Let T be a triangle whose vertexes are in A, and has the remaining points in A in its interior.
Assume T exists for any A (A has no 3 co-linear points, so this should be easy to prove)
A counterexample is easy to find. Let A be the points of a square. There is no T with your desired property.
Also, later, in your proof for Lemma 1, you use C to represent both a circle and a point.
Comment by twio — April 2, 2012 @ 1:20 pm |
Not sure where this blog really is but it seems to me that the solution should make use of convex hulls.
Consider a polygon that surrounds a convex set, in the simplest case a triangle, such that our points sit on the vertices. Now there are two cases. If one starts with a line that does not intersect the interior then it will stay outside under windmilling. It it goes through the interior, it will allways remain so.
Now take any configuration of points and strip it into an onion of such convex hulls. There is always such an onion. Then the line must be chosen such as to intersect the innermost polygon. If it does so, it will remain so. Furthermore, it will pass through all points in S because in its 360 degree turn, it must touch all of them.
Comment by Christian Wieczerkowski — October 17, 2012 @ 3:25 pm |