Maths Olympiad Prep

Library / /66 of 169

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it United States

For a given positive integer kk find, in terms of kk, the minimum value of NN for which there is a set of 2k+12k+1 distinct positive integers that has sum greater than NN but every subset of size kk has sum at most N/2N/2.

Solution

The minimum is N=2k3+3k2+3kN = 2k^3 + 3k^2 + 3k. The set
{k2+1,k2+2,,k2+2k+1} \{k^2+1, k^2+2, \dots, k^2+2k+1\}
has sum 2k3+3k2+3k+1=N+12k^3 + 3k^2 + 3k + 1 = N + 1 which exceeds NN, but the sum of the kk largest elements is only (2k3+3k2+3k)/2=N/2(2k^3 + 3k^2 + 3k)/2 = N/2. Thus this NN is such a value.

Suppose N<2k3+3k2+3kN < 2k^3 + 3k^2 + 3k and there are positive integers a1<a2<<a2k+1a_1 < a_2 < \dots < a_{2k+1} with a1+a2++a2k+1>Na_1 + a_2 + \dots + a_{2k+1} > N and ak+2++a2k+1N/2a_{k+2} + \dots + a_{2k+1} \le N/2. Then
(ak+1+1)+(ak+1+2)++(ak+1+k)ak+2++a2k+1N/2<2k3+3k2+3k2. (a_{k+1} + 1) + (a_{k+1} + 2) + \dots + (a_{k+1} + k) \le a_{k+2} + \dots + a_{2k+1} \le N/2 < \frac{2k^3 + 3k^2 + 3k}{2}.
This rearranges to give 2kak+1Nk2k2k a_{k+1} \le N - k^2 - k and ak+1<k2+k+1a_{k+1} < k^2 + k + 1. Hence ak+1k2+ka_{k+1} \le k^2 + k. Combining these we get
2(k+1)ak+1N+k2+k. 2(k+1)a_{k+1} \le N + k^2 + k.
We also have
(ak+1k)++(ak+11)+ak+1a1++ak+1>N/2 (a_{k+1} - k) + \dots + (a_{k+1} - 1) + a_{k+1} \ge a_1 + \dots + a_{k+1} > N/2
or 2(k+1)ak+1>N+k2+k2(k+1)a_{k+1} > N + k^2 + k. This contradicts the previous inequality, hence no such set exists for N<2k3+3k2+3kN < 2k^3 + 3k^2 + 3k and the stated value is the minimum.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.