Jump to content
BrainDen.com - Brain Teasers
  • 0


superprismatic
 Share

Question

17 answers to this question

Recommended Posts

  • 0

Why is it that the binomial coefficient nCk is an

odd number if and only if, thinking of the numbers

in their binary representations, k = n AND k ?

I would like some clarification. What do you mean by 'thinking of the numbers

in their binary representations'? My interpretation is that nCk is odd if and only if n = k and k > 0, but that interpretation is clearly false. Clarification would be appreciated. Thanks.

Link to comment
Share on other sites

  • 0

I would like some clarification. What do you mean by 'thinking of the numbers

in their binary representations'? My interpretation is that nCk is odd if and only if n = k and k > 0, but that interpretation is clearly false. Clarification would be appreciated. Thanks.

I mean that nCk is odd if and only if the binary

representation of n contains a 1 in every position

where the binary representation of k contains a 1.

So, for example, if n were 84, 1010100 in binary,

then the only values of k which would make 84Ck

odd is 0,4,16,20,64,68,80 and 84 (binary 0000000,

0000100, 0010000, 0010100, 1000000, 1000100, 1010000,

and 1010100). In terms of the way I said it in the OP,

84C20 is odd because 20 = 84 AND 20

(0010100 = 1010100 AND 0010100). I should have used

parentheses in the OP to make it k = (n AND k).

I hope this makes it clear.

Link to comment
Share on other sites

  • 0

Superprismatic, it's amazing to me that (1) this claim is true and (2) someone knows it.

Now that bushindo and molly mae are involved, I expect rapid progress.

All I can contribute right now is this observation.

Call P(m) = power of 2 in m (that is, the number if instances of the factor 2)

Call B(m) = number of 1-bits in m

Then P(m!) = m - B(m)

That is, the power of 2 in m! = m - the number of 1-bits in the number m. For example:

there are 3 1-bits in the number 7, and 7! is divisible by 2^4.

4 = 7 - 3.

Therefore, P( (n-k)! ) = n - k - B(n) + B(k)

And P( n!/k!(n-k)! ) = n - B(n) - ( k - B(k) + (n - k - B(n) + B(k)))

= 2n -2k -2B(n) +2B(k)

=2P(n!) - 2P(k!)

But I can't get from there to seeing how the bits in (k AND n) work to cancel this number to zero.

Hope this helps.

This is interesting, as always. Where do you come up with these things?

Edited by CaptainEd
Link to comment
Share on other sites

  • 0

I can prove the ‘if part’ but not the ‘only If part’... Here it goes...

Let's say, N=N1+N2 such that B(N) AND B(N1) = B(N1).

In that case, we can be sure that wherever N1 has 1, N also has 1 in its binary expression. So, when we subtract N1 from N, we will get zeroes at those places but will get 1 wherever N has 1 but N1 has zero. Which means, N2 will also have 1 only at those places, where N already has 1, leading to two conclusions that [b(N) AND B(N2) = B(N2)] and [N2 has 1 only at all those places where N1 doesn’t have but N has].

Now let’s say, N = 2^a¬1 +2^a2 +2^a3 +….+ 2^an, where a1<a2<….<an. So, if we break N1 and N2 also in similar manner, we will obtain exactly same powers of two that we are getting in case of N, with some falling in N1’s expression and some falling in N2’s expression. For example N = 45 = 2^0 +2^2+2^3+2^5. In this case, to satisfy B(N) AND B(N1) = B(N1) we may have N1 = 2^3 and N2 = 2^0+2^2+2^5. We can get similar expressions just by making sure that both conclusions obtained in previous paragraph hold true.

Now, how many factors of 2 will be there in (N!)? It will be [N/2] + [N/2^2] + [N/2^3] +…. +[N/2^an], where [.] denotes greatest integer function. Let’s check the value of [N/2^p]. There can be two cases: either p belongs to the set {a1, a2, a3,…,an} or it does not belong. In first case we can assume ai = p and in second case we can assume that ai<p<ai+1. So, in both cases, [N/2^p] will be {2^(ai+1-p) + 2^(ai+2-p) + ….. 2^(an-p)}.

A similar analysis with N1 will give us same expression but this time with only those powers of 2 which are involved in N1’s expression and are greater than or equal to p. Same will hold true with N2. So, we can be 100% sure that in this case, [N1/2^p] + [N2/2^p] = [N/2^p] for all p with [.] being greatest integer function.

So, if we count total number of factors of 2 in N!, that will also be equal to total number of factors of 2 in (N1! * N2!). Hence, N©N1 (= N!/(N1! * N2!)) will be an odd number.

Only-if part can also be thought in similar way, but would need more exhaustive calculations.

Link to comment
Share on other sites

  • 0

Superprismatic, it's amazing to me that (1) this claim is true and (2) someone knows it.

...

This is interesting, as always. Where do you come up with these things?

How do I come up with my problems? Well, I like to keep a few relatively new

expository mathematics texts nearby so that I can fill some of the time slots

in my life. I routinely keep notes as I flip the pages. These notes are usually

the basis of my posted topics. Something that surprises me, like the odd binomial

coefficient thing, usually makes it in one of my topics. So, most of my topics

are not original, but some are. I find my perusal of expository texts gives me

lots of insights. I usually get these books using inter-library loan from

university libraries. I'm glad you like some of this stuff, Captain! Thanks!

Link to comment
Share on other sites

  • 0

How do I come up with my problems? Well, I like to keep a few relatively new

expository mathematics texts nearby so that I can fill some of the time slots

in my life. I routinely keep notes as I flip the pages. These notes are usually

the basis of my posted topics. Something that surprises me, like the odd binomial

coefficient thing, usually makes it in one of my topics. So, most of my topics

are not original, but some are. I find my perusal of expository texts gives me

lots of insights. I usually get these books using inter-library loan from

university libraries. I'm glad you like some of this stuff, Captain! Thanks!

Let me just chime in and say that I like your puzzles as well. I'm always happy to see new topics that you post. Can you recommend one or two of these expository texts? There are some time slots in my life that I'd like to put to better use.

Link to comment
Share on other sites

  • 0

Let me just chime in and say that I like your puzzles as well. I'm always happy to see new topics that you post. Can you recommend one or two of these expository texts? There are some time slots in my life that I'd like to put to better use.

I usually look at the latest publications from the Mathematical Association of America (MAA) which can be found here

and order interesting-looking books designated Dolciani or Problem Books. I order them through my local

county library. By the time I am just about done leafing through those, a new MAA publications catalog comes out with

more good books. I don't usually record in my notes what book the ideas came from, so I don't have a list of books

immediately at hand.

Link to comment
Share on other sites

  • 0

I followed your neat proof, but I had a problem because it depended on a fact that demonstrates my ignorance (as so many do...).

Why is it that the number of factors of 2 in N! is the sum of [N/2^i] for i=1to n ?

I admit that in my note, I stated without proof that it is equal to N minus the number of bits in the number N. I don't understand why that is true, either.

Link to comment
Share on other sites

  • 0

Here's nomenclature, a lemma, and the proof itself.

First, nomenclature.

Let P(n) be the number of factors of 2 in n

Let B(n) be the number of 1-bits in the binary representation of n

proof by induction on n

P(0) = 0 - B(0) = 0 - 0 = 0

P(1) = 1 - B(1) = 1 - 1 = 0

P(2) = 2 - B(2) = 2 - 1 = 1

assume P( k! ) = k - B(k)

(a) By definition, P( (k+1)! ) = P(k+1) + P( k! )

represent k+1 as a*2^i, where a is odd

there are two cases, i>0 and i=0

case i>0)

P(k)=0

P(k+1)=i

binary representation of k ends in 0 followed by i 1-bits

binary representation of k+1 ends in 1 followed by i 0-bits

B(k+1) = B(k) - i + 1

P( (k+1)! ) = P(k!) + P(k+1)---by (a)

=P(k!) + i

=k-B(k)+i

=k- ( B(k)-i )

=k+1 - (B(k)-i+1)

=k+1 - B(k+1)

case i=0

binary representation of k ends in 0

binary representation of k+1 ends in 1

P(k+1)=0

B(k+1)= B(k) + 1

P( (k+1)! ) = P(k!) + P(k+1)--by (a)

=P(k!)

=k - B(k)

=k+1 - (B(k) + 1)

k+1 - B(k+1)

suppose n = n1 + n2, where (n1 AND n2) = m, where m>=0

so the bits of n are partitioned into (n1-m), (n2-m), and m.

This implies that (n AND (n1-m)) = n1, (n AND (n2-m)) = n2, (n AND m) = m

B(n) = B(n1-m) + B(n2-m) + B(m)

=B(n1) - B(m) + B(n2) - B(m) + B(m)

=B(n1)+B(n2)-B(m)

P(n) = n-B(n)

=n-( B(n1)+ B(n2) - B(m) )

=n- (B(n1)+B(n2)) + B(m)

= n1 + n2 - (B(n1)+B(n2)) + B(m)

= (n1-B(n1) + (n2-B(n2)) + B(m)

= P(n1) + P(n2) + B(m)

so

P(n) - (P(n1)+P(n2)) = B(m)

now, substituting k for n1 and (n-k) for n2, we get

P(n) - (P(k)+P(n-k)) = B(m)

P( nCk ) = B(m)

P( nCk ) = 0 iff B(m) = B(k AND (n-k)) = 0, which occurs exactly when (n AND k) = k

Edited by CaptainEd
Link to comment
Share on other sites

  • 0

Finally, the proof

suppose n = n1 + n2, where (n1 AND n2) = m, where m>=0

so the bits of n are partitioned into n1, n2, and m.

This implies that (n AND (n1-m)) = (n1-m), (n AND (n2-m)) = (n2-m), (n AND m) = m, (n1 AND m) = m, (n2 AND m) = m

B(n) = B(n1-m) + B(n2-m) + B(m)

=B(n1) - B(m) + B(n2) - B(m) + B(m)

=B(n1)+B(n2)-B(m)

P(n!) = n-B(n)

=n-( B(n1)+ B(n2) - B(m) )

=n- (B(n1)+B(n2)) + B(m)

= n1 + n2 - (B(n1)+B(n2)) + B(m)

= (n1-B(n1) + (n2-B(n2)) + B(m)

= P(n1!) + P(n2!) + B(m)

so

P(n!) - (P(n1!)+P(n2!)) = B(m)

now, substituting k for n1 and (n-k) for n2, we get

P(n!) - ( P(k!)+P((n-k)!) ) = B(m)

P( nCk ) = B(m)

P( nCk ) = 0 iff B(m) = B(k AND (n-k)) = 0, which occurs exactly when (n AND k) = k

Link to comment
Share on other sites

  • 0

Finally, the proof

suppose n = n1 + n2, where (n1 AND n2) = m, where m>=0

so the bits of n are partitioned into n1, n2, and m.

This implies that (n AND (n1-m)) = (n1-m), (n AND (n2-m)) = (n2-m), (n AND m) = m, (n1 AND m) = m, (n2 AND m) = m

B(n) = B(n1-m) + B(n2-m) + B(m)

=B(n1) - B(m) + B(n2) - B(m) + B(m)

=B(n1)+B(n2)-B(m)

P(n!) = n-B(n)

=n-( B(n1)+ B(n2) - B(m) )

=n- (B(n1)+B(n2)) + B(m)

= n1 + n2 - (B(n1)+B(n2)) + B(m)

= (n1-B(n1) + (n2-B(n2)) + B(m)

= P(n1!) + P(n2!) + B(m)

so

P(n!) - (P(n1!)+P(n2!)) = B(m)

now, substituting k for n1 and (n-k) for n2, we get

P(n!) - ( P(k!)+P((n-k)!) ) = B(m)

P( nCk ) = B(m)

P( nCk ) = 0 iff B(m) = B(k AND (n-k)) = 0, which occurs exactly when (n AND k) = k

I just took two numbers n1 = 45 (0101101) and n2 = 27 (0011011). So, n = 72 (1001000) and m = 9 (0001001). So, (n1-m) = 45-9 = 36 (0100100) and (n2-m) = 27-9 = 18 (0010010). Now I don't find n AND (n1-m) = (n1-m) and n AND (n2-m) = (n2-m). For me, n AND (n1-m) = n AND (n2-m) = 0.

I think I am confused. Can you please explain these statements with an example?

Also, clarifications of what I said:

Generally, to calculate number of factors of 2 in N!, we used to follow below approach, until you gave your lemma. :)

Step 1> Find how many even numbers are there between 1 and N. So, divide N by 2. Now N can be odd also. So, we needed to take greatest integer function of that (because unfortunately natural numbers start at odd). So it was [N/2].

Step2> Fine how many numbers are divisible by 4. It will be [N/2^2]. Number of 4 is found because they contribute 1 more factor of two than two itself contributes.

Step 3 onward > Similarly factor of 8 and 16, etc are calculated. We proceed till 2^n where n is maximum but 2^n < N. You can understand this why.

Final step> Add all the numbers obtained in above steps.

I have done the similar thing in my semi-proof.

Finally, it is really great if you got some insight from My proof. :) :)

Link to comment
Share on other sites

  • 0

I mean that nCk is odd if and only if the binary

representation of n contains a 1 in every position

where the binary representation of k contains a 1.

So, for example, if n were 84, 1010100 in binary,

then the only values of k which would make 84Ck

odd is 0,4,16,20,64,68,80 and 84 (binary 0000000,

0000100, 0010000, 0010100, 1000000, 1000100, 1010000,

and 1010100). In terms of the way I said it in the OP,

84C20 is odd because 20 = 84 AND 20

(0010100 = 1010100 AND 0010100). I should have used

parentheses in the OP to make it k = (n AND k).

I hope this makes it clear.

Thanks for sharing these little gems with us, superprimastic. I enjoy the journey greatly, and feel enriched by the experience. Also, thanks for you recommendation. I picked up the Stanford Mathematics Problem Book for my ereader, and look forward to spending some time on it.

Background:

Some notations and general thoughts before we start the proof.

Let P( n, k ) be a binary test for a property defined as follows

P(n, k) = [ (n AND k) == k ]

In other words, P(n, k) returns TRUE if the binary representation of n contains a 1 in every position where the binary representation of k contains a 1, and FALSE otherwise. Using superprimastic's example, if n were 84, 1010100 in binary, then the only values of k which would make P( n, k) = TRUE is 0,4,16,20,64,68,80 and 84 (binary 0000000, 0000100, 0010000, 0010100, 1000000, 1000100, 1010000, and 1010100).

Let f0( m ) be the position of the right-most digit of 0 in the binary expansion of m. Let f1( m ) be the position of the right-most digit of 1 in the binary expansion of m. We consider the right-most digit of a binary number to be at position 1, and the second digit from the right to be at position 2, and so on. For instance, f0( 11001b ) is equal to 2, and f1( 11001b ) is equal to 1, where 11001b is the binary representation of the decimal number 25.

Another general thing is the process of addition and subtracting 1 to a binary number. The general observations are as follows

1) If m is a binary number, then (m-1) can be obtained by flipping all digits of m from position 1 to f1( m ).

2) If m is a binary number, then (m+1) can be obtained by flipping all digits of m from position 1 to f0( m ).

Last general thing is an identity for the binomial coefficient, which is

n+1Ck = nCk + nCk-1

So, let's get to the proof.

Claim: nCk is odd if and only if P(n, k) == TRUE

Outline of proof:

We prove this using induction. We assume that the claim is true for nCk, where k <= n. We then prove that the claim is true for n+1Ck.

Using the binomial identity, the proof then reduces to proving the following two statements

A) If P(n + 1, k ) = TRUE, then exactly one of P(n , k ) and P(n, k - 1 ) will be TRUE. [ in other words, P(n , k ) XOR P(n, k + 1 ) = TRUE ]

B) If P(n + 1, k ) = FALSE, then either

B.1) P(n , k ) = FALSE and P(n, k - 1 ) = FALSE or

B.2) P(n , k ) = TRUE and P(n, k - 1 ) = TRUE.

Part A:

Let's examine statement A,

If P(n + 1, k ) = TRUE, that implies f1( n+1) <= f1( k ), and it is easy to show* the following two statements using the process of adding and subtracting 1 from a binary number

a) If P(n + 1, k ) = TRUE and f1( n+1) = f1( k ), then P(n , k ) = FALSE and P(n, k - 1 ) = TRUE

b) If P(n + 1, k ) = TRUE and f1( n+1) < f1( k ), then P(n , k ) = TRUE and P(n, k - 1 ) = FALSE,

So, given that the claim is true for nCk under induction, the above implies that P(n + 1, k ) = TRUE leads to n+1Ck being odd.

Part B:

Let's examine statement B. Without loss of generality, we only need to show that if P(n + 1, k ) = FALSE and P(n , k ) = TRUE, then P(n , k - 1 ) = TRUE as well. We're only showing 1 direction but it can be extended both direction using the symmetry nCk = nCn - k.

So P(n + 1, k ) = FALSE and P(n , k ) = TRUE implies that f0( n ) > f1( k ). Using the process of adding and subtracting 1 from a binary number, it is easy to show* that P(n , k - 1 ) = TRUE as well.

The above implies that if P(n + 1, k ) = FALSE and one of P(n , k ) = TRUE or P(n, k - 1 ) is TRUE, then the other one is TRUE as well. This implies that if P(n + 1, k ) = FALSE, then nCk and nCk-1 are either both even or both odd, which leads to n+1Ck being even.

QED.

Note: The parts that say 'it's easy to show*' are indeed easy to work out on paper, but quite hard to explain. I'll leave it as an exercise for the reader. There are also some minor details about proving the claim for initial small values of n and k, and also showing that n+1Cn+1 is odd. Both of those are trivial claims, so I won't show it here.

Link to comment
Share on other sites

  • 0

Thanks for sharing these little gems with us, superprimastic. I enjoy the journey greatly, and feel enriched by the experience. Also, thanks for you recommendation. I picked up the Stanford Mathematics Problem Book for my ereader, and look forward to spending some time on it.

Background:

Some notations and general thoughts before we start the proof.

Let P( n, k ) be a binary test for a property defined as follows

P(n, k) = [ (n AND k) == k ]

In other words, P(n, k) returns TRUE if the binary representation of n contains a 1 in every position where the binary representation of k contains a 1, and FALSE otherwise. Using superprimastic's example, if n were 84, 1010100 in binary, then the only values of k which would make P( n, k) = TRUE is 0,4,16,20,64,68,80 and 84 (binary 0000000, 0000100, 0010000, 0010100, 1000000, 1000100, 1010000, and 1010100).

Let f0( m ) be the position of the right-most digit of 0 in the binary expansion of m. Let f1( m ) be the position of the right-most digit of 1 in the binary expansion of m. We consider the right-most digit of a binary number to be at position 1, and the second digit from the right to be at position 2, and so on. For instance, f0( 11001b ) is equal to 2, and f1( 11001b ) is equal to 1, where 11001b is the binary representation of the decimal number 25.

Another general thing is the process of addition and subtracting 1 to a binary number. The general observations are as follows

1) If m is a binary number, then (m-1) can be obtained by flipping all digits of m from position 1 to f1( m ).

2) If m is a binary number, then (m+1) can be obtained by flipping all digits of m from position 1 to f0( m ).

Last general thing is an identity for the binomial coefficient, which is

n+1Ck = nCk + nCk-1

So, let's get to the proof.

Claim: nCk is odd if and only if P(n, k) == TRUE

Outline of proof:

We prove this using induction. We assume that the claim is true for nCk, where k <= n. We then prove that the claim is true for n+1Ck.

Using the binomial identity, the proof then reduces to proving the following two statements

A) If P(n + 1, k ) = TRUE, then exactly one of P(n , k ) and P(n, k - 1 ) will be TRUE. [ in other words, P(n , k ) XOR P(n, k + 1 ) = TRUE ]

B) If P(n + 1, k ) = FALSE, then either

B.1) P(n , k ) = FALSE and P(n, k - 1 ) = FALSE or

B.2) P(n , k ) = TRUE and P(n, k - 1 ) = TRUE.

Part A:

Let's examine statement A,

If P(n + 1, k ) = TRUE, that implies f1( n+1) <= f1( k ), and it is easy to show* the following two statements using the process of adding and subtracting 1 from a binary number

a) If P(n + 1, k ) = TRUE and f1( n+1) = f1( k ), then P(n , k ) = FALSE and P(n, k - 1 ) = TRUE

b) If P(n + 1, k ) = TRUE and f1( n+1) < f1( k ), then P(n , k ) = TRUE and P(n, k - 1 ) = FALSE,

So, given that the claim is true for nCk under induction, the above implies that P(n + 1, k ) = TRUE leads to n+1Ck being odd.

Part B:

Let's examine statement B. Without loss of generality, we only need to show that if P(n + 1, k ) = FALSE and P(n , k ) = TRUE, then P(n , k - 1 ) = TRUE as well. We're only showing 1 direction but it can be extended both direction using the symmetry nCk = nCn - k.

So P(n + 1, k ) = FALSE and P(n , k ) = TRUE implies that f0( n ) > f1( k ). Using the process of adding and subtracting 1 from a binary number, it is easy to show* that P(n , k - 1 ) = TRUE as well.

The above implies that if P(n + 1, k ) = FALSE and one of P(n , k ) = TRUE or P(n, k - 1 ) is TRUE, then the other one is TRUE as well. This implies that if P(n + 1, k ) = FALSE, then nCk and nCk-1 are either both even or both odd, which leads to n+1Ck being even.

QED.

Note: The parts that say 'it's easy to show*' are indeed easy to work out on paper, but quite hard to explain. I'll leave it as an exercise for the reader. There are also some minor details about proving the claim for initial small values of n and k, and also showing that n+1Cn+1 is odd. Both of those are trivial claims, so I won't show it here.

Nice Proof... Thoroughly enjoyed it.... :)

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...