Problems from Ukrainian Authors

It is easy to place $2012$ points for the condition of the problem being fulfilled: we will place $2011$ points on a straight line, and the last one — outside of it (fig. 24).

Proof. Let's draw all the lines through every pair of points from the set $M$. We will find a line and a point from $M$ such that the distance between them is minimal (excluding any pair where the point lies on the line). Let's denote the corresponding line as $l$ and the point as $A$. We will prove by contradiction that there are only two points from $M$ lying on line $l$. Let's assume that there are at least three points lying on $l$ from the set $M$, and let's denote them as "from left to right" as $B_1$, $B_2$ and $B_3$ (fig. 25). Since $A{B}_1+A{B}_3>B_1{B}_3=B_1{B}_2+B_2{B}_3$, then either $A{B}_1>B_1{B}_2$ or $A{B}_3>B_2{B}_3$. Without loss of generality, we assume that $A{B}_3>B_2{B}_3$. Let us denote by $h_1$ – the height of the triangle $A{B}_2{B}_3$ corresponding to the vertex $A$, $h_2$ – the height of the same triangle corresponding to the vertex $B_2$. Then the area of the triangle $A{B}_2{B}_3$ is given by $S=\frac{1}{2}{h}_1\cdot B_2{B}_3=\frac{1}{2}{h}_2\cdot A{B}_3$, where $h_1>h_2$ when $B_2{B}_3<A{B}_3$. However it implies that the distance between point $B_2$ and line $A{B}_3$ is less than the distance between $A$ and $l$. We obtain a contradiction which finishes the proof of the lemma.

Now we will prove that having $n$ points on the plane implies that either all of them belong to the same line or there exists at least $n$ different lines such that each contains at least two points among $n$ given. This will lead to the answer $2012$ for the question asked in this problem. We will prove this statement by mathematical induction. If $n=3$ then it is obvious. Suppose that the statement of induction is true for some value $n$. Then we will prove the step of induction for $n+1$. Assume that we have arbitrary $n+1$ points on the plane, not all of which lie on the same line. According to the lemma we can choose two points such that the line through them does not contain any other points. Let us delete one of those two points such that all other points are not on the same line. After this operation we have $n$ points that satisfy the conditions of mathematical induction. Therefore for a new set of points we can find at least $n$ different lines such that each contains at least $2$ of given points. Adding the line constructed in the beginning we will get at least $n+1$ different lines for the initial set of $n+1$ points, which finishes the proof of the step of induction.

Answer: $2012$ points.

Fig. 24

Fig. 25