Partition of ${1, 2, ... , n}$ into subsets with equal sums.

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$.