# Positively non-positive (from Brilliant.org) Whats wrong with my method?

(taken from brilliant.org)

For how many positive integers $N$ between $3$ and $1000$ (inclusive) is the following statement true:

If $\{a_i\}^N_{i=1}$ is a set of $N$ (not necessarily distinct) real numbers such that

$a_1+a_2+…+a_N=0$,

then we must (always) have

$a_1a_2+a_2a_3+…+a_{N−1}a_N+a_Na_1≤0$?

I think that this is true for all $N$, because we can have all $a_{2k}$ to be a positive number and all $a_{2k+1}$ to be a negative number, then if $N$ is odd then $a_1$ is $0$, this way positive numbers and negative numbers are alternating so the product of them is negative so the sum of the products will be negative, so the answer is $998$, but when I entered it on Brilliant it says my answer is wrong, what is wrong with my method

-

In order for that statement to be true for a given $N$, the conclusion must hold true for all possible choices of $a_1,a_2,\ldots,a_N$ whose sum is $0$.

In other words, you can not decide that a particular $N$ works by specifying that the $a_{2k}$'s are nonnegative and the $a_{2k+1}$'s are negative, since, while the conclusion of the statement might hold for that choice, it might not hold for other choices. For example, your method doesn't seem to cover the possibility that $a_1=1,a_2=1,\ldots,a_{N-1}=1$ and $a_N=1-N$.

-
I agree with your point, but isn't the sum of products for your example $(N-2)+(1-N)+(1-N) = -N \le 0$? In which case it is not a counterexample. – half-integer fan Nov 21 '13 at 14:29
@half-integerfan I wasn't claiming it was a counterexample to the brilliant.org problem. I was just using it to illustrate that Yan Yau's method of proof was incomplete since that possibility wasn't covered. – Casteels Nov 21 '13 at 14:32
OK, I see that was sufficient to answer the original post ("Why is that not correct") but I can't help trying to determine what the right answer should be :) – half-integer fan Nov 21 '13 at 14:37
@YanYau, note that although a single case is not sufficient to prove that an N works, a single counter-example is sufficient to prove that a given N doesn't work, since you were asked to prove a condition always holds. – half-integer fan Nov 24 '13 at 13:27

Now that the Brilliant.org contest week is over I will point out that the stated condition does not hold for any $n \ge 5$, since you can construct a set of numbers like $\{1, 1, 0, -(n-3), 0\}$ with $n-3$ ones and the only negative term surrounded by zeros, so the condition given will always have a positive value on the left hand side.

Even if zeros are disallowed the same will be true with arbitrarily small real numbers in their place. In fact this is even true for integers by scaling the non-zero values arbitrarily large and replacing the zeros with ones. (In each case one zero should be replaced with a positive value and the other with a negative, to preserve the sum condition.)

The condition given holds for $n=2,3$; I did not attempt to determine the result for $n=4$.

-