Problem of the Month
Hint for Problem 8: Revolutionary counting

1. 1. Draw out all \(16\) possible colourings and group them into collections of equivalent colourings. Count the number of groups you have.

   2. The rotation that does nothing always fixes every colouring. For the other rotations, draw out the \(16\) possible colourings and rotate them to figure out if the colouring changes under a particular rotation.

   3. The answer to part (b) is a multiple of the answer to part (a). What is that multiple?

2. 1. Try organising your count by counting the number of inequivalent colourings of the windmill with \(0\) black blades. Then with \(1\) black blade. Then with \(2\), and then with \(3\) black blades. At this point, you’ve already secretly counted the number of inequivalent colourings of the windmill with \(4\), \(5\), and \(6\) black blades.

   2. Fix some rotation, and suppose that the rotation takes some blade to another blade. In order for a colouring to be fixed by the rotation, those two blades must be the same colour.

   3. The answer to part (b) is a multiple of the answer to part (a). What is that multiple?

3. 1. Since we are thinking of rotations as functions, we can take the composition of two rotations and get another rotation. Suppose \(E(c) = t\) and \(S(c) = m\). The goal is to show \(sm = k\). Denote the \(t\) distinct equivalent colourings by \(q_0(c), q_1(c),\ldots,q_{t-1}(c)\) for some rotations \(q_0,q_1,\ldots,q_{t-1}\). Let \(s_0,s_1,\ldots,s_{m-1}\) be the rotations satisfying \(s_j(c) = c\). Consider all compositions \(q_i \circ s_j\), of which there are \(tm\). Try to show that every rotation can be uniquely written as \(q_i \circ s_j\). It may help to prove (and use) the following fact: for any rotation \(r\), there exists a rotation \(r'\) so that \(r' \circ r = r_0\).

   2. Fix a colouring \(c\). How many stable pairs have \(c\) in the second coordinate? For the collection of all colourings \(d\) equivalent to some fixed colouring \(c\), what is the sum of all the \(S(d)\)? Part (a) will come in handy for this question.

   3. Fix a rotation \(r\). How many stable pairs have \(r\) in the first coordinate?

4. Question 3 tells us that the number of inequivalent colourings of the grid is equal to \[\frac{\operatorname{fix}(r_0) + \operatorname{fix}(r_1) + \operatorname{fix}(r_2) + \operatorname{fix}(r_3)}{4}.\]

5. First try to prove that \(\operatorname{fix}(r)\) is the same for all rotations other than \(r_0\). Such a proof will rely on the fact that \(p\) is prime.