Amassando ideas

Resumen del enunciado

Dado un entero $n$ entre $1$ y $10^6$, determinar si es posible partir el conjunto ${1, 2, \ldots, n}$ en dos tal que la suma de los elementos de cada parte sea la misma, y si es posible, imprimir los conjuntos.

No todo es posible

La suma de todos los elementos es $1 + 2 + \ldots + n = \sum_{i=1}^n = \frac{n(n+1)}{2}$ (click aquí si no me crees), por lo que los elementos de cada una de las dos partes deben sumar $\frac{n(n+1)}{4}$. Para eso podemos calcular $n(n+1)$ y verificar si es múltiplo de $4$. Si no lo es imprimimos “NO” y detenemos el programa. En caso contrario imprimimos “YES” y seguimos con la generación de los conjuntos.

¡Acumula lo que puedas!

La estrategia consiste en mantener un contador $S$ inicializándolo en $0$ y recorrer con un bucle todos los enteros desde el $n$ hasta el $1$. En cada iteración, verificamos si $S$ más el índice $k$ supera $\frac{n(n+1)}{4}$, la mitad de la suma total de los elementos. Si no lo hace, entonces añadimos $k$ a $S$ y agregamos $k$ a uno de los conjuntos. En caso contrario, lo agregamos a la otra.

Notar que con este método $S$ nunca supera la suma deseada, porque sólo se suma en $k$ cuando $S+k$ es menor o igual que dicha suma. ¿Pero es posible que $S$ sea menor que $\frac{n(n+1)}{4}$ después de ejecutar el bucle?

Para demostrar que $S$ siempre será igual que $\frac{n(n+1)}{4}$, observemos que siempre existe una iteración con el índice $k$ tal que $S + k$ sea mayor que $\frac{n(n+1)}{4}$, porque si no fuese así podríamos sumar todos los números a $S$ y $S$ terminaría siendo igual que $\frac{n(n+1)}{2}$ que claramente es mayor que $\frac{n(n+1)}{4}$. En dicha iteración, se tiene que $k > \frac{n(n+1)}{4} – S$, por lo que existe un número $l \in [0,k)$ tal que $S + l = \frac{n(n+1)}{4}$.

¿Por qué no al revés?

Imagina el caso $n = 7$. La suma total es de $\frac{n(n+1)}{2} = 28$ por lo que recorrer los números desde el menor haría que $S = 6$ después de $3$ iteraciones y por tanto $\frac{n(n+1)}{4} – S = 8$, lo que no es posible porque $n = 7$ y entre $4$ y $7$ no existen dos enteros distintos tales que su suma sea menor o igual que $8$. Después de $4$ iteraciones $S = 10$ por lo que $\frac{n(n+1)}{4} – S = 4$ y todos los números que podríamos sumarle a $S$ son mayores que $4$.