Maths Olympiad Prep

Library / NMO Selection Tests for the Junior Balkan Mathematical Olympiad /42 of 62

NMO Selection Tests for the Junior Balkan Mathematical Olympiad

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 n−1n-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 n≥5n \ge 5, the maximum number of separators is n−3n-3, namely in the case when all the numbers 2, 3, ..., n−2n-2 are separators.
This maximum is achieved, for example, for the numbers
* 1,1,1,1,2,2,4,4,…,2k−2,2k−21, 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=2k−1S = 2^{k-1} which can be written
S=2k−2+2k−2=2k−2+2k−3+2k−3=⋯=2k−2+2k−3+⋯+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=2k−1+2k−1=2k−1+2k−2+2k−2=⋯=2k−1+2k−2+⋯+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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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