max number of elements in a sequence where each $p$ consecutive subsequence sum is negative and $q$ consecutive subsequence sums is positive

85 Views Asked by At

This problem is from Engel's Problem-solving Strategies in the chapter on "Enumerative Combinatorics". $p$ here represents $p$ elements that always form a negative sum, and $q$ elements that will always form a positive sum. a $p$-sum, or $q$-sum is a subsequence of our original sequence $a_n$ such that the $p$-sum is a consecucitve subsequence e.g $a_2+a_2+\cdots + a_{p+1}$. We are also told that when $\gcd(p,q)=1$ then then such a sequence has at most $p+q-2$ elements. Below is the proof to the case for $\gcd(p,q)=d$ but I am having a hard time understanding the explanation. I hope that someone can help to clarify this proof.

enter image description here

Here is figure 5.2

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

The claim is equivalent to saying that it is impossible to have $p+q-d$ terms.

Let's first do this for $d=1$; assume for contradiction that we have $p+q-1$ terms. We know that $$A=(a_1+a_2+\cdots+a_p)+(a_2+a_3+\cdots+a_{p+1})+\cdots+(a_q+a_{q+1}+\cdots+a_{p+q-1})<0,$$ since each parenthesised group contains $p$ consecutive terms. Likewise we know that $$B=(a_1+a_2+\cdots+a_q)+(a_2+a_3+\cdots+a_{q+1})+\cdots+(a_p+a_{p+1}+\cdots+a_{p+q-1})>0,$$ since each group contains $q$ consecutive terms. However, for each $i$ you can check that $a_i$ features an equal number of times in each sum, so $A=B$, a contradiction. Here the groups in the first sum correspond to rows of the matrix $$\pmatrix{a_1&a_2&\cdots&a_p\\a_2&a_3&\cdots&a_{p+1}\\\vdots&\vdots&&\vdots\\a_q&a_{q+1}&\cdots&a_{p+q-1}}$$ and the groups of the second sum correspond to columns, which is why the two totals must be equal (note that in the scanned proof there is a typo of $s_2$ in the second place of the second row, which should be $s_3$).

Now what the proof is saying is that if $d>1$ you first define a new sequence $s_1,s_2,\ldots$ by $s_1=a_1+\cdots+a_d$, $s_2=a_{d+1}+\cdots+a_{2d}$, and so on. Since $p=rd$ and $q=td$, a sum of $r$ consecutive terms of $s_i$ corresponds to a sum of $p$ consecutive terms of $a_i$, etc, so $s_i$ has the property that any $r$ consecutive terms have negative sum and any $t$ have positive sum. Thus, using the proof above with $a_i$ replaced by $s_i$, $p$ replaced by $r$ and $q$ by $t$, we find that $s_i$ cannot have $r+t-1$ terms. Consequently $a_i$ cannot have had $d(r+t-1)=p+q-d$ terms.