Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
An attempt to "prove without words":
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\}$
...
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 $$
The result for this version of $R_{1395}$ should then be $$\operatorname{card}(R_{1395}) = \binom{1+1395}{2}-2 = 973709 $$
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.
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.$
1 pm 2 in the Search Q&A box at the top of this page brought up the question from last April as the second search result when I tried it. For pm 1 pm 2 that question was the fourth result.
$\endgroup$
– David K
Feb 7 '17 at 6:15
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.
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$.
I am not sure this is the approach, but let me try. I am assuming $\pm1$ in the statement of the problem.
The basic idea is induction. For $n$, solve your problem. That is, $\pm1\pm2\ldots\pm n=x$. Then go to $n$.
Basic induction step: $n=3$. Then $\pm1\pm2\pm3=x$ has a solution for any even $x$ between $\pm6$. This is easy to check.
The induction step: given $n$ such that $n+1$ is divisible by $4$, go to $n+4$.
Let me illustrate this from $n=3$ to $n'=7$ as an example (hoping general step can be written). This involves adding $\pm4\pm5\pm6\pm7$. Using $4+7-5-6=0$, if there is a solution for $x$ with $n$, there is a solution for $x$ with $n'$. The $\pm4\pm5\pm6\pm7$ can moreover be used to add $\{2,4,8,10,12,14,22\}$ (to $6$ generated by $1+2+3$, subtracting is the same). If I show how to add $\{6,16,18,20\}$ the 'induction step' is complete. To add $6$ add $12$ with $\pm4\pm5\pm6\pm7$ and change $3$ to $-3$. To add $16$ add $22$ with $\pm4\pm5\pm6\pm7$ and change $3$ to $-3$. Likewise, $18$ and $20$ follow by adding $22$ and changing sign of $2$ and $1$ respectively.
Let $k=\sum_{i=1}^{1395}i=\frac 121395\cdot 1396$, which is the maximum sum you can attain. Claim: you can achieve any even sum from $-k+2$ to $k$ except $k-2, -k+4$ We proceed by strong induction over numbers of the form $3 \bmod 4$. The base cases are $n=3,$ where we should be able to achieve $6,2,-4$ which we can do with $1+2+3, 1-2+3, 1-2-3$ and $n=7$ where we can achieve $-26,-22,-20,-18,\ldots 24,28$. Then we show if it is true up to $m$, it is true for $m+4$. If our target is within the range we can obtain with $m$, we can put plus signs before $m+1, m+4$ and minus signs before $m+2, m+3$ and use the solution for the target with $m$. If it is greater than $\frac 12m(m+1)$ it is less than or equal to $\frac 12(m+4)(m+5)=\frac 12m(m+1)+4m+10$ For $m \ge 11$ we can negate all the top four terms and reduce our target with numbers up to $m-4$ by $4m-10$. This will not reduce the target below $0$ so we can use the solution for $m$ and the new target. A similar argument works for negative targets with plus signs before the four largest numbers.
Call $S_n$ the set of all values that ca be obtained with the sum $$ 1\pm2\pm3...\pm n $$ with the convention that $S_1=\{1\}$.
You obtain $S_2$ by taking the sole element of $S_1$ and either adding or subtracting $2$: $$ S_2=\{-1,3\} $$ Similarly, you obtain $S_3$ by taking the elements of $S_2$ and either adding or subtracting $3$: $$ S_3=\{-4, 0, 2, 6\} $$ You do the same for $S_4$, taking the elements of $S_3$ and either adding or subtracting $4$: $$ S_4=\{-8, -4, -2, 0, 2, 4, 6, 10\}. $$ In general, you obtain $S_n$ but adding or subtracting $n$ to the elements of $S_{n-1}$. Delete duplicates if there are some. Keep going for a while: \begin{align} S_5&=\{-13, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 15\} \\ S_6&=\{-19, -15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 21\}\\ ... \end{align} You can see the pattern: for $n\geq3$, $$ S_n=\{min, min+4,min+6,...,-1,1,...,max-6,max-4,max\}. $$ That is, all odd numbers from $min$ to $max$ except $min+2$ and $max-2$.
As others have pointed out, \begin{align} max&=1+2+...+n=\frac{n(n+1)}{2}\\ min&=1-2-3...-n=2-(1+2+...+n)=2-max. \end{align}
When $n=1395$ you get \begin{align} max&=\frac{1395\times(1395+1)}{2}=973710\\ min&=2-max=-973708. \end{align} Therefore the conditions you are looking for in the case $n=1395$ are
Note. If you allow the first term to be $\pm1$ then $S_1=\{-1,1\}$. If you work ou the example you find the same values for $x$ except that $min+2$ and $max-2$ are not excluded.
The solution for $n$ as in the title is as follows:
Let $p = (n-3)(n+4)/2$ then the solutions for x are $-p-4, -p, -p+2, \ldots,p-2, p, p +2, p+4$ where from the term $-p$ on we go to the term $p$ each time adding $2$. So only the first and the last two terms are irregular. We can verify:
Proof: we have to show that, having established the series for $n$ then we obtain the new series by adding and subtracting $n+1$ to all previous numbers. Indeed we have that $p' = (n'-3(n'-4)/2 = p + n + 1$ for $n' = n+1$.
