## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 88 arithmetic/sums.of.powers.p

Partition 1,2,3,...,16 into two equal sets, such that the sums of the

numbers in each set are equal, as are the sums of their squares and cubes.

arithmetic/sums.of.powers.s

The solution is A = {1,4,6,7,10,11,13,16}
B = {2,3,5,8,9,12,14,15}

Let X+k be a set formed by adding k to all elements of X.

Then A+k and B+k have the property of satisfying i,ii and iii.

That means, any 16 numbers in A.P can be partioned in such a way to

satisfy i,ii and iii.

How do we arrive at the above solution without using a computer?

By the preceding discussion,

A1 = A-1 = {0,3,5,6,9,10,12,15}
B1 = B-1 = {1,2,4,7,8,11,13,14}

have the property of satisfying i,ii and iii.

Notice that all numbers of A1 have even number of 1's in binary and

all numbers of B1 have odd number of 1's in binary. Essentially the

above partition is a partition based on parity.

Observation:

Partition of (n+1) bit numbers based on parity into two

groups A and B (each consisting of 2^n elements) satisfies

sum of kth powers of elements of A = sum of kth powers of elements of B

for k=1,2,...,n. (The above puzzle is a special case n=3).

The above observation also holds for any radix. In radix r we will have

r groups.

Infact,

Any r^(n+1) terms in A.P can be partitioned into r groups (each of

r^n elements) such that sum of kth powers of all r groups is same (k=1,2,...,n)

Finding such groups with minimal number of elements (less than r^n) appears to

be more difficult!

ALL THIS APPEARS TO BE INTERESTING. IS IT A CONSEQUENCE OF A SIMPLE THEOREM OF

NUMBER THEORY? HOW DO I PROVE THIS?

Thanks in advance for any clues,

-- ramana@svl.cdc.com (Mr. Ramana (Indian analyst))

Continue to: