Question

Para cada entero positivo par $x,$ sea $g(x)$ la mayor potencia de $2$ que divide a $x.$ Por ejemplo, $g(20) = 4$ y $g(16) = 16.$ Para cada entero positivo $n,$ sea $S_n = \sum_{k=1}^{2^{n-1}} g(2k).$ Halla el mayor entero $n$ menor que $1000$ tal que $S_n$ sea un cuadrado perfecto.

For each even positive integer $x,$ let $g(x)$ denote the greatest power of $2$ that divides $x.$ For example, $g(20) = 4$ and $g(16) = 16.$ For each positive integer $n,$ let $S_n = \sum_{k=1}^{2^{n-1}} g(2k).$ Find the greatest integer $n$ less than $1000$ such that $S_n$ is a perfect square.

Respuesta

Solución:

$S_n$ es la suma de $g$ sobre los números pares $2, 4, \ldots, 2^n.$ Entre estos $2^{n-1}$ números, exactamente $2^{n-1-i}$ son divisibles entre $2^i$ pero no entre $2^{i+1}$ (así que tienen $g = 2^i$ ) para cada $1 \le i \le n - 1,$ y el único número $2^n$ tiene $g = 2^n.$ Por lo tanto $\begin{aligned} S_n &= \sum_{i=1}^{n-1} 2^i \cdot 2^{n-1-i} \\ &\quad {}+ 2^n \\ &= (n-1) 2^{n-1} + 2^n \\ &= (n+1) 2^{n-1}. \end{aligned}$

Si $n$ es par, entonces $n + 1$ es impar y el exponente $n - 1$ es impar, así que $S_n$ tiene un número impar de factores de $2$ y no puede ser un cuadrado perfecto. Si $n$ es impar, entonces $2^{n-1}$ ya es un cuadrado perfecto, así que $S_n$ es un cuadrado perfecto exactamente cuando $n + 1$ lo es.

Para $n$ impar, el número $n + 1$ es par, y el mayor cuadrado perfecto par que no supera $1000$ es $900 = 30^2.$ Así, el mayor $n \lt 1000$ válido es $n = 899.$

$S_n$ is the sum of $g$ over the even numbers $2, 4, \ldots, 2^n.$ Among these $2^{n-1}$ numbers, exactly $2^{n-1-i}$ are divisible by $2^i$ but not $2^{i+1}$ (so have $g = 2^i$ ) for each $1 \le i \le n - 1,$ and the single number $2^n$ has $g = 2^n.$ Hence $\begin{aligned} S_n &= \sum_{i=1}^{n-1} 2^i \cdot 2^{n-1-i} \\ &\quad {}+ 2^n \\ &= (n-1) 2^{n-1} + 2^n \\ &= (n+1) 2^{n-1}. \end{aligned}$

If $n$ is even, then $n + 1$ is odd and the exponent $n - 1$ is odd, so $S_n$ has an odd number of factors of $2$ and cannot be a perfect square. If $n$ is odd, then $2^{n-1}$ is already a perfect square, so $S_n$ is a perfect square exactly when $n + 1$ is.

For odd $n,$ the number $n + 1$ is even, and the greatest even perfect square at most $1000$ is $900 = 30^2.$ Thus the greatest valid $n \lt 1000$ is $n = 899.$

2006 AIME I Problema 13

Solución:

El Problema 13 en otros años