Difference between revisions of "2021 Fall AMC 12B Problems/Problem 16"

Line 70: Line 70:
  
 
~Steven Chen (www.professorchenedu.com)
 
~Steven Chen (www.professorchenedu.com)
 +
 +
==See Also==
 +
{{AMC12 box|year=2021 Fall|ab=B|num-a=17|num-b=15}}
 +
{{MAA Notice}}

Revision as of 03:10, 27 November 2021

Problem

Suppose $a$, $b$, $c$ are positive integers such that \[a+b+c=23\] and \[\gcd(a,b)+\gcd(b,c)+\gcd(c,a)=9.\] What is the sum of all possible distinct values of $a^2+b^2+c^2$?

$(\textbf{A})\: 259\qquad(\textbf{B}) \: 438\qquad(\textbf{C}) \: 516\qquad(\textbf{D}) \: 625\qquad(\textbf{E}) \: 687$

Solution 1

Let $\gcd(a,b)=x$, $\gcd(b,c)=y$, $\gcd(c,a)=z$. WLOG, let $x \le y \le z$. We can split this off into cases:

$x=1,y=1,z=7$: let $a=7A, c=7C,$ we can try all possibilities of $A$ and $C$ to find that $a=7, b=9, c=7$ is the only solution.

$x=1,y=2,z=6$: No solutions. By $y$ and $z$, we know that $a$, $b$, and $c$ have to all be divisible by $2$. Therefore, $x$ cannot be equal to $1$.

$x=1,y=3,z=5$: C has to be both a multiple of $3$ and $5$. Therefore, $c$ has to be a multiple of $15$. The only solution for this is $a=5, b=3, c=15$.

$x=1,y=4,z=4$: No solutions. By $y$ and $z$, we know that $a$, $b$, and $c$ have to all be divisible by $4$. Therefore, $x$ cannot be equal to $1$.

$x=2,y=2,z=5$: No solutions. By $x$ and $y$, we know that $a$, $b$, and $c$ have to all be divisible by $2$. Therefore, $z$ cannot be equal to $5$.

$x=2,y=3,z=4$: No solutions. By $x$ and $z$, we know that $a$, $b$, and $c$ have to all be divisible by $2$. Therefore, $y$ cannot be equal to $3$.

$x=3,y=3,z=3$: No solutions. As $a$, $b$, and $c$ have to all be divisible by $3$, $a+b+c$ has to be divisible by $3$. This contradicts the sum $a+b+c=23$.

Putting these solutions together, we have $(7^2+9^2+7^2)+(5^2+3^2+15^2)=179+259=\boxed{\textbf{(B) }438}$

-ConcaveTriangle

Solution 2

Because $a + b + c$ is odd, $a$, $b$, $c$ are either one odd and two evens or three odds.

$\textbf{Case 1}$: $a$, $b$, $c$ have one odd and two evens.

Without loss of generality, we assume $a$ is odd and $b$ and $c$ are even.

Hence, ${\rm gcd} \left( a , b \right)$ and ${\rm gcd} \left( a , c \right)$ are odd, and ${\rm gcd} \left( b , c \right)$ is even. Hence, ${\rm gcd} \left( a , b \right) + {\rm gcd} \left( b , c \right) + {\rm gcd} \left( c , a \right)$ is even. This violates the condition given in the problem.

Therefore, there is no solution in this case.

$\textbf{Case 2}$: $a$, $b$, $c$ are all odd.

In this case, ${\rm gcd} \left( a , b \right)$, ${\rm gcd} \left( a , c \right)$, ${\rm gcd} \left( b , c \right)$ are all odd.

Without loss of generality, we assume \[ {\rm gcd} \left( a , b \right) \leq {\rm gcd} \left( b , c \right) \leq {\rm gcd} \left( c , a \right) . \]

$\textbf{Case 2.1}$: ${\rm gcd} \left( a , b \right) = 1$, ${\rm gcd} \left( b , c \right) = 1$, ${\rm gcd} \left( c , a \right) = 7$.

The only solution for $\left( a, b, c \right)$ is (7, 9, 7).

Hence, $a^2 + b^2 + c^2 = 179$.

$\textbf{Case 2.2}$: ${\rm gcd} \left( a , b \right) = 1$, ${\rm gcd} \left( b , c \right) = 3$, ${\rm gcd} \left( c , a \right) = 5$.

The only solution for $\left( a, b, c \right)$ is (5, 3, 15).

Hence, $a^2 + b^2 + c^2 = 259$.

$\textbf{Case 2.3}$: ${\rm gcd} \left( a , b \right) = 3$, ${\rm gcd} \left( b , c \right) = 3$, ${\rm gcd} \left( c , a \right) = 3$.

There is no solution in this case.

Therefore, putting all cases together, the answer is $179 + 259 = 438$.

Therefore, the answer is $\boxed{\textbf{(B) }438}$.

~Steven Chen (www.professorchenedu.com)

See Also

2021 Fall AMC 12B (ProblemsAnswer KeyResources)
Preceded by
Problem 15
Followed by
Problem 17
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