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:
Answer (928):
The dodecagon has 6 pairs of diametrically opposite vertices. Call such a pair red or blue if both of its vertices are, respectively, red or blue, and otherwise call it mixed. Four points on a circle are the vertices of a rectangle if and only if they are the endpoints of two distinct diameters. Therefore a coloring satisfies the given condition if and only if there is at most one red pair and at most one blue pair. Consider the possible cases.
The total number of colorings that satisfy the given condition is thus .
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions