12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Is the leading $1$ also $\pm1$? $\endgroup$ – Joffan Feb 3 '17 at 20:30
  • 2
    $\begingroup$ Consider this example: $1-2-3+4+5+6+ \dots+1395 = 1+2+3+4-5+6+ \dots+1395 $. Should the question be understood in such a way that the above example is just counted as **one** condition for $x$? Then the task would be to subtract from the $2^{1394}$ choices of the signs (="conditions") those which add to the same $x$. $\endgroup$ – Andreas Feb 3 '17 at 22:38
  • $\begingroup$ @Joffan No It is simply $1$. $\endgroup$ – Taha Akbari Feb 4 '17 at 13:47
  • 6
    $\begingroup$ If the leading 1 is simply 1, your minimum shouldn't start with -1. $\endgroup$ – Jens Feb 7 '17 at 2:02
  • 1
    $\begingroup$ The (second now!) change in the title makes this question a simple duplicate, as @A--B has mentioned in his/her comment. $\endgroup$ – Gottfried Helms Feb 9 '17 at 11:38
9
+50
$\begingroup$

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 $$

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ As hinted in this answer, the fact that $\frac{N-x}{2}$ can always be written as a sum of distinct integers from the original terms of the sum is not trivial, but it seems fairly easy to prove. $\endgroup$ – David K Feb 7 '17 at 15:57
  • $\begingroup$ Yes, it is more or less equivalent to the original problem, but it is intuitively much clearer and (hence) easier to prove. $\endgroup$ – Inactive - Objecting Extremism Feb 7 '17 at 15:59
4
$\begingroup$

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.$

$\endgroup$
  • $\begingroup$ By the way, putting 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
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Perhaps induction over all $n$ would be simpler. To go from $n$ to $n+1$ you just add another layer to Gottfried Helms's diagram. Show by arithemetic that you get two overlapping "shifted" copies of the results for $n.$ $\endgroup$ – David K Feb 7 '17 at 15:54
  • $\begingroup$ I was the first answer here for $\pm1$, so I could not draw inspiration from other answers. I found the induction 'by $4$' simpler. But I completely agree that there might be multiple ways and mine is certainly not the simplest. Plus, my answer was really a sketch. $\endgroup$ – Jan Feb 7 '17 at 16:14
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

  • $x$ is odd
  • $-973708\leq x\leq 973710$
  • $x$ is neither $-973706$ nor $973708$.

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.

$\endgroup$
3
$\begingroup$

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:

  • for $n = 4$ we have $-8, -4, -2, 0, 2, 4, 6, 10$ with p = $(4-3)(4+4/2 = 4)$
  • for $n = 5$ we have $ -13, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 15$ with $p = (5-3)(5+4)/2 = 9$
  • for $n = 1395$ we will have $-973708, -973704, -973702, \text{ each time add 2 , 973704, 973706, 973710}$ with $p = (1935-3)(1935+4)/2 = 973704$

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$.

$\endgroup$

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.