Problem:
Each vertex of a regular dodecagon (-gon) is to be colored either red or blue, and thus there are possible colorings. Find the number of these colorings with the property that no four vertices colored the same color are the four vertices of a rectangle.
Solution:
The condition is equivalent to requiring that no two pairs of opposite vertices on the 12-gon are assigned the same color.
Case 1: No opposite pairs have the same color.
We are free to assign either color to vertices through , and the colors of the opposite vertices through are determined (must be the opposite color). This yields:
Case 2: Exactly one pair of opposite vertices has the same color.
Again, we assign colors freely to vertices through , giving choices. Then, we choose of the opposite pairs to break the rule and assign the same color. This gives:
Case 3: Exactly two opposite pairs have the same color, and the rest are opposite.
We choose of the pairs to violate the condition and be identically colored. There are ways to choose these pairs. Again, starting with ways to assign the first six vertices, we multiply by and then divide by because half of these colorings will result in at least two pairs having the same color on both ends, which violates the condition. Hence:
No further cases are possible: three or more pairs with the same color would force at least two to be identically colored, violating the condition.
Adding all valid cases:
The problems on this page are the property of the MAA's American Mathematics Competitions