13
$\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$
7
  • 1
    $\begingroup$ Is the leading $1$ also $\pm1$? $\endgroup$
    – Joffan
    Feb 3, 2017 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, 2017 at 22:38
  • $\begingroup$ @Joffan No It is simply $1$. $\endgroup$ Feb 4, 2017 at 13:47
  • 6
    $\begingroup$ If the leading 1 is simply 1, your minimum shouldn't start with -1. $\endgroup$
    – Jens
    Feb 7, 2017 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$ Feb 9, 2017 at 11:38

9 Answers 9

10
+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$
2
  • 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, 2017 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$
    – Servaes
    Feb 7, 2017 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$
1
  • $\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, 2017 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$
2
  • $\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, 2017 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, 2017 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .