2021 GMC 10B Problems/Problem 18

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