Question 96
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}^{\ell} \sigma(i)$, where $1 \le k \le \ell \le n$.
a) Exhibit a permutation $\sigma$ of the first $n$ positive integers such that $|S(\sigma)| \ge \lfloor(n+1)^2/4\rfloor$.
b) Show that $|S(\sigma)| \gt n\sqrt{n}/4\sqrt{2}$ for all permutations $\sigma$ of the first $n$ positive integers.
a) Exhibit a permutation $\sigma$ of the first $n$ positive integers such that $|S(\sigma)| \ge \lfloor(n+1)^2/4\rfloor$.
b) Show that $|S(\sigma)| \gt n\sqrt{n}/4\sqrt{2}$ for all permutations $\sigma$ of the first $n$ positive integers.