Problem:
A farmer's rectangular field is partitioned into a 2 by 2 grid of 4 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?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Let the sections of the field be numbered clockwise starting with the upper left as sections 1, 2, 3 , and 4 . There are 4 ways to select a crop to plant in section 1. If section 3 is planted with the crop in section 1 , there are 3 ways to select crops for each of sections 2 and 4 , yielding ways. If section 3 is planted with the crop that cannot be planted adjacent to the crop in section 1, then there are 2 ways to select crops for each of sections 2 and 4 , yielding ways. If section 3 is planted with one of the other 2 crops, then there are 2 ways to select crops for each of sections 2 and 4 , yielding ways. This gives a total of ways.
If only one crop is planted, then there are 4 ways to choose that crop. If two compatible crops are planted, then there are ways to choose those crops and then ways to plant, for possibilities. It is not possible to plant two incompatible crops without violating the condition. If three crops are planted, then there are 4 ways to choose them and ways to plant, for 16 choices. If four crops are planted, then there are ways to plant them. The total number of choices is .
As above, let the sections of the field be numbered clockwise starting with the upper left as sections , and 4 . There are ways for crops to be assigned to sections of the field without regard to crops that are not to be planted in adjacent sections.
This problem will be solved via complementary counting. To this end, let be the set of ways such that sections 1 and 2 are planted with crops that should not be planted in adjacent sections, and similarly, let , and be the set of ways sections 2 and 3,3 and 4 , and 4 and 1 , respectively, can be planted with crops that should not be planted in adjacent sections. Each of the sets , and contains elements. Each of the intersections , and contains elements, while the intersections and each contain elements. Each of the intersections of three of these sets contains 4 elements. The intersection of all four of the sets contains 4 elements.
The Inclusion-Exclusion Principle implies that the size of is . Thus the number of ways to plant the sections so that adjacent sections are not planted with incompatible crops is .
The problems on this page are the property of the MAA's American Mathematics Competitions