Subset Sum Problem

208 Views Asked by At

I recently saw the following problem, and I'm exploring the possibility of generalising it in various directions.

Consider a collection of $n$ cubic blocks with side lengths $1,2,\ldots,n$. It is easy to find conditions on $n$ such that the collection can be split into two (or more) sub-collections so that that each sub-collection can be stacked to create a tower of the same height. I won't give away how to do this in case you want to explore this relatively straightforward problem yourself.

In fact, you can split the collection in two so that both sub-collections are the same surface area. This is harder, but possible. Again, I won't give away the approach in case you want to think about this yourself.

I've struck problems when considering two (or more) sub-collections that have the same total volume. I suspect that this can be never done, but I'm not sure of the best way to prove this. I've tried exploring the generating function,

$$(1+x^{1^3})(1+x^{2^3})\cdots(1+x^{n^3}).$$

However, while this seems good at showing that something can't be done, it appears to be less useful in proving that it can never be done. Basically, I'd have to show that the coefficient of $x^{n^2(n+1)^2/8}$ is always zero. Does anyone know a nice strategy for showing this?

1

There are 1 best solutions below

4
On BEST ANSWER

I found some counterexamples, for example:

$3^3 + 5^3 + 6^3 + 7^3 + 10^3 + 11^3 = 1^3 + 2^3 + 4^3 + 8^3 + 9^3 + 12^3 = 3042$

$3^3 + 4^3 + 5^3 + 6^3 + 8^3 + 10^3 + 11^3 + 12^3 + 13^3 = 1^3 + 2^3 + 7^3 + 9^3 + 14^3 + 15^3 = 7200$

$1^3 + 2^3 + 4^3 + 7^3 + 8^3 + 11^3 + 13^3 + 14^3 = 3^3 + 5^3 + 6^3 + 9^3 + 10^3 + 12^3 + 15^3 = 7200$