Difference between revisions of "2021 Fall AMC 12B Problems/Problem 16"
(→Solution) |
(Added new solution) |
||
(11 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> | + | <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) == |
− | + | 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>. | ||
− | 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> | + | 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=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>: 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>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>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>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>. | ||
+ | |||
+ | 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 | ||
+ | |||
+ | ==See Also== | ||
+ | {{AMC12 box|year=2021 Fall|ab=B|num-a=17|num-b=15}} | ||
+ | {{MAA Notice}} |
Latest revision as of 20:45, 30 April 2023
Contents
Problem
Suppose ,
,
are positive integers such that
and
What is the sum of all possible distinct values of
?
Solution 1 (Observation)
Because is odd,
,
,
are either one odd and two evens or three odds.
:
,
,
have one odd and two evens.
Without loss of generality, we assume is odd and
and
are even.
Hence, and
are odd, and
is even.
Hence,
is even. This violates the condition given in the problem.
Therefore, there is no solution in this case.
:
,
,
are all odd.
In this case, ,
,
are all odd.
Without loss of generality, we assume
:
,
,
.
The only solution is .
Hence, .
:
,
,
.
The only solution is .
Hence, .
:
,
,
.
There is no solution in this case.
Therefore, putting all cases together, the answer is .
~Steven Chen (www.professorchenedu.com)
Solution 2 (Enumeration)
Let ,
,
. Without the loss of generality, let
. We can split this off into cases:
: let
we can try all possibilities of
and
to find that
is the only solution.
: No solutions. By
and
, we know that
,
, and
have to all be divisible by
. Therefore,
cannot be equal to
.
: Note that
has to be both a multiple of
and
. Therefore,
has to be a multiple of
. The only solution for this is
.
: No solutions. By
and
, we know that
,
, and
have to all be divisible by
. Therefore,
cannot be equal to
.
: No solutions. By
and
, we know that
,
, and
have to all be divisible by
. Therefore,
cannot be equal to
.
: No solutions. By
and
, we know that
,
, and
have to all be divisible by
. Therefore,
cannot be equal to
.
: No solutions. As
,
, and
have to all be divisible by
,
has to be divisible by
. This contradicts the sum
.
Putting these solutions together, we have .
~ConcaveTriangle
Solution 3
Since ,
or
.
As , it is impossible for
, so
.
This means that ,
, and
must all be coprime. The only possible ways for this to be true are
and
.
Without loss of generality, let . Since
, then
or
.
.
~bkunzang
Video Solution By Power Of Logic
~~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.