A rectangle is partitioned into regions as shown. Each region is to be painted a solid color - red, orange, yellow, blue, or green - so that regions that touch are painted different colors, and colors can be used more than once. How many different colorings are possible?
- A)
- B)
- C)
- D)
- E)
Answer
D
Key insight
The wide bottom-middle region touches all four others; the remaining four form a path (bottom-left, top-left, top-right, bottom-right), giving 5*4*3*3*3.
Solution
Name the regions: the bottom row has a small left piece , a wide middle piece , and a right piece ; the top row has a left piece and a right piece . Reading the figure, touches all four others; touches ; touches ; touches . The pairs and and do not touch.
Color first: choices. Then color the others in the order , so that each new region touches exactly two already-colored regions, and the previous one, which always have different colors:
- : any color but 's, choices.
- : not 's or 's color, choices.
- : not 's or 's color, choices.
- : not 's or 's color, choices.
Total: .
The answer is .
Why this works
Map-coloring counts are cleanest when regions are colored in an order where each new region's already-colored neighbors are guaranteed to use a known number of distinct colors. Starting with the region that touches everything makes every later count a fixed number, so the multiplication principle applies with no casework.
The trap
Misreading the adjacencies (for example thinking bottom-left touches bottom-right or top-right) or requiring all five colors to be different, which gives 5! = 120.
Common mistakes
- Misreading the adjacencies (for example thinking bottom-left touches bottom-right or top-right) or requiring all five colors to be different, which gives 5! = 120.
- Coloring in an order such as where the number of forbidden colors depends on earlier choices, then treating it as fixed.
Techniques
Set up the equation/formula and compute; no special trick needed