M7MBA wrote:If \(n\) and \(k\) are positive integers and \(\dfrac{(2^n)!}{2^k}\) is an odd integer, what is \(k\) in term of \(n?\)
\(A. \ n\)
\(B. \ 2n−1\)
\(C. \ n^2\)
\(D. \ \dfrac{n^2+n}{2}\)
\(E. \ 2n−1\)
The OA is the option _E_
Source: Veritas Prep
If n = 2, we see that (2^2)! = 4! = 4 x 3 x 2 x 1 = 2^2 x 3 x 2 = 2^3 x 3. Since (2^2)!/2^k is an odd integer, we see that k must be 3.
If n = 3, we see that (2^3)! = 8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 2^3 x 7 x 2 x 3 x 5 x 2^2 x 3 x 2 = 2^7 x 7 x 5 x 3^2. Since (2^3)!/2^k is an odd integer, we see that k must be 7.
We see that if n = 2, k = 3 and if n = 3, k = 7. Therefore, k = 2^n - 1.
(Note: One of the choices B and E must be 2^n - 1 and the other is 2n - 1. They can't be both 2n - 1.)
Alternate Solution:
Since (2^n)!/2^k is odd, k is precisely the number of factors of 2 in (2^n)!. Let's determine the number of factors in (2^n)!. To determine the number of factors of 2 in n!, we use the shortcut where we divide n by 2, then divide the quotient by 2 and continue this process as long as we have a non-zero quotient. When we do get a zero quotient, the number of factors of 2 in n! is given by the sum of the quotients.
Dividing 2^n by 2, we get 2^(n - 1). Dividing 2^(n - 1) by 2, we get 2^(n - 2) and so on. The last division we will perform will be 2/2 = 1, after which we will get a zero quotient. Thus, the number of factors of 2 in (2^n)! is:
2^(n - 1) + 2^(n - 2) + ... + 2 + 1.
Let's call x = 2^(n - 1) + 2^(n - 2) + ... + 2 + 1. Multiply each side by 2:
2x = 2^n + 2^(n - 1) + 2^(n - 2) + ... + 2
Add 1 to each side:
2x + 1 = 2^n + 2^(n - 1) + 2^(n - 2) + ... + 2 + 1
Subtract 2^n from each side:
2x + 1 - 2^n = 2^(n - 1) + 2^(n - 2) + ... + 2 + 1
We see that the right hand side is precisely x; therefore, we have:
2x + 1 - 2^n = x
x = 2^n - 1
Since x = 2^n - 1 is the number of factors of 2 in (2^n)!, we see that k = 2^n - 1.
Answer: E (note the typo)
