Question

对每个正偶数 $x$ ，令 $g(x)$ 表示整除 $x$ 的最大 $2$ 的幂。例如， $g(20) = 4$ ，且 $g(16) = 16$ 。对每个正整数 $n$ ，令 $S_n = \sum_{k=1}^{2^{n-1}} g(2k)$ 。求小于 $1000$ 且使 $S_n$ 为完全平方数的最大整数 $n$ 。

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.

答案

答案：899

知识点：2的幂完全平方数求和

难度评级：2990

解答：

$S_n$ 是对偶数 $2, 4, \ldots, 2^n$ 上的 $g$ 求和。在这 $2^{n-1}$ 个数中，对每个 $1 \le i \le n - 1$ ，恰有 $2^{n-1-i}$ 个数能被 $2^i$ 整除但不能被 $2^{i+1}$ 整除（所以 $g = 2^i$ ），另有唯一的数 $2^n$ 满足 $g = 2^n$ 。因此 $\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}$

若 $n$ 为偶数，则 $n + 1$ 为奇数，而指数 $n - 1$ 为奇数，因此 $S_n$ 中含有奇数个因子 $2$ ，不可能是完全平方数。若 $n$ 为奇数，则 $2^{n-1}$ 已经是完全平方数，所以 $S_n$ 是完全平方数当且仅当 $n + 1$ 是完全平方数。

对奇数 $n$ ，数 $n + 1$ 为偶数。在 $n \lt 1000$ 的条件下，不超过 $1000$ 的最大偶完全平方数是 $900 = 30^2$ 。因此小于一千的最大有效整数是 $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 第 13 题

答案：899

难度评级：2990

解答：

其他年份的第 13 题