There are distinct points in the plane. For each pair of these points, construct the midpoint of the segment joining the pair of points. What is the minimum number of distinct midpoints among all possible ways of placing the points?
Solution
Suppose the points are placed on the -axis with coordinates , . Then midpoints are , . Thus there are distinct midpoints.
Next we shall prove that there are at least distinct midpoints. Let be the points and assume that are the pair that are furthest apart. Consider the segments from and to . The midpoints are distinct. For if are two points so that the midpoints of and coincide, then we have two cases. If the four points are not collinear, then they are vertices of a parallelogram with as diagonals and as a side. This is not possible as the longer diagonal is longer than a side. Otherwise are collinear. Then it is easy to verify that if is in the segment , then must be outside making , a contradiction. Also none of these midpoints is the midpoint of . Thus we have at least distinct midpoints.
In conclusion, the minimum number of midpoints is .