Difference between revisions of "2021 GMC 10B Problems/Problem 18"

Latest revision as of 18:40, 7 March 2022

Problem

Let $f(n)$ be the largest possible power of $2$ that divides $n$ . Find $f((3^2-3)(4^2-4)(5^2-5)(6^2-6)(7^2-7)(8^2-8)...(99^2-99)(100^2-100))$ .

$\textbf{(A)} ~191 \qquad\textbf{(B)} ~192 \qquad\textbf{(C)} ~193 \qquad\textbf{(D)} ~198\qquad\textbf{(E)} ~199$

Solution

Note that $f(n) = \nu_2 (n)$ , where $\nu_2(k)$ is the $2$ -adic valuation of $k$ . By LTE, $\begin{align*} f((3^2-3)\dotsm(100^2-100)) &= f(3^2 - 3)+\dotsb + f(100^2 - 100) \\ &= f(2(3))+ \dotsb +f(99(100)) \\ &= f(2) + f(3) + f(3) + \dotsb + f(99) + f(99) + f(100) \\ &= f(2) + f(100) + 2\sum_{n = 3}^{99}f(n). \end{align*}$

To evaluate the sum, we use casework on the divisibility of $n$ over $2^n.$ For example, for $n=1$ , we count the numbers from $3$ to $99$ which are divisible by $2$ . $n = 1$ : $48$ numbers, $n = 2$ : $24$ numbers, $n = 3$ : $12$ numbers, $n = 4$ : $6$ numbers, $n = 5$ : $3$ numbers, $n=6$ : $1$ number, so adding, we get $\sum_{n=3}^{99} f(n) = 94$ , and finishing, $\begin{align*} f((3^2-3)\dotsm(100^2-100)) &= 3 + 2(94) \\ &=\boxed{\textbf{(A)}~191}\hskip 0.5pt. \end{align*}$ ~pineconee

@@ Line 5: / Line 5: @@
 ==Solution==
-Note that <math>f(n) = \nu_2 (n)</math>, where <math>\nu_2(k)</math> is the <math>2</math>-adic valuation of <math>k</math>. By LTE
+Note that <math>f(n) = \nu_2 (n)</math>, where <math>\nu_2(k)</math> is the <math>2</math>-adic valuation of <math>k</math>. By [//en.wikipedia.org/wiki/Lifting-the-exponent_lemma LTE],
 <cmath>\begin{align*}
 f((3^2-3)\dotsm(100^2-100)) &= f(3^2 - 3)+\dotsb + f(100^2 - 100) \\

Page

Toolbox

Search

Difference between revisions of "2021 GMC 10B Problems/Problem 18"

Latest revision as of 18:40, 7 March 2022

Problem

Solution