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

4

Here is a construction of nice sequences of any length $n$.

Let $a_k = 2^k$, and consider $(a_1, \dots, a_n)$. Now let $1 \leq i \leq j \leq n$, then

$$S(i, j) = 2^i + \dots + 2^j = 2^i(1 + \dots + 2^{j-i}) = 2^{i-1}(2^{j-i+1}-1).$$

Now suppose that $1 \leq k \leq l \leq n$, and $S(i, j) = S(k, l)$, then

$$2^i(2^{j-i+1}-1) = 2^k(2^{l-k+1}-1).$$

As $2^{j-i+1} - 1$ and $2^{l-k+1} - 1$ are both odd, $2^i = 2^k$, and therefore $i = k$. It then follows that $2^{j-i+1} - 1 = 2^{l-k+1} - 1 = 2^{l-i+1} - 1$ so $j-i+1=l-i+1$, and therefore $j = l$.

Hence $(a_1, \dots, a_n)$ is a nice sequence.