Problem

Source: Romania TST 2015 Day 4 Problem 3

Tags: permutations, Partial sums, Probabilistic Method, combinatorics, Romanian TST



Let $n$ be a positive integer . If $\sigma$ is a permutation of the first $n$ positive integers , let $S(\sigma)$ be the set of all distinct sums of the form $\sum_{i=k}^{l} \sigma(i)$ where $1 \leq k \leq l \leq n$ . (a) Exhibit a permutation $\sigma$ of the first $n$ positive integers such that $|S(\sigma)|\geq \left \lfloor{\frac{(n+1)^2}{4}}\right \rfloor $. (b) Show that $|S(\sigma)|>\frac{n\sqrt{n}}{4\sqrt{2}}$ for all permutations $\sigma$ of the first $n$ positive integers .