AMC 10 · 2019 · #13

Grade 7 counting

Archetype Constraint Graph Coloring └ Sub-archetype Degree-Driven Extreme Pinning

graph-coloringfactorsfundamental-counting-principlecasework identify-subproblemscaseworksystematic-enumeration ↑ Prerequisites: factorsfundamental-counting-principle

📏 Medium solution 💡 3 insights

Problem

Each of the eight integers from 2 to 9 gets one of three colors: red, green, or blue. The only rule is that a number may not share a color with any of its proper divisors that also appear in the list. Count all colorings that obey the rule.

Pick an answer.

(A)

144

(B)

216

(C)

256

(D)

384

(E)

432

How to solve

Strategy Identify Subproblems

Eight numbers and three colors give 3⁸ = 6561 raw colorings, far too many to check one by one, so I look for structure instead. Drawing an arrow from each number to its multiples shows the rule links only a few pairs, and the picture breaks into pieces that do not talk to each other: 5 and 7 float free, and the rest hang off 2 and 3. Pieces that share no constraint can be counted separately and multiplied, so the job shrinks to a few tiny counts. Inside the piece holding 3, 6, and 9 the count depends on one yes-or-no fact, whether 3 copies the color of 2, so I finish that piece with two short cases.

1STEP 1

Find which pairs actually clash

Pick out only the pairs that actually clash.

4:{2}, 6:{2,3}, 8:{2,4}, 9:{3}, 2,3,5,7:{ }

2STEP 2

Split into independent pieces

It splits into independent pieces.

{5,7} free; 2-4-8 chain; 3-9; 6 linked to both 2 and 3

3STEP 3

Color the free numbers 5 and 7

Five and seven are completely free.

3 × 3 = 9

4STEP 4

Walk the chain 2, 4, 8

Walk the chain from two to four to eight.

3 · 2 · 1 = 6

5STEP 5

Case on whether 3 copies 2

Six touches both, splitting into cases.

1 · 2₃ matches 2 + 2 · 1₃ differs = 4, 4 · 2 = 8

6STEP 6

Multiply the pieces together

Multiplying the pieces gives 432.

9 · 6 · 8 = 432

Answer

432

Without any rule there are 3⁸ = 6561 colorings, and 432 is well under that, as it must be. It is also a sensible size: the six clashing pairs should cut the count a lot but not to almost nothing, and 432/6561 is about 6.6%. A structure check confirms the number: 432 = 9 · 6 · 8, where 9 = 3² comes from the two unrestricted numbers, 6 from the forced chain 2, 4, 8, and 8 from the {3, 6, 9} piece. Every factor is divisible only by 2 and 3, which fits a count built from threes and twos, and choices like 256 = 2⁸ carry no factor of 3 at all, so they could never come from a 3-color count that starts with 3 free choices.

💡Key takeaway

Draw the links first: parts of a problem that cannot touch each other can be counted separately and multiplied, and with three colors a number blocked by two different colors has no choice left.

Find which pairs actually clash
Split into independent pieces
Color the free numbers 5 and 7
Walk the chain 2, 4, 8
Case on whether 3 copies 2
Multiply the pieces together