| > A sequence has the property that the sum of any 7 consecutive elements
> is positive, while the sum of any 11 consecutive elements is negative.
> What is the longest such sequence?
I have a proof that the longest such sequence is less
than seventy-seven elements, but it is too long to fit
into the margin.
Dan
|
| > A sequence has the property that the sum of any 7 consecutive elements
> is positive, while the sum of any 11 consecutive elements is negative.
> What is the longest such sequence?
Where did you come across this puzzle? I've remet two of the other
five in technical AI journals, where "automated reasoning techniques" were
being applied.
Nostalgically,
Andrew.
|
| A solution after the form-feed...
Let's call our sequence A_1, A_2, ... A_n.
And let's define S_0 = 0
S_j = sum (i=1...j) A_i
Now, the properties of adjacent terms can be expressed as:
S_j < S_(j+7) for all j in {0,...,n-7}
S_k < S_(k-11) for all k in {11,...,n}
Suppose now that n >= 17.
S_17 < S_6 < S_13 < S_2 < S_9 < S_16 < S_5
< S_12 < S_1 < S_8 < S_15 < S_4 < S_11
< S_0 < S_7 < S_14 < S_3 < S_10 < S_17
which is impossible. So n =< 16. In fact, n = 16 *is* attainable.
By setting the values of S_j to anything satisfying:
S_6 < S_13 < S_2 < S_9 < S_16 < S_5
< S_12 < S_1 < S_8 < S_15 < S_4 < S_11
< S_0 < S_7 < S_14 < S_3 < S_10
where S_0 = 0, we can compute immediately the values of A_j, since the
definition of S in terms A is invertible. So for instance if S_6 = -12,
S_13 = -11, S_2 = -10, ... , S_0 = 0, ... , S_10 = 4 then we have
A_j = 13 if j = 3,7,10 or 14
A_j = -5 otherwise.
Every subsequence of length 7 sums to 1, and every subsequence of length 11
sums to -1.
-------------------------------------------------------------------------------
We can generalize the problem from 7 & 11 to p & q. Now we find that
the maximum n is given by:
p + q - (p,q) - 1
where (p,q) is the highest common factor of p & q.
Andrew
|