Consider positive, not necessarily distinct, integers whose sum is . A positive integer is called a separator if one can choose indexes from such that the sum of the corresponding numbers is . 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 .
For we can not have any separators.
For , only 1 can be a separator (if the two numbers are equal).
For only 1 and 2 can be separators (for example, in the case of the numbers 1, 2, 3; ).
For we can have at most two separators, 1 and 3, for example in the case of the numbers 1, 2, 3, 6, with .
We prove that, for , the maximum number of separators is , namely in the case when all the numbers 2, 3, ..., are separators.
This maximum is achieved, for example, for the numbers
* if
Indeed, when , we have , hence which can be written
Also, when , we have , hence and we can write
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.