AMC12 2016 A

AMC12 2016 A · Q25

AMC12 2016 A · Q25. It mainly tests Sequences & recursion (algebra), Perfect squares & cubes.

Let $k$ be a positive integer. Bernardo and Silvia take turns writing and erasing numbers on a blackboard as follows: Bernardo starts by writing the smallest perfect square with $k+1$ digits. Every time Bernardo writes a number, Silvia erases the last $k$ digits of it. Bernardo then writes the next perfect square, Silvia erases the last $k$ digits of it, and this process continues until the last two numbers that remain on the board differ by at least $2$. Let $f(k)$ be the smallest positive integer not written on the board. For example, if $k=1$, then the numbers that Bernardo writes are $16, 25, 36, 49,$ and $64$, and the numbers showing on the board after Silvia erases are $1, 2, 3, 4,$ and $6$, and thus $f(1)=5$. What is the sum of the digits of $f(2)+f(4)+f(6)+\cdots+f(2016)$?

设 $k$ 为正整数。Bernardo 和 Silvia 轮流在黑板上写数并擦除数字，规则如下：Bernardo 先写下最小的、具有 $k+1$ 位的完全平方数。每当 Bernardo 写下一个数，Silvia 就把它的末尾 $k$ 位数字擦掉。随后 Bernardo 写下下一个完全平方数，Silvia 再擦掉其末尾 $k$ 位，如此继续，直到黑板上最后保留下来的两个数之差至少为 $2$。定义 $f(k)$ 为黑板上从未出现过的最小正整数。比如当 $k=1$ 时，Bernardo 写下的数是 $16, 25, 36, 49, 64$；Silvia 擦除后黑板上显示的是 $1, 2, 3, 4, 6$，因此 $f(1)=5$。求 $f(2)+f(4)+f(6)+\cdots+f(2016)$ 的各位数字之和。

(A) 7986 7986

(B) 8002 8002

(D) 8048 8048

(E) 8064 8064

Answer

Correct choice: (E)

正确答案：（E）

Solution

Answer (E): Assume that $k=2j\ge 2$ is even. The smallest perfect square with $k+1$ digits is $10^k=(10^j)^2$. Thus the sequence of numbers written on the board after Silvia erases the last $k$ digits of each number is the sequence $$ 1=\left\lfloor\frac{(10^j)^2}{10^k}\right\rfloor,\ \left\lfloor\frac{(10^j+1)^2}{10^k}\right\rfloor,\ \ldots,\ \left\lfloor\frac{n^2}{10^k}\right\rfloor,\ \ldots $$ The sequence ends the first time that $$ \left\lfloor\frac{(n+1)^2}{10^k}\right\rfloor-\left\lfloor\frac{n^2}{10^k}\right\rfloor\ge 2; $$ before that, every two consecutive terms are either equal or they differ by $1$. Suppose that $$ \left\lfloor\frac{n^2}{10^k}\right\rfloor=a\quad\text{and}\quad \left\lfloor\frac{(n+1)^2}{10^k}\right\rfloor\ge a+2. $$ Then $n^2<(a+1)10^k$ and $(a+2)10^k\le (n+1)^2$. Thus $$ 10^k=(a+2)10^k-(a+1)10^k<(n+1)^2-n^2=2n+1. $$ It follows that $n=\frac{10^k}{2}+m$ for some positive integer $m$. Note that $$ \frac{n^2}{10^k}=\frac{1}{10^k}\left(\frac{10^k}{2}+m\right)^2 =\frac{1}{10^k}\left(\frac{10^{2k}}{4}+m\cdot 10^k+m^2\right) =\frac{10^k}{4}+m+\frac{m^2}{10^k}. $$ Because $k\ge 2$, it follows that $10^k$ is divisible by $4$, and so $$ \left\lfloor\frac{n^2}{10^k}\right\rfloor=\frac{10^k}{4}+m+\left\lfloor\frac{m^2}{10^k}\right\rfloor \quad\text{and}\quad \left\lfloor\frac{(n+1)^2}{10^k}\right\rfloor=\frac{10^k}{4}+m+1+\left\lfloor\frac{(m+1)^2}{10^k}\right\rfloor. $$ The difference will be at least $2$ for the first time when $$ \left\lfloor\frac{m^2}{10^k}\right\rfloor=0 \quad\text{and}\quad \left\lfloor\frac{(m+1)^2}{10^k}\right\rfloor\ge 1, $$ that is, for $m$ such that $m^2<10^k\le (m+1)^2$, equivalently, $m<10^j\le m+1$. Thus $m=10^j-1$ and then $$ f(k)=f(2j)=a+1=\left\lfloor\frac{n^2}{10^k}\right\rfloor+1=\frac{10^k}{4}+m+1=\frac{10^{2j}}{4}+10^j. $$ Therefore $$ \sum_{j=1}^{1008} f(2j)=\sum_{j=1}^{1008}\left(\frac{10^{2j}}{4}+10^j\right) =25\sum_{j=0}^{1007}10^{2j}+10\sum_{j=0}^{1007}10^j =252525\ldots 25+111\ldots 10. $$ Because there are no carries in the sum, the required sum of digits equals $1008\cdot(2+5)+1008\cdot 1=1008\cdot 8=8064$.

答案（E）：设$k=2j\ge 2$为偶数。具有$k+1$位数的最小完全平方数是$10^k=(10^j)^2$。因此，当Silvia把每个数的末尾$k$位擦去后，黑板上写下的数列为 $$ 1=\left\lfloor\frac{(10^j)^2}{10^k}\right\rfloor,\ \left\lfloor\frac{(10^j+1)^2}{10^k}\right\rfloor,\ \ldots,\ \left\lfloor\frac{n^2}{10^k}\right\rfloor,\ \ldots $$ 当首次出现 $$ \left\lfloor\frac{(n+1)^2}{10^k}\right\rfloor-\left\lfloor\frac{n^2}{10^k}\right\rfloor\ge 2 $$ 时，该数列结束；在此之前，任意相邻两项要么相等，要么相差$1$。设 $$ \left\lfloor\frac{n^2}{10^k}\right\rfloor=a\quad\text{且}\quad \left\lfloor\frac{(n+1)^2}{10^k}\right\rfloor\ge a+2。 $$ 则$n^2<(a+1)10^k$且$(a+2)10^k\le (n+1)^2$。因此 $$ 10^k=(a+2)10^k-(a+1)10^k<(n+1)^2-n^2=2n+1。 $$ 从而$n=\frac{10^k}{2}+m$，其中$m$为某个正整数。注意 $$ \frac{n^2}{10^k}=\frac{1}{10^k}\left(\frac{10^k}{2}+m\right)^2 =\frac{1}{10^k}\left(\frac{10^{2k}}{4}+m\cdot 10^k+m^2\right) =\frac{10^k}{4}+m+\frac{m^2}{10^k}。 $$ 由于$k\ge 2$，可知$10^k$能被$4$整除，因此 $$ \left\lfloor\frac{n^2}{10^k}\right\rfloor=\frac{10^k}{4}+m+\left\lfloor\frac{m^2}{10^k}\right\rfloor \quad\text{且}\quad \left\lfloor\frac{(n+1)^2}{10^k}\right\rfloor=\frac{10^k}{4}+m+1+\left\lfloor\frac{(m+1)^2}{10^k}\right\rfloor。 $$ 当且仅当首次满足 $$ \left\lfloor\frac{m^2}{10^k}\right\rfloor=0 \quad\text{且}\quad \left\lfloor\frac{(m+1)^2}{10^k}\right\rfloor\ge 1 $$ 时，上述差值首次至少为$2$。也就是$m$满足$m^2<10^k\le (m+1)^2$，等价于$m<10^j\le m+1$。因此$m=10^j-1$，并且 $$ f(k)=f(2j)=a+1=\left\lfloor\frac{n^2}{10^k}\right\rfloor+1=\frac{10^k}{4}+m+1=\frac{10^{2j}}{4}+10^j。 $$ 于是 $$ \sum_{j=1}^{1008} f(2j)=\sum_{j=1}^{1008}\left(\frac{10^{2j}}{4}+10^j\right) =25\sum_{j=0}^{1007}10^{2j}+10\sum_{j=0}^{1007}10^j =252525\ldots 25+111\ldots 10。 $$ 由于相加时没有进位，所求的数字和为$1008\cdot(2+5)+1008\cdot 1=1008\cdot 8=8064$。

Topics