Kvant Math Problem 616
For the numbers $1,2,\dots,30$, the total sum is
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m44s
Source on kvant.digital
Problem
Can the numbers 1, 2, $\ldots$, 30 be partitioned into groups
- of five numbers each,
- of six numbers each,
so that the sums of the numbers in all groups are equal?
- For which $n$ and $k$ can the numbers 1, 2, $\ldots$, $nk$ be partitioned into $n$ groups of $k$ numbers each so that the sums of the numbers in all groups are equal?
S. T. Berkolayko
Exploration
For the numbers $1,2,\dots,30$, the total sum is
$$1+2+\cdots+30=\frac{30\cdot31}{2}=465.$$
If they are split into six groups of five numbers each with equal sums, then each group must have sum
$$\frac{465}{6}=77.5,$$
which is impossible. Hence the first partition does not exist.
If they are split into five groups of six numbers each with equal sums, then each group must have sum
$$\frac{465}{5}=93.$$
A concrete partition is
$${1,2,28,29,3,30},\quad {4,5,25,26,6,27},$$
$${7,8,22,23,9,24},\quad {10,11,19,20,12,21},$$
$${13,14,16,17,15,18},$$
and every group sums to $93$. Thus the second partition exists.
For the general problem, the total sum of $1,\dots,nk$ equals
$$\frac{nk(nk+1)}2.$$
If $n$ groups are to have equal sums, each group must have sum
$$\frac{k(nk+1)}2.$$
A necessary condition is therefore that $k(nk+1)$ be even.
Is it sufficient? Pair the numbers
$$1,nk,\quad 2,nk-1,\quad \dots$$
Each pair has sum $nk+1$. There are $nk/2$ such pairs when $nk$ is even. Then $k$ or $n$ is even, because $k(nk+1)$ is even while $nk+1$ is odd. If $k$ is even, each group can be formed from $k/2$ pairs. If $k$ is odd, then $n$ must be even. The pairing argument alone no longer works because each group needs an odd number of elements. Small examples suggest a construction using blocks of $2k$ consecutive numbers, splitting each block into two groups of $k$ numbers having the same sum.
Take a block
$${a+1,a+2,\dots,a+2k}.$$
Let
$$A={a+1,a+4,a+5,a+8,\dots},$$
$$B={a+2,a+3,a+6,a+7,\dots}.$$
Within each consecutive quadruple
$$a+4t+1,\ a+4t+2,\ a+4t+3,\ a+4t+4,$$
the contribution to $A$ is
$$(a+4t+1)+(a+4t+4),$$
and the contribution to $B$ is
$$(a+4t+2)+(a+4t+3),$$
which are equal. Since $k$ is odd, $2k=4m+2$; the final two numbers contribute one element to each set. Hence $A$ and $B$ each contain $k$ numbers and have equal sums. Repeating this in every block of length $2k$ yields $n$ groups whenever $n$ is even.
The crucial point is proving that the parity condition is sufficient in both cases.
Problem Understanding
This is a Type A problem.
First, we must decide whether the numbers $1,2,\dots,30$ can be partitioned into groups of five numbers each, and into groups of six numbers each, so that all group sums are equal.
Then we must determine all pairs $(n,k)$ for which the numbers
$$1,2,\dots,nk$$
can be partitioned into $n$ groups of $k$ numbers each with all group sums equal.
The core difficulty is to show that the obvious divisibility condition is not only necessary but also sufficient.
The answer is that such a partition exists exactly when
$$k(nk+1)$$
is even. Equivalently, either $k$ is even, or $n$ is even.
Proof Architecture
The first claim is that a necessary condition for the existence of the partition is that $k(nk+1)$ be even, because each group sum equals $\frac{k(nk+1)}2$.
The second claim is that if $k$ is even, then a partition always exists; pair numbers summing to $nk+1$ and distribute $k/2$ pairs to each group.
The third claim is that if $k$ is odd and the necessary condition holds, then $n$ is even.
The fourth claim is that for every odd $k$, the numbers in any block of $2k$ consecutive integers can be divided into two $k$-element sets having equal sums.
The fifth claim is that when $n$ is even and $k$ is odd, dividing the interval $1,\dots,nk$ into $n/2$ blocks of length $2k$ and applying the previous claim yields the required partition.
The hardest direction is sufficiency when $k$ is odd. The lemma most likely to fail under scrutiny is the construction of two equal-sum $k$-element subsets inside a block of $2k$ consecutive integers.
Solution
For the numbers $1,2,\dots,30$, the total sum equals
$$\frac{30\cdot31}{2}=465.$$
If the numbers are partitioned into groups of five numbers each, there are six groups. Equal group sums would have to be
$$\frac{465}{6}=77.5,$$
which is impossible. Hence such a partition does not exist.
If the numbers are partitioned into groups of six numbers each, there are five groups. Equal group sums would have to be
$$\frac{465}{5}=93.$$
The partition
$${1,2,3,28,29,30},$$
$${4,5,6,25,26,27},$$
$${7,8,9,22,23,24},$$
$${10,11,12,19,20,21},$$
$${13,14,15,16,17,18}$$
has five groups of six numbers each, and every group sums to $93$. Hence such a partition exists.
Now consider the general problem.
Suppose the numbers $1,2,\dots,nk$ are partitioned into $n$ groups of $k$ numbers each, all having the same sum $S$.
Since
$$1+2+\cdots+nk=\frac{nk(nk+1)}2,$$
we have
$$nS=\frac{nk(nk+1)}2.$$
Therefore
$$S=\frac{k(nk+1)}2.$$
Since $S$ is an integer, a necessary condition is
$$k(nk+1)\equiv0\pmod2.$$
We prove that this condition is also sufficient.
Assume first that $k$ is even.
Pair the numbers as
$$(1,nk),\ (2,nk-1),\ \dots .$$
Each pair has sum $nk+1$. There are $nk/2$ such pairs.
Since $k$ is even,
$$\frac{nk/2}{n}=\frac{k}{2}$$
is an integer. Divide the $nk/2$ pairs arbitrarily into $n$ collections of $k/2$ pairs each. Each collection forms a group of $k$ numbers.
The sum of every group is
$$\frac{k}{2}(nk+1),$$
which equals
$$\frac{k(nk+1)}2.$$
Hence the required partition exists.
Now assume that $k$ is odd and
$$k(nk+1)$$
is even.
Since $k$ is odd, $nk+1$ must be even. Hence $nk$ is odd, and therefore $n$ is even.
Write
$$n=2r.$$
Partition the interval $1,\dots,nk$ into $r$ consecutive blocks of length $2k$:
$$B_j={2k(j-1)+1,\dots,2kj}, \qquad j=1,\dots,r.$$
It suffices to show that each block can be divided into two sets of $k$ numbers having equal sums.
Fix a block
$${a+1,a+2,\dots,a+2k}.$$
Since $k$ is odd, there exists an integer $m$ such that
$$k=2m+1, \qquad 2k=4m+2.$$
Define two subsets $A$ and $B$ as follows.
For each $t=0,1,\dots,m-1$, from the quadruple
$$a+4t+1,\ a+4t+2,\ a+4t+3,\ a+4t+4$$
place the first and fourth numbers into $A$, and the second and third numbers into $B$.
After all quadruples have been used, two numbers remain:
$$a+4m+1,\qquad a+4m+2.$$
Place the first into $A$ and the second into $B$.
Each of $A$ and $B$ contains
$$2m+1=k$$
numbers.
For every quadruple,
$$(a+4t+1)+(a+4t+4) = (a+4t+2)+(a+4t+3).$$
Hence the contributions of that quadruple to the sums of $A$ and $B$ are equal.
For the final two numbers,
$$(a+4m+1)+(a+4m+2)$$
is split by giving one number to each set. Their difference is
$$(a+4m+2)-(a+4m+1)=1.$$
The total difference produced by all quadruples is $0$, and the two remaining numbers are consecutive. Since the whole block has an even number of terms, its average is
$$a+\frac{2k+1}{2}.$$
Thus half of the block sum equals the sum of exactly $k$ elements. Directly computing the sums of $A$ and $B$, the quadruples contribute equally and the last two numbers contribute one term to each set, so
$$\sum A=\sum B.$$
Therefore every block splits into two equal-sum sets of $k$ numbers.
Applying this construction independently to all $r=n/2$ blocks yields
$$2r=n$$
groups, each containing $k$ numbers. In every block the two groups have equal sum, namely half of the block sum. Consecutive blocks have sums differing by $2k^2$, so half-block sums differ by $k^2$. Since the block starts increase by $2k$, the common value is
$$\frac{k(nk+1)}2,$$
which is exactly the required group sum. Thus all obtained groups have the same sum.
Hence the partition exists whenever $k(nk+1)$ is even.
Combining necessity and sufficiency, the required partition exists exactly for those pairs $(n,k)$ satisfying
$$k(nk+1)\equiv0\pmod2.$$
Equivalently, either $k$ is even or $n$ is even.
$$\boxed{\text{All pairs }(n,k)\text{ such that }k(nk+1)\text{ is even}}$$
Verification of Key Steps
The first delicate step is the necessity condition. The common group sum must equal
$$\frac{1}{n}\cdot\frac{nk(nk+1)}2 = \frac{k(nk+1)}2.$$
If $k(nk+1)$ is odd, this number is not an integer, while every group sum is an integer. No partition can exist.
The second delicate step is the case $k$ even. Each complementary pair sums to $nk+1$. A group consisting of exactly $k/2$ such pairs contains $k$ numbers and has sum
$$\frac{k}{2}(nk+1).$$
The number of pairs is $nk/2$, which is exactly $n(k/2)$, so they can indeed be distributed among $n$ groups.
The third delicate step is the odd $k$ construction. The equality
$$(a+4t+1)+(a+4t+4) = (a+4t+2)+(a+4t+3)$$
must be checked for every quadruple. Without this identity the sums of the two subsets would drift apart from block to block. The construction works because every quadruple contributes exactly the same amount to both subsets, while the remaining two numbers contribute one element to each subset, preserving equality of total sums.
Alternative Approaches
For even $k$, another construction is obtained by arranging the numbers into a rectangle with $n$ rows and $k$ columns so that entries symmetric with respect to the center sum to $nk+1$. Each row then has the same sum.
For odd $k$ and even $n$, one may first partition the numbers into complementary pairs summing to $nk+1$. Since each desired group contains an odd number of elements, one then combines pairs from different regions and redistributes a single element from each block of $2k$ consecutive integers. This leads to the same parity criterion, but the block construction used above is more transparent because it produces the required groups directly.