Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2016 AMC 12A Problems/Problem 25"

(→‎See Also)
m (→‎Solution 2(Cheap Realization))
Line 32: Line 32:
 
==Solution 2(Cheap Realization)==
 
==Solution 2(Cheap Realization)==
  
−
If you are one of those people who are willing take educated guesses, then just realize that <math>\textbf{(E)}\text{ 8064}</math> is the only answer choice that is a multiple of 2016... just saying.
+
If you are one of those people who are willing take educated guesses, then just realize that <math>\textbf{(E)}\text{ 8064}</math> is the only answer choice that is a multiple of <math>2016</math>
  
 
==See Also==
 
==See Also==

Revision as of 01:13, 15 June 2020

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) + \dots + f(2016)$?

$\textbf{(A)}\ 7986\qquad\textbf{(B)}\ 8002\qquad\textbf{(C)}\ 8030\qquad\textbf{(D)}\ 8048\qquad\textbf{(E)}\ 8064$

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$. Calculus $\left(\frac{\text{d}}{\text{d}x} x^2=2x\right)$ and a bit of thinking says this first happens at $x\ge 100/2 = 50$*. The perfect squares from here go: $2500, 2601, 2704, 2809\dots$. Note that the ones and tens also make the perfect squares, $1^2,2^2,3^2\dots$. After the ones and tens make $100$, the hundreds place will go up by $2$, thus reaching our goal. Since $10^2=100$, the last perfect square to be written will be $\left(50+10\right)^2=60^2=3600$. The missing number is one less than the number of hundreds $(k=2)$ of $3600$, or $35$.

Now consider f(4). Instead of the difference between two squares needing to be $100$, the difference must now be $10000$. This first happens at $x\ge 5000$. After this point, similarly, $\sqrt{10000}=100$ more numbers are needed to make the $10^4$ th's place go up by $2$. This will take place at $\left(5000+100\right)^2=5100^2= 26010000$. Removing the last four digits (the zeros) and subtracting one yields $2600$ for the skipped value.

In general, each new value of $f(k+2)$ 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 $\left(500000+1000\right)^2$, the last for $k = 8$ will be $\left(50000000+10000\right)^2$, and so on until $k=2016$. 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 $5001^2$, $k=8$ is $50001^2$, and so on. So the first missing number is $5001^2-1,50001^2-1\text{ etc.}$ 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\cdot 10^{k-2}+1\cdot 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) +\dots + f(2016)$ is:

$2.52525252525\dots 2525\cdot 10^{2015}$ + $1.11111\dots 110\cdot 10^{1008}$, with $2016$ 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 $\boxed{\textbf{(E)}\text{ 8064}}$.

Addendum: *You could also use the fact that \[(x+1)^2 = x^2 +2x+1\] In other words, the difference between $x^2$ and $(x+1)^2$ is equal to $2x+1$. We can set the inequality $2x+1 \geq 100$. Obviously, the first integer $x$ that satisfies this is 50. This way, while being longer, is IMO more motivated and doesn't use calculus.

Solution 2(Cheap Realization)

If you are one of those people who are willing take educated guesses, then just realize that $\textbf{(E)}\text{ 8064}$ is the only answer choice that is a multiple of $2016$

See Also

Related Question: https://artofproblemsolving.com/wiki/index.php/2013_AIME_II_Problems/Problem_6

2016 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 24 		Followed by
Last Problem
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_12A_Problems/Problem_25&oldid=125464"