Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Squares > Squares of Permutations of Digits

On the NRICH forum, David asks, in essence,

Consider the set, S, of all five-digit 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 S-T, 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²x4 + 2abx³ + (b²+2ac)x² + 2bcx + c²,
b²x4 + 2bcx³ + (c²+2ba)x² + 2cax + a²,
c²x4 + 2cax³ + (a²+2cb)x² + 2abx + b².

The squares of the elements of B are

a²x4 + 2acx� + (c²+2ab)x² + 2cbx + b²,
b²x4 + 2bax� + (a²+2bc)x² + 2acx + c²,
c²x4 + 2cbx� + (b²+2ca)x² + 2bax + a².

If you find the sum of the squares of either set, you get

E=(a�+b�+c�)x4 + (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 sum-of-squares:

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�)x4 + (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 6-element subsets S1, S2, etc. such that Si={nmabc, nmacb, nmbca, nmbac, nmcab, nmcba}, where n,m,a,b,c represent the five digits that are permuted to form S.  Now, partition Si into two sets Si1 and Si2 as follows:

Si1={nmabc, nmbca, nmcab}
Si2={nmacb, nmbac, nmcba}

The sum of the squares of the elements of Si1 is nm000� + 2*nm000*D + E, which equals the sum of the squares of the elements of Si2.

Now, let S1 be the union of all the sets Si1, and let S2 be the union of all the sets Si2.  Since, for all i, the sum of squares of S1i equals the sum of squares of Si2, it follows that the sum of squares of S1 equals the sum of squares of S2.

More about this puzzle

This puzzle appeared on the NRICH forum, posed by David.  Others on the forum, whose initials are A and D, asked clarifying questions.  I replied to all of them saying: from your questions, I can see that you are all interested in this problem.

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 3-digit number, 123, have equal sums? Turns out this power is 2.

For 4-digit numbers, 1234 and its permutations, the sum of fifth powers of the partitions of the set are equal.

For 5-digit numbers, 9th powers are equal, as I said so excitedly, above.

And for 6-digit 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 n-digit 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 n-digit 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 kth 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 kth powers of the elements of S(n)even and the sum of kth 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 kth powers of the elements of S(n)even is equal to the sum of kth powers of the elements of S(n)odd when k≤(n-2)(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 20th powers of the elements of the two sets are equal!

Internet references

 . . . . . .

Related pages in this website

 . . . . . .

 

The webmaster and author of this Math Help site is Graeme McRae.