2016 AMC 12A Problem 25

Attempt Problem 25 of the 2016 AMC 12A below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2016 AMC 12A solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

25.

Let kk 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+1k+1 digits. Every time Bernardo writes a number, Silvia erases the last kk digits of it. Bernardo then writes the next perfect square, Silvia erases the last kk digits of it, and this process continues until the last two numbers that remain on the board differ by at least 2.2. Let f(k)f(k) be the smallest positive integer not written on the board. For example, if k=1,k=1, then the numbers that Bernardo writes are 16,25,36,49,16, 25, 36, 49, and 64,64, and the numbers showing on the board after Silvia erases are 1,2,3,4,1, 2, 3, 4, and 6,6, and thus f(1)=5.f(1)=5. What is the sum of the digits of f(2)+f(4)f(2)+f(4) +f(6)++f(2016)?+f(6)+\cdots+f(2016)?

79867986

80028002

80308030

80488048

80648064

Answer: E
Concepts:perfect squarefloor and ceiling functionsdigits
Difficulty rating: 2720
Solution:

Take k=2j.k=2j. The smallest perfect square with k+1k+1 digits is 10k=(10j)2,10^{k}=(10^{j})^2, and after Silvia erases, the numbers shown are n2/10k\left\lfloor n^2/10^{k}\right\rfloor for n=10j,10j+1,n=10^{j}, 10^{j}+1,\ldots

Put M=10k.M=10^k. A jump of at least 22 from nn to n+1n+1 requires (n+1)2n2=2n+1>M,(n+1)^2-n^2=2n+1\gt M, so write n=M/2+mn=M/2+m with m0.m\ge0. The case m=0m=0 gives a jump of only 1,1, so the first larger jump has m1.m\ge1. Let A=n2/MA=\left\lfloor n^2/M\right\rfloor and B=(n+1)2/M.B=\left\lfloor(n+1)^2/M\right\rfloor. Because MM is divisible by 4,4, A=M4+m+m2M,B=M4+m+1+(m+1)2M. \begin{aligned} A&=\dfrac M4+m+\left\lfloor\dfrac{m^2}{M}\right\rfloor,\\ B&=\dfrac M4+m+1\\ &\quad{}+\left\lfloor\dfrac{(m+1)^2}{M}\right\rfloor. \end{aligned}

Therefore the first jump of at least 22 occurs at the first mm for which m2<M(m+1)2.m^2\lt M\le(m+1)^2. Since M=10j,\sqrt M=10^j, this is m=10j1.m=10^j-1. The last displayed value before the gap is M/4+10j1,M/4+10^j-1, so the smallest missing integer is f(2j)=102j4+10j.f(2j)=\dfrac{10^{2j}}4+10^j.

Summing over j=1,,1008,j=1,\ldots,1008, j=11008f(2j)=25j=01007102j+10j=0100710j=2525252016 digits+111101009 digits. \begin{gathered} \sum_{j=1}^{1008}f(2j)\\ =25\sum_{j=0}^{1007}10^{2j}\\ {}+10\sum_{j=0}^{1007}10^{j}\\ =\underbrace{2525\cdots25}_{2016\text{ digits}}\\ {}+\underbrace{111\cdots10}_{1009\text{ digits}}. \end{gathered} There are no carries, so the digit sum is 1008(2+5)1008\cdot(2+5) +10081=10088=8064.+1008\cdot 1=1008\cdot 8=8064.

Thus, the correct answer is E.

← Problem 24#24
Full Exam

Problem 25 in Other Years