AMC 10 Step by Step

2021 AMC Fall 10A Problem 18

P16-20~5 minPrint

A farmer's rectangular field is partitioned into 22 by 22 grid of 44 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? figure

Log in to save your progress.
Show solution without answering

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 PP, top-right QQ, bottom-right RR, bottom-left SS. Then PP and RR are diagonal and do not share a border, and neither do QQ and SS. But QQ touches both PP and RR, and so does SS.

So choose the crops for PP and RR first. Then QQ and SS each only need to get along with PP and RR, and do not affect each other.

Case 1: PP and RR get the same crop. There are 44 ways (for example, both corn). Now QQ must only avoid that crop's enemy (wheat), leaving 33 choices. SS also has 33 choices. Total: 4×3×3=364 \times 3 \times 3 = 36.

Case 2: PP and RR get different crops. There are 4×3=124 \times 3 = 12 ways. Now QQ must avoid two enemies, one for each of them. For example, if PP is corn and RR is soybeans, QQ cannot be wheat or potatoes. Different crops always have different enemies, so exactly 22 crops are ruled out and QQ has 22 choices. SS also has 22. Total: 12×2×2=4812 \times 2 \times 2 = 48.

Add the cases. 36+48=8436 + 48 = 84.

The answer is (C) 84\boxed{\textbf{(C)}\ 84}.

Why this works

In a 2×22 \times 2 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. 22 families ×\times 22 crops =4= 4.
- Three in one family, one in the other: 44 choices for the odd section and 22 for which family it is, so 88 patterns. The three connected sections share one crop (22 ways), and the odd one has 22 ways. 8×2×2=328 \times 2 \times 2 = 32.
- Two side-by-side sections in each family: 44 patterns, each block has 22 ways. 4×2×2=164 \times 2 \times 2 = 16.
- Families on the diagonals: 22 patterns, and no two same-family sections touch, so each section has 22 ways. 2×24=322 \times 2^4 = 32.

Total: 4+32+16+32=844 + 32 + 16 + 32 = 84.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Each crop has exactly one "enemy" (corn–wheat, soybeans–potatoes). In the 2×22 \times 2 grid, each section borders the two sections beside and below/above it but not the diagonally opposite one. So the two diagonal sections PP and RR are unrestricted with respect to each other, while each of the other two sections QQ and SS borders both PP and RR.

Choose the crops of PP and RR first, then count options for QQ (and identically for SS).

Case 1: PP and RR get the same crop (44 ways). Then QQ must avoid just one enemy, leaving 33 choices; same for SS. Total 4⋅3⋅3=364 \cdot 3 \cdot 3 = 36.

Case 2: PP and RR get different crops (4⋅3=124 \cdot 3 = 12 ordered ways). Now QQ must avoid the enemy of PP and the enemy of RR. These are two different crops (distinct crops have distinct enemies), so QQ has 4−2=24 - 2 = 2 choices; same for SS. Total 12⋅2⋅2=4812 \cdot 2 \cdot 2 = 48.

Adding: 36+48=8436 + 48 = 84.

The answer is (C) 84\boxed{\textbf{(C)}\ 84}.

Review in the AoPS books

Similar problems

Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.