Olimpiada de Matemáticas de Alemania Occidental 1981

Question

Si$n=2^k$ entonces de un conjunto de elementos$2n-1$ podemos seleccionar los números$n$ para que su suma sea divisible entre$n$.

Lo dividí en dos casos, primero si alguno$n$ de ellos tiene el mismo mod de resto$n$ que hemos terminado, en el otro caso estoy teniendo dificultades.

¿Qué pasa si$n$ es un número natural?

Answer 1

Inducción en $k$:

Las reivindicaciones está claro para $n=2^0$.

Deje $k>0$, suponga que la demanda tiene por $n'=2^{k-1}$ y deje $S$ ser un conjunto de $2n-1$ enteros. Por hipótesis de inducción, podemos recoger $n'$ números de la primera $2n'-1$ elementos de $S$, de tal forma que su suma es múltiplo de $n'$. Después de la eliminación de estos de $S$, todavía tenemos $2n-1-n'=3n'-1$, por lo que desde el primer $2n'-1$ de estos, podemos volver a coger $n'$ tales que su suma es múltiplo de $n'$. Después de la eliminación de estos así, nos quedamos con $2n-1-2n'=2n'-1$ números y de nuevo podemos recoger $n'$ elementos tales que su suma es múltiplo de $n'$.

Así que ahora tenemos tres subconjuntos disjuntos de a $S$ del tamaño de la $n'$ cada uno y de tal manera que cada una de las sumas a un múltiplo de $n'$. Tenga en cuenta que un múltiplo de $n'$ es un múltiplo de a $n$ o de un extraño múltiples de $n'$; uno de estos dos tipos deben ocurrir al menos dos veces entre los tres subconjuntos. Mediante la combinación de dos tales como subconjuntos, llegamos a un conjunto de tamaño $n$ con la suma de un múltiplo de $n$.