Solution for October 2008

Solution. Any sequence that satisfies both
the sum of every 7 consecutive terms is positive, (1)
and
the sum of every 11 consecutive terms is negative (2)
can have at most 16 terms. To prove this, we must first show that any sequence of 17 or more terms cannot satisfy both conditions, and then we must provide an example of a sequence of 16 terms that does satisfy both conditions. (Any such example will automatically furnish examples of suitable sequences of length n with n < 16.) Our correspondents devised three nice approaches to the problem.

Method 1.
If, to the contrary, the two conditions were satisfied by a sequence of 17 terms a₁, a₂, ..., a₁₇, then we could arrange the subsequences of length 7 in the rows of an 11 by 7 array,

By condition (1), the sum of all the entries taken a row at a time must be positive; that same sum taken a column at a time must be negative by (2). This tells us that no sequence having the desired properties can have length 17 or more.

For an example of a suitable sequence having 16 terms, we can let the 10 row sums a_j+1 + a_j+2 +...+ a_j+7be any positive numbers (for j running from 0 to 9); for simplicity, let all ten sums be 1. By subtracting successive pairs of these sums, for example,

we deduce that a_j = a_j+7 for 1 ≤ j ≤ 9. Similarly, we can let the sums
a_j+1 + a_j+2 + ... + a_j+11 be any negative numbers (for j running from 0 to 5); let these sums be –1, say. From these six equations we deduce that a_j = a_j+11. These equalities imply that every subsequence of seven consecutive terms will contain five a₁'s and two a₃'s, while subsequences of eleven consecutive terms will contain eight a₁'s and three a₃'s; therefore,

–5, –5, 13, –5, –5, –5, 13, –5, –5, 13, –5, –5, –5, 13, –5, –5.

Method 2. Bojan Basic's approach.
Basic, Fondanaiche, Lim, and Sengupta all generalized our problem. They found that for any two positive integers m and n, the longest possible sequence of real numbers for which the sum of every m consecutive terms is positive while the sum of every n consecutive terms is negative has, in terms of the greatest common divisor (gcd(m, n)),
m + n – gcd(m, n) – 1 terms. (3)
We shall use Bojan Basic's idea of defining a sequence of partial sums S_j by

S₀ = 0, S₁ = a₁, S₂ = a₁ + a₂, …, S_j = a₁ + a₂, …,+ a_j .

Instead of presenting a general argument, we will illustrate the method by way of three examples.

Example 1. Take m = 3 and n = 5. We show that the longest sequence has 3+5–1–1 = 6 terms in agreement with (3).

To show that no sequence satisfying these conditions can have 7 or more terms, we assume to the contrary that a₁, a₂, …, a₇ is such a sequence. Consider the following chain of inequalities:

This contradiction 0 < 0 proves that any sequence satisfying the two conditions of this example must have fewer than 7 terms. Note that in (4) we took the chain of inequalities as far as possible using the condition S_j < S_j₊₃ (S₆ < S₉ is not valid since S₇ is the longest partial sum), and then we brought the indices back with as many applications of the second condition S_j₊₅ <S_j as possible. The fastest way to bring the indices back to 0 is to use the positive partial sums n = 5 times and the negative partial sums m = 3 times.

How to get an example with six terms? Start the chain to the right of S₇ in (4):

Any assignment of real values to the S_i that satisfies (5) will produce a sequence of six terms that satisfies the initial conditions; for example, S₂ can be any negative real number, and S₅ any number between that and 0. If we set S₂ = –2, S₅ = –1, S₃ = 1, S₆ = 2, S₁ = 3, and S₄ = 4, then use the definitions S₁ = a₁ and a_j₊₁ = S_j₊₁ – S_j, our sequence will be 3, –5, 3, 3, –5, 3. Because this sequence was chosen to satisfy (5), we know that the sum of any three consecutive terms is positive (here that sum is always 1), while any five consecutive terms have a negative sum (here –1).

Example 2. Take m = 4 and n = 6. Since gcd(4, 6) = 2, we expect the longest sequence to have 4+6–2–1 = 7 terms in agreement with (3). We now have

which shows that our sequence cannot have 8 or more terms. (Here we brought the indices back to 0 by using S_j < S_j₊₄ only

times, while S_j₊₆ < S_j we used

times.) To produce a valid sequence of seven terms we use the above chain without S₈, namely S₂ < S₆ < 0 < S₄ , together with the remaining conditions S₃ < S₇ < S₁ < S₅. Because these conditions are necessary and sufficient, S₂ can be assigned any negative value while S₃ is completely arbitrary. Taking S₂ = – 2, S₆ = –1, S₄ = 1, S₃ = 0, S₇ = 1, S₁ = 2, and S₅ = 3, our sequence starts with S₁ = a₁ = 2, and is thus 2, –4, 2, 1, 2, –4, 2.

Example 3. The original problem: Take m = 7 and n = 11. Since gcd(7, 11) = 1, we expect the longest sequence to have 7+11–1–1 = 16 terms in agreement with (3). Because 7 and 11 are relatively prime, any sequence of 17 consecutive terms produces a single chain of inequalities,

For an example with 16 terms we drop S₁₇ from the above chain (start with S₆ and end with S₁₀). So to recover the sequence –5, –5, 13, –5, … we had earlier, we set S₆ = –12 and let each S_j in the chain be 1 greater than the previous partial sum in the chain.

Method 3. Use Matrices.
Several correspondents implicitly used matrices; Billion supplied the explicit matrices. To illustrate the idea we will first work a small example with m = 2 and n = 3; that is, we want a_j + a_j₊₁ to be positive for all j and a_j + a_j₊₁ + a_j₊₂ to be negative. We expect the longest sequence to have 2+3–2 = 3 terms. We summarize this information with the matrix equation

where the b_j's can be assigned any positive values. Let us take b_j = 1 for all j, and solve the equation by computing the inverse matrix, which exists because the above matrix is clearly nonsingular:

We read off the desired sequence in the last column: –2, 3, –2. By observing that the matrix in the preceding equation will take vector

, we see that any assignment of positive values to the b_j's will produce a sequence a_j, a_j₊₁, a_j₊₂ in the order negative, positive, negative. Were there to exist a sequence longer than three terms that satisfied the given conditions, say a₁, a₂, a₃, a₄, …, then we know that a₂ would necessarily be positive as part of the triple a₁, a₂, a₃, but it would necessarily be negative as part of the triple a₂, a₃, a₄. Since the pattern – + – cannot be preserved for all j in a sequence of more than three terms, we see that, indeed, the longest sequence satisfying the given conditions has three terms.

For his solution to the original problem (with m = 7 and n = 11) Billion used the matrix equations MA = B, and A = M^–1B, with

M = array1 ,

M^-1 = array1 ,

A = [a₁, a₂, …, a₁₆]^t, and B = [b₁, b₂, …, b₁₀, –b₁₁, …, –b₁₆]^t. With b_j = 1 for all j, he recovered our sequence

A = [–5, –5, 13, –5, –5, –5, 13, –5, –5, 13, –5, –5, –5, 13, –5, –5]^t.

With b_j = 2 for j ≤ 10 and b_j = 3 for j > 10, he found that

A = [–12, –12, 31, –12, –12, –12, 31, –12, –12, 31, –12, –12, –12, 31, –12, –12]^t

is likewise a suitable sequence. Once again we see that any sequence of more than 16 terms could not satisfy the given conditions: a₃ would necessarily be positive in the subsequence a₁, a₂, a₃, …, a₁₆, but negative in the subsequence a₂, a₃, a₄, …, a₁₇.