Difference between revisions of "2016 AMC 12A Problems/Problem 25"
m (→See Also) |
|||
(17 intermediate revisions by 13 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | Let <math>k</math> 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 <math>k+1</math> digits. Every time Bernardo writes a number, Silvia erases the last <math>k</math> digits of it. Bernardo then writes the next perfect square, Silvia erases the last <math>k</math> digits of it, and this process continues until the last two numbers that remain on the board differ by at least 2. Let <math>f(k)</math> be the smallest positive integer not written on the board. For example, if <math>k = 1</math>, then the numbers that Bernardo writes are <math>16, 25, 36, 49, 64</math>, and the numbers showing on the board after Silvia erases are <math>1, 2, 3, 4, and 6</math>, and thus <math>f(1) = 5</math>. What is the sum of the digits of <math>f(2) + f(4)+ f(6) + \dots + f(2016)</math>? | + | Let <math>k</math> 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 <math>k+1</math> digits. Every time Bernardo writes a number, Silvia erases the last <math>k</math> digits of it. Bernardo then writes the next perfect square, Silvia erases the last <math>k</math> digits of it, and this process continues until the last two numbers that remain on the board differ by at least 2. Let <math>f(k)</math> be the smallest positive integer not written on the board. For example, if <math>k = 1</math>, then the numbers that Bernardo writes are <math>16, 25, 36, 49, 64</math>, and the numbers showing on the board after Silvia erases are <math>1, 2, 3, 4,</math> and <math>6</math>, and thus <math>f(1) = 5</math>. What is the sum of the digits of <math>f(2) + f(4)+ f(6) + \dots + f(2016)</math>? |
<math>\textbf{(A)}\ 7986\qquad\textbf{(B)}\ 8002\qquad\textbf{(C)}\ 8030\qquad\textbf{(D)}\ 8048\qquad\textbf{(E)}\ 8064</math> | <math>\textbf{(A)}\ 7986\qquad\textbf{(B)}\ 8002\qquad\textbf{(C)}\ 8030\qquad\textbf{(D)}\ 8048\qquad\textbf{(E)}\ 8064</math> | ||
Line 7: | Line 7: | ||
==Solution== | ==Solution== | ||
− | Consider <math>f(2)</math>. 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 <math>100</math>. | + | Consider <math>f(2)</math>. 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 <math>100</math>. Since <math>100\le (x+1)^2-x^2=2x+1</math>, this first happens at <math>x\ge \lfloor 99/2\rfloor = 50</math>. The perfect squares from here go: <math>2500, 2601, 2704, 2809\dots</math>. Note that the ones and tens also make the perfect squares, <math>1^2,2^2,3^2\dots</math>. After the ones and tens make <math>100</math>, the hundreds place will go up by <math>2</math>, thus reaching our goal. Since <math>10^2=100</math>, the last perfect square to be written will be <math>\left(50+10\right)^2=60^2=3600</math>. The missing number is one less than the number of hundreds <math>(k=2)</math> of <math>3600</math>, or <math>35</math>. |
− | Now consider f(4). Instead of the difference between two squares needing to be <math>100</math>, the difference must now be <math>10000</math>. This first happens at <math>x\ge 5000</math>. After this point, similarly, <math>\sqrt{10000}=100</math> more numbers are needed to make the <math>10^4</math> th's place go up by <math>2</math>. This will take place at <math>\left(5000+100\right)^2=5100^2= 26010000</math>. Removing the last four digits (the zeros) and subtracting one yields <math>2600</math> for the skipped value. | + | Now consider <math>f(4)</math>. Instead of the difference between two squares needing to be <math>100</math>, the difference must now be <math>10000</math>. This first happens at <math>x\ge 5000</math>. After this point, similarly, <math>\sqrt{10000}=100</math> more numbers are needed to make the <math>10^4</math> th's place go up by <math>2</math>. This will take place at <math>\left(5000+100\right)^2=5100^2= 26010000</math>. Removing the last four digits (the zeros) and subtracting one yields <math>2600</math> for the skipped value. |
In general, each new value of <math>f(k+2)</math> will add two digits to the "<math>5</math>" and one digit to the "<math>1</math>". This means that the last number Bernardo writes for <math>k=6</math> is <math>\left(500000+1000\right)^2</math>, the last for <math>k = 8</math> will be <math>\left(50000000+10000\right)^2</math>, and so on until <math>k=2016</math>. Removing the last <math>k</math> digits as Silvia does will be the same as removing <math>k/2</math> trailing zeroes on the number to be squared. This means that the last number on the board for <math>k=6</math> is <math>5001^2</math>, <math>k=8</math> is <math>50001^2</math>, and so on. So the first missing number is <math>5001^2-1,50001^2-1\text{ etc.}</math> The squaring will make a "<math>25</math>" with two more digits than the last number, a "<math>10</math>" with one more digit, and a "<math>1</math>". The missing number is one less than that, so the "1" will be subtracted from <math>f(k)</math>. In other words, <math>f(k) = 25\cdot 10^{k-2}+1\cdot 10^{k/2}</math>. | In general, each new value of <math>f(k+2)</math> will add two digits to the "<math>5</math>" and one digit to the "<math>1</math>". This means that the last number Bernardo writes for <math>k=6</math> is <math>\left(500000+1000\right)^2</math>, the last for <math>k = 8</math> will be <math>\left(50000000+10000\right)^2</math>, and so on until <math>k=2016</math>. Removing the last <math>k</math> digits as Silvia does will be the same as removing <math>k/2</math> trailing zeroes on the number to be squared. This means that the last number on the board for <math>k=6</math> is <math>5001^2</math>, <math>k=8</math> is <math>50001^2</math>, and so on. So the first missing number is <math>5001^2-1,50001^2-1\text{ etc.}</math> The squaring will make a "<math>25</math>" with two more digits than the last number, a "<math>10</math>" with one more digit, and a "<math>1</math>". The missing number is one less than that, so the "1" will be subtracted from <math>f(k)</math>. In other words, <math>f(k) = 25\cdot 10^{k-2}+1\cdot 10^{k/2}</math>. | ||
Line 26: | Line 26: | ||
Since <math>2n = 2016</math>, <math>n = 1008</math>, and <math>8n = 8064</math>, or <math>\boxed{\textbf{(E)}\text{ 8064}}</math>. | Since <math>2n = 2016</math>, <math>n = 1008</math>, and <math>8n = 8064</math>, or <math>\boxed{\textbf{(E)}\text{ 8064}}</math>. | ||
− | + | ==Solution 2 (Rigorous)== | |
− | |||
− | |||
− | ==See Also== | + | We assume <math>n \geq 1</math> for all claims. |
− | {{AMC12 box|year=2016|ab=A|num-b=24|after=Last Problem}} | + | |
+ | We will let <math>g_k(x) = \left \lfloor \frac{x^2}{10^k}\right \rfloor</math>. This is the result when the last k digits are truncated off <math>x^2</math>. | ||
+ | |||
+ | Let <math>x_n</math> = the smallest a, such that <math>g_{2n}(a) - g_{2n}(a-1) \geq 2</math> | ||
+ | |||
+ | We then have <math>\left \lfloor \frac{a^2}{10^{2n}} \right \rfloor - \left \lfloor \frac{(a-1)^2}{10^{2n}} \right \rfloor \geq 2</math> | ||
+ | |||
+ | '''Claim 1:''' <math>x_n > 5\cdot10^{2n-1}</math> | ||
+ | |||
+ | '''Proof of Claim 1:''' | ||
+ | |||
+ | Assume for the sake of contradiction, we have <math>x_n \leq 5 \cdot 10^{2n-1}</math> | ||
+ | |||
+ | Let <math>c = \frac{2x_n - 1}{10^{2n}}</math>, <math>d = \frac{(x_n-1)^2}{10^{2n}}</math> | ||
+ | |||
+ | Note that since <math>x_n \leq 5 \cdot 10^{2n-1}</math>, we have <math>c < 1</math> | ||
+ | |||
+ | It is well known that <math>\lfloor i+j \rfloor \leq \lfloor i \rfloor + \lfloor j \rfloor + 1</math> for any <math>i</math> and <math>j</math> | ||
+ | |||
+ | Since <math>x_n</math> satisfies the condition, we have: | ||
+ | |||
+ | <math>1 = \lfloor c \rfloor + 1 \geq \lfloor{c+d} \rfloor - \lfloor d \rfloor \geq 2</math> | ||
+ | |||
+ | This is a contradiction. <math>\blacksquare</math> | ||
+ | |||
+ | '''Claim 2: <math>x_n = 5 \cdot 10^{2n-1} + 10^n</math>''' | ||
+ | |||
+ | '''Proof of Claim 2:''' | ||
+ | |||
+ | We will show our choice of <math>x_n = 5 \cdot 10^{2n-1} + 10^n</math> satisfies the criteria above. | ||
+ | |||
+ | <math>\left \lfloor \frac{{x_n}^2}{10^{2n}} \right \rfloor - \left \lfloor \frac{(x_n-1)^2}{10^{2n}} \right \rfloor = \left \lfloor \frac{25 \cdot 10^{4n - 2} + 10^{3n} + 10^{2n}}{10^{2n}} \right \rfloor - \left \lfloor \frac{25 \cdot 10^{4n - 2} + 10^{3n} - 2 \cdot 10^n + 1}{10^{2n}} \right \rfloor </math> | ||
+ | |||
+ | <math>= (25 \cdot 10^{2n-2} + 10^{n} + 1) - (25 \cdot 10^{2n-2} + 10^{n} - 1) = 2</math> | ||
+ | |||
+ | Now, we will show all values smaller than <math>5 \cdot 10^{2n-1} + 10^n</math> don’t satisfy the criteria. | ||
+ | We will assume for the sake of contradiction, there exists an <math>x'_n</math> which satisfies the criteria. | ||
+ | |||
+ | We will write <math>x'_n</math> as <math>5 \cdot 10^{2n - 1} + k</math>. By our hypothesis, we have <math>k < 10^n</math>. We also have <math>k > 0</math> by claim 1. | ||
+ | |||
+ | We have <math>\left \lfloor \frac{{x'}_n^2}{10^{2n}} \right \rfloor - \left \lfloor \frac{(x'_n-1)^2}{10^{2n}} \right \rfloor = \left \lfloor \frac{25 \cdot 10^{4n - 2} + k \cdot 10^{2n} + k^2}{10^{2n}} \right \rfloor - \left \lfloor \frac{25 \cdot 10^{4n - 2} + (k-1) \cdot 10^{2n} + (k-1)^2 }{10^{2n}} \right \rfloor </math> | ||
+ | |||
+ | <math>= (25 \cdot 10^{2n-2} + k) - (25 \cdot 10^{2n-2} + k - 1) = 1 \geq 2.</math> This gets a contradiction. <math>\blacksquare</math> | ||
+ | |||
+ | '''Claim 3: <math>f(2n) = 25 \cdot10^{2n - 2} + 10^{n}</math>. ''' | ||
+ | |||
+ | '''Proof of Claim 3:''' | ||
+ | Because of claim 2, <math>x_n</math> is <math>5 \cdot 10^{2n-1} + 10^n</math>. Note that <math>g_n(x_n)</math> and <math>g_n(x_n - 1)</math> are the first numbers written that will differ by at least 2. Thus, <math>f(2n) = g_n(x_n - 1) + 1 = 25 \cdot 10^{2n-2} + 10^n</math><math>\blacksquare</math> | ||
+ | |||
+ | |||
+ | Thus, <math>f(2) + f(4) \dots f(2016) = \underbrace{(2525 \dots 25)}_{1008 \ 25s} + \underbrace{(111111 \dots 1111)}_{1008 \ 1s}</math>. This addition has no regroups/carry overs, so we can just take the sums of the digits of each of the addends, and sum them together to get 8064.<math>\boxed{(E)}</math> | ||
+ | |||
+ | -Alexlikemath | ||
+ | |||
+ | ==Video Solution by The Art of Problem Solving== | ||
+ | |||
+ | https://www.youtube.com/watch?v=xVKNTQ9bKcg&list=PLyhPcpM8aMvI7N78mYZyatqveRU30iNcf&index=5 | ||
+ | |||
+ | - AMBRIGGS | ||
+ | |||
+ | ==See Also=={{AMC12 box|year=2016|ab=A|num-b=24|after=Last Problem}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 18:28, 16 November 2022
Contents
Problem
Let 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
digits. Every time Bernardo writes a number, Silvia erases the last
digits of it. Bernardo then writes the next perfect square, Silvia erases the last
digits of it, and this process continues until the last two numbers that remain on the board differ by at least 2. Let
be the smallest positive integer not written on the board. For example, if
, then the numbers that Bernardo writes are
, and the numbers showing on the board after Silvia erases are
and
, and thus
. What is the sum of the digits of
?
Solution
Consider . 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
. Since
, this first happens at
. The perfect squares from here go:
. Note that the ones and tens also make the perfect squares,
. After the ones and tens make
, the hundreds place will go up by
, thus reaching our goal. Since
, the last perfect square to be written will be
. The missing number is one less than the number of hundreds
of
, or
.
Now consider . Instead of the difference between two squares needing to be
, the difference must now be
. This first happens at
. After this point, similarly,
more numbers are needed to make the
th's place go up by
. This will take place at
. Removing the last four digits (the zeros) and subtracting one yields
for the skipped value.
In general, each new value of will add two digits to the "
" and one digit to the "
". This means that the last number Bernardo writes for
is
, the last for
will be
, and so on until
. Removing the last
digits as Silvia does will be the same as removing
trailing zeroes on the number to be squared. This means that the last number on the board for
is
,
is
, and so on. So the first missing number is
The squaring will make a "
" with two more digits than the last number, a "
" with one more digit, and a "
". The missing number is one less than that, so the "1" will be subtracted from
. In other words,
.
Therefore:
And so on. The sum is:
+
, with
repetitions each of "
" and "
".
There is no carrying in this addition. Therefore each
adds
to the sum of the digits.
Since
,
, and
, or
.
Solution 2 (Rigorous)
We assume for all claims.
We will let . This is the result when the last k digits are truncated off
.
Let = the smallest a, such that
We then have
Claim 1:
Proof of Claim 1:
Assume for the sake of contradiction, we have
Let ,
Note that since , we have
It is well known that for any
and
Since satisfies the condition, we have:
This is a contradiction.
Claim 2:
Proof of Claim 2:
We will show our choice of satisfies the criteria above.
Now, we will show all values smaller than don’t satisfy the criteria.
We will assume for the sake of contradiction, there exists an
which satisfies the criteria.
We will write as
. By our hypothesis, we have
. We also have
by claim 1.
We have
This gets a contradiction.
Claim 3: .
Proof of Claim 3:
Because of claim 2, is
. Note that
and
are the first numbers written that will differ by at least 2. Thus,
Thus, . This addition has no regroups/carry overs, so we can just take the sums of the digits of each of the addends, and sum them together to get 8064.
-Alexlikemath
Video Solution by The Art of Problem Solving
https://www.youtube.com/watch?v=xVKNTQ9bKcg&list=PLyhPcpM8aMvI7N78mYZyatqveRU30iNcf&index=5
- AMBRIGGS
See Also
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.