2019 AMC 12A Problem 13

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

Small hint:

Numbers

5

and

7

are unconstrained; handle the chain

2, 4, 8

and the constraints on

6, 9

Big hint:

The color of

6

must avoid both

2

and

3,

so count depends on whether

2

and

3

share a color

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.