Un conjunto de todos los números que se pueden escribir como$1\pm2\pm3\pm...\pm n$ si podemos reemplazar$\pm$ por$+$ o$-$.

Question

Tenemos una $M_n$ de todos los números que pueden escribirse como $1\pm2\pm3\pm...\pm n$. Cuántos números se contienen, si podemos, $\pm$ por $+$ o $-$. Por ejemplo, si $n$ es $3$ entonces tenemos $(1+2+3)=6$,$(1+2-3)=0$,$(1-2+3)=2$ e $(1-2-3)=-4$ lo con $n=3$, $M_3$ contiene $-4,0,2,6$.

En otras palabras, si $M_n$ es el conjunto de todos los números de la forma $1\pm 2\cdots\pm n$, donde cada signo puede ser independiente elegido para ser $+$ o $-$, entonces ¿cuál es el tamaño de $M_n$? Por lo anterior, $|M_3| = 4$.

Gracias por tu respuesta.

Answer 1

Para cualquier entero $p \le q$, vamos

• $I(p,q) = \{\; k \in \mathbb{Z} : p \le k \le q\;\}$ el conjunto de los enteros entre $p$ e $q$.
• $S(p,q) = \{\; \sum_{k\in A} k : A \subset I(p,q)\;\}$ el conjunto de subconjunto sumas de $I(p,q)$.

Para cualquier entero $n \ge 2$, vamos a $N_n = \sum\limits_{k\in I(2,n)} k = \sum\limits_{k=2}^n k = \frac{n(n+1)}{2} - 1$.

Para cualquier $t = 1 \pm 2 \pm 3 \pm \cdots \pm n \in M_n$, vamos a $A \subset I(p,q)$ ser el colección de enteros $k$ cuyo signo en la expansión de $t$ es positivo. Tenemos $$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$$ Esto establecer una correspondencia entre $M_n$ e $S(2,n)$. Como resultado, $$|M_n| = |S(2,n)|$$

Es fácil ver $S(2,n) \subset I(0,N_n)$ e $0,2,N_n \in S(2,n)$ pero $1,N_n - 1 \not\in S(2,n)$.

Ahora suponga $n \ge 3$. Para cualquier $p \in S(2,n)$ tal que $2 \le p < N_n - 2$, podemos encontrar un no-vacío adecuado $A \subset I(2,n)$ tal que $p = \sum\limits_{k \in A} k$. Hay dos posibilidades:

1. $A$ no tiene el formulario de $I(q,n)$

   En este caso, $A$ contiene un elemento $r$ tal que $r+1 \in I(2,n)\setminus A$. Deje $A' = ( A \setminus \{ r \} ) \cup \{ r + 1 \}$, tenemos: $A' \subset I(2,n)$ e $\sum\limits_{k \in A'} k = p + 1$. Esto implica $p + 1 \in S(2,n)$.

2. $A$ tiene la forma $I(q,n)$

   En este caso, $q > 3$ porque $p < N_n - 2$. Deje $A'' = ( A \setminus \{ q \} ) \cup \{ 2, q-1 \}$. Una vez más, hemos $A'' \subset I(2,n)$ e $\sum\limits_{k \in A''} k = p + 1$. Esto implica $p + 1 \in S(2,n)$ nuevo.

Combinar estos y aviso de $2 \in S(2,n)$, nos encontramos con $S(2,n) = I(0,N_n) \setminus \{ 1, N_n - 1 \}$.
Como resultado, para $n \ge 3$, tenemos: $$|M_n| = |S(2,n)| = |I(0,N_n)| - 2 = N_n - 1 = \frac{n(n+1)}{2} - 2$$

Answer 2

En orden para hacer las cosas más simétrica puedo deducir $1$ de todos los miembros de los conjuntos de $M_n$. Esto significa que considerar los conjuntos de $A_n:=\{k-1\,|\,k\in M_n\}$ en lugar de ello, se define recursivamente por $$A_1=\{0\}\>,\qquad A_n:=(A_{n-1}-n)\cup(A_{n-1}+n)\quad(n\geq2)\ .\tag{1}$$ Uno calcula $$A_2=\{-2,2\},\quad A_3=\{-5,-1,1,5\},\quad A_4=\{-9,-5,-3,-1,1,3,5,9\}\ .\tag{2}$$ Definir $$N_n:=\sum_{k=2}^n k={1\over2}(n^2+n-2)\qquad(n\geq2)\ .$$ A continuación, $N_2=2$, $N_3=5$, $N_4=9$. Yo reclamo que $$A_n=\bigl[-N_n..(2)..N_n\bigr]'\qquad(n\geq2)\ ,\tag{3}$$ mediante el cual el $'$ indica que en ambos extremos de la cadena, el segundo elemento tiene que ser omitido, ver $(2)$. Esto implica $$|A_n|=N_n-1={1\over2}(n^2+n-4)\qquad(n\geq3)\ .$$ La prueba de $(3)$: La afirmación es verdadera para $n\leq4$. De acuerdo a $(1)$ debemos tener en cuenta que los dos conjuntos $$\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}$$ Cuando $n\geq5$ estos dos conjuntos se superponen en torno al origen tanto que el $'$ no hará daño a nadie allí. De ello se desprende que obtenemos $$[-N_n..(2)..N_{n-1}-n]'\>\cup\>[-N_{n-1}+n..(2)..N_n]'=[-N_n..(2)..N_n]'\ ,$$ como se desee.