Partitioning the set of the first $n$ cubes into 2 subsets with the same total sum and number of elements. I have been experimenting with some code I wrote to verify that the numbers $1^3, 2^3, ...,2000^3
$ can be split into 2 subsets, each with $1000$ elements and the same sum. I then discovered that it seems that all of the integers of the form $2000n$ which I entered into my code can be split into subsets in this way and it seems that integers of the form $1000(2n+1)$ can be split up into subsets with the same number of elements and a difference between the subsets' sum of 4. I am interested to know the reason for this behaviour and which numbers have the property described.
 A: 2000 is just smoke and mirrors. Your observation is explained by a few simple facts:


*

*A fourth derivative of any cubic polynomial (for example, $x^3$) is zero.

*Same thing with finite difference derivative.

*You need two values of a function to obtain one value of a finite difference derivative. To obtain the second derivative, you need two of those, and so on.

*$2^4=16$

*2000 is divisible by 16.


The rest is simple. We arrange the first 16 cubes so as to mimic the $4^{th}$ numeric derivative:
$$1^3 - 2^3 - 3^3 + 4^3 - 5^3 + 6^3 + 7^3 - 8^3 - 9^3 + 10^3 + 11^3 - 12^3 + 13^3 - 14^3 - 15^3 + 16^3 = 0$$
Then we arrange the next 16 cubes in a similar pattern, and so on.

I never said that ranges $1..n$ with $n$ not divisible by 16 can't be split like that. In fact, many of them can. Then again, many others can't. Which is which?


*

*$n$ is odd: impossible, because you can't have two subsets with the same number of elements.

*$n$ is divisible by 2, but not by 4: impossible, because you have an odd numbers of odd terms, and so the total sum is odd, and hence can't be split in equal halves.

*$n=16k$: always possible, see above.

*$n=16k+4$: impossible for $n=4$, otherwise we split the first 20 terms as $\{1, 3, 5, 8, 9, 10, 12, 16, 18, 20\}$ and $\{2, 4, 6, 7, 11, 13, 14, 15, 17, 19\}$ (that's not the only solution), and the rest goes in chunks of 16 as above.

*$n=16k+8$: impossible for $n=8$, otherwise we split the first 24 terms as $\{1, 3, 5, 10, 11, 12, 13, 14, 15, 20, 22, 24\}$ and $\{2, 4, 6, 7, 8, 9, 16, 17, 18, 19, 21, 23\}$ (there are many other solutions, but this one looks particularly nice), and the rest goes in chunks of 16 as above.

*$n=16k+12$: we split the first 12 terms as $\{1, 2, 4, 8, 9, 12\}$ and $\{3, 5, 6, 7, 10, 11\}$, and the rest goes in chunks of 16 as above.


All in all, the split is possible for all numbers $n$ divisible by 4, except for 4 and 8, and impossible otherwise.
