Maths Olympiad Prep

Library / /24 of 32

Combinatorics Difficulty 6.2 National Olympiad Prove it Romania

Consider nn positive, not necessarily distinct, integers a1,a2,,ana_1, a_2, \dots, a_n whose sum is 2S2S. A positive integer kk is called a separator if one can choose kk indexes from {1,2,,n}\{1, 2, \dots, n\} such that the sum of the corresponding numbers is SS. What is the maximum possible number of separators?

Solution

If 1 is a separator, then we can not have any other separators than 1 and n1n-1.
For n=1n=1 we can not have any separators.
For n=2n=2, only 1 can be a separator (if the two numbers are equal).
For n=3n=3 only 1 and 2 can be separators (for example, in the case of the numbers 1, 2, 3; 1+2+3=31+2+3=3).
For n=4n=4 we can have at most two separators, 1 and 3, for example in the case of the numbers 1, 2, 3, 6, with 1+2+3=61+2+3=6.
We prove that, for n5n \ge 5, the maximum number of separators is n3n-3, namely in the case when all the numbers 2, 3, ..., n2n-2 are separators.
This maximum is achieved, for example, for the numbers
* 1,1,1,1,2,2,4,4,,2k2,2k21, 1, 1, 1, 2, 2, 4, 4, \dots, 2^{k-2}, 2^{k-2} if n=2kn=2k
Indeed, when n=2kn=2k, we have 2S=2k2S = 2^k, hence S=2k1S = 2^{k-1} which can be written
S=2k2+2k2=2k2+2k3+2k3==2k2+2k3++2+1+1. S = 2^{k-2} + 2^{k-2} = 2^{k-2} + 2^{k-3} + 2^{k-3} = \dots = 2^{k-2} + 2^{k-3} + \dots + 2 + 1 + 1.

Also, when n=2k+1n=2k+1, we have 2S=2k+12S = 2^{k+1}, hence S=2kS = 2^k and we can write
S=2k1+2k1=2k1+2k2+2k2==2k1+2k2++2+1+1. S = 2^{k-1} + 2^{k-1} = 2^{k-1} + 2^{k-2} + 2^{k-2} = \dots = 2^{k-1} + 2^{k-2} + \dots + 2 + 1 + 1.

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.