lotus

previous page: 87 arithmetic/sum.of.cubes.p
  
page up: Puzzles FAQ
  
next page: 89 arithmetic/tests.for.divisibility/eleven.p

88 arithmetic/sums.of.powers.p




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:













TOP
previous page: 87 arithmetic/sum.of.cubes.p
  
page up: Puzzles FAQ
  
next page: 89 arithmetic/tests.for.divisibility/eleven.p