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 "2017 AMC 10A Problems/Problem 20"

m (→‎Solution 2)
 
(31 intermediate revisions by 14 users not shown)
Line 5: Line 5:
  
 
==Solution 1==
 
==Solution 1==
−
Note that <math>n \equiv S(n) \pmod{9}</math>. This can be seen from the fact that <math>\sum_{k=0}^{n}10^{k}a_k \equiv \sum_{k=0}^{n}a_k \pmod{9}</math>. Thus, if <math>S(n) = 1274</math>, then <math>n \equiv 5 \pmod{9}</math>, and thus <math>n+1 \equiv S(n+1) \equiv 6 \pmod{9}</math>. The only answer choice that is <math>6 \pmod{9}</math> is <math>\boxed{\textbf{(D)}\ 1239}</math>.
+
Note that <math>n \equiv S(n) \pmod{9}</math>. This can be seen from the fact that <math>\sum_{k=0}^{n}10^{k}a_k \equiv \sum_{k=0}^{n}a_k \pmod{9}</math>. Thus, if <math>S(n) = 1274</math>, then <math>n \equiv 5 \pmod{9}</math>, and thus <math>n+1 \equiv S(n+1) \equiv 6 \pmod{9}</math>. The only answer choice that satisfies <math>n+1 \equiv 6 \pmod{9}</math> is <math>\boxed{\textbf{(D)} 1239}</math>.
  
 
==Solution 2==
 
==Solution 2==
−
We can find out that the least number of digits the number <math>N</math> is <math>142</math>, with <math>141</math> <math>9</math>'s and one <math>5</math>.
+
One divisibility rule that we can use for this problem is that a multiple of <math>9</math> will always have its digits sum to a multiple of <math>9</math>. We can find out that the least number of digits the number <math>n</math> has is <math>142</math>, with <math>141</math> <math>9</math>'s and <math>1</math> <math>5</math>, assuming the rule above. No matter what arrangement or different digits we use, the divisibility rule stays the same. To make the problem simpler, we can just use the <math>141</math> <math>9</math>'s and <math>1</math> <math>5</math>. By randomly mixing the digits up, we are likely to get: <math>9999</math>...<math>9995999</math>...<math>9999</math>. By adding <math>1</math> to this number, we get: <math>9999</math>...<math>9996000</math>...<math>0000</math>.
−
By randomly mixing the digits up, we are likely to get: <math>9999</math>...<math>9995999</math>...<math>9999</math>.
+
Knowing that <math>n+1</math> is divisible by <math>9</math> when <math>6</math>, we can subtract <math>6</math> from every available choice, and see if the number is divisible by <math>9</math> afterwards.
−
By adding 1 to this number, we get: <math>9999</math>...<math>9996000</math>...<math>0000</math>.
+
After subtracting <math>6</math> from every number, we can conclude that <math>1233</math> (originally <math>1239</math>) is the only number divisible by <math>9</math>.  
−
Knowing that this number is ONLY divisible by <math>9</math> when <math>6</math> is subtracted, we can subtract 6 from every available choice, and see if the number is divisible by <math>9</math> afterwards.
 
−
After subtracting 6 from every number, we can conclude that <math>1233</math> (originally <math>1239</math>) is the only number divisible by 9.  
 
 
So our answer is <math>\boxed{\textbf{(D)}\ 1239}</math>.
 
So our answer is <math>\boxed{\textbf{(D)}\ 1239}</math>.
 +
 +
==Solution 3==
 +
The number <math>n</math> can be viewed as having some unique digits in the front, following by a certain number of nines. We can then evaluate each potential answer choice.
 +
 +
If <math>A</math> is correct, then <math>n</math> must be some number <math>99999999...9</math>, because when we add one to <math>99999999...9</math> we get <math>10000000...00</math>. Thus, if <math>1</math> is the correct answer, then the equation <math>9x=1274</math> must have an integer solution (i.e. <math>1274</math> must be divisible by <math>9</math>). But since it does not, <math>1</math> is not the correct answer.
 +
 +
If <math>B</math> is correct, then <math>n</math> must be some number <math>29999999...9</math>, because when we add one to <math>29999999...9</math>, we get <math>30000000...00</math>. Thus, if <math>3</math> is the correct answer, then the equation <math>2+9x=1274</math> must have an integer solution. But since it does not, <math>3</math> is not the correct answer.
 +
 +
Based on what we have done for evaluating the previous two answer choices, we can create an equation we can use to evaluate the final three possibilities. Notice that if <math>S(n+1)=N</math>, then <math>n</math> must be a number whose initial digits sum to <math>N-1</math>, and whose other, terminating digits, are all <math>9</math>. Thus, we can evaluate the three final possibilities by seeing if the equation <math>(N-1)+9x=1274</math> has an integer solution.
 +
 +
The equation does not have an integer solution for <math>N=12</math>, so <math>C</math> is not correct. However, the equation does have an integer solution for <math>N=1239</math> (<math>x=4</math>), so <math>\boxed{\textbf{(D)} ~1239}</math> is the answer.
 +
 +
==Solution 4 (Intuition)==
 +
If adding <math>1</math> to <math>n</math> does not carry any of its digits, then <math>S(n+1)=S(n)+1</math> (ex: <math>25+1=26</math>. Sum of digits <math>7 \rightarrow 8</math>). But since no answer choice is <math>1275</math>, that means <math>n</math> has some amount of <math>9</math>'s from right to left.
 +
 +
When <math>n+1</math>, some <math>9</math>'s will bump to 0, not affected its<math>\pmod 9</math>. But the first non-9 digit (from right to left) will be bumped up by 1. So <math>S(n) + 1 \pmod {9} \equiv S(n+1) \pmod{9}</math>. For example, <math>34999+1=35000</math>, and the sum of digits <math>7+27 \rightarrow 8+0</math>.
 +
 +
Since <math>S(n) \equiv 5 \pmod{9}</math>, that means <math>S(n+1) \equiv 6 \pmod{9}</math>. The only answer choice that meets this requirement is <math>\boxed{\textbf{(D) } 1239}.</math>
 +
 +
==Solution 5 (Answer choices and luck)==
 +
We note quickly from the given value of <math>S(n)</math> that the form of n is likely going to be of the form <math>999999999...X9...9999</math> 
 +
where X is a natural number between 1 and 9 inclusive
 +
 +
This allows us to create the following equation
 +
 +
 +
<math>S(n+1)=1273 - 9y= A </math>
 +
 +
where <math>A</math> is an answer choice and <math>y</math> is any natural number
 +
 +
Plugging in answer choices for <math>A</math> we quickly see that
 +
<math>\boxed{\textbf{(D) } 1239}.</math> is our answer
 +
 +
<math>\textbf{Note}</math>: we do have a second possible form for <math>n</math> which is
 +
 +
<math>99999...993</math>
 +
 +
and thus <math>n+1 = 99999...994</math> and <math>S(n+1)=1273</math>
 +
 +
but since <math>1273</math> is not an answer choice we can disregard this case
 +
 +
~BakedPotato66
 +
 +
== Video Solution ==
 +
https://youtu.be/zfChnbMGLVQ?t=3996
 +
 +
~ pi_is_3.14
 +
 +
==Video Solution==
 +
https://youtu.be/pbt6p5s8J50
  
 
==See Also==
 
==See Also==
Line 19: Line 67:
 
{{AMC12 box|year=2017|ab=A|num-b=17|num-a=19}}
 
{{AMC12 box|year=2017|ab=A|num-b=17|num-a=19}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
 +
[[Category:Intermediate Number Theory Problems]]

Latest revision as of 21:45, 22 July 2024

Problem

Let $S(n)$ equal the sum of the digits of positive integer $n$. For example, $S(1507) = 13$. For a particular positive integer $n$, $S(n) = 1274$. Which of the following could be the value of $S(n+1)$?

$\textbf{(A)}\ 1 \qquad\textbf{(B)}\ 3\qquad\textbf{(C)}\ 12\qquad\textbf{(D)}\ 1239\qquad\textbf{(E)}\ 1265$

Solution 1

Note that $n \equiv S(n) \pmod{9}$. This can be seen from the fact that $\sum_{k=0}^{n}10^{k}a_k \equiv \sum_{k=0}^{n}a_k \pmod{9}$. Thus, if $S(n) = 1274$, then $n \equiv 5 \pmod{9}$, and thus $n+1 \equiv S(n+1) \equiv 6 \pmod{9}$. The only answer choice that satisfies $n+1 \equiv 6 \pmod{9}$ is $\boxed{\textbf{(D)} 1239}$.

Solution 2

One divisibility rule that we can use for this problem is that a multiple of $9$ will always have its digits sum to a multiple of $9$. We can find out that the least number of digits the number $n$ has is $142$, with $141$ $9$'s and $1$ $5$, assuming the rule above. No matter what arrangement or different digits we use, the divisibility rule stays the same. To make the problem simpler, we can just use the $141$ $9$'s and $1$ $5$. By randomly mixing the digits up, we are likely to get: $9999$...$9995999$...$9999$. By adding $1$ to this number, we get: $9999$...$9996000$...$0000$. Knowing that $n+1$ is divisible by $9$ when $6$, we can subtract $6$ from every available choice, and see if the number is divisible by $9$ afterwards. After subtracting $6$ from every number, we can conclude that $1233$ (originally $1239$) is the only number divisible by $9$. So our answer is $\boxed{\textbf{(D)}\ 1239}$.

Solution 3

The number $n$ can be viewed as having some unique digits in the front, following by a certain number of nines. We can then evaluate each potential answer choice.

If $A$ is correct, then $n$ must be some number $99999999...9$, because when we add one to $99999999...9$ we get $10000000...00$. Thus, if $1$ is the correct answer, then the equation $9x=1274$ must have an integer solution (i.e. $1274$ must be divisible by $9$). But since it does not, $1$ is not the correct answer.

If $B$ is correct, then $n$ must be some number $29999999...9$, because when we add one to $29999999...9$, we get $30000000...00$. Thus, if $3$ is the correct answer, then the equation $2+9x=1274$ must have an integer solution. But since it does not, $3$ is not the correct answer.

Based on what we have done for evaluating the previous two answer choices, we can create an equation we can use to evaluate the final three possibilities. Notice that if $S(n+1)=N$, then $n$ must be a number whose initial digits sum to $N-1$, and whose other, terminating digits, are all $9$. Thus, we can evaluate the three final possibilities by seeing if the equation $(N-1)+9x=1274$ has an integer solution.

The equation does not have an integer solution for $N=12$, so $C$ is not correct. However, the equation does have an integer solution for $N=1239$ ($x=4$), so $\boxed{\textbf{(D)} ~1239}$ is the answer.

Solution 4 (Intuition)

If adding $1$ to $n$ does not carry any of its digits, then $S(n+1)=S(n)+1$ (ex: $25+1=26$. Sum of digits $7 \rightarrow 8$). But since no answer choice is $1275$, that means $n$ has some amount of $9$'s from right to left.

When $n+1$, some $9$'s will bump to 0, not affected its$\pmod 9$. But the first non-9 digit (from right to left) will be bumped up by 1. So $S(n) + 1 \pmod {9} \equiv S(n+1) \pmod{9}$. For example, $34999+1=35000$, and the sum of digits $7+27 \rightarrow 8+0$.

Since $S(n) \equiv 5 \pmod{9}$, that means $S(n+1) \equiv 6 \pmod{9}$. The only answer choice that meets this requirement is $\boxed{\textbf{(D) } 1239}.$

Solution 5 (Answer choices and luck)

We note quickly from the given value of $S(n)$ that the form of n is likely going to be of the form $999999999...X9...9999$ where X is a natural number between 1 and 9 inclusive

This allows us to create the following equation


$S(n+1)=1273 - 9y= A$

where $A$ is an answer choice and $y$ is any natural number

Plugging in answer choices for $A$ we quickly see that $\boxed{\textbf{(D) } 1239}.$ is our answer

$\textbf{Note}$: we do have a second possible form for $n$ which is

$99999...993$

and thus $n+1 = 99999...994$ and $S(n+1)=1273$

but since $1273$ is not an answer choice we can disregard this case

~BakedPotato66

Video Solution

https://youtu.be/zfChnbMGLVQ?t=3996

~ pi_is_3.14

Video Solution

https://youtu.be/pbt6p5s8J50

See Also

2017 AMC 10A (Problems • Answer Key • Resources)
Preceded by
Problem 19 		Followed by
Problem 21
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
2017 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 17 		Followed by
Problem 19
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=2017_AMC_10A_Problems/Problem_20&oldid=223412"