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?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
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 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 , so there are ways to paint , which automatically determines the color for . cannot be painted red, so there are ways to paint 6 , 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 : 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 : 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.
\text { Adding up gives } 216+216=\text { (E) } 432 \text
The problems on this page are the property of the MAA's American Mathematics Competitions