2016 AMC 12A Problems/Problem 25

Problem 25

Problem

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, 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) + ... + f(2016)?

Solution

Consider f(2). The numbers left on the blackboard will show the hundreds place at the end. In order for the hundreds place to differ by 2, the difference between two perfect squares needs to be at least 100. This first happens at 100/2 = 50. The perfect squares from here go: 2500, 2601, 2704, 2809, ... Note that the ones and tens make the perfect squares, 1^2, 2^2, ... After the ones and tens make 100, the hundreds place will go up by 2, thus reaching our goal. Since 100 = 10^2, the last perfect square to be written will be (50+10)^2 = 3600. The missing number is one less than this, or 35.

Now consider f(4). Instead of the difference between two squares needing to be 100, the difference must now be 10,000. This first happens at 5,000. After this point, 100 more numbers are needed to make the 10^4th place go up by 2. This will take place at (5,000+100)^2, or 26,010,000. Removing the last four digits and subtracting one yields 2600 for the skipped value.

In general, each new value of f will add two digits to the "5" and one digit to the "1". This means that the last number Bernardo writes for k=6 is (500,000+1,000)^2, the last for k = 8 will be (50,000,000+10,000)^2, and so on. Removing the last k digits as Silvia does will be the same as removing k/2 trailing zeroes on the number to be squared. This means that the last number on the board for k=6 is (5,001)^2, k=8 is (50,001)^2, and so on. The squaring will make a "25" with two more digits than the last number, a "10" with one more digit, and a "1". The missing number is one less than that, so the "1" will be subtracted from f(k). In other words, f(k) = 25*10^(k-2)+1*10^(k/2)

Therefore:

f(2) = 35 = 25 + 10

f(4) = 2600 = 2500 + 100

f(6) = 251000 = 250000 + 1000

f(8) = 25010000 = 25000000 + 10000

And so on. The sum f(2) + f(4) + f(6) + ... + f(2n) is:

(252525252525...2525) + (111111...110), with n repetitions each of "25" and "1". There is no carrying in this addition. Therefore each f(k) adds 2 + 5 + 1 = 8 to the sum of the digits. Since 2n = 2016, n = 1008, and 8n = 8064, or Answer Choice (E).