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 "2018 AMC 10A Problems/Problem 22"
(→‎Solution 4 (Fastest))
(34 intermediate revisions by 25 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
Let <math>a, b, c,</math> and <math>d</math> be positive integers such that <math>\gcd(a, b)=24</math>, <math>\gcd(b, c)=36</math>, <math>\gcd(c, d)=54</math>, and <math>70<\gcd(d, a)<100</math>. Which of the following must be a divisor of <math>a</math>?
 
Let <math>a, b, c,</math> and <math>d</math> be positive integers such that <math>\gcd(a, b)=24</math>, <math>\gcd(b, c)=36</math>, <math>\gcd(c, d)=54</math>, and <math>70<\gcd(d, a)<100</math>. Which of the following must be a divisor of <math>a</math>?
  
 
<math>\textbf{(A)} \text{ 5} \qquad \textbf{(B)} \text{ 7} \qquad \textbf{(C)} \text{ 11} \qquad \textbf{(D)} \text{ 13} \qquad \textbf{(E)} \text{ 17}</math>
 
<math>\textbf{(A)} \text{ 5} \qquad \textbf{(B)} \text{ 7} \qquad \textbf{(C)} \text{ 11} \qquad \textbf{(D)} \text{ 13} \qquad \textbf{(E)} \text{ 17}</math>
  
−
== Solution ==
+
== Solution 1 ==
 +
 
 +
The GCD information tells us that <math>24</math> divides <math>a</math>, both <math>24</math> and <math>36</math> divide <math>b</math>, both <math>36</math> and <math>54</math> divide <math>c</math>, and <math>54</math> divides <math>d</math>. Note that we have the prime factorizations:
 +
<cmath>\begin{align*}
 +
24 &= 2^3\cdot 3,\\
 +
36 &= 2^2\cdot 3^2,\\
 +
54 &= 2\cdot 3^3.
 +
\end{align*}</cmath>
 +
 
 +
Hence we have
 +
<cmath>\begin{align*}
 +
a &= 2^3\cdot 3\cdot w\\
 +
b &= 2^3\cdot 3^2\cdot x\\
 +
c &= 2^2\cdot 3^3\cdot y\\
 +
d &= 2\cdot 3^3\cdot z
 +
\end{align*}</cmath>
 +
for some positive integers <math>w,x,y,z</math>. Now if <math>3</math> divides <math>w</math>, then <math>\gcd(a,b)</math> would be at least <math>2^3\cdot 3^2</math> which is too large, hence <math>3</math> does not divide <math>w</math>. Similarly, if <math>2</math> divides <math>z</math>, then <math>\gcd(c,d)</math> would be at least <math>2^2\cdot 3^3</math> which is too large, so <math>2</math> does not divide <math>z</math>. Therefore,
 +
<cmath>\gcd(a,d)=2\cdot 3\cdot \gcd(w,z)</cmath>
 +
where neither <math>2</math> nor <math>3</math> divide <math>\gcd(w,z)</math>. In other words, <math>\gcd(w,z)</math> is divisible only by primes that are at least <math>5</math>. The only possible value of <math>\gcd(a,d)</math> between <math>70</math> and <math>100</math> and which fits this criterion is <math>78=2\cdot3\cdot13</math>, so the answer is <math>\boxed{\textbf{(D) }13}</math>.
 +
 
 +
== Solution 2 ==
  
−
We can say that a and b 'have' 2^3 * 3, that b and c have 2^2 * 3^2, and that c and d have 3^3 * 2. Combining 1 and 2 yields b has (at a minimum) 2^3 * 3^2, and thus a has 2^3 * 3 (and no more powers of 3 because otherwise the gcd(a,b) would be different). In addition, c has 3^3 * 2^2, and thus d has 3^3 * 2 (similar to a, we see that d cannot have any other powers of 2). We now assume 'worst case scenario', where a = 2^3 * 3 and d = 3^3 * 2. According to this base case, we have gcd(a, d) = 2 * 3 => 6. We want an extra factor between the two such that this number necessarily becomes between 70 and 100. Checking through, we see that 6 * 13 -> B is the only one that works.
+
We can say that <math>a</math> and <math>b</math> 'have' <math>2^3 * 3</math>, that <math>b</math> and <math>c</math> have <math>2^2 * 3^2</math>, and that <math>c</math> and <math>d</math> have <math>3^3 * 2</math>. Combining <math>1</math> and <math>2</math> yields <math>b</math> has (at a minimum) <math>2^3 * 3^2</math>, and thus <math>a</math> has <math>2^3 * 3</math> (and no more powers of <math>3</math> because otherwise <math>gcd(a,b)</math> would be different). In addition, <math>c</math> has <math>3^3 * 2^2</math>, and thus <math>d</math> has <math>3^3 * 2</math> (similar to <math>a</math>, we see that <math>d</math> cannot have any other powers of <math>2</math>). We now assume the simplest scenario, where <math>a = 2^3 * 3</math> and <math>d = 3^3 * 2</math>. According to this base case, we have <math>gcd(a, d) = 2 * 3 = 6</math>. We want an extra factor between the two such that this number is between <math>70</math> and <math>100</math>, and this new factor cannot be divisible by <math>2</math> or <math>3</math>. Checking through, we see that <math>6 * 13</math> is the only one that works. Therefore the answer is <math>\boxed{\textbf{(D) } 13}</math>
  
 
Solution by JohnHankock
 
Solution by JohnHankock
 +
 +
== Solution 2.1 (updated with better notation)==
 +
Do casework on <math>v_2</math> and <math>v_3.</math>  Notice that we must have <math>v_3(a) = 1</math> and <math>v_2(d)=1</math> and the values of <math>b,d</math> does not matter.  Therefore, <math>\gcd(d,a) = 6k,</math> where <math>k</math> is not divisible by <math>2</math> or <math>3.</math>  We see that <math>13</math> is the only possible answer.
 +
 +
-Williamgolly
 +
 +
==Solution 3 (Better notation)==
 +
 +
First off, note that <math>24</math>, <math>36</math>, and <math>54</math> are all of the form <math>2^x\times3^y</math>. The prime factorizations are <math>2^3\times 3^1</math>, <math>2^2\times 3^2</math> and <math>2^1\times 3^3</math>, respectively. Now, let <math>a_2</math> and <math>a_3</math> be the number of times <math>2</math> and <math>3</math> go into <math>a</math>,respectively. Define <math>b_2</math>, <math>b_3</math>, <math>c_2</math>, and <math>c_3</math> similiarly. Now, translate the <math>lcm</math>s into the following:
 +
<cmath>\min(a_2,b_2)=3</cmath> <cmath>\min(a_3,b_3)=1</cmath> <cmath>\min(b_2,c_2)=2</cmath> <cmath>\min(b_3,c_3)=2</cmath> <cmath>\min(a_2,c_2)=1</cmath> <cmath>\min(a_3,c_3)=3</cmath> .
 +
 +
(Unfinished)
 +
~Rowechen Zhong
 +
 +
==Solution 4 (Fastest)==
 +
Notice that <math>gcd (a,b,c,d)=gcd(gcd(a,b),gcd(b,c),gcd(c,d))=gcd(24,36,54)=6</math>, so <math>gcd(d,a)</math> must be a multiple of <math>6</math>. The only answer choice that gives a value between <math>70</math> and <math>100</math> when multiplied by 6 is <math>\boxed{\textbf{(D) } 13}</math>. - mathleticguyyy + einstein
 +
 +
In the case where there can be 2 possible answers, we can do casework on gcd(d,a)
 +
~Williamgolly
 +
 +
==Hardness of problem==
 +
 +
The ranking of this number theory problem is easy hard(just starting to be hard) or a 7 out of 10. This is because you've got to think through out although it is more of which and easy solution
 +
 +
~justin6688
 +
 +
== Video Solution by Richard Rusczyk ==
 +
 +
https://artofproblemsolving.com/videos/amc/2018amc10a/467
 +
 +
~ dolphin7
 +
 +
==Video Solution==
 +
https://youtu.be/yjrqINsQP5c
 +
 +
~savannahsolver
 +
 +
== Video Solution (Meta-Solving Technique) ==
 +
https://youtu.be/GmUWIXXf_uk?t=1003
 +
 +
~ pi_is_3.14
 +
 +
==See Also==
 +
{{AMC10 box|year=2018|ab=A|num-b=21|num-a=23}}
 +
 +
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Revision as of 20:55, 2 February 2021

Problem

Let $a, b, c,$ and $d$ be positive integers such that $\gcd(a, b)=24$, $\gcd(b, c)=36$, $\gcd(c, d)=54$, and $70<\gcd(d, a)<100$. Which of the following must be a divisor of $a$?

$\textbf{(A)} \text{ 5} \qquad \textbf{(B)} \text{ 7} \qquad \textbf{(C)} \text{ 11} \qquad \textbf{(D)} \text{ 13} \qquad \textbf{(E)} \text{ 17}$

Solution 1

The GCD information tells us that $24$ divides $a$, both $24$ and $36$ divide $b$, both $36$ and $54$ divide $c$, and $54$ divides $d$. Note that we have the prime factorizations: \begin{align*} 24 &= 2^3\cdot 3,\\ 36 &= 2^2\cdot 3^2,\\ 54 &= 2\cdot 3^3. \end{align*}

Hence we have \begin{align*} a &= 2^3\cdot 3\cdot w\\ b &= 2^3\cdot 3^2\cdot x\\ c &= 2^2\cdot 3^3\cdot y\\ d &= 2\cdot 3^3\cdot z \end{align*} for some positive integers $w,x,y,z$. Now if $3$ divides $w$, then $\gcd(a,b)$ would be at least $2^3\cdot 3^2$ which is too large, hence $3$ does not divide $w$. Similarly, if $2$ divides $z$, then $\gcd(c,d)$ would be at least $2^2\cdot 3^3$ which is too large, so $2$ does not divide $z$. Therefore, \[\gcd(a,d)=2\cdot 3\cdot \gcd(w,z)\] where neither $2$ nor $3$ divide $\gcd(w,z)$. In other words, $\gcd(w,z)$ is divisible only by primes that are at least $5$. The only possible value of $\gcd(a,d)$ between $70$ and $100$ and which fits this criterion is $78=2\cdot3\cdot13$, so the answer is $\boxed{\textbf{(D) }13}$.

Solution 2

We can say that $a$ and $b$ 'have' $2^3 * 3$, that $b$ and $c$ have $2^2 * 3^2$, and that $c$ and $d$ have $3^3 * 2$. Combining $1$ and $2$ yields $b$ has (at a minimum) $2^3 * 3^2$, and thus $a$ has $2^3 * 3$ (and no more powers of $3$ because otherwise $gcd(a,b)$ would be different). In addition, $c$ has $3^3 * 2^2$, and thus $d$ has $3^3 * 2$ (similar to $a$, we see that $d$ cannot have any other powers of $2$). We now assume the simplest scenario, where $a = 2^3 * 3$ and $d = 3^3 * 2$. According to this base case, we have $gcd(a, d) = 2 * 3 = 6$. We want an extra factor between the two such that this number is between $70$ and $100$, and this new factor cannot be divisible by $2$ or $3$. Checking through, we see that $6 * 13$ is the only one that works. Therefore the answer is $\boxed{\textbf{(D) } 13}$

Solution by JohnHankock

Solution 2.1 (updated with better notation)

Do casework on $v_2$ and $v_3.$ Notice that we must have $v_3(a) = 1$ and $v_2(d)=1$ and the values of $b,d$ does not matter. Therefore, $\gcd(d,a) = 6k,$ where $k$ is not divisible by $2$ or $3.$ We see that $13$ is the only possible answer.

-Williamgolly

Solution 3 (Better notation)

First off, note that $24$, $36$, and $54$ are all of the form $2^x\times3^y$. The prime factorizations are $2^3\times 3^1$, $2^2\times 3^2$ and $2^1\times 3^3$, respectively. Now, let $a_2$ and $a_3$ be the number of times $2$ and $3$ go into $a$,respectively. Define $b_2$, $b_3$, $c_2$, and $c_3$ similiarly. Now, translate the $lcm$s into the following: \[\min(a_2,b_2)=3\] \[\min(a_3,b_3)=1\] \[\min(b_2,c_2)=2\] \[\min(b_3,c_3)=2\] \[\min(a_2,c_2)=1\] \[\min(a_3,c_3)=3\] .

(Unfinished) ~Rowechen Zhong

Solution 4 (Fastest)

Notice that $gcd (a,b,c,d)=gcd(gcd(a,b),gcd(b,c),gcd(c,d))=gcd(24,36,54)=6$, so $gcd(d,a)$ must be a multiple of $6$. The only answer choice that gives a value between $70$ and $100$ when multiplied by 6 is $\boxed{\textbf{(D) } 13}$. - mathleticguyyy + einstein

In the case where there can be 2 possible answers, we can do casework on gcd(d,a) ~Williamgolly

Hardness of problem

The ranking of this number theory problem is easy hard(just starting to be hard) or a 7 out of 10. This is because you've got to think through out although it is more of which and easy solution

~justin6688

Video Solution by Richard Rusczyk

https://artofproblemsolving.com/videos/amc/2018amc10a/467

~ dolphin7

Video Solution

https://youtu.be/yjrqINsQP5c

~savannahsolver

Video Solution (Meta-Solving Technique)

https://youtu.be/GmUWIXXf_uk?t=1003

~ pi_is_3.14

See Also

2018 AMC 10A (Problems • Answer Key • Resources)
Preceded by
Problem 21 		Followed by
Problem 23
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

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=2018_AMC_10A_Problems/Problem_22&oldid=144728"