A farmer's rectangular field is partitioned into by grid of rectangular sections as shown in the figure. In each section the farmer will plant one crop: corn, wheat, soybeans, or potatoes. The farmer does not want to grow corn and wheat in any two sections that share a border, and the farmer does not want to grow soybeans and potatoes in any two sections that share a border. Given these restrictions, in how many ways can the farmer choose crops to plant in each of the four sections of the field? 
- A)
- B)
- C)
- D)
- E)
Answer
C
Key insight
Diagonal sections do not touch, so fill them first. Each other section then has 3 choices if the diagonal crops match, 2 if not.
Solution
Each crop has exactly one crop it cannot sit next to: corn and wheat are "enemies", and so are soybeans and potatoes. Any crop can sit next to a copy of itself.
Name the sections: top-left , top-right , bottom-right , bottom-left . Then and are diagonal and do not share a border, and neither do and . But touches both and , and so does .
So choose the crops for and first. Then and each only need to get along with and , and do not affect each other.
Case 1: and get the same crop. There are ways (for example, both corn). Now must only avoid that crop's enemy (wheat), leaving choices. also has choices. Total: .
Case 2: and get different crops. There are ways. Now must avoid two enemies, one for each of them. For example, if is corn and is soybeans, cannot be wheat or potatoes. Different crops always have different enemies, so exactly crops are ruled out and has choices. also has . Total: .
Add the cases. .
The answer is .
Why this works
In a grid, the two diagonal sections are the ones that do not touch. Once you fix them, the other two sections face the same rule and do not bother each other, so you can just multiply. Splitting into "diagonal pair same" and "diagonal pair different" keeps it to two short cases. In grid coloring problems, look for cells that do not touch and fill them first.
Alternative approach
Sort the crops into two families: grains (corn, wheat) and roots (soybeans, potatoes). Two neighbors from different families are always fine. Two neighbors from the same family must be the same crop. So first decide each section's family, then pick crops:
- All four in one family: they must all be the same crop. families crops .
- Three in one family, one in the other: choices for the odd section and for which family it is, so patterns. The three connected sections share one crop ( ways), and the odd one has ways. .
- Two side-by-side sections in each family: patterns, each block has ways. .
- Families on the diagonals: patterns, and no two same-family sections touch, so each section has ways. .
Total: .
The trap
Treating diagonal sections as neighbors, or thinking neighbors must be different crops. Only corn next to wheat and soybeans next to potatoes are forbidden.
Concise solution
Each crop has exactly one "enemy" (corn–wheat, soybeans–potatoes). In the grid, each section borders the two sections beside and below/above it but not the diagonally opposite one. So the two diagonal sections and are unrestricted with respect to each other, while each of the other two sections and borders both and .
Choose the crops of and first, then count options for (and identically for ).
Case 1: and get the same crop ( ways). Then must avoid just one enemy, leaving choices; same for . Total .
Case 2: and get different crops ( ordered ways). Now must avoid the enemy of and the enemy of . These are two different crops (distinct crops have distinct enemies), so has choices; same for . Total .
Adding: .
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
- Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.2)
- Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.2, §3.4)
- Prealgebra, Chapter 14: Counting (§14.3)
Techniques
Split into exhaustive cases and handle each