Partitioning the set of the first $n$ cubes into 2 subsets with the same total sum and number of elements.

Question

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.

Answer 1

2000 is just smoke and mirrors. Your observation is explained by a few simple facts:

1. A fourth derivative of any cubic polynomial (for example, $x^3$) is zero.
2. Same thing with finite difference derivative.
3. 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.
4. $2^4=16$
5. 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.