AMC10 2020 A

AMC10 2020 A · Q21

AMC10 2020 A · Q21. It mainly tests Sequences & recursion (algebra), Primes & prime factorization.

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

存在唯一的严格递增的非负整数序列 $a_1 < a_2 < \dots < a_k$ 使得 $\frac{2^{289} + 1}{2^{17} + 1} = 2^{a_1} + 2^{a_2} + \dots + 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）：注意，这个问题等价于求当左边写成二进制时，其中非零数字的个数。更一般地，对奇数 $n$，考虑分式 $$ \frac{2^{n^2}+1}{2^n+1}. $$ 由等比数列求和公式， $$ \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