Un subconjunto cuya suma de elementos es divisible por $n$

Question

Dejemos que $a_1,a_2,\ldots,a_n \in (0,2n)$ sea $n$ números enteros distintos $(n \geq 4)$ . Demostrar que existe un subconjunto no vacío del conjunto $\{a_1,\ldots,a_n\}$ cuya suma de elementos es divisible por $2n$ .

Dado que hay $n$ enteros distintos en $(0,2n)$ debe haber un número en $(0,n]$ y un número diferente en $[n,2n)$ en el conjunto $\{a_1,\ldots,a_n\}$ o ambos son $n$ . ¿Podemos utilizar esto para demostrar que existe un subconjunto de $\{a_1,\ldots,a_n\}$ cuya suma de elementos es divisible por $2n$ ?

Answer 1

Se nos da $n$ elementos no nulos del grupo (aditivo) $\mathbb Z_{2n}$ y estamos tratando de demostrar que algunos de ellos se suman al elemento cero.

Esto se puede hacer trivialmente si tenemos un elemento junto con su inverso en nuestra colección, por lo que podemos asumir que nuestros elementos son específicamente $$\pm 1, \pm 2, \ldots , \pm (n-1) , n ,$$ para alguna elección de signos $\pm$ . Como podemos tomar negativos de todo sin cambiar nada, podemos suponer además que $n-1$ viene con un signo más. En ese caso, hemos terminado si también tenemos $+1$ (ya que $1+(n-1)+n=0$ ), así que ahora la situación es que tenemos $$-1, \pm 2, \pm 3 , \ldots , \pm (n-2), n-1 , n .$$ También estamos en casa si tenemos $-(n-2)$ (ya que $-1-(n-2)+(n-1)=0$ ), por lo que basta con considerar la colección $$-1,-2,\pm 3, \ldots , \pm (n-3), n-2, n-1, n .$$ Podemos continuar en este estilo y llegar finalmente al siguiente escenario específico (para impar $n$ ; si $n$ es par, entonces funciona un argumento similar y de hecho aún más fácil): $$-1,-2, \ldots , -m+1, \pm m, m+1, m+2 ,\ldots , 2m-1 ; \quad\quad n=2m-1$$ Ahora es muy fácil producir una suma cero (con tres términos) en los dos casos restantes (los dos signos posibles de $m$ ).

Answer 2

También se puede hacer con un encasillamiento un tanto rebuscado. Probemos primero que dado $n-1$ números distintos en $(0,2n)$ podemos encontrar varios de ellos cuya suma es divisible por $n$ . Colóquelos en algún orden y considere $n-1$ números $a_1, a_1+a_2,\dots, a_1+\dots+a_{n-1}$ . Si uno de ellos es divisible por $n$ hemos terminado. Si dos de ellos tienen el mismo resto modulo $n$ hemos terminado. Por lo tanto, debemos tener todos los posibles restos no nulos que ocurren exactamente una vez, lo que nos obliga a tener un resto muy particular de la suma $(n-1)a_1+(n-2)a_2+\dots+a_n$ . Sin embargo, si intercambiamos dos números adyacentes, este resto cambia por su diferencia, por lo que si tenemos 2 restos diferentes entre $a_j$ podemos evitar fácilmente este escenario. En caso contrario, todos los números tienen el mismo resto, lo que obliga a que el mayor sea al menos $1+n(n-2)>2n$ si $n\ge 4$ .

Consideremos ahora dos casos:

1) $n$ está en el conjunto. A continuación, elige el subconjunto de otros números cuya suma sea divisible por $n$ y, si no es divisible por $2n$ , unirse a $n$ a ella.

2) $n$ no está ahí. Entonces hay un par $k,2n-k$ para algunos $k\in[1,n-1]$ y no hay nada que hacer.