wu :: forums
wu :: forums - Binary Implications and Binomial Parity

Welcome, Guest. Please Login or Register.
Jan 27th, 2022, 9:55pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: william wu, ThudnBlunder, Eigenray, SMQ, towr, Grimbal, Icarus)
   Binary Implications and Binomial Parity
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Binary Implications and Binomial Parity  (Read 815 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Binary Implications and Binomial Parity  
« on: Oct 29th, 2003, 7:35pm »
Quote Quote Modify Modify

Let r and s be natural numbers. Denote the binary expansion of r by r1r2...rn. Similarly, denote the binary expansion of s by s1s2...sn. Assume these binary expansions are both of length n.
 
Let the relation r [smiley=rrightarrow.gif] s mean that the following sentence is true:  
 
[forall]i[in]{1,...,n}, IF ri = 1, THEN si = 1

 
Thus for example, for binary strings 1010 and 1110, it follows that 1010 [smiley=rrightarrow.gif] 1110.
 
 
Prove that  

r [smiley=rrightarrow.gif] s IF AND ONLY IF C(s,r) is odd

where C(s,r) is the binomial coefficient: (s!)/(r!(s-r)!)
 
 


Note 1: An amazing result from the 1900s! It was passed to me via a colleague (Jon Yard). Does anyone know how it is proven (I don't), or what the theorem's name is if it has a name? If anyone knows the proof and feels it is too hard for recreational math, please say so.
 
Note 2: This result apparently has a little to do with Hilbert's 10th problem.
« Last Edit: Oct 29th, 2003, 7:45pm by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Rezyk
Junior Member
**





   
Email

Gender: male
Posts: 85
Re: Binary Implications and Binomial Parity  
« Reply #1 on: Oct 29th, 2003, 10:44pm »
Quote Quote Modify Modify

Tool #1: The number of times 2 divides X! is equal to X minus the number of 1s in the binary representation of X. (proof omitted)  
 
Tool #2: When adding 2 numbers in binary, iff there is no carry anywhere, the number of "1" digits is conserved. (proof omitted)  
 
C(s, r) is odd
[bigleftrightarrow] s!/(r!(s-r)!) is not divisible by 2
[bigleftrightarrow] number of times 2 divides s! = (number of times 2 divides r!)+(number of times 2 divides (s-r)!)
[bigleftrightarrow] s - (number of 1s in binary repr. of s) = r - (number of 1s in binary repr. of r) + s-r - (number of 1s in binary repr. of s-r)
[bigleftrightarrow] number of 1s in binary repr. of s = (number of 1s in binary repr. of r) + (number of 1s in binary repr. of s-r)
[bigleftrightarrow] there is no carry anywhere in adding r to (s-r) in binary
[bigleftrightarrow] r [smiley=rrightarrow.gif] s
« Last Edit: Oct 30th, 2003, 3:30pm by Rezyk » IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Binary Implications and Binomial Parity  
« Reply #2 on: Oct 30th, 2003, 11:05am »
Quote Quote Modify Modify

Awesome solution, Rezyk! And really elementary. Let me add something for the completeness of the derivation:
 
Tool #1 - proof:
[smiley=blacksquare.gif]
Denote F(n) the maximal power of 2 dividing n!, P(n) - number of 1's in the binary representation (BR) of n. We want to show that F(n) + P(n) = n. Use induction by n:
 
1. F(1) + P(1) = 1 + 0 = 1.
2. Let the rightmost 1 in BR of (n+1) be at position j. Then, the j-th position in BR of n was 0, but positions 1, ..., j-1 were all 1's. So, P(n+1) = P(n) - (j-2). Also, 2j-1 divides n+1, so F(n+1) = F(n) + (j-1). Therefore, F(n+1) + P(n+1) = n+1.

[smiley=blacksquare.gif]
« Last Edit: Oct 31st, 2003, 12:12am by Barukh » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board