AMC12 2020 A

AMC12 2020 A · Q19

AMC12 2020 A · Q19. It mainly tests Primes & prime factorization, Powers & residues.

There exists a unique strictly increasing sequence of nonnegative integers $a_1 < a_2 < \cdots < a_k$ such that $$\frac{2^{289} + 1}{2^{17} + 1} = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_k}.$$ What is $k$?

存在唯一的严格递增的非负整数序列$a_1 < a_2 < \cdots < a_k$，使得$$\frac{2^{289} + 1}{2^{17} + 1} = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_k}.$$$k$是多少？

(A) 117 117

(B) 136 136

(D) 273 273

(E) 306 306

Answer

Correct choice: (C)

正确答案：（C）

Solution

Answer (C): Note that the problem is equivalent to finding the number of nonzero digits when the left-hand side is written in binary. More generally, consider the fraction \[ \frac{2^{n^2}+1}{2^n+1} \] for odd $n$. By the formula for the sum of a geometric series, \[ \frac{2^{n^2}+1}{2^n+1}=2^{(n-1)n}-2^{(n-2)n}+2^{(n-3)n}-\cdots+2^{2n}-2^n+1. \] This expression is not in the form of the problem statement because of the negative signs, but it is possible to transform it into such a form by considering pairs of adjacent terms. For $i=1,3,5,\ldots,n-2$, \[ 2^{(i+1)n}-2^{in}=2^{in}(2^n-1) \] \[ =2^{in}(1+2+\cdots+2^{n-1}) \] \[ =2^{in}+2^{in+1}+\cdots+2^{(i+1)n-1}. \] Thus each pair $2^{(i+1)n}-2^{in}$ contributes $((i+1)n-1)-in+1=n$ nonzero digits to the binary expansion of the left-hand side. The total number of expressions of this form is equal to the number of integers in the set $\{1,3,5,\ldots,n-2\}$, which is $\frac12(n-1)$. Thus, including the last term of $1$, the total number of summands is $n\cdot\frac12(n-1)+1$. For $n=17$, this value is $17\cdot 8+1=137$.

答案（C）：注意，这个问题等价于求左边写成二进制时非零数字的个数。更一般地，考虑分式 \[ \frac{2^{n^2}+1}{2^n+1} \] 其中 $n$ 为奇数。由等比数列求和公式， \[ \frac{2^{n^2}+1}{2^n+1}=2^{(n-1)n}-2^{(n-2)n}+2^{(n-3)n}-\cdots+2^{2n}-2^n+1. \] 由于有负号，这个表达式不是题目所需的形式，但可以通过把相邻两项配对来转化成所需形式。对 $i=1,3,5,\ldots,n-2$， \[ 2^{(i+1)n}-2^{in}=2^{in}(2^n-1) \] \[ =2^{in}(1+2+\cdots+2^{n-1}) \] \[ =2^{in}+2^{in+1}+\cdots+2^{(i+1)n-1}. \] 因此，每一对 $2^{(i+1)n}-2^{in}$ 给左边的二进制展开贡献 $((i+1)n-1)-in+1=n$ 个非零数字。这种形式的表达式个数等于集合 $\{1,3,5,\ldots,n-2\}$ 中整数的个数，即 $\frac12(n-1)$。因此再加上最后一项 $1$，加数总数为 $n\cdot\frac12(n-1)+1$。当 $n=17$ 时，该值为 $17\cdot 8+1=137$。

Topics