Kvant Math Problem 286

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m42s
Source on kvant.digital

Problem

On a plane, $N$ points are placed. Mark all the midpoints of segments whose endpoints are among these points. What is the minimum number of points on the plane that can be marked?

A. Pechkovsky

Exploration

Let $m(N)$ denote the minimum possible number of distinct marked points.

For $N=2$, there is one segment and one midpoint, so $m(2)=1$.

For $N=3$, if the points are collinear and equally spaced, the three segments have midpoints at the two original points and at the midpoint between them, giving $3$ distinct marked points. Thus $m(3)\le 3$.

For $N=4$, four equally spaced collinear points produce the midpoint positions

$$\frac12,\ 1,\ \frac32,\ 2,\ \frac52,$$

in suitable coordinates, hence $5$ distinct marked points. This suggests the pattern $m(N)=2N-3$.

The lower bound must hold for every configuration. A projection onto a line seems useful. Choose a direction for which all original points have distinct coordinates. If these coordinates are

$$a_1<a_2<\cdots<a_N,$$

then every midpoint corresponds to a sum $a_i+a_j$. Among these sums, the chain

$$a_1+a_2<a_1+a_3<\cdots<a_1+a_N<a_2+a_N<\cdots<a_{N-1}+a_N$$

already gives $2N-3$ distinct values.

The delicate point is relating distinct projected midpoint values to distinct midpoint points in the plane. Since several points may project to the same value, the number of midpoint points is at least the number of distinct projected values, which is exactly the inequality needed.

Problem Understanding

We are given $N$ points in the plane. For every segment whose endpoints are two of the given points, we mark its midpoint. Different segments may have the same midpoint, and such a point is counted only once.

The task is to determine the smallest possible number of distinct marked points.

This is a Type C problem. We must determine the minimum value and exhibit a configuration attaining it.

The expected answer is

$$2N-3.$$

A set of $N$ equally spaced points on a line produces exactly $2N-3$ distinct midpoints. The main difficulty is proving that no configuration can produce fewer.

Proof Architecture

The first lemma states that there exists a linear projection onto a line that assigns distinct real numbers to all given points.

The second lemma states that for distinct real numbers

$$a_1<a_2<\cdots<a_N,$$

the set of sums $a_i+a_j$ with $i<j$ contains at least $2N-3$ distinct values. The proof uses a strictly increasing chain of sums.

The third lemma states that the number of distinct midpoint points in the plane is at least the number of distinct projected midpoint values.

The hardest direction is the lower bound. The lemma most likely to fail under insufficient scrutiny is the second one, because it is where the count $2N-3$ appears.

Solution

Let $M$ be the number of distinct marked points.

We first construct a configuration with $M=2N-3$.

Place the $N$ points at

$$0,1,2,\ldots,N-1$$

on a line. The midpoint of the segment joining $i$ and $j$ is

$$\frac{i+j}{2}.$$

Since $i<j$, the sum $i+j$ can take every integer value from $1$ to $2N-3$. Hence the distinct midpoints are

$$\frac12,\ 1,\ \frac32,\ \ldots,\ \frac{2N-3}{2},$$

whose number is

$$2N-3.$$

Therefore

$$m(N)\le 2N-3.$$

It remains to prove that every configuration satisfies

$$M\ge 2N-3.$$

Choose a line such that no two given points have the same orthogonal projection onto it. Such a line exists because only finitely many directions are parallel to a segment joining two given points.

Let the projected coordinates of the $N$ points be

$$a_1<a_2<\cdots<a_N.$$

Every marked midpoint projects to the midpoint of the corresponding projected endpoints. Thus the set of projected midpoint values is

$$\left{\frac{a_i+a_j}{2}:1\le i<j\le N\right}.$$

Consider the following sums:

$$a_1+a_2,\ a_1+a_3,\ \ldots,\ a_1+a_N,\ a_2+a_N,\ a_3+a_N,\ \ldots,\ a_{N-1}+a_N.$$

Since

$$a_2<a_3<\cdots<a_N,$$

we have

$$a_1+a_2<a_1+a_3<\cdots<a_1+a_N.$$

Since

$$a_2<a_3<\cdots<a_{N-1},$$

we also have

$$a_2+a_N<a_3+a_N<\cdots<a_{N-1}+a_N.$$

Moreover,

$$a_1+a_N<a_2+a_N$$

because $a_1<a_2$.

Combining these inequalities yields the strictly increasing chain

$$a_1+a_2 < a_1+a_3 < \cdots < a_1+a_N < a_2+a_N < \cdots < a_{N-1}+a_N.$$

This chain contains

$$(N-1)+(N-2)=2N-3$$

distinct sums.

Hence the set

$${a_i+a_j: i<j}$$

contains at least $2N-3$ distinct elements. Consequently the set of projected midpoint values contains at least $2N-3$ distinct elements.

Each distinct midpoint point in the plane contributes exactly one projected value. Several midpoint points may share a projected value, but one midpoint point cannot contribute more than one value. Therefore the number $M$ of distinct midpoint points is at least the number of distinct projected midpoint values. Thus

$$M\ge 2N-3.$$

Together with the construction above,

$$m(N)=2N-3.$$

$$\boxed{2N-3}$$

Equality holds for $N$ equally spaced collinear points.

Verification of Key Steps

The count of $2N-3$ distinct sums comes from the chain

$$a_1+a_2<a_1+a_3<\cdots<a_1+a_N<a_2+a_N<\cdots<a_{N-1}+a_N.$$

The transition

$$a_1+a_N<a_2+a_N$$

uses only $a_1<a_2$. Without checking this inequality explicitly, the two increasing subsequences would not automatically combine into one increasing sequence.

The projection argument requires a direction for which all projected coordinates are distinct. If the projection line were chosen perpendicular to a segment joining two original points, two projected coordinates could coincide and the ordered sequence

$$a_1<a_2<\cdots<a_N$$

would not exist. Excluding finitely many forbidden directions guarantees such a projection.

The comparison between midpoint points and projected midpoint values must be made in the correct direction. Distinct points may project to the same value, so the number of projected values can be smaller than the number of points. Thus

$$#(\text{projected values})\le M.$$

Reversing this inequality would invalidate the lower bound.

Alternative Approaches

A more algebraic proof identifies each point with a vector in $\mathbb R^2$. Midpoints correspond to elements of the restricted sumset

$$\left{\frac{x+y}{2}:x,y\in A,\ x\ne y\right}.$$

After projecting onto a generic line, the problem becomes one about sums of distinct real numbers. The lower bound then follows from the classical estimate

$$|A\oplus A|\ge 2|A|-3.$$

Another approach proceeds directly on a line. After projecting the configuration injectively onto a line, one may regard the projected coordinates as an ordered set of real numbers and prove the estimate entirely in one dimension. This is essentially the argument used above, but written as a standalone additive combinatorial statement. The direct chain of sums is shorter and avoids invoking any external theorem.