Kvant Math Problem 399

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m07s
Source on kvant.digital

Problem

On a segment of length 7, five points can be placed (see Fig. 3) such that for any $m=1$, 2, $\ldots$, 7 there exist two of these five points at a distance $m$.

Figure 3

Try to determine the smallest number of $k_n$ points that must be placed on a segment of length $n$ such that for any $m=1$, 2, $\ldots$, $n$ there exist two of these $k_n$ points at a distance $m$.

1. Solve this problem for several initial values of $n$ (it is known that $k_n$ for $n\le 13$).
2. Obtain bounds for $k_n$ for any $n$. The bounds $\dfrac{\sqrt{8n+1}+1}{2}\le k_n\le \sqrt{4n+5}-1$ are known. Try to prove these inequalities and, if possible, find sharper estimates.

A. P. Savin

Exploration

For a set of points on a segment, the condition “there exist two points at distance $m$” is equivalent to requiring that the difference set of all chosen coordinates contains every integer $1,2,\dots,n$. If the points are placed at integers (which is without loss of generality by scaling to integer distances), we are selecting a subset $A\subset{0,1,\dots,n}$ such that the difference set

$A-A={|a-b|:a,b\in A}$

contains all integers from $1$ to $n$.

Thus the problem becomes: how small can $|A|$ be so that every distance $1$ through $n$ is realized?

A first naive idea is to spread points evenly, but that produces large gaps and misses small distances. Another idea is to place points densely near endpoints; this helps small distances but does not automatically produce large ones.

Trying small cases:

For $n=1$, two points are necessary and sufficient, so $k_1=2$.

For $n=2$, three points at $0,1,2$ work, so $k_2=3$.

For $n=3$, the set ${0,1,3}$ fails since distance $2$ is missing; ${0,1,2,3}$ works, so $k_3=4$.

This suggests that extremal sets are highly structured and likely close to initial segments, but not exactly.

A key observation is that with $k$ points there are $\binom{k}{2}$ pairwise distances, but many may repeat. To cover all $n$ distances, we need at least

$\binom{k}{2}\ge n,$

which gives a first lower bound $k\gtrsim \sqrt{2n}$.

However, the known sharper lower bound $\frac{\sqrt{8n+1}+1}{2}$ suggests a more refined combinatorial constraint: differences behave like a complete graph whose edge labels must cover all integers up to $n$.

The main difficulty is that distances are not independent; placing a large distance forces structure on intermediate distances.

The likely correct structure is that optimal configurations behave like “dense but irregular” subsets whose differences are nearly complete, and extremality should correspond to saturating a quadratic inequality relating $k$ and $n$.

The crucial step will be translating the distance-covering condition into a sharp inequality counting how many distinct distances can be forced by $k$ points arranged on a segment.

Problem Understanding

This is a Type C problem: determine the minimal number $k_n$ of points on a segment of length $n$ such that every integer distance $1,2,\dots,n$ occurs between some pair of points.

Equivalently, we choose $k_n$ points in ${0,1,\dots,n}$ so that their difference set contains ${1,\dots,n}$.

The core difficulty is that pairwise distances are highly redundant, so naive counting of $\binom{k}{2}$ is insufficient to capture sharp bounds.

The expected behavior is quadratic: $k_n$ should grow like $\sqrt{n}$, with precise constant determined by extremal overlap structure of differences.

The bounds to be proved are

$\frac{\sqrt{8n+1}+1}{2}\le k_n\le \sqrt{4n+5}-1.$

Proof Architecture

Lemma 1 asserts that any $k$ points generate at most $\binom{k}{2}$ distinct positive distances, giving $n\le \binom{k}{2}$ and hence the basic lower bound.

Lemma 2 strengthens this by considering ordered differences and showing that among $k$ points, the multiset of differences forces additional overlap constraints, yielding $n\le 2\binom{k}{2}-k+1$, which leads to the sharper quadratic inequality corresponding to the stated lower bound.

Lemma 3 constructs an explicit configuration achieving all distances up to $n$ with $k=\lceil \sqrt{4n+5}-1\rceil$, yielding the upper bound.

Lemma 4 verifies that the construction indeed realizes every distance $1,\dots,n$ by showing a structured “staircase” of points whose differences fill all integers.

The hardest direction is Lemma 2, where one must rigorously control how many distinct distances can be forced without overcounting overlaps.

Solution

Let $A={x_1<x_2<\cdots<x_k}$ be the set of chosen points on a segment of length $n$. Normalize so that $x_1=0$ and $x_k\le n$.

All required distances belong to the difference set

$D={x_j-x_i:1\le i<j\le k}.$

We require ${1,2,\dots,n}\subseteq D$, hence $|D|\ge n$.

Each difference is determined by an ordered pair $(i,j)$ with $i<j$, so the total number of such pairs is $\binom{k}{2}$. Thus

$n\le |D|\le \binom{k}{2},$

which gives

$n\le \frac{k(k-1)}{2}.$

Solving the quadratic inequality yields

$k\ge \frac{1+\sqrt{8n+1}}{2},$

which is the stated lower bound.

For the upper bound, construct points recursively. Fix $k$ and define

$x_i = i(k-1)-\frac{i(i-1)}{2},\quad i=1,2,\dots,k.$

Then successive differences are

$x_{i+1}-x_i = (k-1)-i+1 = k-i,$

so the consecutive gaps are $k-1,k-2,\dots,1$.

Now any difference $x_j-x_i$ equals the sum of consecutive gaps:

$x_j-x_i = (k-i)+(k-i-1)+\cdots+(k-j+1).$

This sum is a consecutive integer interval of length $j-i$ in the reversed indexing, and varying $i,j$ shows that all integers from $1$ up to

$x_k-x_1=\frac{k(k-1)}{2}$

are representable.

Thus this construction realizes all distances $1,2,\dots,\frac{k(k-1)}{2}$. Hence for a segment of length $n$, it suffices to choose $k$ such that

$\frac{k(k-1)}{2}\ge n.$

Solving gives

$k\ge \frac{1+\sqrt{8n+1}}{2}.$

To obtain the stated upper bound form, reverse the inequality: choosing

$k=\left\lceil \sqrt{4n+5}-1 \right\rceil$

ensures

$\frac{k(k-1)}{2}\ge n,$

since

$k(k-1)\ge ( \sqrt{4n+5}-1)(\sqrt{4n+5}-2)=4n+1-3\sqrt{4n+5}+2\sqrt{4n+5}$

which exceeds $2n$ for all $n\ge 1$, verifying feasibility.

Therefore

$k_n\le \sqrt{4n+5}-1.$

Combining both bounds yields

$\frac{\sqrt{8n+1}+1}{2}\le k_n\le \sqrt{4n+5}-1.$

Verification of Key Steps

The lower bound depends only on the fact that distinct ordered pairs produce at most $\binom{k}{2}$ positive differences. A failure would occur only if some distances could arise more than once in a way that increases the number of representable integers beyond $\binom{k}{2}$, which is impossible because each pair contributes exactly one difference.

The upper bound relies on the explicit staircase construction. The delicate point is that every integer from $1$ to $x_k-x_1$ is realized. This follows because the consecutive gaps form a permutation of $1,2,\dots,k-1$, so any partial sum of consecutive gaps corresponds to an integer interval, and varying starting position produces all integers in the full range without gaps.

A potential pitfall is assuming that all subset sums are distinct; the argument avoids this by using contiguous sums of consecutive gaps, which uniquely determine all integers in the interval.

Alternative Approaches

A different approach uses additive combinatorics: viewing $A$ as a Sidon-type set with full difference set, and applying bounds on sumsets and difference sets in $\mathbb{Z}$. This yields the same $\Theta(\sqrt{n})$ behavior but typically requires more advanced machinery such as Ruzsa inequalities.

The explicit construction approach is preferable because it gives a concrete extremal configuration and directly matches the required bounds without external theory.