1
$\begingroup$

$k=\frac{512!}{256!*128!*...*2!*1! } $

I need to check if the expression k is divisible by $2^9$ or $2^{10}$. This is a multiple choice question and the options and the question goes like this:

Statement I : $2^9 divides$ $k$

Statement II : $2^{10} divides$ $k$

(a) Statement I is true, Statement II is true

(b) Statement I is false, Statement II is true

(c) Statement I is true, Statement II is false

(d) Statement I is false, Statement II is false

I almost have no lead in this problem. I just figured out that the numbers are in power of 2 and $2^8!$ can get cancelled from numerator and denominator. :(

$\endgroup$
  • 2
    $\begingroup$ You need Legendre's formula for the power of a prime dividing a factorial Clearly II implies I. From a test taking perspective, the fact that the question is asked means the answer is c. They would have chosen different exponents if not. $\endgroup$ – Ross Millikan Jan 9 at 4:23
1
$\begingroup$

Well, to start with, any number that's divisible by $2^{10}$ is divisible by $2^n$ - so it's not (b).

To count how many times $2$ is a factor in $n!$, we ask a series of questions. That factorial is a product of $n$ terms; of those terms, how many are divisible by $2$? How many are divisible by $2^2$? How many are divisible by $2^3$? And so on, until we reach a power of $2$ that's larger than $n$. As an example, here's the power of $2$ that goes into $2019!$:
There are $1009$ even numbers $\le 2019$, so that's $1009$ terms divisible by $2$. $504$ are divisible by $4$, $252$ are divisible by $8$, $126$ by $16$, $63$ by $32$, $31$ by $64$, $15$ by $128$, $7$ by $256$, $3$ by $512$, and finally one term is divisible by $1024$. Add those up: $1009+504+252+126+63+31+15+7+3+1=2011$. $2019!$ is divisible by $2^{2011}$ but not by $2^{2012}$.

Can you see how it will go for the factorials you're working with? They're all simpler than the example I gave. Once we have that, take the exponents we get for each term in the denominator and add them to get the exponent in the product. Subtract that from the exponent in the numerator to get the total here.

An additional note: the quantity $\frac{512!}{256!\cdot 128!\cdot 64!\cdots 2!\cdot 1!}$ is an integer because it's a multinomial coefficient - or at least it is if we add another $1!$ term to that product in the denominator.

Oh, and a side note - there is a clever formula for the exponent of $2$ in a factorial. We don't need to know it to do this; it makes things a little easier, but we can just calculate them anyway.

$\endgroup$
1
$\begingroup$
  • $1! = 2^0$
  • $2! = 2^1$
  • $4! = 2^3 × 3$
  • $8! = 2^7 × 315$
  • $16! = 2^{15} × 638512875$

Do you see the pattern here? Can you use it to find exactly how many powers of 2 are in the numerator and denominator?

$\endgroup$
  • 1
    $\begingroup$ If that pattern is maintained, the denominator has the total power of: $1+3+7+15+31+63+127+255 = 502$ and the numerator has a total power of: $255+256=511$ in the base of $2$. So, $k$ will be divisible by $2^9$ but not by $2^{10}$. Therefore, correct choice is: (c) . $\endgroup$ – tomriddle99 Jan 9 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.