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)
Line 5: Line 5:
 
== Solution ==
 
== Solution ==
  
−
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 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 -> D is the only one that works.
  
 
Solution by JohnHankock
 
Solution by JohnHankock

Revision as of 16:07, 8 February 2018

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

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 -> D is the only one that works.

Solution by JohnHankock

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_10A_Problems/Problem_22&oldid=90551"