
On the NRICH forum, David asks, in essence,
Consider the set, S, of all fivedigit numbers formed by permuting the digits 1,2,3,4,5. The sum of squares of these 120 numbers is 156226437720. Prove that you can find a subset, T, of S such that the sum of the squares of the elements of T is 78113218860, which is half the sum of the squares of the elements of S. Then set S is partitioned into two sets, T and ST, such that the two partitions have equal sums of squares of their elements.
My answer to David's question begins with a lemma.
Lemma: The sum, and the sum of squares, of elements of the following sets are equal: {abc, bca, cab}; {acb, bac, cba}
Here, we are letting abc, bca, etc. represent the decimal digits a, b, and c in that order, using decimal place value. In other words, abc represents ax�+bx+c, where x=10. In fact, the lemma is true regardless of the value of x. Here I will restate the lemma to make it more general in this way...
Let set A={ax�+bx+c, bx�+cx+a, cx�+ax+b}, and
let set B={ax�+cx+b, bx�+ax+c, cx�+bx+a}.
The sum of the elements of A is D=(a+b+c)x�+(a+b+c)x+(a+b+c), and the sum of the elements of B is the same. So our lemma is half proved. Now let's consider the sum of the squares of the elements of A and of B...
The squares of the elements of A are
a²x^{4} + 2abx³ + (b²+2ac)x² + 2bcx + c²,
b²x^{4} + 2bcx³ + (c²+2ba)x² + 2cax + a²,
c²x^{4} + 2cax³ + (a²+2cb)x² + 2abx + b².
The squares of the elements of B are
a²x^{4} + 2acx� + (c²+2ab)x² + 2cbx + b²,
b²x^{4} + 2bax� + (a²+2bc)x² + 2acx + c²,
c²x^{4} + 2cbx� + (b²+2ca)x² + 2bax + a².
If you find the sum of the squares of either set, you get
E=(a�+b�+c�)x^{4} + (2ab+2bc+2ca)x� + (a�+b�+c�+2ab+2bc+2ca)x� + (2ab+2bc+2ca)x + (a�+b�+c�)
Proof that set S can be partitioned into sets with equal sumofsquares:
As you read this proof, keep in mind the symbols from the lemma,
D = sum of {abc, bca, cab} = sum of {acb, bac, cba}
E = sum of squares of both sets
that is,
D=(a+b+c)x� + (a+b+c)x + (a+b+c),
E=(a�+b�+c�)x^{4} + (2ab+2bc+2ca)x� + (a�+b�+c�+2ab+2bc+2ca)x� + (2ab+2bc+2ca)x + (a�+b�+c�)
Now, for the proof itself...
Partition the elements of S into 6element subsets S_{1}, S_{2}, etc. such that S_{i}={nmabc, nmacb, nmbca, nmbac, nmcab, nmcba}, where n,m,a,b,c represent the five digits that are permuted to form S. Now, partition S_{i} into two sets S_{i1} and S_{i2} as follows:
S_{i1}={nmabc, nmbca, nmcab}
S_{i2}={nmacb, nmbac, nmcba}
The sum of the squares of the elements of S_{i1} is nm000� + 2*nm000*D + E, which equals the sum of the squares of the elements of S_{i2}.
Now, let S_{1} be the union of all the sets S_{i1}, and let S_{2} be the union of all the sets S_{i2}. Since, for all i, the sum of squares of S_{1i} equals the sum of squares of S_{i2}, it follows that the sum of squares of S1 equals the sum of squares of S_{2}.
So am I!
Being rather dull, myself, and having a number of speedy computers at my disposal, I decided to partition the set, S, in a natural way (hint! hint!) and found that the sum of squares of the elements of the two partitions are indeed the same.
But wait! There's more!
The sum of cubes of the two partitions is the same. The sum of fourth powers is the same. The sum of fifth powers is the same. I kept multiplying these 120 number by themselves until I discovered the highest power for which the sum of this power of each of the elements of the two partitions is the same. That power is 9! (No, not 9 factorial, I'm just overjoyed, that's all.)
Then I started investigating other numbers of digits, besides 5 digits. That is, what is the largest power for which this natural parition of the set of permutations of the 3digit number, 123, have equal sums? Turns out this power is 2.
For 4digit numbers, 1234 and its permutations, the sum of fifth powers of the partitions of the set are equal.
For 5digit numbers, 9th powers are equal, as I said so excitedly, above.
And for 6digit numbers, 14th powers are equal.
This is true, by the way, not just for permutations of 123456, but for permutations of any digits I care to choose. The digits have to be distinct, however, because otherwise this "natural" partition of permutations can't be found. (Was that another hint? I think it was!)
In summary, for an ndigit number with distinct digits, the set of numbers formed by permuting those digits can be partitioned into two sets with equal k'th powers according to the following table:
n k no larger than 2 0 3 2 4 5 5 9 6 14
What was this "natural" partition of the set of permutations of an ndigit number that I kept hinting at? Perhaps you've guessed it. The permutations of the digits abc can be divided into "even" and "odd" permutations, depending on the number of pairwise interchanges of the digits it takes to get to the given permutation. In the lemma, above, it is clear that the two sets of permutations of abc are the even and odd permutations of these three digits. The sums of the k^{th} powers of the elements of these two sets are equal when k=0, 1, or 2. As the lemma shows, this is true regardless of the number base used to represent the value of the digits abc. (This base is "x" in the lemma.)
This observation can be extended, as follows...
Let S(n) be the set of permutations of the number 1234...n (in some base larger than n). If you partition S(n) into subsets S(n)_{even} and S(n)_{odd}, then it turns out that the sum of k^{th} powers of the elements of S(n)_{even} and the sum of k^{th} powers of the elements of S(n)_{odd} are equal when k is less than or equal to some number.
I've done some experiments using a spreadsheet, using permutations of as many as six digits in various bases, and I would conjecture that the sum of k^{th} powers of the elements of S(n)_{even} is equal to the sum of k^{th} powers of the elements of S(n)_{odd} when k≤(n2)(n+1)/2. For example, if my conjecture is right, the set of permutations of the digits 1234567 can be divided into two sets (even and odd permutations) such that the sums of the 20^{th} powers of the elements of the two sets are equal!
. . . . . .
. . . . . .
The webmaster and author of this Math Help site is Graeme McRae.