Given a positive integer n, what is the largest k such that
the numbers 1,2,...,n can be put into k boxes so that
the sum of the numbers in each box is the same?
[When
n = 8, the example {1,2,3,6},{4,8},{5,7} shows that
the largest k is at least 3.]
for n odd, k=(n+1)/2
for n even, k=n/2
Attempted (rather clumsy) proof:
Let's say s is the sum in each box.
The smaller s is, the larger k is, since
(s k) = n (n+1)/2 = sum({ i= 1 to n} i )
The smallest possible sum is n and the next smallest possible sum is n+1, since n must itself be in some box.
For the odd n, s can be n, with n sitting in its own box, and the other boxes must hold ( n-i, i ), and so k = (n+1)/2, a maximum.
For the even n, n will not work as the sum s, because then we are again forced to make boxes of the form ( n-i, i) and this leaves n/2 remaining with no partner. However s = n+1 works with n/2 pairs of the form:
( n+1-i, i ), and k = n/2.
QED
Edited on October 1, 2018, 8:37 am
soln(?)
