4
$\begingroup$

What can be maximum length of such sequence?

Hint one such sequence is

-21,0,10,10,10,10,0,-21

$\endgroup$
  • $\begingroup$ Is this your own puzzle, or from somewhere else (i.e. a competition or the internet)? For all non-original puzzles we require acknowledgement and/or a link. $\endgroup$ – bobble Jun 17 at 17:17
  • 1
    $\begingroup$ I was asked this question by a friend who in-turn was asked in an interview. So a bit difficult to find the link $\endgroup$ – Sagar Chand Jun 17 at 17:19
  • $\begingroup$ The sum of any 5/8 consecutive numbers, or the sum of every 5/8 consecutive numbers? $\endgroup$ – Ian MacDonald Jun 17 at 18:32
  • 1
    $\begingroup$ @IanMacDonald What is the difference between the two things you said? $\endgroup$ – hexomino Jun 17 at 18:39
  • 1
    $\begingroup$ This is a variant of IMO 1977 problem 2. $\endgroup$ – Ankoganit Jun 18 at 3:10
6
$\begingroup$

I think the length of the longest such sequence is

$11$

Proof of upper bound

Suppose we have such a sequence of length $12$ say $a_1, a_2, \ldots, a_{12}$.
By comparing the sums $a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7 + a_8$ and $a_4 + a_5 + a_6 + a_7 + a_8$ we see that $a_1 + a_2 + a_3 < 0$. By increasing the indices incrementally by one each time we can see that we also have $a_2 + a_3 + a_4 < 0$, $a_3 + a_4 + a_5 < 0$, $a_4 + a_5 + a_6 < 0$ and $a_5 + a_6 + a_7 < 0$.

Similarly, by comparing the sums $a_5 + a_6 + a_7 + a_8 + a_9 + a_{10} + a_{11} + a_{12}$ and $a_5 + a_6 + a_7 + a_8 + a_9$, we see that $a_{10} + a_{11} + a_{12} < 0$. By decreasing, the indices incrementally by one each time we can see that we also have $a_9 + a_{10} + a_{11} < 0$, $a_8 + a_9 + a_{10} < 0$, $a_7 + a_8 + a_9 < 0$ and $a_6 + a_7 + a_8 < 0$.

Overall, we see that the sum of any three consecutive terms must be negative.
Now consider $a_1 + (a_2 + a_3 + a_4 + a_5 + a_6) = (a_1 + a_2 + a_3) + (a_4 + a_5 + a_6) < 0$.
From this we see that $a_1 < 0$. We can increment all the indices by $1$ in the above equation to get $a_2 < 0$ and by continuing this procedure, we find that $a_3, a_4, a_5 < 0$. But $a_1 + a_2 + a_3 + a_4 + a_5 > 0$ which is a contradiction.

Proof of lower bound

Here is a sequence of length $11$ which satisfies the constraints $$ -12, 19, -12, -12, 19, -12, 19, -12, -12, 19, -12 $$

How did I find such a sequence

Let's say I take my upper bound proof and try to apply to a sequence with length $11$.
I quickly find that I am unable to prove that $a_5 + a_6 + a_7 < 0$.
The knock-on effect is that I can prove some elements of my sequence are negative but that the elements $a_2, a_5, a_7, a_{10}$ cannot be shown to be negative.
So, let's assume that all elements are negative except for these four, which I'll assume to be positive.
Then, each group of $5$ consecutive entries contains $3$ negatives and $2$ positives and each group of $8$ consecutive entries contains $5$ negatives and $3$ positives. This means that I can simplify things by setting all positive entries to the same value $X$ and all negative entries to the same value $-Y$.
My sequence is then guaranteed to satisfy the constraints as long as $$ 2X - 3Y > 0\,\,\,\,\,\,\,\, 3X - 5Y < 0$$ $$\Rightarrow \frac{3}{2} Y < X < \frac{5}{3}Y $$ To simplify things, I decided to make $Y$ divisible by $6$ (this is not a necessary step but makes both ends of the inequality integers). I also decided that I wanted to try and make $X$ an integer (also not necessary). Setting $Y=6$ gives $9 < X < 10$, so not an integer.
Setting $Y=12$ gives $18 < X < 20$ so $X=19$ works, as required.
Note here that there are plenty of other choices for $X$ and $Y$, I just chose these to make the arithmetic nicer.

As Florian F has pointed out in the comments there is a simpler integer choice. Given that

$$\frac{3}{2} < \frac{3+5}{2+3} = \frac{8}{5} < \frac{5}{3}$$ we can pick $X=8$ and $Y=5$ to generate another valid sequence $$ -5, 8, -5, -5, 8, -5, 8, -5, -5, 8,-5 $$

And pushing this Fibonacci link a bit further we know that

$$\frac{3}{2} < \phi < \frac{5}{3}$$ which means that another nice valid sequence is $$-1, \phi, -1, -1, \phi, -1, \phi, -1, -1, \phi, -1 $$

| improve this answer | |
$\endgroup$
  • $\begingroup$ What is the reasoning behind -12 and 19? I mean how did you come up with that? $\endgroup$ – Sagar Chand Jun 18 at 4:47
  • 1
    $\begingroup$ @SagarChand I will edit in how I found this sequence. $\endgroup$ – hexomino Jun 18 at 8:56
  • $\begingroup$ Actually the simplest rational between $\frac{3}{2}$ and $\frac{5}{3}$ is $\frac{3+5}{2+3} = \frac{8}{5}$. So you can replace $-12$ by $-5$ and $19$ by $8$. Aren't these nicer numbers? $\endgroup$ – Florian F Jun 19 at 15:55
  • 1
    $\begingroup$ @FlorianF I was thinking recently that you could make $X=\phi$ and $Y=1$ and this also works. I may include both choices in an edit. $\endgroup$ – hexomino Jun 19 at 16:14
  • $\begingroup$ The last one is very beautiful! $\endgroup$ – justhalf Jun 20 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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