### Usenet Newsgroups

# Rec.Puzzles Hall of Fame

The rec.puzzles Hall of Fame is a compilation of over 500 of the most popular puzzles that have been posted and discussed in the rec.puzzles newsgroup. In most cases a detailed solution has been provided. Many of these puzzles also appear in Braingle's own collection.

Categories

## 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))

Solution

## Follow Braingle!