2016 AMC 12A Problem 25

Question

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)?

7986

8002

8030

8048

8064

Answer: E

Concepts:perfect square floor and ceiling functions digits

Difficulty rating: 2720

Small hint:

For even

k=2j,

the numbers shown are

\left\lfloor \frac{n^2}{10^{k}}\right\rfloor

for

n\ge 10^{j}

Big hint:

Show

f(2j)=\dfrac{10^{2j}}{4}+10^{j},

then add over

j

Solution:

Take

k=2j.

The smallest perfect square with

k+1

digits is

10^{k}=(10^{j})^2,

and after Silvia erases, the numbers shown are

\left\lfloor \frac{n^2}{10^{k}}\right\rfloor

for

n=10^{j}, 10^{j}+1,\ldots

Put

M=10^k.

A jump of at least

2

from

n

to

n+1

requires

(n+1)^2-n^2=2n+1\gt M,

so write

n=\frac{M}{2}+m

with

m\ge0.

The case

m=0

gives a jump of only

1,

so the first larger jump has

m\ge1.

Let

A=\left\lfloor \frac{n^2}{M}\right\rfloor

and

B=\left\lfloor\frac{(n+1)^2}{M}\right\rfloor.

Because

M

is divisible by

4,

\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

2

occurs at the first

m

for which

m^2\lt M\le(m+1)^2.

Since

\sqrt M=10^j,

this is

m=10^j-1.

The last displayed value before the gap is

\frac{M}{4}+10^j-1,

so the smallest missing integer is

f(2j)=\dfrac{10^{2j}}4+10^j.

Summing over

j=1,\ldots,1008,

\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\cdot(2+5)

+1008\cdot 1=1008\cdot 8=8064.

Thus, the correct answer is E.