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 "2021 Fall AMC 12B Problems/Problem 16"

(→‎Solution)
(Added new solution)
 
(8 intermediate revisions by 4 users not shown)
Line 3: Line 3:
 
Suppose <math>a</math>, <math>b</math>, <math>c</math> are positive integers such that <cmath>a+b+c=23</cmath> and <cmath>\gcd(a,b)+\gcd(b,c)+\gcd(c,a)=9.</cmath> What is the sum of all possible distinct values of <math>a^2+b^2+c^2</math>?  
 
Suppose <math>a</math>, <math>b</math>, <math>c</math> are positive integers such that <cmath>a+b+c=23</cmath> and <cmath>\gcd(a,b)+\gcd(b,c)+\gcd(c,a)=9.</cmath> What is the sum of all possible distinct values of <math>a^2+b^2+c^2</math>?  
  
−
<math>(\textbf{A})\: 259\qquad(\textbf{B}) \: 438\qquad(\textbf{C}) \: 516\qquad(\textbf{D}) \: 625\qquad(\textbf{E}) \: 687</math>
+
<math>\textbf{(A)}\: 259\qquad\textbf{(B)} \: 438\qquad\textbf{(C)} \: 516\qquad\textbf{(D)} \: 625\qquad\textbf{(E)} \: 687</math>
  
−
==Solution==
+
== Solution 1 (Observation) ==
−
Let <math>\gcd(a,b)=x</math>, <math>\gcd(b,c)=y</math>, <math>\gcd(c,a)=z</math>. WLOG, let <math>x \le y \le z</math>. We can split this off into cases:  
+
Because <math>a + b + c</math> is odd, <math>a</math>, <math>b</math>, <math>c</math> are either one odd and two evens or three odds.
 +
 
 +
<math>\textbf{Case 1}</math>: <math>a</math>, <math>b</math>, <math>c</math> have one odd and two evens.
 +
 
 +
Without loss of generality, we assume <math>a</math> is odd and <math>b</math> and <math>c</math> are even.
 +
 
 +
Hence, <math>{\rm gcd} \left( a , b \right)</math> and <math>{\rm gcd} \left( a , c \right)</math> are odd, and <math>{\rm gcd} \left( b , c \right)</math> is even.
 +
Hence, <math>{\rm gcd} \left( a , b \right) + {\rm gcd} \left( b , c \right) + {\rm gcd} \left( c , a \right)</math> is even. This violates the condition given in the problem.
 +
 
 +
Therefore, there is no solution in this case.
 +
 
 +
<math>\textbf{Case 2}</math>: <math>a</math>, <math>b</math>, <math>c</math> are all odd.
 +
 
 +
In this case, <math>{\rm gcd} \left( a , b \right)</math>, <math>{\rm gcd} \left( a , c \right)</math>, <math>{\rm gcd} \left( b , c \right)</math> are all odd.
 +
 
 +
Without loss of generality, we assume
 +
<cmath>
 +
\[
 +
{\rm gcd} \left( a , b \right) \leq {\rm gcd} \left( b , c \right) \leq {\rm gcd} \left( c , a \right) .
 +
\]
 +
</cmath>
 +
<math>\textbf{Case 2.1}</math>: <math>{\rm gcd} \left( a , b \right) = 1</math>, <math>{\rm gcd} \left( b , c \right) = 1</math>, <math>{\rm gcd} \left( c , a \right) = 7</math>.
 +
 
 +
The only solution is <math>(a, b, c) = (7, 9, 7)</math>.
 +
 
 +
Hence, <math>a^2 + b^2 + c^2 = 179</math>.
 +
 
 +
<math>\textbf{Case 2.2}</math>: <math>{\rm gcd} \left( a , b \right) = 1</math>, <math>{\rm gcd} \left( b , c \right) = 3</math>, <math>{\rm gcd} \left( c , a \right) = 5</math>.
 +
 
 +
The only solution is <math>(a, b, c) = (5, 3, 15)</math>.
 +
 
 +
Hence, <math>a^2 + b^2 + c^2 = 259</math>.
 +
 
 +
<math>\textbf{Case 2.3}</math>: <math>{\rm gcd} \left( a , b \right) = 3</math>, <math>{\rm gcd} \left( b , c \right) = 3</math>, <math>{\rm gcd} \left( c , a \right) = 3</math>.
 +
 
 +
There is no solution in this case.
 +
 
 +
Therefore, putting all cases together, the answer is <math>179 + 259 = \boxed{\textbf{(B)} \: 438}</math>.
 +
 
 +
~Steven Chen (www.professorchenedu.com)
 +
 
 +
==Solution 2 (Enumeration)==
 +
Let <math>\gcd(a,b)=x</math>, <math>\gcd(b,c)=y</math>, <math>\gcd(c,a)=z</math>. Without the loss of generality, let <math>x \le y \le z</math>. We can split this off into cases:  
  
 
<math>x=1,y=1,z=7</math>: let <math>a=7A, c=7C,</math> we can try all possibilities of <math>A</math> and <math>C</math> to find that <math>a=7, b=9, c=7</math> is the only solution.  
 
<math>x=1,y=1,z=7</math>: let <math>a=7A, c=7C,</math> we can try all possibilities of <math>A</math> and <math>C</math> to find that <math>a=7, b=9, c=7</math> is the only solution.  
Line 12: Line 54:
 
<math>x=1,y=2,z=6</math>: No solutions. By <math>y</math> and <math>z</math>, we know that <math>a</math>, <math>b</math>, and <math>c</math> have to all be divisible by <math>2</math>. Therefore, <math>x</math> cannot be equal to <math>1</math>.  
 
<math>x=1,y=2,z=6</math>: No solutions. By <math>y</math> and <math>z</math>, we know that <math>a</math>, <math>b</math>, and <math>c</math> have to all be divisible by <math>2</math>. Therefore, <math>x</math> cannot be equal to <math>1</math>.  
  
−
<math>x=1,y=3,z=5</math>: C has to be both a multiple of <math>3</math> and <math>5</math>. Therefore, <math>c</math> has to be a multiple of <math>15</math>. The only solution for this is <math>a=5, b=3, c=15</math>.  
+
<math>x=1,y=3,z=5</math>: Note that <math>c</math> has to be both a multiple of <math>3</math> and <math>5</math>. Therefore, <math>c</math> has to be a multiple of <math>15</math>. The only solution for this is <math>a=5, b=3, c=15</math>.  
  
−
<math>x=1,y=4,z=4</math>: No solutions. By <math>y</math> and <math>z</math>, we know that <math>a</math>, <math>b</math>, and <math>c</math> have to all be divisible by <math>2</math>. Therefore, <math>x</math> cannot be equal to <math>1</math>.  
+
<math>x=1,y=4,z=4</math>: No solutions. By <math>y</math> and <math>z</math>, we know that <math>a</math>, <math>b</math>, and <math>c</math> have to all be divisible by <math>4</math>. Therefore, <math>x</math> cannot be equal to <math>1</math>.  
  
−
<math>x=2,y=2,z=5</math>: No solutions. By <math>x</math> and <math>y</math>, we know that <math>a</math>, <math>b</math>, and <math>c</math> have to all be divisible by <math>2</math>. Therefore, <math>z</math> cannot be equal to <math>1</math>.  
+
<math>x=2,y=2,z=5</math>: No solutions. By <math>x</math> and <math>y</math>, we know that <math>a</math>, <math>b</math>, and <math>c</math> have to all be divisible by <math>2</math>. Therefore, <math>z</math> cannot be equal to <math>5</math>.  
  
−
<math>x=2,y=3,z=4</math>: No solutions. By <math>x</math> and <math>z</math>, we know that <math>a</math>, <math>b</math>, and <math>c</math> have to all be divisible by <math>2</math>. Therefore, <math>y</math> cannot be equal to <math>1</math>.  
+
<math>x=2,y=3,z=4</math>: No solutions. By <math>x</math> and <math>z</math>, we know that <math>a</math>, <math>b</math>, and <math>c</math> have to all be divisible by <math>2</math>. Therefore, <math>y</math> cannot be equal to <math>3</math>.  
  
 
<math>x=3,y=3,z=3</math>: No solutions. As <math>a</math>, <math>b</math>, and <math>c</math> have to all be divisible by <math>3</math>, <math>a+b+c</math> has to be divisible by <math>3</math>. This contradicts the sum <math>a+b+c=23</math>.  
 
<math>x=3,y=3,z=3</math>: No solutions. As <math>a</math>, <math>b</math>, and <math>c</math> have to all be divisible by <math>3</math>, <math>a+b+c</math> has to be divisible by <math>3</math>. This contradicts the sum <math>a+b+c=23</math>.  
  
−
Putting these solutions together, we have <math>(7^2+9^2+7^2)+(5^2+3^2+15^2)=179+259=\boxed{\textbf{(B) }438}</math>
+
Putting these solutions together, we have <math>(7^2+9^2+7^2)+(5^2+3^2+15^2)=179+259=\boxed{\textbf{(B)} \: 438}</math>.
 +
 
 +
~ConcaveTriangle
 +
 
 +
==Solution 3==
 +
Since <math>a+b+c=23</math>, <math>\gcd(a,b,c)=23</math> or <math>\gcd(a,b,c)=1</math>.
 +
 
 +
As <math>\gcd(a,b)+\gcd(b,c)+\gcd(c,a)=9</math>, it is impossible for <math>\gcd(a,b,c)=23</math>, so <math>\gcd(a,b,c)=1</math>.
 +
 
 +
This means that <math>\gcd(a,b)</math>, <math>\gcd(b,c)</math>, and <math>\gcd(c,a)</math> must all be coprime. The only possible ways for this to be true are <math>1+1+7=9</math> and <math>1+3+5=9</math>.
 +
 
 +
Without loss of generality, let <math>a\le b\le c</math>. Since <math>a+b+c=23</math>, then <math>a=7, b=7, c=9</math> or <math>a=3, b=5, c=15</math>.
 +
 
 +
<math>(7^2+7^2+9^2)+(3^2+5^2+15^2)=179+259=\boxed{\textbf{(B)} \: 438}</math>.
 +
 
 +
~bkunzang
 +
 
 +
==Video Solution By Power Of Logic==
 +
https://youtu.be/QNNIVYKvIyI
 +
 
 +
~~Hayabusa1
  
−
-ConcaveTriangle
+
==See Also==
 +
{{AMC12 box|year=2021 Fall|ab=B|num-a=17|num-b=15}}
 +
{{MAA Notice}}

Latest revision as of 19:45, 30 April 2023

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

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 is $(a, b, c) = (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 is $(a, b, c) = (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 = \boxed{\textbf{(B)} \: 438}$.

~Steven Chen (www.professorchenedu.com)

Solution 2 (Enumeration)

Let $\gcd(a,b)=x$, $\gcd(b,c)=y$, $\gcd(c,a)=z$. Without the loss of generality, 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$: Note that $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 3

Since $a+b+c=23$, $\gcd(a,b,c)=23$ or $\gcd(a,b,c)=1$.

As $\gcd(a,b)+\gcd(b,c)+\gcd(c,a)=9$, it is impossible for $\gcd(a,b,c)=23$, so $\gcd(a,b,c)=1$.

This means that $\gcd(a,b)$, $\gcd(b,c)$, and $\gcd(c,a)$ must all be coprime. The only possible ways for this to be true are $1+1+7=9$ and $1+3+5=9$.

Without loss of generality, let $a\le b\le c$. Since $a+b+c=23$, then $a=7, b=7, c=9$ or $a=3, b=5, c=15$.

$(7^2+7^2+9^2)+(3^2+5^2+15^2)=179+259=\boxed{\textbf{(B)} \: 438}$.

~bkunzang

Video Solution By Power Of Logic

https://youtu.be/QNNIVYKvIyI

~~Hayabusa1

See Also

2021 Fall AMC 12B (Problems • Answer Key • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_Fall_AMC_12B_Problems/Problem_16&oldid=192645"