A circle has been divided into sectors of different sizes. Then of the sectors are painted red, painted green, and painted blue so that no two neighboring sectors are painted the same color. One such coloring is shown below.

How many different colorings are possible?
- A)
- B)
- C)
- D)
- E)
Answer
D
Key insight
Each color covers two non-neighboring sectors. Split the sectors into three such pairs (4 ways), then give the pairs the three colors (6 ways).
Solution
The sectors all have different sizes, so turning the circle gives a different coloring; every sector is its own spot. Number them to going around, so is next to .
1. Split the job in two. Each color is used on exactly two sectors. So a coloring means:
- split the six sectors into three pairs, with no pair being neighbors;
- give the three pairs the three colors, in ways.
- Count the pairings by sector 1's partner. Sector cannot pair with its neighbors or , so its partner is , or .
Partner 3. Left: . Sector can pair with , or .
- with leaves : neighbors, not allowed.
- with leaves : neighbors, not allowed.
- with leaves : fine.
One pairing: .
Partner 5. This is the mirror image of partner 3. Left: . Sector can pair with or .
- with leaves : neighbors, not allowed.
- with leaves : fine.
One pairing: .
Partner 4 (the opposite sector). Left: . Sector can pair with or .
- with leaves : fine.
- with leaves : fine.
Two pairings: and .
3. Total. There are pairings, and each can be colored in ways:
The answer is .
Why this works
When every color is used the same number of times, take the colors off first: count the ways to group the spots, then put the colors back with a simple . Grouping six spots in a circle is small enough to handle by asking "who is sector 1's partner?" and checking each case carefully.
Alternative approach
Count all colorings, then remove the bad ones. Placing two reds, two greens and two blues on six sectors can be done in ways.
- Red pair next to each other: there are neighboring pairs for red, then the other four sectors take two greens and two blues in ways, so . The same for green and for blue.
- Red and green both next to each other: red takes a neighboring pair ( ways); the other four sectors are in a row with neighboring pairs for green, and blue takes what is left. That is for each of the pairs of colors.
- All three next to each other: red takes a neighboring pair ( ways); the row of four must split into its first two and last two, with green on either end ( ways). That is .
Adding the three s counts a coloring with two touching pairs twice, so subtract the s. A coloring with all three touching pairs was then added times and subtracted times, so add the back. Bad colorings: . Good ones: .
The trap
Finding only three of the four ways to pair up the sectors, usually missing one of the two that use an opposite pair, and answering 3 × 6 = 18, choice (C).
Concise solution
The sectors have different sizes, so all six are distinguishable and no colouring is identified with a rotation of itself. Only the cyclic adjacency matters, so label the sectors in order around the circle, with next to .
Each colour is used on exactly two sectors, so a colouring amounts to two independent choices:
- split the six sectors into three pairs, no pair being two neighbours;
- give the three pairs the three colours, in ways.
Count the pairings. Sector must be paired with , or .
Partner . Sectors remain. Sector can take , or : taking leaves the neighbours ; taking leaves the neighbours ; taking leaves , which are not neighbours. One pairing, .
Partner . The mirror image of the previous case. Sector must take (taking would leave the neighbours ). One pairing, .
Partner . Sectors remain, and sector can take or . Taking leaves ; taking leaves . Both work, so two pairings, and .
That is pairings, and each gives colourings:
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
- Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
- Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.2, §3.4)
Techniques
Map the objects to something easier to count · Split into exhaustive cases and handle each · Count the complement and subtract from the total