Partition set into equal-sum subsets

Question

What is known about how to divide $\{1,4,9,16,...,81^2\}$ into $3$ equal-sum subsets with $27$ elements per subset?

Answer 1

This is a classic problem. There is a nice way to split the elements of $S=\{0,1,\cdots,b^k-1\}$ into $b$ sets $S_0,S_1,\cdots,S_{b-1}$ so that , for each $0 \leq j \lt k,$ the sum of $s^j$ is the same for each of the $S_i.$ It follows that the same is true if one replaces $s$ with $qs+r$ throughout.

That will do nicely for you with $(b,k,q,r)=(3,4,1,1)$ and you will have the sum of the cubes and first powers also equal.

LATER I didn't find a reference I really liked (though I know there are many good ones) so here is a (sketch of a) recipe (basically the classic method) which will give $2^{k-1}$ different ways to split the first $3^k$ non-negative integers into $3$ sets with equal sums of powers. You can easily shift everything up by $1$ if you like, but this way is particularly nice if you write things out base $3.$ Proving this works is a good exercise.

• For $k=1$ there is just one way $0\ |\ 1\ |\ 2$

• For $k=2$ take the matrix $\begin{bmatrix} 0 & 1 & 2 \\ 3 &4 &5 \\ 6 & 7 &8 \\ \end{bmatrix}$ and split into three parts taking in each part one thing from each row and column. Hence either

$0,4,8\ |\ 1,5,6\ |\ 2,3,7$ OR $0,5,7\ |\ 1,3,8\ |\ 2,4,6$

Either way, in each set $\sum s=12$.

• For $k=3$ take one or the other of the solutions above $a,b,c\ |\ d,e,f\ |\ g,h,i$ as the first row of a $3 \times 3$ matrix with $3^{k-2}$ things in each position:

$$\begin{bmatrix} a+0,b+0,c+0 & d+0,e+0,f+0 & g+0,h+0,i+0 \\ a+9,b+9,c+9 & d+9,e+9,f+9 & g+9,h+9,i+9 \\ a+18,b+18,c+18 & d+18,e+18,f+18 & g+18,h+18,i+18 \\ \end{bmatrix}$$

All together you have the integers from $0$ to $26$. Split those into 3 parts taking in each part one triple from each row and column. There are two ways to do that so four in all (since there were two solutions to start with). For all of them, $\sum s^0=9, \sum s^1=39, \sum s^2=1092$

• For $k=4,$ take one of the four solutions above as the first row of a $3 \times 3$ matrix with $3^{k-2}$ things in each position:

$\begin{bmatrix} a,b,\cdots,i & j,k,\cdots ,r& s,t,\cdots, \alpha \\ a+27,b+27,\cdots,i+27 & j+27,k+27,\cdots ,r+27& s+27,t+27,\cdots, \alpha+27 \\ a+54, b+54,\cdots,i+54 & j+54,k+547,\cdots ,r+54& s+54,t+54,\cdots, \alpha+54 \\ \end{bmatrix}$

All together you have the integers from $0$ to $80$. Split those into 3 parts taking in each part one $9$-tuple from each row and column. There are two ways to do that so eight in all (since there were four solutions to start with). For all of them, $\sum s^0, \sum s^1, \sum s^2$ and $\sum s^3$ are the same.