Find all conditions for $x$ that the equation $1\pm 2 \pm 3 \pm 4 \pm \dots \pm n=x$ has a solution.

Find all conditions for $x$ so that the equation $1\pm 2 \pm 3 \pm 4 \pm \dots \pm 1395=x$ has a solution.

My attempt: $x$ cannot be odd because the left hand side is always even then we have $x=2k(k \in \mathbb{N})$ also It has a maximum and minimum

$1-2-3-4-\dots-1395\le x \le 1+2+3+4+\dots +1395$

But I can't show if these conditons are enough or make some other conditions.


Solution 1:

An attempt to "prove without words":

picture

Ok, I'll give some words...

We start with the only sum $0$ : first row, rowindex $k=0$, set-of-results $R_0=\{0\}$ ).

After that we initialize our set of summands by $1$ and by subtraction (red arrow) or addition (green arrow) we arrive at the set of results $R_1 = \{-1,+1\}$ . Note the distance of all elements is $2$.

After that we add $2$ to our summands and by subtraction or addition to any element of the previous set of results we get $R_2=\{-3,-1,1,3\}$

After that we add $3$ to our summands and by subtraction or addition to any element of the previous set of results we get $R_3=\{-6,-4,-2,0,2,4,6\}$

...


We already see, how this generalizes:

The new summand $s_k$ subtracted from the smallest element in the previous result gives the new smallest element which is $- \binom{1+s_k}{2}$ (leftmost red arrow) and the analoguous to the old largest element gives $+ \binom{1+s_k}{2}$. Because the previous set of results was dense in steps of 2, and $s_k$ is smaller than the largest element of the previous result we get no new holes, and thus the result-set is again dense in steps of $2$, reaching from the negative binomial value to the positive binomial value.

Counting the cardinalities of the result-sets show, that we always have $ \operatorname{card}(R_k)= \binom{1+k}{2}+1 $ where $\operatorname{card}(R_0)=1$

The result for $R_{1395}$ should then be $$\operatorname{card}(R_{1395}) = \binom{1+1395}{2}+1 = 973711 $$


[Update] See my similar answer for the case that the first element of the sum is not $\pm 1$ but only $1$ .
After you've the second time changed your title (what's this for?) the other picture is relevant instead of the first given one. The logic is the same; the grey arrows are that now-invalid ones for the set-of-preferred-results $R_k$ :

picture

The result for this version of $R_{1395}$ should then be $$\operatorname{card}(R_{1395}) = \binom{1+1395}{2}-2 = 973709 $$

Solution 2:

Let $N:=1+2+\ldots+1395$, which is even. You've already found the necessary conditions that $x$ be even and $-N\leq x\leq N$. These conditions are also sufficient; to show this it suffices to choose the signs in the sum such that it sums to $x$, for every even $x$ with $-N\leq x\leq N$.

For $x=N$ we simply choose the $+$-sign everywhere. For $x$ even with $-N\leq x<N$ the difference $N-x$ is even, and so $\frac{N-x}{2}$ is an integer between $0$ and $N$. This means we can write $\frac{N-x}{2}$ as a sum of distinct integers from $1$ to $1395$, though not necessarily in a unique way (this is very easy to prove by induction). Now choose the $-$-sign at all these integers in stead of the $+$-sign; this is the same as subtracting $\frac{N-x}{2}$ from $N$ twice, so this way the sum sums to $N-2\cdot\frac{N-x}{2}=x$.


EDIT: The suggested claim that is very easy to prove by induction (on $n$) is the following:

For every natural number $n$, every integer from $1$ to $1+2+\ldots+n$ can be written as a sum of distinct integers from $1$ to $n$.

The base case is clear, and the induction step (from $n$ to $n+1$) only requires the observation that the last $n+1$ integers can be written in the form $x+(n+1)$ where $x\leq1+2+\ldots+n$.


EDIT: Only on a third reading did I notice that the sign of the $1$ can not be chosen. To this question I don't have anything better or more clear to say than David K has already said in his answer, and in particular in his linked answer.

Solution 3:

In general, if $n$ is a positive integer, the minimum value of the sum $\pm 1 \pm 2 \pm 3 \pm \cdots \pm n$ is $-\frac{n(n+1)}{2}$, the maximum is $\frac{n(n+1)}{2}$, and all integers of the same parity between those values are possible sums. That is, if $\frac{n(n+1)}{2}$ is even, all possible values are even, and if $\frac{n(n+1)}{2}$ is odd, all possible values are odd.

This is based on an answer I posted to a very similar question several months ago; the main question in that case, like the original version of this question, did not have $\pm$ in front of the $1,$ but the version with $\pm1$ is a relatively trivial extension of the problem for which I gave a solution at the end of that answer.

Since the sums with $\pm$ in front of the $1$ are much simpler to show than the sums without that $\pm,$ I'll recapitulate the argument for the sum with $\pm1.$

If any of the $\pm$ signs in $\pm 1 \pm 2 \pm 3 \pm \cdots \pm n$ is negative, we can make a greater number by changing that sign to a positive. But if all signs are positive then any change will make the sum less. So the maximum value has all signs positive, and is $$ 1 + 2 + 3 + \cdots n = \frac{n(n+1)}{2}. $$ A mirror-image argument shows that the minimum value is $-\frac{n(n+1)}{2},$ achieved when all the $\pm$ signs are negative.

Now suppose that somewhere in the sum there are two consecutive terms whose signs are positive and then negative, that is, the terms are $+j - (j+1)$ where $1 \leq j \leq n-1.$ Then we can change these two terms to $-j + (j+1)$ in order to increase the sum by exactly $2.$ The only situation in which we cannot do this is when all the negative terms occur before all the positive terms; that is, either all are positive (the maximum value), all are negative (the minimum value), or the sum has the form $$ -1 - 2 - 3 - \cdots - k + (k+1) + (k + 2) + \cdots + n. $$ In the "all positive" case, of course we cannot increase the sum; in the other two cases, the first term is $-1,$ and we can change this to $+1$ and thereby increase the sum by $2.$

So every sum except the maximum one can be increased by $2$; starting at $-\frac{n(n+1)}{2},$ that lets us reach every integer of the same parity from $-\frac{n(n+1)}{2}$ to $\frac{n(n+1)}{2},$ inclusive.

You cannot reach any number of opposite parity from $\frac{n(n+1)}{2},$ because every time you change the sign of the term $j$ you either add or subtract $2j$ from the sum.

Now just plug in $1395$ for $n.$

Solution 4:

Let $K = \sum_{i=1}^n {k_i}i$ where $k_i \in \{1,-1\}$ be one of the expressible numbers and $M = \sum_{i=1}^n {m_i}i$ where $m_i \in \{1,-1\}$ be another.

$M - K = \sum_{i=1}^n (m_i - k_i) i = \sum_{i=1}^n [\{-2|0|2\}]i$ is an even number so all such numbers have the same parity.

Cleary any $K$ is such $-\frac{n(n+1)}2=- \sum i \le K \le \frac{n(n+1)}n$.

Let $K < \frac{n(n+1)}n$ so one of the ${k_i} = -1$. Let $j$ be so that ${k_{m }} = 1; \forall m < j$ but ${k_j} = -1$.

Let $\overline{K} = \sum {m_i}$ where $m_i = k_i$ for $i \ne j|j-i$; ${m_j} = 1$ (whereas ${k_j} = -1)$ and, if $j > 1$ then ${m_{j-1}} = -1$ whereas ${k_{j-1}} = 1$. Then $\overline {K} = K + 2j - 2(j-1) = K + 2$.

So via induction, all (and only) $K; -\frac{n(n+1)}2=- \sum i \le K \le \frac{n(n+1)}n; K $ of the same parity of $\frac{n(n+1)}n$ are possible.

So for $n = 1395$, all even numbers between $-\frac{1395*1396}2$ and $\frac{1395*1396}2$ are possible.

Solution 5:

Given that the $1$ in the series is not $\pm1$, I can see one other condition, namely that $x$ cannot have the values $Max-2$ or $Min + 2$, where Max and Min are the maximum and minimum values of the series.

The Max occurs when all signs are positive. The only way to get a sum of $Max-2$ is by changing the sign of $1$ from positive to negative, thus decreasing the sum by $2$. Changing the sign of $2$ from positive to negative would decrease the sum by $4$. Changing the sign of $3$ from positive to negative would decrease the sum by $6$, etc. It is thus not possible to achieve the number $Max - 2$.

The Min occurs when all signs are negative, except for the $1$ which must be positive. The smallest positive increase it is possible to make is by changing the sign of the $2$ from negative to positive. This increases the sum by $4$. It is thus not possible to achieve the number $Min + 2$.