Hay 3 de Suma Cero de los Números!

Question

Demostrar que para cualquier conjunto de $2n+3$ enteros del intervalo de $[-2n-1,2n+1]$ no es un triple a $(x,y,z)$ tal que $x+y+z=0$.

---

Ejemplo : Seleccione el número 5 de {-3,-2,-1,0,1,2,3} existen x,y,z con x+y+z=0

Supongo que se trata de resolver con la Inducción.

Answer 1

Aquí está la prueba de varios casos, a pesar de Caso 0 es trivial, el Caso 1 y el Caso 3 son similares el uno al otro, y el Caso 2 y Caso 4 también son similares entre sí (así, podríamos decir que sólo hay dos casos importantes).

Caso 0. Si $0$ está entre los números elegidos, a continuación, utilizar ese no es distinto de cero $x$ con ambos $x$ $-x$ entre los números elegidos, de modo que la suma de $x+(-x)+0=0$ obras. Tal $x$ existe ya que de lo contrario la función valor absoluto sería un inyectiva mapa del conjunto de $(2n+2)$-a muchos no-cero números elegidos en el intervalo de $[1,..,2n+1]$ lo cual es imposible.

En todos los casos restantes, voy a suponer que $0$ no es elegido.

Caso 1. Ni $-2n-1$ ni $2n+1$ están entre los números elegidos. Entonces también podríamos eliminar $\pm 2n$, eliminando así en la mayoría de los dos números elegidos, y restringir nuestra atención en el intervalo de $[−2n+1,..,2n−1]=[−2(n−1)−1,..,2(n−1)+1]$, y en él podemos tener al menos $2n+3−2=2(n−1)+3$ números elegidos, y aplicar la hipótesis de inducción (donde el contexto de una prueba por inducción debe ser claro, el caso base se $n=0$, la elección de tres enteros del intervalo de $[-1,0,1]$, entonces es claro que la elección es única y $-1+0+1=0$). Estamos de hecho en este caso.

Así que podemos suponer sin pérdida de generalidad que cualquiera de las $-2n-1$o $2n+1$, o ambos se encuentran entre los números elegidos. Después de sustituir cada número con su opuesto (si es necesario) podemos asumir (en todos los restantes casos) $2n+1$ es uno de los números elegidos.

Caso 2. Tanto en $-2n-1$ $2n+1$ están entre los números elegidos. Es mejor para ilustrar este caso con un ejemplo de la primera. Decir $n=3$, por lo que consideramos el intervalo de $[-7,..,7]$ y el tanto $-7$ $7$ están entre los números elegidos. Entonces (suponiendo que la declaración que estamos tratando de demostrar que eran falsas) no es posible que tanto $-6$ $-1$ son elegidos (desde entonces $-6+(-1)+7=0$). Más en general, podría haber más de un número elegido en cada par $\{-6,-1\}$, $\{-5,-2\}$, $\{-4,-3\}$, $\{3,4\}$, $\{2,5\}$, $\{1,6\}$. Por lo tanto, no podría ser en la mayoría de los tres números elegidos en $[-6,..,-1]$ y en la mayoría de los tres en $[1,..,6]$, y estos números juntos con $-7$ $7$ hacer en la mayoría de las $8$ elegido los números, pero los números elegidos debían ser $2n+3=9$, una contradicción. Claramente esto funciona en general: Si $-2n-1$ $2n+1$ están entre los números elegidos, a continuación, existen en la mayoría de las $n$-muchos números elegidos en $[-2n,..,-1]$, en la mayoría de las $n$-muchos de ellos en $[1,..,2n]$, y esto haría que en la mayoría de las $2n+2$ total, una contradicción.

Así, en todos los demás casos podemos suponer que la $2n+1$ es elegido, sino $-2n-1$ no lo es.

Caso 3. En la mayoría de uno de los números de $-2n$ $2n$ es elegido. Este es un tratamiento muy parecido Caso 1: Restringir nuestra atención en el intervalo de $[−2(n−1)−1,..,2(n−1)+1]$, donde tenemos al menos $2(n−1)+3$ números elegidos, y aplicar la hipótesis de inducción.

Caso 4. Tanto en $-2n$ $2n$ son elegidos. Este es tratada similar a la del Caso 2. Por eso, $2n+1$ $\pm 2n$ son elegidos. El número de $n$ puede ser elegido. En la mayoría de las $n$-la cantidad de números en $[-2n,..,-1]$ puede ser elegido, y esto incluye el número elegido $-2n$. En la mayoría de las $(n-1)$-la cantidad de números puede ser elegido en $[1,..,n-1]\cup[n+1,..,2n-1]$. Esto hace que en total en la mayoría de las $3+1+n-1+n-1=(2n+2)$-la cantidad de números, una contradicción, lo que completa la prueba. (El último recuento una vez más en una forma ligeramente diferente: Los números de $2n+1$ $2n$ son elegidos, y $n$ puede ser elegido. En la mayoría de los $n$-muchos de ellos en $[-2n,..,-1]$ (incluyendo el número de $-2n$) y en la mayoría de las $(n-1)$-muchos de ellos en $[1,..,n-1]\cup[n+1,..,2n-1]$, esto hace que $3+n+n-1=2n+2$ números en la mayoría.)

Nota. La suposición de que los extremos son impares es importante. De hecho, podríamos recoger cuatro números de $\{-2,-1,1,2\}$ $[-2,..,2]$ sin triple entre ellos, que resume a $0$. Del mismo modo podemos elegir seis números de $\{-4,-3,-2,2,3,4\}$ $[-4,..,4]$ con ninguna de suma cero triple. Esto parece generalizar, $[-2n,..,-n]\cup[n,..,2n]$ $(2n+2)$- la cantidad de números en $[-2n,..,2n]$ con ninguna de suma cero triple.

Answer 2

Cuando usted escoge $2n+3$ elementos de $[-2n-1,2n+1]$, se puede considerar dos casos:

• Tienes que elegir el subrango $[-2n-1, 1]$ (que contiene exactamente $2n+3$ elementos) y se puede decir que $$-1 + 0 + 1 = 0$$ y del mismo modo es el caso cuando usted escoge el subrango $[-1, 2n+1]$. Así, recogiendo cualquier subrango de $[-2n-1,2n+1]$ que contiene $2n+3$ elementos, se puede afirmar que $-1 + 0 + 1 = 0$ y $-1$, $0$, $1$ están incluidos.
• Usted no escoge un subrango: los elementos son seleccionados al azar. Usted tiene al menos un entero positivo y uno negativo. El uso de la caja, se puede decir que, la elección de otros dos elementos, a menos que usted escoja uno distinto de cero elementos. Sin pérdida de generalidad, supongamos que usted elija un número positivo $c$. Intuitivamente, se puede probar que existen dos número negativo $a$, $b$ tal que $a + b = -(c)$. Finalmente, $$a+b+c= 0$$ y listo.

Este es un boceto, y no estoy totalmente seguro acerca de su exactitud, ni creo que puede ser considerada como una verdadera prueba.