Difference between revisions of "2019 AMC 12A Problems/Problem 13"
Sevenoptimus (talk | contribs) m (Slightly fixed punctuation) |
(→Solution) |
||
Line 5: | Line 5: | ||
<math>\textbf{(A)}\ 144\qquad\textbf{(B)}\ 216\qquad\textbf{(C)}\ 256\qquad\textbf{(D)}\ 384\qquad\textbf{(E)}\ 432</math> | <math>\textbf{(A)}\ 144\qquad\textbf{(B)}\ 216\qquad\textbf{(C)}\ 256\qquad\textbf{(D)}\ 384\qquad\textbf{(E)}\ 432</math> | ||
− | ==Solution== | + | ==Solution 1== |
The <math>5</math> and <math>7</math> can be painted with no restrictions because the set of integers does not contain a multiple or proper factor of <math>5</math> or <math>7</math>. There are 3 ways to paint each, giving us <math>\underline{9}</math> ways to paint both. The <math>2</math> is the most restrictive number. There are <math>\underline{3}</math> ways to paint <math>2</math>, but WLOG, let it be painted red. <math>4</math> cannot be the same color as <math>2</math> or <math>8</math>, so there are <math>\underline{2}</math> ways to paint <math>4</math>, which automatically determines the color for <math>8</math>. <math>6</math> cannot be painted red, so there are <math>\underline{2}</math> ways to paint <math>6</math>, but WLOG, let it be painted blue. There are <math>\underline{2}</math> choices for the color for <math>3</math>, which is either red or green in this case. Lastly, there are <math>\underline{2}</math> ways to choose the color for <math>9</math>. | The <math>5</math> and <math>7</math> can be painted with no restrictions because the set of integers does not contain a multiple or proper factor of <math>5</math> or <math>7</math>. There are 3 ways to paint each, giving us <math>\underline{9}</math> ways to paint both. The <math>2</math> is the most restrictive number. There are <math>\underline{3}</math> ways to paint <math>2</math>, but WLOG, let it be painted red. <math>4</math> cannot be the same color as <math>2</math> or <math>8</math>, so there are <math>\underline{2}</math> ways to paint <math>4</math>, which automatically determines the color for <math>8</math>. <math>6</math> cannot be painted red, so there are <math>\underline{2}</math> ways to paint <math>6</math>, but WLOG, let it be painted blue. There are <math>\underline{2}</math> choices for the color for <math>3</math>, which is either red or green in this case. Lastly, there are <math>\underline{2}</math> ways to choose the color for <math>9</math>. | ||
<math>9 \cdot 3 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = \boxed{\textbf{(E) }432}</math>. | <math>9 \cdot 3 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = \boxed{\textbf{(E) }432}</math>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | We note that the primes can be colored any of the <math>3</math> colors since they don't have any proper divisors other than <math>1</math>, which is not in the list. Furthermore, <math>6</math> is the only number in the list that has <math>2</math> distinct prime factors (namely, <math>2</math> and <math>3</math>), thus we do casework on <math>6</math>. | ||
+ | |||
+ | Case 1: <math>2</math> and <math>3</math> are the same colors | ||
+ | |||
+ | In this case, we have <math>3</math> primes to choose the color for (<math>2</math>, <math>5</math>, and <math>7</math>). Afterwards, <math>4</math>, <math>6</math>, and <math>9</math> have two possible colors, which will determine the color of <math>8</math>. Thus, there are <math>3^3\cdot 2^3=216</math> possibilities here. | ||
+ | |||
+ | Case 2: <math>2</math> and <math>3</math> are different colors | ||
+ | |||
+ | In this case, we have <math>4</math> primes to color. WLOG, we'll color the <math>2</math> first, then the <math>3</math>. Then there are <math>3</math> color choices for <math>2,5,7</math>, and <math>2</math> color choices for <math>3</math>. This will determine the color of <math>6</math> as well. After that, we only need to choose the color for <math>4</math> and <math>9</math>, which each have <math>2</math> choices. Thus, there are <math>3^3\cdot 2^3=216</math> possibilities here as well. | ||
+ | |||
+ | Adding up gives <math>216+216=\boxed{\textbf{(E) }432}</math>. | ||
==See Also== | ==See Also== |
Revision as of 22:35, 10 February 2019
Contents
[hide]Problem
How many ways are there to paint each of the integers either red, green, or blue so that each number has a different color from each of its proper divisors?
Solution 1
The and
can be painted with no restrictions because the set of integers does not contain a multiple or proper factor of
or
. There are 3 ways to paint each, giving us
ways to paint both. The
is the most restrictive number. There are
ways to paint
, but WLOG, let it be painted red.
cannot be the same color as
or
, so there are
ways to paint
, which automatically determines the color for
.
cannot be painted red, so there are
ways to paint
, but WLOG, let it be painted blue. There are
choices for the color for
, which is either red or green in this case. Lastly, there are
ways to choose the color for
.
.
Solution 2
We note that the primes can be colored any of the colors since they don't have any proper divisors other than
, which is not in the list. Furthermore,
is the only number in the list that has
distinct prime factors (namely,
and
), thus we do casework on
.
Case 1: and
are the same colors
In this case, we have primes to choose the color for (
,
, and
). Afterwards,
,
, and
have two possible colors, which will determine the color of
. Thus, there are
possibilities here.
Case 2: and
are different colors
In this case, we have primes to color. WLOG, we'll color the
first, then the
. Then there are
color choices for
, and
color choices for
. This will determine the color of
as well. After that, we only need to choose the color for
and
, which each have
choices. Thus, there are
possibilities here as well.
Adding up gives .
See Also
2019 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 12 |
Followed by Problem 14 |
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.