Skip to main content

2016 AMC 12A Problem 25

Problem 25 of 25HarderAlgebraNumber Theory

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,16, 25,25, 36,36, 49,49, and 64,64, and the numbers showing on the board after Silvia erases are 1,1, 2,2, 3,3, 4,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)?

Answer choices

Show solution

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 ⌊n210k⌋\left\lfloor \frac{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)2−n2=2n+1>M,(n+1)^2-n^2=2n+1\gt M, so write n=M2+mn=\frac{M}{2}+m with m≥0.m\ge0. The case m=0m=0 gives a jump of only 1,1, so the first larger jump has m≥1.m\ge1. Let A=⌊n2M⌋A=\left\lfloor \frac{n^2}{M}\right\rfloor and B=⌊(n+1)2M⌋.B=\left\lfloor\frac{(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=10j−1.m=10^j-1. The last displayed value before the gap is M4+10j−1,\frac{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)=25∑j=01007102j+10∑j=0100710j=2525⋯25⏟2016 digits+111⋯10⏟1009 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) +1008⋅1=1008⋅8=8064.+1008\cdot 1=1008\cdot 8=8064. Thus, the correct answer is E.

More practice

Concepts: perfect square · floor and ceiling functions · digits

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.