Difference between revisions of "2018 AMC 10B Problems/Problem 21"

(Solution 1)
(26 intermediate revisions by 12 users not shown)
Line 1: Line 1:
 +
{{duplicate|[[2018 AMC 12B Problems|2018 AMC 12B #19]] and [[2018 AMC 10B Problems|2018 AMC 10B #21]]}}
 +
 
==Problem==
 
==Problem==
 
Mary chose an even <math>4</math>-digit number <math>n</math>. She wrote down all the divisors of <math>n</math> in increasing order from left to right: <math>1,2,...,\dfrac{n}{2},n</math>. At some moment Mary wrote <math>323</math> as a divisor of <math>n</math>. What is the smallest possible value of the next divisor written to the right of <math>323</math>?
 
Mary chose an even <math>4</math>-digit number <math>n</math>. She wrote down all the divisors of <math>n</math> in increasing order from left to right: <math>1,2,...,\dfrac{n}{2},n</math>. At some moment Mary wrote <math>323</math> as a divisor of <math>n</math>. What is the smallest possible value of the next divisor written to the right of <math>323</math>?
Line 6: Line 8:
 
==Solution 1==
 
==Solution 1==
  
Prime factorizing <math>323</math> gives you <math>17 \cdot 19</math>. The desired answer needs to be a multiple of <math>17</math> or <math>19</math>, because if it is not a multiple of <math>17</math> or <math>19</math>, the LCM, or the least possible value for <math>n</math>, will not be more than 4 digits. Looking at the answer choices, <math>\fbox{(C) 340}</math> is the smallest number divisible by <math>17</math> or <math>19</math>. Checking, we can see that <math>n</math> would be <math>6460</math>.
+
Since prime factorizing <math>323</math> gives you <math>17 \cdot 19</math>, the desired answer needs to be a multiple of <math>17</math> or <math>19</math>, this is because if it is not a multiple of <math>17</math> or <math>19</math>, <math>n</math> will be more than a <math>4</math> digit number. For example, if the answer were to instead be <math>324</math>, <math>n</math> would have to be a multiple of <math>2^2 * 3^4 * 17 * 19</math> for both <math>323</math> and <math>324</math> to be a valid factor, meaning <math>n</math> would have to be at least <math>104652</math>, which is too big. Looking at the answer choices, <math>\text{(A) }324</math> and <math>\text{(B) }330</math> are both not a multiple of neither 17 nor 19, <math>\text{(C) }340</math> is divisible by <math>17</math>. <math>\text{(D) }361</math> is divisible by <math>19</math>, and <math>\text{(E) }646</math> is divisible by both <math>17</math> and <math>19</math>. Since <math>\boxed{\text{(C) }340}</math> is the smallest number divisible by either <math>17</math> or <math>19</math> it is the answer. Checking, we can see that <math>n</math> would be <math>6460</math>, a four-digit number. Note that <math>n</math> is also divisible by <math>2</math>, one of the listed divisors of <math>n</math>. (If <math>n</math> was not divisible by <math>2</math>, we would need to look for a different divisor)
 +
 
 +
-Edited by Mathandski
  
 
==Solution 2==
 
==Solution 2==
Let the next largest divisor be <math>k</math>. Suppose <math>\gcd(k,323)=1</math>. Then, as <math>323|n, k|n</math>, therefore, <math>323\cdot k|n.</math> However, because <math>k>323</math>, <math>323k>323\cdot 324>9999</math>. Therefore, <math>\gcd(k,323)>1</math>. Note that <math>323=17\cdot 19</math>. Therefore, the smallest the gcd can be is <math>17</math> and our answer is <math>323+17=\boxed{\text{(C) }340}</math>.
+
Let the next largest divisor be <math>k</math>. Suppose <math>\gcd(k,323)=1</math>. Then, as <math>323|n, k|n</math>, therefore, <math>323\cdot k|n.</math> However, because <math>k>323</math>, <math>323k>323\cdot 324>9999</math>. Therefore, <math>\gcd(k,323)>1</math>. Note that <math>323=17\cdot 19</math>. Therefore, the smallest the GCD can be is <math>17</math> and our answer is <math>323+17=\boxed{\text{(C) }340}</math>.
 +
 
 +
==Solution 3==
 +
Again, recognize <math>323=17 \cdot 19</math>. The 4-digit number is even, so its prime factorization must then be <math>17 \cdot 19 \cdot 2 \cdot n</math>. Also, <math>1000\leq 646n \leq 9998</math>, so <math>2 \leq n \leq 15</math>. Since <math>15 \cdot 2=30</math>, the prime factorization of the number after <math>323</math> needs to have either <math>17</math> or <math>19</math>. The next highest product after <math>17 \cdot 19</math> is <math>17 \cdot 2  \cdot 10 =340</math> or <math>19 \cdot 2  \cdot 9 =342</math> <math>\implies \boxed{\text{(C) }340}</math>.
 +
 
 +
 
 +
You can also tell by inspection that <math>19\cdot18 > 20\cdot17</math>, because <math>19\cdot18</math> is closer to the side lengths of a square, which maximizes the product.
 +
 
 +
~bjhhar
 +
 
 +
==Video Solution 1==
 +
 
 +
https://www.youtube.com/watch?v=qlHE_sAXiY8
 +
 
 +
==Video Solution 2==
 +
 
 +
https://www.youtube.com/watch?v=KHaLXNAkDWE
 +
 
 +
==Video Solution 3==
 +
 
 +
https://www.youtube.com/watch?v=vc1FHO9YYKQ
 +
 
 +
~bunny1
  
 
==See Also==
 
==See Also==
Line 15: Line 41:
 
{{AMC12 box|year=2018|ab=B|num-b=18|num-a=20}}
 
{{AMC12 box|year=2018|ab=B|num-b=18|num-a=20}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
 +
[[Category:Intermediate Number Theory Problems]]

Revision as of 21:59, 31 December 2020

The following problem is from both the 2018 AMC 12B #19 and 2018 AMC 10B #21, so both problems redirect to this page.

Problem

Mary chose an even $4$-digit number $n$. She wrote down all the divisors of $n$ in increasing order from left to right: $1,2,...,\dfrac{n}{2},n$. At some moment Mary wrote $323$ as a divisor of $n$. What is the smallest possible value of the next divisor written to the right of $323$?

$\textbf{(A) } 324 \qquad \textbf{(B) } 330 \qquad \textbf{(C) } 340 \qquad \textbf{(D) } 361 \qquad \textbf{(E) } 646$

Solution 1

Since prime factorizing $323$ gives you $17 \cdot 19$, the desired answer needs to be a multiple of $17$ or $19$, this is because if it is not a multiple of $17$ or $19$, $n$ will be more than a $4$ digit number. For example, if the answer were to instead be $324$, $n$ would have to be a multiple of $2^2 * 3^4 * 17 * 19$ for both $323$ and $324$ to be a valid factor, meaning $n$ would have to be at least $104652$, which is too big. Looking at the answer choices, $\text{(A) }324$ and $\text{(B) }330$ are both not a multiple of neither 17 nor 19, $\text{(C) }340$ is divisible by $17$. $\text{(D) }361$ is divisible by $19$, and $\text{(E) }646$ is divisible by both $17$ and $19$. Since $\boxed{\text{(C) }340}$ is the smallest number divisible by either $17$ or $19$ it is the answer. Checking, we can see that $n$ would be $6460$, a four-digit number. Note that $n$ is also divisible by $2$, one of the listed divisors of $n$. (If $n$ was not divisible by $2$, we would need to look for a different divisor)

-Edited by Mathandski

Solution 2

Let the next largest divisor be $k$. Suppose $\gcd(k,323)=1$. Then, as $323|n, k|n$, therefore, $323\cdot k|n.$ However, because $k>323$, $323k>323\cdot 324>9999$. Therefore, $\gcd(k,323)>1$. Note that $323=17\cdot 19$. Therefore, the smallest the GCD can be is $17$ and our answer is $323+17=\boxed{\text{(C) }340}$.

Solution 3

Again, recognize $323=17 \cdot 19$. The 4-digit number is even, so its prime factorization must then be $17 \cdot 19 \cdot 2 \cdot n$. Also, $1000\leq 646n \leq 9998$, so $2 \leq n \leq 15$. Since $15 \cdot 2=30$, the prime factorization of the number after $323$ needs to have either $17$ or $19$. The next highest product after $17 \cdot 19$ is $17 \cdot 2  \cdot 10 =340$ or $19 \cdot 2  \cdot 9 =342$ $\implies \boxed{\text{(C) }340}$.


You can also tell by inspection that $19\cdot18 > 20\cdot17$, because $19\cdot18$ is closer to the side lengths of a square, which maximizes the product.

~bjhhar

Video Solution 1

https://www.youtube.com/watch?v=qlHE_sAXiY8

Video Solution 2

https://www.youtube.com/watch?v=KHaLXNAkDWE

Video Solution 3

https://www.youtube.com/watch?v=vc1FHO9YYKQ

~bunny1

See Also

2018 AMC 10B (ProblemsAnswer KeyResources)
Preceded by
Problem 20
Followed by
Problem 22
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
2018 AMC 12B (ProblemsAnswer KeyResources)
Preceded by
Problem 18
Followed by
Problem 20
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