Competition problem — Combinatorics

Library / /7 of 31

Combinatorics Difficulty 8.0 Shortlist Prove it Baltic Way

Let $a_1, a_2, \dots, a_{100}$ be a permutation of numbers $1, 2, \dots, 100$ . Denote by $N$ the number of different values of the sums
$\sum_{i=u}^{v} a_i, \quad \text{where} \quad 1 \le u \le v \le 100.$
Is it possible that $N \ge 2500$ ?

Solution

Answer: yes.
For example consider a permutation $1, 100, 2, 99, 3, 98, \ldots$ For odd $i$ we have $a_i + a_{i+1} = 101$ . It is not difficult to check that if $u$ and $v$ have the same parity (and therefore the number of summands is odd) then for all choices of $u$ and $v = u + 2\ell$ all the sums
$\sum_{i=2k-1}^{2k-1+2\ell} a_i = 101\ell + a_{2k-1+2\ell}, \quad \sum_{i=2k}^{2k+2\ell} a_i = 101\ell + a_{2k}$
are different! Therefore the total number of different values is at least $51 \cdot 50 = 2550 > 2500$ .

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 and solution reproduced as published; topic and difficulty added by this site.