Difference between revisions of "2018 AMC 10A Problems/Problem 22"

m (added "Problem" to the top)
m (Solution 1: LaTeXed numbers)
Line 7: Line 7:
 
== Solution 1 ==
 
== Solution 1 ==
  
The gcd information tells us that 24 divides <math>a</math>, both 24 and 36 divide <math>b</math>, both 36 and 54 divide <math>c</math>, and 54 divides <math>d</math>. Note that we have the prime factorizations:
+
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*}
 
<cmath>\begin{align*}
 
24 &= 2^3\cdot 3,\
 
24 &= 2^3\cdot 3,\
Line 21: Line 21:
 
d &= 2\cdot 3^3\cdot z
 
d &= 2\cdot 3^3\cdot z
 
\end{align*}</cmath>
 
\end{align*}</cmath>
for some positive integers <math>w,x,y,z</math>. Now if 3 divdes <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 3 does not divide <math>w</math>. Similarly, if 2 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 2 does not divide <math>z</math>. Therefore,
+
for some positive integers <math>w,x,y,z</math>. Now if <math>3</math> divdes <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>
 
<cmath>\gcd(a,d)=2\cdot 3\cdot \gcd(w,z)</cmath>
where neither 2 nor 3 divide <math>\gcd(w,z)</math>. In other words, <math>\gcd(w,z)</math> is divisible only by primes that are at least 5. The only possible value of <math>\gcd(a,d)</math> between 70 and 100 and which fits this criterion is <math>78=2\cdot3\cdot13</math>, so the answer is <math>\boxed{\textbf{(D) }13}</math>.
+
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 ==
 
== Solution 2 ==

Revision as of 20:23, 1 January 2020

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$ divdes $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

Elaborating on to what Solution 1 stated, we are not able to add any extra factor of 2 or 3 to $gcd(a, d)$ because doing so would later the $gcd$ of $(a, b)$ and $(c, d)$. This is why:

The $gcd(a, b)$ is $2^3 * 3$ and the $gcd$ of $(c, d)$ is $2 * 3^3$. However, the $gcd$ of $(b, c) = 2^2 * 3^2$ (meaning both are divisible by 36). Therefore, $a$ is only divisible by $3^1$ (and no higher power of 3), while $d$ is divisible by only $2^1$ (and no higher power of 2).

Thus, the $gcd$ of $(a, d)$ can be expressed in the form $2 * 3 * k$ for which $k$ is a number not divisible by $2$ or $3$. The only answer choice that satisfies this (and the other condition) is $\boxed{\textbf{(D) } 13}$.

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

See Also

2018 AMC 10A (ProblemsAnswer KeyResources)
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