Suppose there are $997$ points given in a plane. If every two points are joined by a line segment with its midpoint coloured in red, show that there are at least $1991$ red points in the plane. Can you find a special case with exactly $1991$ red points?
Problem
Source: APMO 1991
Tags: induction, geometry, parallelogram, analytic geometry, combinatorial geometry, combinatorics unsolved, combinatorics
11.03.2006 09:38
I'm curious as to whether or not this proof works... We will prove by induction that given $n \ge 2$ points in a plane, there are at least $2n-3$ distinct midpoints. Base Case: $n = 2$, we clearly have one midpoint. Induction Step: Call one of the points on the convex hull of the $n+1$ points $P$. Then take the convex hull of the other $n$ points not including $P$. We know $P$ is outside of the convex hull. By our inductive hypothesis, these $n$ points have at least $2n-3$ distinct midpoints. But there must exist two (consecutive) vertices $A$ and $B$ of the convex hull such that the midpoints of $AP$ and $BP$ lie outside of the convex hull and cannot be the same as any of the other midpoints (which clearly have to lie inside the convex hull). Hence there are at least $2n-3+2 = 2(n+1)-3$ distinct midpoints, completing the induction. (For the case that all the points are collinear, just take $A$ and $B$ the closest points to $P$ and we create two new midpoints.) So for $n = 997$, we have at least $2(997)-3 = 1991$ midpoints. And if we take the points $(0,0); (2,0); \ldots; (1992,0)$, we have exactly $1991$ distinct midpoints, namely $(1,0); (2,0); \ldots; (1991,0)$.
12.03.2006 14:56
I have not yet got the complete solution. But I believe this is the first step. Consider a point A1, when it is joined with the rest of the 996 points, no two lines shall intersect. Therefore there shall be 996 red points. And I noticed that 1991=996 +995. So, I am trying on these lines.
12.03.2006 20:27
Let points $A_i$ and $A_j$ be such that segment $A_iA_j$ has the greatest length of all other segments that are connecting some two points. Then construct segments $A_iA_1$, $A_iA_2$ ... $A_iA_n$ and $A_jA_1$, $A_jA_2$ ... $A_jA_n$. Those segments have distinct midpoints, because if any segment $A_iA_x$ have the same midpoint with some $A_jA_y$ then quadriliteral $A_iA_jA_xA_y$ is parallelogram with diagonals $A_iA_x$ and $A_jA_y$ so $A_iA_x>A_iA_j$ or $A_jA_y>A_iA_j$. So we have at least $995\cdot 2 +1=1997$ distinct midpoints ("1" is the midpoint of $A_iA_j$). Other solution: Sort points in the coordinate plane by their $y$ coordinates (points with same $y$ coordinate are sorted by $x$ coordinate). Then take this segments $A_1A_2$, $A_2A_3$... $A_{n-1}A_n$ and $A_1A_3$, $A_3A_5$ and $A_2A_4$, $A_4A_6$... It isn't hard to show that all this segments have distinct midpoints and so on (I am not so sure about this second solution, because I solve this problem in that way a few months ago and I wrote this right from my head, so maybe something is missing, but I don't think so ... ) Special case is when all points are on a line and $A_1A_2=A_2A_3=...=A_{n-1}A_n$ bye
20.02.2017 21:43
My attempt at a solution: As before, plot the points on a coordinate plane. Now, choose the uppermost point, and if not unique the leftmost of these to be $P_1$. Similarly, choose the lowermost, rightmost point to be $P_2$. Consider all the segments with $P_1$ as a vertex. There are $996$. Similarly, there are $996$ with $P_2$, and only one is double counted, i.e. $P_1P_2$. Thus, there are atleast $1991$ unique red points, since all of these midpoints must be unique. (Proof is left as a simple exercise in inequalities..) Hence, we are done. Note: This also proves it for the more general $2n-3$, as stated above. Fun fact: This problem was unknowingly solved while doing the famous "windmill problem"..
30.11.2022 05:22
Impose a Cartesian coordinate system on the set of points such that they have all distinct $y$-coordinates; let these be $y_1, y_2, \cdots, y_{997}$ in increasing order. Furthermore, let $A_i$ be the point with $y$-coordinate $y_i$. Now, consider the midpoints of $\overline{A_iA_{i+1}}$ for $1 \leq i \leq 996$; there are $996$ such midpoints, and by the order none of them have the same $y$-coordinate, and thus they do not coincide. Furthermore, consider the midpoints of $\overline{A_iA_{i+2}}$ for $1 \leq i \leq 995$. These cannot coincide with any of the former midpoints because the $y_i$ are all distinct. This yields $996+995=1991$ distinct midpoints, as desired. For a construction, take all the points to be equally spaced along a line.
08.09.2023 14:44
Let, the points, be $(a_1, b_1), (a_2, b_2),....., (a_{997},b_{997}).$Now, take the midpoints of the points, $(a_i, b_i), (a_{i+1}, b_{i+1}).$ There, are $996,$ of these, and these do not coincide. Now, take the points, $(a_i, b_i), (a_{i+2}, b_{i+2}),$ which holds, $995,$ midpoints. These, again can not coincide, hence, this is $996+995=1991,$ hence, proved.
03.05.2024 19:20
Suppose there are $n>1$ points instead, and let them be $A_1, A_2, \dots, A_n$. Assign each of them an x-coordinate such that $x_i$ corresponds to $A_i$ and WLOG assume that $x_1<x_2<\dots<x_n$. It is very clear that the midpoints of $A_iA_{i+1}$ for $1 \le i < n$ due to ordering. Moreover, consider the midpoint of $A_iA_{i+2}$ ; in order for $A_{i+1}A_{i+3}$ to share the same midpoint, we require $x_i+x_{i+2} = x_{i+1} + x_{i+3}$, a contradiction. Thus, there are at least $(n-1)+(n-2) = 2n-3$ unique such midpoints, with equality when the points are equally spaced on a line. $\square$
08.11.2024 12:16
We prove a stronger result; Given $n$ points in a plan, if every two points are joined by a line segment with its midpoint coloured in red, then there are at-least $2n-3$ red points. Let $A, B$ be two points such that $AB$ has maximum length amongst the set of points. Now, at point $A$, we make $n-1$ red points with other $n-1$ points. Similarly, there are $n-1$ red-points due to point $B$. Now, we have total red points to be at-least: $2(n-1)-1 = 2n-3$ (we subtract $1$ as we over-counted the midpoint of $AB$). Construction: Let the $n$ points be evenly spaced in a straight line. Then, we will have exactly $2n-3$ red-points.