12
$\begingroup$

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?

Thanks in Advance.

$\endgroup$
4
  • 1
    $\begingroup$ Nice question. And I am wondering if such groups are unique $\endgroup$ Feb 18, 2017 at 17:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – Peter
    Feb 18, 2017 at 17:08
  • 1
    $\begingroup$ If these three groups exist, then the sum of their elements should be $60147$ $\endgroup$ Feb 18, 2017 at 17:10
  • $\begingroup$ related problem : en.m.wikipedia.org/wiki/Subset_sum_problem $\endgroup$ Feb 18, 2017 at 18:00

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .