Author 
Topic: Binary Implications and Binomial Parity (Read 815 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Binary Implications and Binomial Parity
« on: Oct 29^{th}, 2003, 7:35pm » 
Quote Modify

Let r and s be natural numbers. Denote the binary expansion of r by r_{1}r_{2}...r_{n}. Similarly, denote the binary expansion of s by s_{1}s_{2}...s_{n}. 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 r_{i} = 1, THEN s_{i} = 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!(sr)!) 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 29^{th}, 2003, 7:45pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Rezyk
Junior Member
Gender:
Posts: 85


Re: Binary Implications and Binomial Parity
« Reply #1 on: Oct 29^{th}, 2003, 10:44pm » 
Quote 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!(sr)!) is not divisible by 2 [bigleftrightarrow] number of times 2 divides s! = (number of times 2 divides r!)+(number of times 2 divides (sr)!) [bigleftrightarrow] s  (number of 1s in binary repr. of s) = r  (number of 1s in binary repr. of r) + sr  (number of 1s in binary repr. of sr) [bigleftrightarrow] number of 1s in binary repr. of s = (number of 1s in binary repr. of r) + (number of 1s in binary repr. of sr) [bigleftrightarrow] there is no carry anywhere in adding r to (sr) in binary [bigleftrightarrow] r [smiley=rrightarrow.gif] s

« Last Edit: Oct 30^{th}, 2003, 3:30pm by Rezyk » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Binary Implications and Binomial Parity
« Reply #2 on: Oct 30^{th}, 2003, 11:05am » 
Quote 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 jth position in BR of n was 0, but positions 1, ..., j1 were all 1's. So, P(n+1) = P(n)  (j2). Also, 2^{j1} divides n+1, so F(n+1) = F(n) + (j1). Therefore, F(n+1) + P(n+1) = n+1. [smiley=blacksquare.gif]

« Last Edit: Oct 31^{st}, 2003, 12:12am by Barukh » 
IP Logged 



