Straight outta 2018

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. 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.


The answer is 2018.

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.

7 solutions

Romain Bouchard
Feb 5, 2018

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 2018 2018 points have to be aligned and so the minimum and only value for m m is 2018 2018 .

Some proofs can be found in the Wikipedia article.

Moderator note:

This problem is a great example of an application of the Extremal Principle .

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.

Peter van der Linden - 3 years, 4 months ago

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 :)

Romain Bouchard - 3 years, 4 months ago

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.

Srikanth Tupurani - 3 years, 4 months ago

Beautiful! :D

Markus Pfaff - 3 years, 3 months ago

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?

Santiago Sanz Wuhl - 3 years, 3 months ago

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.

Jon Ducker - 3 years, 3 months ago

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?

Peter Möller - 3 years, 3 months ago

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.

Nate Thönnesen - 3 years, 3 months ago

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

joe vujicic - 3 years, 3 months ago
Swapan Das
Feb 15, 2018

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?

Stewart Gordon - 3 years, 3 months ago

The question is more delicate than it seems; in some projective planes this may not be true: look up "Fano plane".

Stochastic Bertoletti - 3 years, 3 months ago
Sahit Dodda
Feb 12, 2018

They must all be on the same plane so they must be on the same line or only have 2 connected points

Arijit Dey
Feb 17, 2018

Solution Using Extremal Principle* Consider a line l ( b d ) l(bd) and a point a 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 f be the foot of perpendicular from a 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 f ; but now the length of perpendicular from f f to ad is yet shorter than length of f 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);

Divyansh Singhal
Feb 17, 2018

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.

Yash Ghaghada
Feb 16, 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

Gh Dgfhdgf
Feb 15, 2018

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.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...