Skip to main content
OlympiadHQ

Browse · MathNet

Print

Baltic Way shortlist

Baltic Way counting and probability

Problem

Let be a permutation of numbers . Denote by the number of different values of the sums Is it possible that ?
Solution
Answer: yes. For example consider a permutation For odd we have . It is not difficult to check that if and have the same parity (and therefore the number of summands is odd) then for all choices of and all the sums are different! Therefore the total number of different values is at least .
Final answer
yes

Techniques

Coloring schemes, extremal argumentsInvariants / monovariants