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

1 Answer 1

First of all, here is a construction of nice sequences of any length $n$.

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

$$S(i, j) = 2^{i-1} + \dots + 2^{j-1} = 2^{i-1}(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-1}(2^{j-i+1}-1) = 2^{k-1}(2^{l-k+1}-1).$$

As $2^{j-i+1} - 1$ and $2^{l-k+1} - 1$ are both odd, $2^{i-1} = 2^{k-1}$, 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.


For the main question, note that if $(a_1, \dots, a_n)$ is a nice sequence, the elements are distinct because $S(i,i) = a_i$. Furthermore, for any $1 \leq k \leq n$, $(a_1, \dots, a_k)$ is also a nice sequence. In particular, if $a_1 = 1$ (which we want because we are looking for the smallest possible value of the maximal element of the sequence), then the sequence is strictly increasing. So, in order to get the smallest possible number for each term in the sequence, we need $a_k$ to be the smallest positive integer that cannot be obtained as the sum of consecutive elements in the sequence $(a_1, \dots, a_{k-1})$. The sequence $(a_k)_{k=1}^{\infty}$ constructed in this way is called MacMahon's Prime Numbers of Measurement which is sequence $A002048$ on the Online Encyclopedia of Integer Sequences (OEIS). The first few terms of this sequence are

$$1, 2, 4, 5, 8, 10, 14, 15, 16, 21, 22, 25, 26, 28, 33, 34, 35, 36, 38, 40, 42, 46, 48, 49, 50, 53, 57,\ \dots$$

As far as I know, there is no explicit description of the terms of this sequence, but we have the crude upper bound $a_k \leq 2^{k-1}$ from the construction above.


Note: The way I obtained the second answer was by determining the smallest possible value of the greatest element of a nice sequence of length $n$ for $n = 1, \dots, 5$. I then entered this sequence into the OEIS which gave over $200$ possibilities, so I determined the value for $n = 6$ which still gave over $100$ possibilities. By including the values for $n = 7$ and $8$, the list was down to two possibilities. The first was the sequence I mentioned above which, from its description, seemed to be the sequence I was looking for. By computing the value for $n = 9$, I ruled out the other sequence and confirmed that the numbers were indeed those of the above sequence. From this point, I tried to figure out how this problem was related to the description of the sequence in the OEIS.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.