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

m
(Solution 2.1 (updated with better notation))
(30 intermediate revisions by 21 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>?
  
Line 5: 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 12: Line 14:
 
\end{align*}</cmath>
 
\end{align*}</cmath>
  
Hence we can write
+
Hence we have
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
 
a &= 2^3\cdot 3\cdot w\\
 
a &= 2^3\cdot 3\cdot w\\
Line 19: 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> 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>
 
<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 number of this form between 70 and 100 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 ==
  
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>
+
We can say that <math>a</math> and <math>b</math> 'have' <math>2^3 \cdot 3</math>, that <math>b</math> and <math>c</math> have <math>2^2 \cdot 3^2</math>, and that <math>c</math> and <math>d</math> have <math>3^3 \cdot 2</math>. Combining <math>1</math> and <math>2</math> yields <math>b</math> has (at a minimum) <math>2^3 \cdot 3^2</math>, and thus <math>a</math> has <math>2^3 \cdot 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 \cdot 2^2</math>, and thus <math>d</math> has <math>3^3 \cdot 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 \cdot 3</math> and <math>d = 3^3 \cdot 2</math>. According to this base case, we have <math>\gcd(a, d) = 2 \cdot 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 \cdot 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 ==
 
Elaborating on to what Solution 1 stated, we are not able to add any extra factor of 2 or 3 to <math>gcd(a, d)</math> because doing so would later the <math>gcd</math> of <math>(a, b)</math> and <math>(c, d)</math>. This is why:
 
 
The <math>gcd(a, b)</math> is <math>2^3 * 3</math> and the <math>gcd</math> of <math>(c, d)</math> is <math>2 * 3^3</math>. However, the <math>gcd</math> of <math>(b, c) = 2^2 * 3^2</math> (meaning both are divisible by 36). Therefore, <math>a</math> is only divisible by <math>3^1</math> (and no higher power of 3), while <math>d</math> is divisible by only <math>2^1</math> (and no higher power of 2).
 
 
Thus, the <math>gcd</math> of <math>(a, d)</math> can be expressed in the form <math>2 * 3 * k</math> for which <math>k</math> is a number not divisible by <math>2</math> or <math>3</math>. The only answer choice that satisfies this (and the other condition) is <math>\boxed{\textbf{(D) } 13}</math>.
 
  
 
==Solution 3 (Better notation)==
 
==Solution 3 (Better notation)==
Line 43: Line 38:
 
(Unfinished)
 
(Unfinished)
 
~Rowechen Zhong
 
~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 <math>6</math> is <math>\boxed{\textbf{(D) } 13}</math>. - mathleticguyyy + einstein
 +
 +
In the case where there can be 2 possible answers, we can do casework on <math>\gcd(d,a)</math>
 +
~Williamgolly
 +
 +
==Solution 5==
 +
 +
 +
Since <math>\gcd (a,b) = 24</math>, <math>a = 24j</math> and <math>b = 24k</math> for some positive integers <math>j,k</math> such that <math>j</math> and <math>k</math> are relatively prime.
 +
 +
Similarly , since <math>\gcd (b,c) = 36</math>, we have <math>b = 24k</math> and <math>c=36m</math> with the same criteria. However, since <math>24</math> is not a multiple of <math>36</math>, we must contribute an extra <math>3</math> to <math>b</math> in order to make it a multiple of <math>36</math>. So, <math>k</math> is a multiple of three, and it is relatively prime to <math>m</math>.
 +
 +
Finally, <math>\gcd (c,d) = 54</math>, so using the same logic, <math>m</math> is a multiple of <math>3</math> and is relatively prime to <math>n</math> where <math>d = 54n</math>.
 +
 +
Since we can't really do anything with these messy expressions, we should try some sample cases of <math>a,b,c</math> and <math>d</math>. Specifically, we let <math>j = 5, 7, 11, 13</math> or <math>17</math>, and see which one works.
 +
 +
First we let <math>j= 5</math>. Note that all of these values of <math>j</math> work for the first <math>\gcd</math> expression because they are all not divisible by <math>3</math>.
 +
 +
Without the loss of generality, we let <math>k=m=3</math> for all of our sample cases. We can also adjust the value of <math>n</math> in <math>d=54n</math>, since there is no fixed value for <math>\gcd(a,d)</math>; there is only a bound.
 +
 +
So we try to make our bound <math>70 < \gcd(a,d) < 100</math> satisfactory. We do so by letting <math>j=n</math>.
 +
 +
Testing our first case <math>a=24 \cdot 5</math> and <math>d = 54 \cdot 5</math>, we find that <math>\gcd(a,d) = 30</math>. To simplify our work, we note that <math>\gcd(24,54) = 6</math>, so <math>\gcd(24k, 54k)</math> for all <math>k>1</math> is equal to <math>6k</math>.
 +
 +
So now, we can easily find our values of <math>\gcd(a,b)</math>:
 +
 +
<cmath>\gcd(24 \cdot 5, 54 \cdot 5) = 6 \cdot 5 = 30</cmath>
 +
 +
<cmath>\gcd(24 \cdot 7, 54 \cdot 7) = 6 \cdot 7 = 42</cmath>
 +
 +
<cmath>\gcd(24 \cdot 11, 54 \cdot 11) = 6 \cdot 11 = 66</cmath>
 +
 +
<cmath>\boxed{\gcd(24 \cdot 13, 54 \cdot 13) = 6 \cdot 13 = 78}</cmath>
 +
 +
<cmath>\gcd(24 \cdot 17, 54 \cdot 17) = 6 \cdot 17 = 104</cmath>
 +
 +
We can clearly see that only <math>j=n=13</math> is in the bound <math>70 < \gcd(a,d) < 100</math>. So, <math>13</math> must be a divisor of <math>a</math>, which is answer choice <math>\boxed{\textbf{(D)}}</math>.
 +
 +
-FIREDRAGONMATH16
 +
 +
==Solution 6==
 +
 +
<asy>
 +
//Variable Declarations
 +
defaultpen(0.45);
 +
size(200pt);
 +
fontsize(15pt);
 +
pair X, Y, Z, W;
 +
real R;
 +
path quad;
 +
 +
//Variable Definitions
 +
R = 1;
 +
X = R*dir(45);
 +
Y = R*dir(135);
 +
Z = R*dir(-135);
 +
W = R*dir(-45);
 +
quad = X--Y--Z--W--cycle;
 +
 +
//Diagram
 +
draw(quad);
 +
label("$b$",X,NE);
 +
label("$a=2^3 \cdot 3 \cdot p$",Y,NW);
 +
label("$d=2 \cdot 3^3 \cdot q$",Z,SW);
 +
label("$c$",W,SE);
 +
label("$2^3 \cdot 3$",X--Y);
 +
label("$2^2 \cdot 3^2$",X--W);
 +
label("$2 \cdot 3^3$",Z--W);
 +
label("$2 \cdot 3 \cdot k$",Z--Y);
 +
</asy>
 +
 +
The relationship of <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> is shown in the above diagram. <math>gcd(a,d)=2 \cdot 3 \cdot k</math>.
 +
<math>70 < 6k < 100</math>, <math>12 \le k \le 16</math>, <math>k=\boxed{\textbf{(D) }13}</math>
 +
 +
Note that <math>gcd(b,c)=36</math> is not required to solve the problem.
 +
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
 +
 +
 +
==Solution 7 (Easier version of Solution 1)==
 +
 +
Just as in solution <math>1</math>, we prime factorize <math>a, b, c</math> and <math>d</math> to observe that
 +
 +
<math>a=2^3\cdot{3}\cdot{w}</math>
 +
 +
<math>b=2^3\cdot{3^2}\cdot{x}</math>
 +
 +
<math>c=2^2\cdot{3^3}\cdot{y}</math>
 +
 +
<math>d=2\cdot{3^3}\cdot{z}.</math>
 +
 +
Substituting these expressions for <math>a</math> and <math>d</math> into the final given,
 +
 +
<math>70<\text{gcd}(2\cdot{3^3}\cdot{z}, 2^3\cdot{3}\cdot{w})<100.</math>
 +
 +
The greatest common divisor of these two numbers is already <math>6</math>. If <math>k</math> is what we wish to multiply <math>6</math> by to obtain the gcd of these two numbers, then
 +
 +
<math>70<6k<100</math>. Testing the answer choices, only <math>13</math> works for <math>k</math> (in order for the compound inequality to hold). so our gcd is <math>78</math>, which means that <math>\boxed{\textbf{(D) }13}</math> must divide <math>a</math>.
 +
 +
-Benedict T (countmath1)
 +
 +
== 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==
 
==See Also==

Revision as of 22:00, 1 November 2022

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 \cdot 3$, that $b$ and $c$ have $2^2 \cdot 3^2$, and that $c$ and $d$ have $3^3 \cdot 2$. Combining $1$ and $2$ yields $b$ has (at a minimum) $2^3 \cdot 3^2$, and thus $a$ has $2^3 \cdot 3$ (and no more powers of $3$ because otherwise $\gcd(a,b)$ would be different). In addition, $c$ has $3^3 \cdot 2^2$, and thus $d$ has $3^3 \cdot 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 \cdot 3$ and $d = 3^3 \cdot 2$. According to this base case, we have $\gcd(a, d) = 2 \cdot 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 \cdot 13$ is the only one that works. Therefore the answer is $\boxed{\textbf{(D) } 13}$

Solution by JohnHankock

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

Solution 5

Since $\gcd (a,b) = 24$, $a = 24j$ and $b = 24k$ for some positive integers $j,k$ such that $j$ and $k$ are relatively prime.

Similarly , since $\gcd (b,c) = 36$, we have $b = 24k$ and $c=36m$ with the same criteria. However, since $24$ is not a multiple of $36$, we must contribute an extra $3$ to $b$ in order to make it a multiple of $36$. So, $k$ is a multiple of three, and it is relatively prime to $m$.

Finally, $\gcd (c,d) = 54$, so using the same logic, $m$ is a multiple of $3$ and is relatively prime to $n$ where $d = 54n$.

Since we can't really do anything with these messy expressions, we should try some sample cases of $a,b,c$ and $d$. Specifically, we let $j = 5, 7, 11, 13$ or $17$, and see which one works.

First we let $j= 5$. Note that all of these values of $j$ work for the first $\gcd$ expression because they are all not divisible by $3$.

Without the loss of generality, we let $k=m=3$ for all of our sample cases. We can also adjust the value of $n$ in $d=54n$, since there is no fixed value for $\gcd(a,d)$; there is only a bound.

So we try to make our bound $70 < \gcd(a,d) < 100$ satisfactory. We do so by letting $j=n$.

Testing our first case $a=24 \cdot 5$ and $d = 54 \cdot 5$, we find that $\gcd(a,d) = 30$. To simplify our work, we note that $\gcd(24,54) = 6$, so $\gcd(24k, 54k)$ for all $k>1$ is equal to $6k$.

So now, we can easily find our values of $\gcd(a,b)$:

\[\gcd(24 \cdot 5, 54 \cdot 5) = 6 \cdot 5 = 30\]

\[\gcd(24 \cdot 7, 54 \cdot 7) = 6 \cdot 7 = 42\]

\[\gcd(24 \cdot 11, 54 \cdot 11) = 6 \cdot 11 = 66\]

\[\boxed{\gcd(24 \cdot 13, 54 \cdot 13) = 6 \cdot 13 = 78}\]

\[\gcd(24 \cdot 17, 54 \cdot 17) = 6 \cdot 17 = 104\]

We can clearly see that only $j=n=13$ is in the bound $70 < \gcd(a,d) < 100$. So, $13$ must be a divisor of $a$, which is answer choice $\boxed{\textbf{(D)}}$.

-FIREDRAGONMATH16

Solution 6

[asy] //Variable Declarations defaultpen(0.45); size(200pt); fontsize(15pt); pair X, Y, Z, W; real R; path quad;  //Variable Definitions R = 1; X = R*dir(45); Y = R*dir(135); Z = R*dir(-135); W = R*dir(-45); quad = X--Y--Z--W--cycle;  //Diagram draw(quad); label("$b$",X,NE); label("$a=2^3 \cdot 3 \cdot p$",Y,NW); label("$d=2 \cdot 3^3 \cdot q$",Z,SW); label("$c$",W,SE); label("$2^3 \cdot 3$",X--Y); label("$2^2 \cdot 3^2$",X--W); label("$2 \cdot 3^3$",Z--W); label("$2 \cdot 3 \cdot k$",Z--Y); [/asy]

The relationship of $a$, $b$, $c$, and $d$ is shown in the above diagram. $gcd(a,d)=2 \cdot 3 \cdot k$. $70 < 6k < 100$, $12 \le k \le 16$, $k=\boxed{\textbf{(D) }13}$

Note that $gcd(b,c)=36$ is not required to solve the problem.

~isabelchen


Solution 7 (Easier version of Solution 1)

Just as in solution $1$, we prime factorize $a, b, c$ and $d$ to observe that

$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}.$

Substituting these expressions for $a$ and $d$ into the final given,

$70<\text{gcd}(2\cdot{3^3}\cdot{z}, 2^3\cdot{3}\cdot{w})<100.$

The greatest common divisor of these two numbers is already $6$. If $k$ is what we wish to multiply $6$ by to obtain the gcd of these two numbers, then

$70<6k<100$. Testing the answer choices, only $13$ works for $k$ (in order for the compound inequality to hold). so our gcd is $78$, which means that $\boxed{\textbf{(D) }13}$ must divide $a$.

-Benedict T (countmath1)

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 (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