En un conjunto de números enteros de $n$ donde ningún subconjunto no vacío adecuada se resume a un múltiplo de $n$, todos los elementos son congruentes

Question

Quiero probar lo siguiente:

Deje $A$ ser un conjunto de $n$ enteros positivos tales que para cualquier subconjunto $M$, $M$ ni vacío ni igual a $A$, la suma de los elementos de $M$ no es divisible por $n$. Demostrar que los elementos de la $A$ son todos congruentes $\pmod n.$

El $n=2$ caso es evidente (tanto el número debe ser impar). Para $n=3$, la única manera posible de residuos son de 1,2, y es obvio que si los residuos están presentes, entonces su suma es divisible por 3, contradicción. $n=4$ es de nuevo fácilmente comprobable por caja (ya que no puedes tener ambos 1 y 3 como residuos en el mismo conjunto.)

Sin embargo, no sé cómo uno podría generalizar esta. Para empezar, si $r$ es un residuo $\pmod n$, usted no puede incluir $r$ $n-r$ como residuos en el mismo conjunto, logrando así, que tal conjunto tiene en la mayoría de las $\left \lfloor \dfrac{n+1}{2} \right \rfloor$ distintos residuos.( $\lfloor a\rfloor$ es la parte entera de a $a$)

¿Cómo puedo finalizar la prueba?

Answer 1

La lista de los $n$ elementos de $A$$a_1, a_2, \ldots, a_n$. Vamos a demostrar una adecuada subconjunto no vacío de ellos sumas a $0$ mod $n$, o bien todos ellos son congruentes. Considerar las sumas parciales $s_i = a_1 + a_2 + \cdots + a_i$$0 \le i \le n$.

Por el principio del palomar, dos de estos $n+1$ sumas parciales caer en el mismo residuo de la clase de mod $n$, decir $s_i = s_j$. A menos $i = 0$$j = n$, que se hacen porque llegamos $a_{i+1} + a_{i+2} + \cdots + a_{j} \equiv 0 \pmod{n}$. Por lo tanto, asumir que $s_0 \equiv s_n \equiv 0$, pero que el $n-1$ otras sumas parciales son exactamente las $n-1$ cero residuos de mod $n$.

Ahora para cualquier $1 \le i \le n-1$, considere la posibilidad de cambiar $a_{i}$$a_{i+1}$, la formación de los nuevos importes parciales $s_0, s_1, s_2, \ldots, s_{i}', s_{i+1}', \ldots, s_n$. Si esto hace que dos de las nuevas sumas parciales para coincidir mod $n$, nos vuelve a hacer como antes. Así que podemos asumir que el cobro de las sumas parciales de la nueva secuencia todavía son todos distintos, específicamente: $\{s_i', s_{i+1}'\} \equiv \{s_i, s_{i+1}\}$. Restando $s_{i-1}$, $\{s_i' - s_{i-1}, s_{i+1}' - s_{i-1}\} \equiv \{s_i - s_{i-1}, s_{i+1} - s_{i-1}\}$. Es decir, $$ \{a_{i+1}, a_{i+1} + a_i\} \equiv \{a_i, a_i + a_{i+1}\}. $$ En general, si $\{q,r\} = \{s,t\}$, $q = s$ $r = t$ o $q = t$$r = s$. En este caso, se $a_{i+1} \equiv a_i + a_{i+1}$ o $a_{i+1} \equiv a_i$. Si $a_{i+1} \equiv a_i + a_{i+1}$,$a_{i} \equiv 0$, lo $\{a_{i}\}$ es un elemento del conjunto que suma a $0$ mod $n$. De lo contrario, $a_i \equiv a_{i+1} \pmod{n}$.

La aplicación de esta para todos los $i$, obtenemos que $a_1 \equiv a_2 \equiv \cdots \equiv a_n$. (También podemos notar que este residuo debe ser relativamente privilegiada para $n$.) $\square$