AoPS - Problem

Source: Romania TST 2015 Day 4 Problem 3

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

ComplexPhi

04.06.2015 20:27

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 .

A model for part (a) is: If $n=2k$,then let $\sigma(2i)=i,\sigma(2i-1)=2k-i+1,i=1,2,...,k$.It's easy to find $k^2+2k$ distinct sums of the requested form,whereas $ \left \lfloor{\frac{(n+1)^2}{4}}\right \rfloor =k^2+k$. If $n=2k+1$,then we just consider $\sigma'$ for which $\sigma'(i)=\sigma(i),i=1,2,..,2k$,and $\sigma'(2k+1)=2k+1$.Now we have the $k^2+2k$ sums from the permutation on $2k$ elements ,plus the sum over all of $\sigma'$'s elements,which is obviously greater than any of the sums on $\sigma$'s elements,so that we get at least $k^2+2k+1=\left \lfloor{\frac{(n+1)^2}{4}}\right \rfloor $ distinct sums,Q.E.D.