S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
It is currently Wed, 20 Aug 2014 19:31:16 UTC

All times are UTC [ DST ]




Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: partition
PostPosted: Mon, 21 Jul 2008 06:20:20 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sun, 4 May 2003 16:04:19 UTC
Posts: 2906
show that 0,1,...,2^k-1 can be partitioned into two equal sets S1 and S2 such that for any integer m<k, then:

Sum (i in S1) i^m = Sum (j in S2) j^m

where 0^0 is defined to be 1.

_________________
Has anyone noticed that the below is WRONG? Otherwise this statement would be true:
-1\cong1\pmod{13}
i\cong5 \pmod{13} where
i^2=-1


Last edited by bugzpodder on Thu, 24 Jul 2008 18:56:25 UTC, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Tue, 22 Jul 2008 22:09:46 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sun, 4 May 2003 16:04:19 UTC
Posts: 2906
As an example:

0^n + 3^n + 5^n + 6^n = 1^n + 2^n + 4^n + 7^n
for n = 0, 1, 2 but not 3 if we assume 0^0 = 1

_________________
Has anyone noticed that the below is WRONG? Otherwise this statement would be true:
-1\cong1\pmod{13}
i\cong5 \pmod{13} where
i^2=-1


Last edited by bugzpodder on Thu, 24 Jul 2008 18:57:07 UTC, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Tue, 22 Jul 2008 22:16:46 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame

Joined: Sat, 18 Mar 2006 08:42:24 UTC
Posts: 834
bugzpodder wrote:
As an example:

0^n + 3^n + 5^n + 6^n = 1^n + 2^n + 4^n + 7^n
for n = 0, 1, 2 but not 3 if we assume 0^0 = 0


if we assume that 0^0 = 1 not 0. so by "equal sets" that you mentioned in your previous post,

you mean two sets with the same number of elements then.


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 23 Jul 2008 21:00:34 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sun, 4 May 2003 16:04:19 UTC
Posts: 2906
>> if we assume that 0^0 = 1 not 0

[edit] 0^0 should be 1, my fault[/edit]

>> so by "equal sets" that you mentioned in your previous post. you mean two sets with the same number of elements then.

correct, I am not aware of any other plausible meanings for "equal" in this case. Usually I guess equal means two sets are identical, but clearly this cant be the case here as they are partitions.

_________________
Has anyone noticed that the below is WRONG? Otherwise this statement would be true:
-1\cong1\pmod{13}
i\cong5 \pmod{13} where
i^2=-1


Last edited by bugzpodder on Thu, 24 Jul 2008 18:57:47 UTC, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Thu, 24 Jul 2008 00:25:37 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame

Joined: Sat, 18 Mar 2006 08:42:24 UTC
Posts: 834
bugzpodder wrote:
Umm, 0+3+5+6=14, 1+2+4+7=14
so unless I am mistaken, here we assumes 0^0=0

well, you're mistaken! we want to have 0^0 + 3^0 +5^0 + 6^0 = 1^0 + 2^0 + 4^0 + 7^0, which holds if we define 0^0 = 1.


Top
 Profile  
 
 Post subject:
PostPosted: Thu, 24 Jul 2008 18:56:04 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sun, 4 May 2003 16:04:19 UTC
Posts: 2906
ahh, good point. I was computing 0^1, my bad. Fixed the original post. Thanks.

_________________
Has anyone noticed that the below is WRONG? Otherwise this statement would be true:
-1\cong1\pmod{13}
i\cong5 \pmod{13} where
i^2=-1


Top
 Profile  
 
 Post subject:
PostPosted: Thu, 24 Jul 2008 23:20:54 UTC 
Offline
Senior Member

Joined: Tue, 24 Apr 2007 06:25:18 UTC
Posts: 105
I have a conjecture!
Spoiler:
I came up with this by considering the first 3 cases and it is the clearest pattern.
k=1, partition as 0|1
k=2, partition as 0,3|1,2
k=3: partition as 0,3,5,6|1,2,4,7

Clearly the pattern is to take the previous partition, and add the elements of the form 2^k-1-x to the set containing x.


I do not as yet have a good reason why it works beyond the first power unfortunately.

I'll think about it some more and see if I can come up with a proof or adjustment.


Top
 Profile  
 
 Post subject:
PostPosted: Thu, 24 Jul 2008 23:29:15 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sun, 4 May 2003 16:04:19 UTC
Posts: 2906
siclar, your observation is in fact correct.

I have two comments for this. First of all, in most of these cases induction would be a good choice of proof method to proceed. (if you have a pattern and want to prove it)

Secondly, if you take this pattern, you can actually observe the exact same pattern here:
http://www.sosmath.com/CBB/viewtopic.php?t=38575

_________________
Has anyone noticed that the below is WRONG? Otherwise this statement would be true:
-1\cong1\pmod{13}
i\cong5 \pmod{13} where
i^2=-1


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC [ DST ]


Who is online

Users browsing this forum: No registered users


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
Contact Us | S.O.S. Mathematics Homepage
Privacy Statement | Search the "old" CyberBoard

users online during the last hour
Powered by phpBB © 2001, 2005-2011 phpBB Group.
Copyright © 1999-2013 MathMedics, LLC. All rights reserved.
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA