Partición en subconjuntos con la misma suma

Question

Números enteros positivos $ a_1, a_2,\ldots, a_n $ tal que $ a_k\leq k $ y la suma de todos estos números es par e igual a $ 2S $ . Demostrar que el número se puede dividir en dos grupos, la cantidad de cada uno de los cuales es igual a $ S $ .

Parece que tengo que usar la inducción, pero no puedo averiguar cómo... Por favor, dame una pista.

Answer 1

Me parece que se puede utilizar la inducción y la siguiente transformación sobre las secuencias $(a_1,\ldots,a_n)$ de enteros positivos con $a_i\le i$ e incluso la suma: $$ (a_1,\ldots,a_{n-1},a_n)\mapsto \begin{cases} (a_1,\ldots,a_{n-2})&\text{if}\quad a_{n-1}=a_n,\\ (a_1,\ldots,a_{n-2},|a_n-a_{n-1}|)&\text{if}\quad a_{n-1}\not=a_n. \end{cases} $$ La secuencia resultante es del mismo tipo y también tiene suma par. Esto puede continuar hasta que la secuencia desaparezca, lo que significa una expresión de la forma $\pm a_1\pm\cdots\pm a_n=0$ se formó.