Brain Teasers
Brain Teasers Trivia Mentalrobics Games Community
Personal Links
Your Friends
More Community
Newsgroups
Wiki
Teaser Comments
Trivia Comments

User Rankings
Search for User
Add to Google delicious Add to del.icio.us

More ways to get Braingle...
rss

Braingle Time
2:02 pm

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.

   
rec.puzzles
Newsgroup
FAQ
Hall of Fame
alt.brain.teasers
Newsgroup
FAQ
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


Users in Chat : None 

Online Now: 18 users and 630 guests

Copyright © 1999-2014 | Updates | FAQ | RSS | Widgets | Links | Green | Subscribe | Contact | Privacy | Conditions | Advertise

Custom Search





Sign In A Create a free account