MathDB

Distinct sums of permuted numbers !!!

Source: Romania TST 2015 Day 4 Problem 3

June 4, 2015

permutationsPartial sumsProbabilistic MethodcombinatoricsRomanian TST

Problem Statement

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 .

Back to Problems View on AoPS