3
$\begingroup$

I have a school assignment to do, but I have no idea, where to start. I hope you can help. Here it is:

We have a finite sequence $A = (a_1, a_2,\ldots, a_n)$, length of $A$ is $n$, elements of $A$ are natural numbers.

Let $S(i,j)$ be partial sum of this sequence from $a_i$ to $a_j$, where $1\leq i\leq j\leq n$.

Formally written as $S(i,j) = a_i+a_{i+1}+\cdots+a_j$.

We can call sequence $A$ "nice", when all partial sums $S(i,j)$ are different from each other.

Formally written - For every $1\leq i\leq j\leq n$ and $1\leq k\leq l\leq n$ it holds that "$S(i,j)=S(k,l)$ implies $i=k$ and $j=l$".

E.g. $(1,3,2)$ is "nice" and $(1,4,2,3)$ is not "nice".

I have following tasks:

Prove that for every natural $n$ a "nice" sequence exists.

The main question:

What is the smallest possible value of the greatest element of a "nice" sequence $A$ of length $n$? Or in other words - for every $n$ find the smallest natural number $p$ for which a "nice" sequence $A$ of length $n$, in which no element is larger than $p$, exists.

Hint: search for upper and lower bounds on $p$ in the form of appropriate functions of $n$.

  • 0
    For the first question, can you find a set of size n such that all subsets have different sums? That is, we are ignoring the order on A but picking arbitrary subsets. This gives you an upper bound for p(n). The order just restricts what subsets you need to consider and may help you reduce p.2010-12-05
  • 1
    For part 1, try to build the sequences. Start with a simple sequence, for instance 2 elements, so that it is nice. Then see what number you can append to this sequence so that the result is still a nice sequence. Then continue the procedure, see what you can append. Try to see if there is a systematic rule.2010-12-05

1 Answers 1