Partition of ${1, 2, ... , n}$ into subsets with equal sums. 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.
 A: 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$.
