Problem:
For a given positive integer k find, in terms of k, the minimum value of N for which there is a set of 2k+1 distinct positive integers that has sum greater than N but every subset of size k has sum at most N/2.
Solution:
The minimum is N=2k3+3k2+3k. The set
{k2+1,k2+2,…,k2+2k+1}
has sum 2k3+3k2+3k+1=N+1 which exceeds N, but the sum of the k largest elements is only (2k3+3k2+3k)/2=N/2. Thus this N is such a value.
Suppose N<2k3+3k2+3k and there are positive integers a1​<a2​<⋯<a2k+1​ with a1​+a2​+⋯+a2k+1​>N and ak+2​+⋯+a2k+1​≤N/2. Then
(ak+1​+1)+(ak+1​+2)+⋯+(ak+1​+k)≤ak+2​+⋯+a2k+1​≤N/2<22k3+3k2+3k​
This rearranges to give 2kak+1​≤N−k2−k and ak+1​<k2+k+1. Hence ak+1​≤k2+k. Combining these we get
2(k+1)ak+1​≤N+k2+k
We also have
(ak+1​−k)+⋯+(ak+1​−1)+ak+1​≥a1​+⋯+ak+1​>N/2
or 2(k+1)ak+1​>N+k2+k. This contradicts the previous inequality, hence no such set exists for N<2k3+3k2+3k and the stated value is the minimum.
This problem was proposed by Dick Gibbs.
The problems on this page are the property of the MAA's American Mathematics Competitions