A set of all numbers that can be written as $1\pm2\pm3\pm...\pm n$ if we can replace $\pm$ by $+$ or $-$.

Question

We have a $M_n$ of all numbers that can be written as $1\pm2\pm3\pm...\pm n$. How many numbers will set contain if we can $\pm$ by $+$ or $-$. For example if $n$ is $3$ then we have $(1+2+3)=6$,$(1+2-3)=0$,$(1-2+3)=2$ and $(1-2-3)=-4$ so with $n=3$, $M_3$ contains $-4,0,2,6$.

In other words, if $M_n$ is the set of all numbers of the form $1\pm 2\cdots\pm n$, where each sign can be independently chosen to be either $+$ or $-$, then what is the size of $M_n$? By the above, $|M_3| = 4$.

Thanks for your answering.

Answer 1

For any integer $p \le q$, let

• $I(p,q) = \{\; k \in \mathbb{Z} : p \le k \le q\;\}$ be the set of integers between $p$ and $q$.
• $S(p,q) = \{\; \sum_{k\in A} k : A \subset I(p,q)\;\}$ be the set of subset sums over $I(p,q)$.

For any integer $n \ge 2$, let $N_n = \sum\limits_{k\in I(2,n)} k = \sum\limits_{k=2}^n k = \frac{n(n+1)}{2} - 1$.

For any $t = 1 \pm 2 \pm 3 \pm \cdots \pm n \in M_n$, let $A \subset I(p,q)$ be the collection of integer $k$ whose sign in the expansion of $t$ is positive. We have $$t = 1 + \sum_{k \in A} k - \sum_{k \in I(2,n) \setminus A} k = 1 - N_n + 2\sum_{k \in A} k$$ This establish a one-one correspondence between $M_n$ and $S(2,n)$. As a result, $$|M_n| = |S(2,n)|$$

It is easy to see $S(2,n) \subset I(0,N_n)$ and $0,2,N_n \in S(2,n)$ but $1,N_n - 1 \not\in S(2,n)$.

Now assume $n \ge 3$. For any $p \in S(2,n)$ such that $2 \le p < N_n - 2$, we can find a non-empty proper $A \subset I(2,n)$ such that $p = \sum\limits_{k \in A} k$. There are two possibilities:

1. $A$ doesn't have the form $I(q,n)$

   In this case, $A$ contains an element $r$ such that $r+1 \in I(2,n)\setminus A$. Let $A' = ( A \setminus \{ r \} ) \cup \{ r + 1 \}$, we have: $A' \subset I(2,n)$ and $\sum\limits_{k \in A'} k = p + 1$. This implies $p + 1 \in S(2,n)$.

2. $A$ does have the form $I(q,n)$

   In this case, $q > 3$ because $p < N_n - 2$. Let $A'' = ( A \setminus \{ q \} ) \cup \{ 2, q-1 \}$. Once again, we have $A'' \subset I(2,n)$ and $\sum\limits_{k \in A''} k = p + 1$. This implies $p + 1 \in S(2,n)$ again.

Combine these and notice $2 \in S(2,n)$, we find $S(2,n) = I(0,N_n) \setminus \{ 1, N_n - 1 \}$.
As a result, for $n \ge 3$, we have: $$|M_n| = |S(2,n)| = |I(0,N_n)| - 2 = N_n - 1 = \frac{n(n+1)}{2} - 2$$

Answer 2

In order to make things more symmetric I deduct $1$ from all members of your sets $M_n$. This means I consider the sets $A_n:=\{k-1\,|\,k\in M_n\}$ instead, defined recursively by $$A_1=\{0\}\>,\qquad A_n:=(A_{n-1}-n)\cup(A_{n-1}+n)\quad(n\geq2)\ .\tag{1}$$ One computes $$A_2=\{-2,2\},\quad A_3=\{-5,-1,1,5\},\quad A_4=\{-9,-5,-3,-1,1,3,5,9\}\ .\tag{2}$$ Define $$N_n:=\sum_{k=2}^n k={1\over2}(n^2+n-2)\qquad(n\geq2)\ .$$ Then $N_2=2$, $N_3=5$, $N_4=9$. I claim that $$A_n=\bigl[-N_n..(2)..N_n\bigr]'\qquad(n\geq2)\ ,\tag{3}$$ whereby the $'$ indicates that at both ends of the chain the second element has to be omitted, see $(2)$. This implies $$|A_n|=N_n-1={1\over2}(n^2+n-4)\qquad(n\geq3)\ .$$ Proof of $(3)$: The claim is true for $n\leq4$. According to $(1)$ we have to consider the two sets $$\eqalign{\bigl[-N_{n-1}..(2)..N_{n-1}\bigr]'-n &=\bigl[-N_n..(2)..N_{n-1}-n\bigr]'\>,\cr \bigl[-N_{n-1}..(2)..N_{n-1}\bigr]'+n&=\bigl[-N_{n-1}+n\>..(2)..N_n\bigr]'\ .\cr}$$ When $n\geq5$ these two sets overlap around the origin so much that the $'$ doesn't do any harm there. It follows that we obtain $$[-N_n..(2)..N_{n-1}-n]'\>\cup\>[-N_{n-1}+n..(2)..N_n]'=[-N_n..(2)..N_n]'\ ,$$ as desired.