Dado un entero entre y , determinar si es posible partir el conjunto 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 (click aquí si no me crees), por lo que los elementos de cada una de las dos partes deben sumar . Para eso podemos calcular y verificar si es múltiplo de . 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 inicializándolo en y recorrer con un bucle todos los enteros desde el hasta el . En cada iteración, verificamos si más el índice supera , la mitad de la suma total de los elementos. Si no lo hace, entonces añadimos a y agregamos a uno de los conjuntos. En caso contrario, lo agregamos a la otra.
Notar que con este método nunca supera la suma deseada, porque sólo se suma en cuando es menor o igual que dicha suma. ¿Pero es posible que sea menor que después de ejecutar el bucle?
Para demostrar que siempre será igual que , observemos que siempre existe una iteración con el índice tal que sea mayor que , porque si no fuese así podríamos sumar todos los números a y terminaría siendo igual que que claramente es mayor que . En dicha iteración, se tiene que , por lo que existe un número tal que .
¿Por qué no al revés?
Imagina el caso . La suma total es de por lo que recorrer los números desde el menor haría que después de iteraciones y por tanto , lo que no es posible porque y entre y no existen dos enteros distintos tales que su suma sea menor o igual que . Después de iteraciones por lo que y todos los números que podríamos sumarle a son mayores que .