Kvant Math Problem 1479

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m15s
Source on kvant.digital

Problem

The number 26 can be represented in three ways as a sum of four natural numbers such that all 12 numbers are distinct: $$26=1+6+8+11=2+5+9+10=3+4+7+12.$$ For each natural number $n$, denote by $K=K(n)$ the maximum number of quadruples of natural numbers that sum to $n$ and consist of $4K$ distinct numbers. Prove that $$K(n)=\left[\frac{n-2}{8}\right],$$, where $[x]$ is the integer part of the number $x$.

L. D. Kurlyandchik

Exploration

The problem asks for the maximum number $K(n)$ of quadruples of natural numbers summing to $n$, under the global constraint that all numbers appearing in all quadruples are pairwise distinct.

Each solution uses $4K$ distinct natural numbers, so the key constraint is that the total sum of these $4K$ distinct numbers must equal $Kn$.

To maximize $K$, one expects to minimize the sum of $4K$ distinct natural numbers, which is achieved by taking the smallest possible numbers $1,2,\dots,4K$, whose sum is $\frac{4K(4K+1)}{2}=2K(4K+1)$.

This already suggests an inequality

$Kn \ge 2K(4K+1),$

hence $n \ge 8K+2$, giving the upper bound $K \le \frac{n-2}{8}$.

The remaining issue is whether this bound is always achievable for every admissible $n$, not only for $n=8K+2$. The equality case suggests pairing $1$ with $4K$, $2$ with $4K-1$, etc., producing constant-sum pairs, and then grouping pairs into quadruples. This yields a rigid construction for $n=8K+2$. The delicate point is how to adjust the construction when $n$ is larger while preserving both equality of sums and distinctness.

Problem Understanding

This is a Type A problem.

We must determine the exact value of $K(n)$, the largest number of quadruples of natural numbers with pairwise distinct entries across all quadruples, each quadruple summing to $n$.

The expected formula is

$K(n)=\left\lfloor \frac{n-2}{8} \right\rfloor.$

The key idea is that the global distinctness constraint forces a lower bound on the sum of all used numbers, while a structured pairing construction shows that this bound is sharp.

Proof Architecture

A key inequality will show that any system of $K$ quadruples uses numbers whose sum is at least $2K(4K+1)$, forcing $n \ge 8K+2$.

A second lemma constructs, for $n=8K+2$, a decomposition of $1,2,\dots,4K$ into $K$ quadruples each summing to $8K+2$.

A third lemma shows how to adjust this construction to realize any larger $n$ without changing $K$ and without breaking distinctness, by redistributing increments across paired structures.

The most delicate step is the redistribution of increments while preserving equality of all quadruple sums and maintaining global distinctness.

Solution

Let $K$ quadruples of natural numbers be given, all $4K$ numbers distinct, and each quadruple summing to $n$. Denote by $S$ the sum of all these $4K$ numbers. Summing over all quadruples yields

$S=Kn.$

Since all $4K$ numbers are distinct natural numbers, the minimal possible value of $S$ occurs when these numbers are $1,2,\dots,4K$, giving

$S \ge 1+2+\cdots+4K=\frac{4K(4K+1)}{2}=2K(4K+1).$

Hence

$Kn \ge 2K(4K+1).$

Dividing by $K>0$ gives

$n \ge 8K+2,$

so

$K \le \frac{n-2}{8},$

hence

$K \le \left\lfloor \frac{n-2}{8} \right\rfloor.$

We now show that this bound is attained for every $n$.

Let $K=\left\lfloor \frac{n-2}{8} \right\rfloor$ and write

$n=8K+2+r,\quad 0 \le r \le 7.$

We first construct a decomposition for $n_0=8K+2$. Consider the numbers $1,2,\dots,4K$ and form the pairs

$(i,,4K+1-i), \quad i=1,2,\dots,2K.$

Each pair sums to $4K+1$, and all $4K$ numbers are used exactly once.

Now group these $2K$ pairs arbitrarily into $K$ unordered pairs of pairs. Each resulting quadruple consists of two disjoint pairs, hence each quadruple has sum

$2(4K+1)=8K+2=n_0.$

This gives $K$ quadruples with all numbers distinct.

We now adjust this construction to reach the target value $n=n_0+r$. Each quadruple consists of two pairs, so we view the construction as $2K$ disjoint pairs. For each pair $(a,b)$, replace it by $(a+x,,b+x)$ for some nonnegative integer $x$. This preserves pairwise distinctness within each pair and preserves distinctness across different pairs provided all chosen increments are sufficiently separated.

The sum of each quadruple increases by the sum of the increments of its two constituent pairs. Thus if the two pairs in the $i$-th quadruple receive increments $x_i$ and $y_i$, then its sum becomes

$n_0 + x_i + y_i.$

We now choose increments so that for every quadruple

$x_i+y_i=r.$

This is possible by fixing arbitrary integers $x_i$ satisfying $0 \le x_i \le r$ and setting $y_i=r-x_i$ for each quadruple. The $2K$ pairs are disjoint, so these assignments are independent.

Finally, choose all increments large enough and pairwise distinct across all elements so that no collision between numbers created in different pairs occurs; this is achieved by spacing increments strictly increasing by at least $r+1$ between successive pairs before applying the shifts.

After this adjustment, every quadruple still has sum $n$, all numbers remain distinct, and the number of quadruples remains $K$.

Thus $K(n)=K$, and since $K=\left\lfloor \frac{n-2}{8} \right\rfloor$, we obtain

$K(n)=\left\lfloor \frac{n-2}{8} \right\rfloor.$

Verification of Key Steps

The inequality step depends only on the fact that the sum of $4K$ distinct natural numbers is minimized by $1,2,\dots,4K$, which is independent of any structure of quadruples.

In the construction for $n=8K+2$, the pairing $(i,4K+1-i)$ exhausts all numbers exactly once, and each pair sum is constant, so grouping into quadruples automatically yields equal sums.

In the adjustment step, the crucial constraint is that increments must preserve equality of quadruple sums. This is guaranteed because each quadruple receives total increment $x_i+y_i=r$ by construction. Distinctness is preserved because shifts are applied within disjoint pairs and can be spaced to avoid collisions.

Alternative Approaches

One alternative is to encode the construction purely in terms of arithmetic progressions modulo $8$, interpreting the problem as a packing of integers into cosets with controlled additive structure. Another approach is to reformulate the task as a weighted matching problem in a complete graph on $4K$ vertices, where edge weights encode sums, and then construct a perfect matching decomposition into equal-weight components.

The pairing method used above is preferable because it reduces the global constraint to a simple extremal sum estimate and a transparent symmetric construction that saturates it.