# Divide $1^2,2^2..,81^2$ numbers into 3 groups.

Given $1^2,2^2,3^2,.....,81^2$ numbers. How can I divide them into $3$ groups with $27$ numbers in each so that they have the same sum.

Is there any algorithm to solve this task?

• Nice question. And I am wondering if such groups are unique Feb 18, 2017 at 17:04
• @Display name I agree that I missed that the groups have to be of equal sizes. But concerning the argument that the OP demands an algorithm : Brute force is always a possibility (if a solution actually exists), so I disagree concerning this. The question does not demand an efficient algorithm. Feb 18, 2017 at 17:08
• If these three groups exist, then the sum of their elements should be $60147$ Feb 18, 2017 at 17:10
• related problem : en.m.wikipedia.org/wiki/Subset_sum_problem Feb 18, 2017 at 18:00

We take a sequence of 9 consecutive squares, $n^2, (n+1)^2,...,(n+8)^2$. Then, $$(n+0)^2 + (n+4)^2 + (n+8)^2 = 3n^2 + 24n + 80$$ $$(n+1)^2 + (n+5)^2 + (n+6)^2 = 3n^2 + 24n + 62$$ $$(n+2)^2 + (n+3)^2 + (n+7)^2 = 3n^2 + 24n + 62$$ So, we can divide 27 squares into 3 groups of equal sum, by rotating the dominant group out of these 9. We can then divide total 81 into 3 groups of 27 each, which in turn can be divided into 3 groups of 9 with equal sum each. All that is left is to take one 9-group each from these 3 sets.

A solution is :

? print(x)
[1, 4, 9, 14, 15, 16, 19, 22, 26, 27, 31, 36, 38, 41, 44, 48, 49, 51, 55, 63, 67
, 68, 69, 71, 72, 74, 77]
? print(y)
[7, 8, 10, 13, 17, 20, 28, 29, 32, 33, 34, 35, 39, 40, 43, 47, 52, 53, 54, 57, 5
9, 60, 61, 64, 79, 80, 81]
? print(z)
[2, 3, 5, 6, 11, 12, 18, 21, 23, 24, 25, 30, 37, 42, 45, 46, 50, 56, 58, 62, 65,
66, 70, 73, 75, 76, 78]
?

• Should be comment as OP specifically asked for an algorithm
– Teoc
Feb 18, 2017 at 17:03
• I think, there is a method to produce the vectors systematically, but I have no idea how to do this. Feb 18, 2017 at 18:12
• It took me great effort and several tries to get a solution! I guess, this is not the only one. Feb 18, 2017 at 18:12
• I think this question asks for square numbers only, not for a number like 14. Feb 18, 2017 at 18:15
• @DougSpoonwood, and in fact the sums of the squares of the numbers in each of the three lists are equal. Feb 18, 2017 at 18:34

For a set $$X$$, let us denote mass of $$X$$ by $$m(X)=\sum\limits_{x\in X} x$$. Note that$$1^2 + 2^2+ 3^2 + \cdots + 81^2 = \frac{81\cdot 82 \cdot 163}{6} =180441.$$Thus each of our sets should have mass $$60147$$. Our goal is to find $$3$$ sets $$A$$, $$B$$ and $$C$$ such that $$|A|=|B|=|C|=27$$ and $$m(A)=m(B)=m(C)=60147$$. Let us split the set $$X=\{1^2,2^2,\ldots,81^2\}$$ into 3 as follows. Let$$A=\{1^2,4^2,7^2,10^2,\ldots,79^2\} \rightsquigarrow m(A)=57942.$$$$B=\{2^2,5^2,8^2,11^2,\ldots,80^2\} \rightsquigarrow m(B)=60129.$$$$C=\{3^2,6^2,9^2,12^2,\ldots,81^2\} \rightsquigarrow m(C)=62370.$$Among all the above sets we see that the $$m(B)$$ is closest to $$60147$$ and so we work with $$B$$. We try to increase $$m(B)$$ by $$18$$. That means we have to swap elements from other sets. Swapping single element wont work since $$x^{2}-y^2=18$$ doesn't have any integral solution.

So our next idea is to see whether we can increase the mass by $$18$$ by swapping $$2$$ elements. That is can we find $$a,b\in B$$ and $$c,d\in A\cup C$$ such that $$a^{2}+b^{2}+18=c^{2}+d^{2}$$. And this does seem to have a solution. Take $$a=2,b=14$$ and $$c=7,d=13$$. Thus $$\{2,14\}\in B$$ will be swapped to $$\{7,13\}\in A$$. Thus our set $$B$$ is now$$B=\{7^2,5^2,8^2,11^2,13^2,17^2,20^2,23^2,\ldots,80^2\}$$and $$m(B)=60147$$. We have swapped elements from $$A$$ and $$B$$. $$m(B)$$ has increased by $$18$$ and so $$m(A)$$ will reduce by $$18$$. Thus $$m(A)=57924$$ and$$A=\{1^2,4^2,2^2,10^2,14^2,16^2,19^2,\ldots,79^2\}$$We have to increase mass of $$A$$ by $$2223$$ and decrease mass of $$C$$ by $$2223$$. Note that $$2223=48^2-9^2$$. This gives us an idea. If i swap $$9^2$$ and $$48^2$$ then i am done. But $$9^2$$ and $$48^2$$ are in $$C$$, so that means, somehow if i shift the element $$9^2$$ to $$A$$, then i can swap $$9^2$$ and $$48^2$$ and achieve my goal.

Now note that $$981=9^2+18^2+24^2=2^2+4^2+31^2$$. This means we can swap the elements $$9^2,18^2,24^2\in C$$ with $$2^2,4^2,31^2\in A$$. The sum remains unaltered. Now swap the elements $$48^2\in C$$ and $$9^2\in A$$ and we are done.

• Amazing work! +1 Nov 4, 2020 at 16:49
• @cosmo5 : thanks for the nice comments :)
– C.S.
Nov 4, 2020 at 23:12