Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
    
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. –  Ross Millikan Dec 5 '10 at 19:37
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. –  Raskolnikov Dec 5 '10 at 19:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.