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 "2010 AMC 10A Problems/Problem 25"

(Created page with 'We can find the answer by working backwards. We begin with <math>1-1^2=0</math> on the bottom row, then the <math>1</math> goes to the right of the equal's sign in the row above.…')
 
(→‎Solution 1)
 
(21 intermediate revisions by 16 users not shown)
Line 1: Line 1:
−
We can find the answer by working backwards. We begin with <math>1-1^2=0</math> on the bottom row, then the <math>1</math> goes to the right of the equal's sign in the row above. We find the smallest value <math>x</math> for which <math>x-1^2=1</math> (and that does not violate the fact that <math>1^2</math> must be the greatest perfect square less than <math>x</math>), which is <math>2</math>.
+
==Problem==
  
−
We continue with the same way with the next row, but at the fourth row, we see that solving <math>x-1^2=3</math> yields <math>x=4</math>, but in that case we would have to make the <math>1^2</math> a <math>2^2</math> since <math>4 \geq 2^2</math>. So we make it a <math>2^2</math> and solve <math>x-2^2=3</math>. We continue on using this same method where we move the perfect square up by <math>1</math> each time until we get the <math>x</math> to be a value greater than the RHS plus the perfect square number. When we repeat this until we have <math>8</math> rows, we get:
+
Jim starts with a positive integer <math>n</math> and creates a sequence of numbers. Each successive number is obtained by subtracting the largest possible integer square less than or equal to the current number until zero is reached. For example, if Jim starts with <math>n = 55</math>, then his sequence contains <math>5</math> numbers:
  
−
<cmath> \begin{align*} 7223\\ 7223-84^2 &= 167\\ 167-12^2 &= 23\\ 23-4^2 &= 7\\ 7-2^2 &= 3\\ 3-1^2 &= 2\\ 2-1^2 &= 1\\ 1-1^2 &= 0\end{align*} </cmath>
 
  
−
Hence the solution is the last digit of <math>7223</math>, which is <math>3</math>.
+
<cmath>\begin{array}{ccccc}
 +
{}&{}&{}&{}&55\\
 +
55&-&7^2&=&6\\
 +
6&-&2^2&=&2\\
 +
2&-&1^2&=&1\\
 +
1&-&1^2&=&0\\
 +
\end{array}</cmath>
 +
 
 +
Let <math>N</math> be the smallest number for which Jim’s sequence has <math>8</math> numbers. What is the units digit of <math>N</math>?
 +
 
 +
<math>
 +
\mathrm{(A)}\ 1
 +
\qquad
 +
\mathrm{(B)}\ 3
 +
\qquad
 +
\mathrm{(C)}\ 5
 +
\qquad
 +
\mathrm{(D)}\ 7
 +
\qquad
 +
\mathrm{(E)}\ 9
 +
</math>
 +
 
 +
==Solution 1==
 +
 
 +
We can find the answer by working backwards. We begin with <math>1-1^2=0</math> on the bottom row, then the <math>1</math> goes to the right of the equal's sign in the row above. We find the smallest value <math>x</math> for which <math>x-1^2=1</math> and <math>x>1^2</math>, which is <math>x=2</math>.
 +
 
 +
We repeat the same procedure except with <math>x-1^2=1</math> for the next row and <math>x-1^2=2</math> for the row after that. However, at the fourth row, we see that solving <math>x-1^2=3</math> yields <math>x=4</math>, in which case it would be incorrect since <math>1^2=1</math> is not the greatest perfect square less than or equal to <math>x</math> . So we make it a <math>2^2</math> and solve <math>x-2^2=3</math>. We continue on using this same method where we increase the perfect square until <math>x</math> can be made bigger than it. When we repeat this until we have <math>8</math> rows, we get:
 +
 
 +
<cmath> \begin{array}{ccccc}{}&{}&{}&{}&7223\\ 7223&-&84^{2}&=&167\\ 167&-&12^{2}&=&23\\ 23&-&4^{2}&=&7\\ 7&-&2^{2}&=&3\\ 3&-&1^{2}&=&2\\ 2&-&1^{2}&=&1\\ 1&-&1^{2}&=&0\\ \end{array} </cmath>
 +
 
 +
Hence the solution is the last digit of <math>7223</math>, which is <math>\boxed{\textbf{(B)}\ 3}</math>.
 +
 
 +
Note: We can go up to <math>167</math>, and then notice the pattern of units digits alternating between <math>3</math> and <math>7</math>, so we do not need to calculate <math>7223</math>.
 +
 
 +
==Solution 2==
 +
Notice that to get the previous term, we must add the smallest square number, (let's call it <math>n^2</math>) such that the sum is less than <math>(n+1)^2</math>. Otherwise, instead of subtracting <math>n^2</math> from the previous term, we're subtracting a greater square number.
 +
 
 +
 
 +
Remember that <math>(x+1)^2 = x^2 + 2x + 1</math>. Recall that to find the previous term, we must add a square number such that it is less than the next square number. <math>a + n^2 < (n+1)^2</math>. For this to be true, <math>a < 2n + 1</math>. What that means is that given a term <math>a</math>, we can find the previous term by adding <math>n^2</math> where <math>n > \frac {a-1}{2}</math>.
 +
 
 +
 
 +
For example, to find the term that precedes <math>167</math>, we know that <math>n>166/2 = 83</math>. Therefore, <math>n=84</math> and the previous term is <math>167 + 84^2 = 7223</math>. The last digit of <math>7223</math> is <math>3 \Rightarrow \boxed{\textbf{(B)}\ 3}</math>
 +
 
 +
==Video Solution by the Beauty of Math==
 +
https://youtu.be/wKPoslWOlKY
 +
== See also ==
 +
{{AMC10 box|year=2010|num-b=24|after=Last Problem|ab=A}}
 +
{{AMC12 box|year=2010|num-b=14|num-a=16|ab=A}}

Latest revision as of 22:48, 3 April 2021

Problem

Jim starts with a positive integer $n$ and creates a sequence of numbers. Each successive number is obtained by subtracting the largest possible integer square less than or equal to the current number until zero is reached. For example, if Jim starts with $n = 55$, then his sequence contains $5$ numbers:


\[\begin{array}{ccccc} {}&{}&{}&{}&55\\ 55&-&7^2&=&6\\ 6&-&2^2&=&2\\ 2&-&1^2&=&1\\ 1&-&1^2&=&0\\ \end{array}\]

Let $N$ be the smallest number for which Jim’s sequence has $8$ numbers. What is the units digit of $N$?

$\mathrm{(A)}\ 1 \qquad \mathrm{(B)}\ 3 \qquad \mathrm{(C)}\ 5 \qquad \mathrm{(D)}\ 7 \qquad \mathrm{(E)}\ 9$

Solution 1

We can find the answer by working backwards. We begin with $1-1^2=0$ on the bottom row, then the $1$ goes to the right of the equal's sign in the row above. We find the smallest value $x$ for which $x-1^2=1$ and $x>1^2$, which is $x=2$.

We repeat the same procedure except with $x-1^2=1$ for the next row and $x-1^2=2$ for the row after that. However, at the fourth row, we see that solving $x-1^2=3$ yields $x=4$, in which case it would be incorrect since $1^2=1$ is not the greatest perfect square less than or equal to $x$ . So we make it a $2^2$ and solve $x-2^2=3$. We continue on using this same method where we increase the perfect square until $x$ can be made bigger than it. When we repeat this until we have $8$ rows, we get:

\[\begin{array}{ccccc}{}&{}&{}&{}&7223\\ 7223&-&84^{2}&=&167\\ 167&-&12^{2}&=&23\\ 23&-&4^{2}&=&7\\ 7&-&2^{2}&=&3\\ 3&-&1^{2}&=&2\\ 2&-&1^{2}&=&1\\ 1&-&1^{2}&=&0\\ \end{array}\]

Hence the solution is the last digit of $7223$, which is $\boxed{\textbf{(B)}\ 3}$.

Note: We can go up to $167$, and then notice the pattern of units digits alternating between $3$ and $7$, so we do not need to calculate $7223$.

Solution 2

Notice that to get the previous term, we must add the smallest square number, (let's call it $n^2$) such that the sum is less than $(n+1)^2$. Otherwise, instead of subtracting $n^2$ from the previous term, we're subtracting a greater square number.


Remember that $(x+1)^2 = x^2 + 2x + 1$. Recall that to find the previous term, we must add a square number such that it is less than the next square number. $a + n^2 < (n+1)^2$. For this to be true, $a < 2n + 1$. What that means is that given a term $a$, we can find the previous term by adding $n^2$ where $n > \frac {a-1}{2}$.


For example, to find the term that precedes $167$, we know that $n>166/2 = 83$. Therefore, $n=84$ and the previous term is $167 + 84^2 = 7223$. The last digit of $7223$ is $3 \Rightarrow \boxed{\textbf{(B)}\ 3}$

Video Solution by the Beauty of Math

https://youtu.be/wKPoslWOlKY

See also

2010 AMC 10A (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 10 Problems and Solutions
2010 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Problem 16
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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_AMC_10A_Problems/Problem_25&oldid=150976"