Question

How many ways are there to paint each of the integers $2, 3, \ldots, 9$ either red, green, or blue so that each number has a different color from each of its proper divisors?

$144$

$216$

$256$

$384$

$432$

Answer: E

Concepts:graph theory divisibility casework

Difficulty rating: 1630

Solution:

The primes $5$ and $7$ have no proper divisors here, giving $3$ choices each.

Along the chain $2 \to 4 \to 8,$ there are $3 \cdot 2 \cdot 1 = 6$ colorings. Number $9$ must differ from $3,$ giving $2$ choices once $3$ is set.

Number $6$ must differ from both $2$ and $3.$ Summing over the colors of $2$ and $3$ (equal in $3$ pairs, unequal in $6$ pairs), the combined factor for $4, 8, 9, 6$ totals $2 \cdot 2 \cdot (3 \cdot 2 + 6 \cdot 1) = 48.$

Multiplying by the $9$ ways for $5$ and $7$ gives $48 \cdot 9 = 432.$

Thus, the correct answer is E.

2019 AMC 12A Problem 13

Answer: E

Difficulty rating: 1630

Solution:

Problem 13 in Other Years