2019 AMC 12A Problems/Problem 13
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?
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 without loss of generality, 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 .
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 ), so we do casework on .
Case 1: and are the same color
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. Without loss of generality, 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 .
require different colors each, so there are ways to color these.
and can be any color, so there are ways to color these.
can have colors once is colored, and thus also has colors following , which leaves another for .
All together: .
|2019 AMC 12A (Problems • Answer Key • Resources)|
|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|