 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Equal values (Posted on 2018-10-01) 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.]

 See The Solution Submitted by Ady TZIDON No Rating Comments: ( Back to comment list | You must be logged in to post comments.) soln(?) | Comment 1 of 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
 Posted by Steven Lord on 2018-10-01 08:34:46 Please log in:

 Search: Search body:
Forums (1)