Maths Olympiad Prep

Library / /418 of 462

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Ireland

A designer plans to decorate the opening ceremony for this year's IMO contest in Romania with rows of coloured clock faces. Each clock face consists of twelve coloured rectangles glued to a round white base, as illustrated below.
Figure 1

The following design rules apply:
1. Each rectangle is blue, yellow, or red.
2. All three colours must be used somewhere on the clock face.

Two clock faces are considered identical whenever one can be rotated to match the colours of the other.

How many distinct clock faces could be made?

Solution

Consider first the set SmS_m of all possible clock faces using mm colours, where we consider two to be equal only if the colours match without any rotation: there are m12m^{12} elements in SmS_m. Let ff be the map that rotates an element of SmS_m by 1/121/12 of a complete circle, i.e. 30 degrees. (ff depends on mm, but the action is the same regardless of mm, so we just write ff.) All elements xSmx \in S_m have period 12 under ff, but some have smaller periods. Let p(x)p(x) be the least period of xx, and let nm(k)n_m(k) be the number of elements xSmx \in S_m such that p(x)=kp(x) = k.

It is clear that the possible values of p(x)p(x) are the divisors of 12, and that the number of distinct clock faces, allowing at most mm colours and counting rotated clock faces as being identical, is
N(m):=nm(12)12+nm(6)6+nm(4)4+nm(3)3+nm(2)2+nm(1)1. N(m) := \frac{n_m(12)}{12} + \frac{n_m(6)}{6} + \frac{n_m(4)}{4} + \frac{n_m(3)}{3} + \frac{n_m(2)}{2} + \frac{n_m(1)}{1}.

Since there are three ways to select two of the three colours, the answer to the problem is N(3)3N(2)+3N(1)N(3) - 3N(2) + 3N(1); the last term is because each one-colour clock face is removed twice, so we must add it back.

To make the solution explicit, it remains to compute a formula for nm(k)n_m(k) for each divisor kk of 12. It is clear that nm(1)=mn_m(1) = m.

Next, nm(2)=m2mn_m(2) = m^2 - m: we remove from the set of elements with period 2 those that also have period 1. Similarly, nm(3)=m3mn_m(3) = m^3 - m and nm(4)=m4m2n_m(4) = m^4 - m^2.

With a little more thought, we see that nm(6)=m6m3m2+mn_m(6) = m^6 - m^3 - m^2 + m and nm(12)=m12m6m4+m2n_m(12) = m^{12} - m^6 - m^4 + m^2. For instance, for nm(12)n_m(12), we remove from SmS_m those elements with period 6 and those with period 4, leaving only elements with least period 12. However, when we removed the elements with smaller period, we double-counted those with least period dividing gcd(6,4)=2\gcd(6, 4) = 2, so we add these back.

Explicitly, we obtain N(1)=1N(1) = 1, N(2)=352N(2) = 352, N(3)=44,368N(3) = 44,368 and so the final answer is N(3)3N(2)+3N(1)=43,315N(3) - 3N(2) + 3N(1) = 43,315.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.