18
$\begingroup$

The following is one of the old contest problems (22nd All Soviet Union Math Contest, 1988).

Let $m, n, k$ be positive integers such that $m \ge n$ and $1 + 2 + ... + n = mk$. Prove that the numbers $1, 2, ... , n$ can be divided into $k$ groups in such a way that the sum of the numbers in each group equals $m$.

I am trying to prove it but have gotten no idea yet.

For some small $n$'s we can see the validity of the assertion. In addition,

if $k= \frac {n}{2}$, then {$1, n$}, {$2, n-1$}, $\ldots$, {$n$,1} works, and

if $k =\frac {n+1}{2}$, then {$1, n-1$}, {$2, n-2$}, $\ldots$, {$n-1, 1$}, {$n$} works.

This observation doesn't seem to be of help for general solution.

$\endgroup$
  • $\begingroup$ It seems almost answered. $S=1+2+\cdots + n= {n(n+1)\over 2}$. Then either $n\over 2$ is integer or $n+1\over 2$ is integer. $\endgroup$ – nickchalkida Sep 17 '15 at 2:53
  • 2
    $\begingroup$ That really doesn't help, @nickchalkida $\endgroup$ – Thomas Andrews Sep 17 '15 at 2:54
  • $\begingroup$ Some thoughts: define $err = \sum_{t=1}^k |s(t) - m|$ where $s(t)$ is the sum of elements of the $t$-th set. Find a way to move elements from the biggest set to the smallest set or to interchange elements between the two to make $err$ decrease strictly by step so that after finite number of steps it goes to $0$. $\endgroup$ – corindo Sep 17 '15 at 3:04
  • $\begingroup$ Your example with $k=n/2$ generalizes somewhat. Suppose $k \mid n/2$; assign $1,2,\ldots,n$ to groups $1,2,\ldots k, k,k-1,\ldots,2,1,1,2,\ldots, k,k,\ldots,2,1,\ldots$ respectively. This solves $n=2rk$; by preceding the pattern with your $k=(n+1)/2$ solution, you can also solve the case $n=2rk-1$. $\endgroup$ – Tad Sep 17 '15 at 5:00
  • $\begingroup$ Sorry I am confused... I don't understand what a "general solution" would look like other than what you have given? There are only certain values of k and m for which the statement will be true... and you found one of them which seems good enough to answer the question. (as far as i can tell, m and k can be any combination of multiplying the prime factors of $\sum 1...n$, for example for n=11, $\sum 1...n$=66, and (m,k) can be (11,6), (22,3), (33,2), (66,1). $\endgroup$ – don bright Sep 18 '15 at 3:37
1
$\begingroup$

Induction on $n$. For $n=1,2$ there is nothing to prove. Assume the result is proved for $<n$ and consider the case $n$.

We establish the case $n$ by induction on $m$. If $n$ is odd the smallest possible value of $m$ is $m=n$. We have $n=(n-1)+1=(n-2)+2=\dots=\frac{1}{2}(n+1)+\frac{1}{2}(n-1)$, so the result is true for $m=n,k=\frac{1}{2}(n+1)$.

If $n$ is even, then the smallest possible value of $m$ is $n+1$. We have $n+1=(n-1)+2=\dots=(\frac{n}{2}+1)+\frac{n}{2}$, so the result is true for $m=n+1$ and $k=\frac{n}{2}$.

Now consider the case $m$ where $2n>m>n+1$ suppose it is true for $<m$. For $m$ odd we can take the sums $n+(m-n)=(n-1)+(m-n+1)=\dots=\frac{1}{2}(m+1)+\frac{1}{2}(m-1)$. These use up the numbers $m-n,m-n+1,\dots,n$. By induction the remaining numbers $1,2,\dots,m-n-1$ will give us the remaining sums of $m$.

Similarly, if $m$ is even, we can take the sums $n+(m-n)=(n-1)+(m-n+1)=\dots=(\frac{m}{2}+1)+(\frac{m}{2}-1)$. That uses up the numbers $m-n,m-n+1,\dots,n$ except for $\frac{m}{2}$. By induction the numbers $1,2,\dots,m-n-1$ can be divided into groups summing to $\frac{m}{2}$. But the numbers $1,\dots,m-n-1$ and $\frac{m}{2}$ must total a multiple of $m$, so we can divide the groups summing to $\frac{m}{2}$ into pairs which sum to $m$.

Finally consider $m\ge2n$. We can form the $k$ groups $n+(n-2k+1),(n-1)+(n-2k+2),\dots,(n-k+1)+(n-k)$ which each sum to $2n-2k+1$. But by induction we can group the remaining integers $1,2,\dots,n-2k$ into $k$ groups each with sum $m-2n+2k-1$, since $(m-2n)(m-n-1)\ge0$ and hence $m-3n-1+\frac{2n(n+1)}{m}\ge0$, so $m-3n-1+4k\ge0$ and hence $m-2n+2k=1\ge n-2k$.

That completes the induction on $m$ and hence the induction on $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.