Problem of the Month
Problem 8: Revolutionary counting

This Problem of the Month is inspired by Question 24 of the Team Problems from the CEMC’s 2026 Canadian Team Mathematics Contest:

Try the problem as a warm up! The following problems will investigate counting problems of the form "in how many inequivalent ways can you colour something where two colourings are equivalent if one can be obtained from the other by a rotation?"

1. Consider a \(2 \times 2\) grid of four unit squares, where each square is coloured either black or white. Let \(r_1,r_2,r_3\), and \(r_0\) denote the rotations of the grid by \(90\degree\) clockwise, \(180\degree\) clockwise, \(270\degree\) clockwise, and \(0\degree\) respectively. View these four rotations as functions that take as an input a colouring of the grid, and give as an output a colouring. For example,

   

   and \(r_0(c) =c\) for all colourings \(c\). Two colourings \(c\) and \(d\) are equivalent if there is a rotation \(r\) so that \(r(c) = d\).

   1. How many inequivalent colourings of the \(2\times 2\) grid exist?

   2. For each rotation \(r\), let \(\text{fix}(r)\) be the number of colourings \(c\) satisfying \(r(c) = c\). Compute \(\text{fix}(r_0) + \text{fix}(r_1) + \text{fix}(r_2) + \text{fix}(r_3)\).

   3. Compare your answers to the previous two parts.

2. Consider a windmill with six identical blades evenly spaced around a central circle. The central circle, and each of the blades, are to be coloured either black or white. Let \(r_0,r_1,r_2,r_3,r_4,\) and \(r_5\) denote the rotations of the windmill by \(0\degree, 60\degree, 120\degree, 180\degree, 240\degree\), and \(300\degree\) clockwise, respectively. Two colourings \(c\) and \(d\) are equivalent if there is a rotation \(r\) such that \(r(c) = d\). The image below shows two inequivalent colourings of the windmill.

   

   1. How many inequivalent colourings of the windmill are there?

   2. For each rotation \(r\) let \(\text{fix}(r)\) denote the number of colourings \(c\) of the windmill satisfying \(r(c) = c\). Compute \(\text{fix}(r_0) + \text{fix}(r_1) + \text{fix}(r_2) + \text{fix}(r_3) + \text{fix}(r_4) + \text{fix}(r_5)\).

   3. Compare your answers to the previous two parts.

3. Now for a more general approach! Suppose we have some object and \(k\) rotations \(r_0,r_1,\ldots,r_{k-1}\) we can perform on the object, where \(r_z\) is a rotation by \(\frac{360z}{k}\) degrees clockwise. Assume that the object can be coloured according to some rules, and consider the collection of all possible colourings of the object according to the rules. In Question 1 for example, the object is the \(2 \times 2\) grid, \(k = 4\) since there are four rotations, and there are \(2^4 = 16\) possible colourings of the grid where each square is either black or white. Two colourings \(c\) and \(d\) are equivalent if there is a rotation \(r\) so that \(r(c) = d\). Let \(N\) be the number of inequivalent colourings of the object.

   1. Fix a colouring \(c\). Let \(E(c)\) be the number of colourings (including \(c\) itself) that are equivalent to \(c\). Let \(S(c)\) be the number of rotations satisfying \(r(c) = c\). Show that \(E(c)S(c) = k\).

   2. A stable pair is a pair \((r,c)\) where \(r\) is a rotation, \(c\) is a colouring, and \(r(c) = c\). Show that the number of stable pairs is equal to \(kN\).

   3. For a rotation \(r\), let \(\text{fix}(r)\) denote the number of colourings \(c\) satisfying \(r(c) = c\). Show that the number of stable pairs is equal to \(\text{fix}(r_0) + \text{fix}(r_1) + \cdots + \text{fix}(r_{k-1})\).

4. Consider the \(4 \times 4\) grid of \(16\) unit squares given at the beginning of this document. Let \(r_0, r_1, r_2\), and \(r_3\) be the rotations by \(0\degree\), \(90\degree\), \(180\degree\), and \(270\degree\) clockwise, respectively. By computing \(\text{fix}(r_0) + \text{fix}(r_1) + \text{fix}(r_2) + \text{fix}(r_3)\), solve the problem at the beginning of this document.

5. Let \(p\) be a prime. Consider a windmill with \(p\) identical blades evenly spaced around a central circle. The central circle, and each of the blades, are to be coloured either black or white. Two colourings are considered equivalent if you can rotate one into the other. How many inequivalent colourings of the windmill are there?