All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Equal values (Posted on 2018-10-01) Difficulty: 2 of 5
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 2
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:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information