I've placed 2018 points in a plane such that it is not possible to draw a straight line that passes through exactly two points.
If a line passes through more than two of the points, then what is the minimum number of points that it passes through?
If 3 points are placed on a plane such that it is not possible to draw a line through exactly two points, then the 3 points must be collinear.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The intuition is easy: if not all points are in line you can get a line 2 this point and another point. Haven't checked the proof yet, but I can imagine it's harder than the intuitive feeling.
Log in to reply
Indeed. The problem is not that hard (and with a small number of points the intuition gets quickly confirmed) but when I saw that Erdös formulated it in 1943 I knew there was something non-trivial about the proof :)
i have solved this problem long back. the best way to approach this problem is to solve it for cases when there are four points.
Beautiful! :D
There's something I don't understand. Imagine you have a finite set of 3 points, (3, 1), (5,4), (0,0) and a line y=3x-7. This theorem states that those 3 points belong in the line. Why?
Log in to reply
The theorem says that for any set of points, you can draw at least one line that goes through exactly two points OR all the points are in the same line.
In the example you gave of three points (3, 1), (5,4), (0,0), the line y = x/3 goes through (0,0) and through (3,1), but not through (5,4). Therefore this is a line with exactly two points, and the theorem is satisfied even though the three points are not on the same line.
I understand the Extremal Principle but not the Sylvester-Gallai theorem. Assuming we have a 4x4-grid with 16 points (just like on the wikipage), why shouldn't I be able to draw a line from top-left to bottom-right and with that connect 4 points instead of 2 or 16? Isn't here missing some information in the problem-description? or should the sylvester-gallai theorem just not be used for a problem like this?
Log in to reply
Because that 4 by 4 grid exists in the plane but is not the entire plane, and there is at least one line on that plane that would connect only two dots on that grid. In that 4x4 example there are multiple lines that connect different pairs. The only way to prevent that is for them all to be colinear.
its because if you look at the diagram it all lines up so they might be trying to give you a clue and if two don't line up then it would have to be all of the points to make it line up
All 2018 points must be in the line. Because even if one point is outside the lone, you get the opportunity of drawing a line through the point from any direction , and then you would have many lines passing through exactly two points, which would be a violation of the required conditon.
All you've done is to show that there can't be an arrangement in which 2017 of the points are collinear and the remaining one is off the line. How do you know that there can't possibly be a position in which (for instance) each line that connects points passes through three or four points?
The question is more delicate than it seems; in some projective planes this may not be true: look up "Fano plane".
They must all be on the same plane so they must be on the same line or only have 2 connected points
Solution Using Extremal Principle*
Consider a line
l
(
b
d
)
and a point
a
such that of all pairs of distances between point and line the pair minimizes the distance between the point and the line;
let
f
be the foot of perpendicular from
a
to the line. Assuming not all but more than 2 points on the line we have now at least 3 points on the line;
two of which are on the same side of
f
;
but now the length of perpendicular from
f
to ad is yet shorter than length of
f
;
Each time we make such an assumption we have a shorter length than the minimum allowed length.
so we now allow the sequence of decreasing lengths to go on without any bounds nut that also cannot happen as a decreasing sequence of positive numbers(NOT INTEGERS) cannot be divergent;
So by the two above observations we conclude that the sequence converges to 0 and indeed each term of the sequence is 0 (by the 1st lemma);
If any of the point is isolated then many lines can be drawn through the isolated point and the others(taken as 2nd point;assuming isolated point to be first) so we can't isolate any point out of the line. Hence the answer is 2018.
Start from smaller number, eg 3( because it's given) here all collinear
Now 4, notice that if you put the fourth point on the line passing from the previous three points then the condition is satisfied. But if you put the fourth point elsewhere then there are three lines passing from 2 points which we don't want, so now we can clearly see what's goin on.....
For any given number of points they must be all collinear for the given requirement
the questions states that the points are all on a plane. A plane is straight, and there are only 2018 points, thus the answer is 2018.
Problem Loading...
Note Loading...
Set Loading...
The Sylvester–Gallai theorem states that, given a finite number of points in the Euclidean plane, either all the points lie on a single line or there is a line which contains exactly two of the points. In our problem, since we restricted the latter case, all 2 0 1 8 points have to be aligned and so the minimum and only value for m is 2 0 1 8 .
Some proofs can be found in the Wikipedia article.