A circular tabletop is divided into four congruent sectors by two diameters that are perpendicular to each other. Each sector is to be painted with one of four colors. How many distinct ways can the table be painted? (A color may be used on more than one sector, but paintings that are the same after a rotation are not considered distinct)

Source: MathMovesU MATH CHALLENGE PROBLEM - 2011/12/07

Level: Senior

Let the colors be 1, 2, 3, and 4. The paintings of the types AAAA, AAAB, AABB, AABC, ABCD, where A, B, C, D are members of {1, 2, 3, 4} and are different colors, exhaust all possibilities. Let N(t) denotes the number of distinct cyclic permutations of type t, where t is one of the 5 types described. We will calculate N(t) for each type t.
(i) t = AAAA.
There are 4 ways to choose A. All the cyclic permutations of AAAA are identical. Thus N(AAAA) = 4.
(ii) t = AAAB.
There are 4 ways to choose A and 3 ways to choose B, so there are 4*3 = 12 ways to choose A and B. All the cyclic permutations of AAAB are the identical. Thus N(AAAB) = 12.
(iii) t = AABB.
There are 4C2 = 6 ways to choose both A and B. There are 2 distinct cyclic permutations of AABB, namely AABB and ABAB. Thus N(AABB) = 6*2 = 12.
(iv) t = AABC.
There are 4 ways to choose A, 3C2 = 3 ways to choose B and C. So there are 4*3 = 12 ways to choose A, B, and C. There are 3 distinct cyclic permutations of AABC, namely AABC, AACB, and ABAC. Thus N(AABC) = 12*3 = 36.
(v) t = ABCD.
There are 4C4 = 1 way to choose A, B, C, and D. There are 1 way to fix position for A, and 3! = 6 ways to choose the positions of B, C, and D. So there are 1*6 = 6 distinct cyclic permutations of ABCD. Thus N(ABCD) = 1*6 = 6.
Summing all N(t) for the 5 types of t, the number of distinct ways the table can be painted is
N(AAAA)+N(AAAB)+N(AABB)+N(AABC)+N(ABCD)
= 4+12+12+36+6
= 70.