17
$\begingroup$

How many different values does the expression $1 \pm 2 \pm 3 \pm \cdots \pm n$ take?

I was wondering about this problem and didn't think it was immediately obvious. The answer can't be $2^{n-1}$ since the combinations all might not be unique. I was thinking of looking at partitions of $\{1,2,\ldots,n, k\}$ where $1 \pm 2 \pm 3 \pm \cdots \pm n = k$ and thus the sum must be even. Therefore, $\dfrac{n(n+1)}{2}+k = \dfrac{n(n+1)+2k}{2}$ must be even which means $n(n+1) + 2k$ must be a multiple of $4$ so $n(n+1)+2k = 4m$. Thus if $n \equiv 1,2 \bmod 4$, then $k \equiv 1,3 \bmod 4$ and if $n \equiv 3,0 \bmod 4$ then $k \equiv 0,2 \bmod 4$.

$\endgroup$
  • 1
    $\begingroup$ So, what is the question about this? $\endgroup$ – Obinna Nwakwue Apr 30 '16 at 15:09
  • 2
    $\begingroup$ @ObinnaNwakwue it's at the top in a box $\endgroup$ – Stella Biderman Apr 30 '16 at 15:10
  • $\begingroup$ The problem is that not all values of $k$ are obtainable. $\endgroup$ – user19405892 Apr 30 '16 at 15:12
  • $\begingroup$ Well, everyone else has answered it but: a)all values are between n (n+1)/2 and -n (n+1)/2 +2. b) then numbers are precisely n(n+1)/2 - 2k where k is a number that is a sum of 0 or more distinct terms, 0,1,2....n. (so all values are the same parity) and c) it's easy to show every number between 0 and n (n+1)/2 can be written as a sum of 0 or more distinct terms between 0 and n. Ergo: the solutions are precisely all the terms between -n (n+1)/2 and n (n+1)/2 of the same parity. a) b) and c) each have to be shown but they are each straightforward. $\endgroup$ – fleablood Apr 30 '16 at 19:32
  • $\begingroup$ See a rather similar similar question here. $\endgroup$ – Jean Marie Apr 23 '17 at 16:00
8
$\begingroup$

To start with, you can forget about the leading term, $1$. All that term does is to shift all the values one place to the right on the number line. The expression $\pm 2 \pm 3 \pm \cdots \pm n$ has the same number of distinct values as $1 \pm 2 \pm 3 \pm \cdots \pm n$.

From this point until further notice, I'll consider only sums of the form $\pm 2 \pm 3 \pm \cdots \pm n$.

All possible sums have the same parity.

The minimum sum is $\sum_{i=2}^n(-i) = -\frac{(n+2)(n-1)}{2}$, when all the $\pm$ signs are negative. The sum $-\frac{(n+2)(n-1)}{2} + 2$ is clearly not achievable, but $-\frac{(n+2)(n-1)}{2} + 4$ is, as long as $n \geq 2$.

Now as long as the sum includes two terms $j - (j+1)$ (positive followed by negative), we can change the two terms to $-j + (j+1)$ and thereby increase the sum by $2$.

If there are no such terms, that is, all the negative terms occur before any of the positive terms, the sum has the form $$-2 - 3 - \ldots - (j-1) - j + (j+1) + \ldots + n = k \tag1$$ where $1 \leq j \leq n$. (In the case $j = 1$, all terms are positive.)

We have already considered the case $j = n$. In the case $j=1$, the sum has the maximum value, $\frac{(n+2)(n-1)}{2}$, and in the case $j=2$, the sum has the second greatest possible value, $\frac{(n+2)(n-1)}{2} - 4$. Now suppose instead that $3 \leq j \leq n-1$. Then we can change the sum on line $(1)$ to $$2 - 3 - \ldots - (j-1) + j - (j+1) + \ldots + n = k + 2.$$

In other words, if $n > 3$, then except for the values $-\frac{(n+2)(n-1)}{2}$, $\frac{(n+2)(n-1)}{2} - 4$, and $\frac{(n+2)(n-1)}{2}$, every possible value of the sum (including $-\frac{(n+2)(n-1)}{2} + 4$) corresponds to another sum that is greater by $2$. So the possible sums are $-\frac{(n+2)(n-1)}{2}$, $\frac{(n+2)(n-1)}{2}$, and every integer of the same parity from $-\frac{(n+2)(n-1)}{2} + 4$ to $\frac{(n+2)(n-1)}{2} - 4$, inclusive.

The number of integers in $\left[-\frac{(n+2)(n-1)}{2}, \frac{(n+2)(n-1)}{2}\right]$ is $(n+2)(n-1) + 1$, and those of the same parity are $\frac{(n+2)(n-1)}{2} + 1$. So if $n > 3$, the total number of possible sums (excluding the values $-\frac{(n+2)(n-1)}{2}+2$ and $\frac{(n+2)(n-1)}{2}-2$, which are not possible sums) is $$\left(\frac{(n+2)(n-1)}{2} + 1\right) - 2 = \frac12(n^2 + n - 4).$$

For example, if $n=4$ then there are $8$ possible sums: $-9,-5,-3,-1,1,3,5$, and $9$.

By inspection, this formula also gives the number of sums for $n=3$ (the sums are $-5,-1,1,$ and $5$), but the number of sums for $n=2$ is $2$, which does not agree with the formula; $n=2$ must be treated as a special case.


If you modify the original expression by making the first term $\pm1$, that is, if you consider $\pm 1 \pm 2 \pm \cdots \pm n$, the minimum 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.

$\endgroup$
4
$\begingroup$

Let us use generating functions

$$G_n(X)=X\prod_{k=2}^n(X^{-k}+X^k)=\dfrac{1}{X^p}\prod_{k=2}^n(1+X^{2k}) \ \ \ \text{with} \ \ \ p=\frac{n(n+1)}{2}-2$$ (very close to the proposal of @Jack D'Aurizio). In this way, we transfer the issue into counting how many combinations as positive or negative exponents of indeterminate $X$ are present in the expansion of $G_n(X)$.

Let us manipulate the first values of $n$ which is enough to get a good perception of the method.

We begin by the case $n=3$:

$$G_3(X)=X(X^{-2} + X^2)(X^{-3} + X^3)=$$ $$X^{1-2-3} + X^{1+2-3} + X^{1-2+3} +X^{1+2+3}$$ $$=X^{-4} + X^0 + X^2 + X^6$$

Note the central symmetry (with respect to position $1$) of the exponents $-4,0,2,6$. This central symmetry will exist for all values of $n$.

Let us now consider the cases $n=4, 5, 6$:

$n=4$:

$$G_4(X)=X(X^{-2} + X^2)(X^{-3} + X^3)(X^{-4} + X^4) =$$ $$X^{-8} + X^{-4} + X^{-2} + X^0+ X^2 + X^4 + X^6 + X^{10}$$

Till now, there are no repetitions. Here they come for $n \geq 5$:

$n=5$:

$$G_5(X)=X(X^{-2} + X^2)(X^{-3} + X^3)(X^{-4} + X^4)(X^{-5} + X^5)$$ $$=X^{-13} + X^{-9} + X^{-7} + X^{-5} + 2X^{-3} + X^{-1} + 2\,X + X^3 + 2\,X^5 + X^7 + X^9 + X^{11} + X^{15}$$

This time, not all coefficients are one; the reason is clear: for example, monomial $^2X^5$ means that $5$ is obtainable in two ways, i.e., $1+2+3+4-5$ and $1-2-3+4+5$. This is an "added value" of the approach by generating functions.

A last case, $n=6$, in order to see the differences between the cases $n$ odd and $n$ even:

$$X(X^{-2} + X^2) \cdots (X^{-5} + X^5)(X^{-6} + X^6)=$$ $$=X^{-19} + X^{-15} + X^{-13} + X^{-11} + 2X^{-9} + 2X^{-7} + 2X^{-5} + 2X^{-3} + 3X^{-1} + 2\,X + 3\,X^3 + 2\,X^5 + 2\,X^7 + 2\,X^9 + 2\,X^{11} + X^{13} + X^{15} + X^{17} + X^{21}$$

I will not go beyond this point because there is a clear recurrence relationship, but developing it would look to the reader like paraphrasing the (very detailed) redaction of @David K .

$\endgroup$
1
$\begingroup$

Hint: $$ 1\pm 2\pm 3\pm 4\ldots \pm n = \frac{n(n+1)}{2}-a_2-a_3-\ldots-a_n, \qquad a_k\in\{0,2k\}.$$ Consider $(1+x^4)(1+x^6)\cdot\ldots\cdot(1+x^{2n})$. How many monomials appear in the expansion?

$\endgroup$
  • $\begingroup$ How does that help? $\endgroup$ – user19405892 Apr 30 '16 at 15:26
  • $\begingroup$ I think it gives the answer. How many (and which) integers can you get by adding some of the elements from $\{2,3,4,\ldots,n\}$? Double them and subtract them from $\frac{n(n+1)}{2}$. $\endgroup$ – Jack D'Aurizio Apr 30 '16 at 15:27
  • $\begingroup$ You can get $5,6,\ldots,2n-1$. Thus there are $2n-5$ possible values? $\endgroup$ – user19405892 Apr 30 '16 at 15:32
1
$\begingroup$

In a similar, but newer question here in MSE I gave a "proof without words" (however, I needed a couple of words to explain the picture).

Here is a similar picture; if you have read the explanations in that other thread once, you never need this anymore...
picture

It means, we begin with the set-of-result $R_0 = \{0\}$ having cardinality $ \# R_0=1$ .

Then we initialize a set of summands, $S_1=\{1\}$ . To each element in $R_0$ we add the new summand $s_1=1$ getting a new results-set $R_1 = \{1\}$. Its cardinality is $\#R_1=1$ . In the picture this is reflected by the top-most green arrow for addition; because we do not use $-1$ the subtraction-arrow is grey and the subtraction-value $-1$ is not a valid element in $R_1$

After that we add the element $s_2=2$ to our summands-set. We arrive at the new results-set $R_2$ by adding (green arrows) and subtracting (red arrows) that $s_2$ to each element in $R_1$.

And so on. In the picture I've documented in grey the missing elements compared with the symmetric tree, when the first summand were $ \pm 1$ in the problem definition instead of only $+1$ .

But the evolution of the iteration becomes immediately clear after seeing $R_4$ and $R_5$. In each new row shall 3 elements be invalid/missing compared with the symmetric tree as shown in the other answer. The formula for the cardinalities can simply be derived to be (for $ k \ge 3$): $$ \# R_k = \binom{1+k}{2} -2 $$

$\endgroup$
  • $\begingroup$ This gives a very pleasing intuition about why the elements at the "maximum minus 2" and "minimum plus 2" are missing when we force the sign of the term 1 to be positive. $\endgroup$ – David K Feb 7 '17 at 15:49

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.