Below are the \(2^4 = 16\) colourings of the \(2 \times 2\) grid, arranged into rows. All colourings in the same row are equivalent.
Since there are six rows, there are six inequivalent colourings.
All \(16\) colourings satisfy \(r_0(c) = c\), since \(r_0\) doesn’t do anything to the grid! So \(\operatorname{fix}(r_0) = 16\).
To calculate \(\operatorname{fix}(r_1)\), note that the colour or the top-left square must be the same as the colour of the top-right square since the colouring of the grid doesn’t change after a rotation of \(90\degree\) clockwise. Similarly, the colour of the top-right square must be the same as that of the bottom-right square, and the bottom-left square. Therefore the only two colourings \(c\) that satisfy \(r_1(c) = c\) are the colourings with all four squares coloured the same colour. Therefore \(\operatorname{fix}(r_1) = 2\). A similar argument shows \(\operatorname{fix}(r_3) = 2\).
For a colouring to be fixed by \(r_2\), the top-left and bottom-right squares must be the same colour, and the top-right and bottom-left squares must be the same colour. There are four such colourings shown here:
Therefore, \(\operatorname{fix}(r_2) = 4\).
Putting everything together we have \[\operatorname{fix}(r_0) + \operatorname{fix}(r_1) + \operatorname{fix}(r_2) + \operatorname{fix}(r_3) = 16 + 2 + 4 + 2 = 24.\]
If \(N\) is the number of inequivalent colourings, then \[\operatorname{fix}(r_0) + \operatorname{fix}(r_1) + \operatorname{fix}(r_2) + \operatorname{fix}(r_3) = 4N.\] Note that \(4\) is the number of possible rotations.
We will first count the number of inequivalent colourings when the central circle is white, and our final answer will be double the result.
There is one colouring when all blades are black. There is one colouring when all blades are white.
There is six ways to colour the windmill with exactly one black blade, but they are all equivalent. The same holds for the number of colourings with exactly one white blade.
Suppose now that exactly two blades are black. They can either be adjacent, separated by one white blade, or separated by two white blades. Any two colourings with the same number of white blades separating the two black blades are equivalent. Therefore, there are three inequivalent colourings with two black blades. The same holds for the case when there are exactly two white blades.
When there are three black and three white blades, there are four inequivalent colourings as shown.
This gives a total of \(14\) inequivalent colourings when the central circle is white, and therefore a total of \(2 \times 14 = 28\) inequivalent colourings of the windmill in total.
There are \(7\) regions that can be coloured either black or white, and therefore \(2^7\) possible colourings of the windmill. All of these colourings are fixed by \(r_0\), and therefore \(\operatorname{fix}(r_0) = 2^7\).
Starting from the top of the windmill and going clockwise, name the blades \[b_1, b_2, b_3, b_4, b_5 \quad \text{ and } \quad b_6.\] Just like we think of the rotations as functions with inputs and outputs colourings of the windmill, we can similarly view rotations as functions with inputs and outputs the blades of the windmill. Note that \(r_1(b_1) = b_2\), \(r_1(b_2) = b_3\), \(r_1(b_3) = b_4\), \(r_1(b_4) = b_5\), and \(r_1(b_5) = b_6\). Therefore, for a colouring to be fixed by \(r_1\), the colour of \(b_1\) should be the same as that of \(b_2\), which should be the same as that of \(b_3\), \(b_4\), \(b_5\), and \(b_6\). Said a different way, all the blades must be the same colour! There are two choices for the colour of the central circle, and two choices for the colour of the blades. Therefore, \(\operatorname{fix}(r_1) = 4\). A similar argument shows that \(\operatorname{fix}(r_5) = 4\).
To compute \(\operatorname{fix}(r_2)\), observe that \(r_2(b_1) = b_3\), \(r_2(b_3) = b_5\), and \(r_2(b_5) = b_1\). Therefore, \(b_1\), \(b_3\), and \(b_5\) must all be the same colour for a colouring fixed by \(r_2\). Similarly, since \(r_2(b_2) = b_4\), \(r_2(b_4) = b_6\), and \(r_2(b_6) = b_2\), we must have that \(b_2\), \(b_4\), and \(b_6\) must be the same colour. So, supposing a colouring \(c\) satisfies \(r_2(c) = c\), there are two choices for the colour of the central circle, two choices for the colour of \(b_1\) (which fixes the colour of \(b_3\) and \(b_5\)), and two choices for the colour of \(b_2\) (which fixes the colour of \(b_4\) and \(b_6\)). Therefore, \(\operatorname{fix}(r_2) = 2^3 = 8\). A similar argument shows \(\operatorname{fix}(r_4) = 8\).
Now onto the rotation \(r_3\). Observe that \(r_3(b_1) = b_4\) and \(r_3(b_4) = b_1\) and so \(b_1\) and \(b_4\) must have the same colour in a colouring fixed by \(r_3\). Similarly, \(b_2\) and \(b_5\) must have the same colour, and \(b_3\) and \(b_6\) must have the same colour. So, a colouring of the windmill that is fixed by \(r_3\) is determined by the colours of the central circle, \(b_1\), \(b_2\), and \(b_3\). Each of these regions has two possible colours, so \(\operatorname{fix}(r_3) = 2^4 = 16\).
Organising all of this information gives \[\operatorname{fix}(r_0) + \operatorname{fix}(r_1) + \cdots + \operatorname{fix}(r_5) = 2^7 + 4 + 8 + 16+ 8 + 4 = 168.\]
The answers to the previous two parts are \(28\) and \(168\). It turns out that \(28 \times 6 = 168\), and \(6\) is the number of possible rotations.
Suppose \(E(c) = t\), and let the \(t\) distinct equivalent colourings be given by \[q_0(c),q_1(c),q_2(c),\ldots,q_{t-1}(c),\] where the \(q_i\) are distinct rotations with \(q_0 = r_0\) (so \(q_0(c) = c\)). Let \(S(c) = m\) and let \(s_0,s_1,\ldots,s_{m-1}\) be the \(m\) distinct rotations satisfying \(s_j(c) = c\), with \(s_0 = r_0\).
For two rotations \(s\) and \(q\), let \(q\circ s\) denote the rotation obtained by performing \(s\) followed by \(q\). Note that the composition of two rotations is another rotation.
Consider now all compositions of the form \(q_i \circ s_j\). There are \(m\) choices for \(s_j\) and \(t\) choices for \(q_i\), so there are \(mt\) such compositions. The goal is to show that every rotation is the same as exactly one of these compositions, and hence conclude that \(k = mt\).
To that end, let \(0 \leq i_1,i_2 \leq t-1\), \(0 \leq j_1,j_2\leq m-1\), and suppose \(q_{i_1}\circ s_{j_1}\) and \(q_{i_2} \circ s_{j_2}\) are the same rotation. Then \(q_{i_1}\circ s_{j_1}(c) = q_{i_2} \circ s_{j_2}(c)\). Since each of the \(s_j\) fix \(c\), as a consequence we get \(q_{i_1}(c) = q_{i_2}(c)\). However, the \(q_i\) were defined so that distinct \(q_j\) give distinct colourings \(q_j(c)\). So, the only way \(q_{i_1}(c) = q_{i_2}(c)\) is if \(q_{i_1} = q_{i_2}\). Denote the rotation \(q_{i_1}\) simply by \(q_i\).
Recall that \(q_i\) is a rotation by \(\frac{360z}{k}\) degrees clockwise for some integer \(z\). Let \(q\) be the rotation by \(\frac{360(k-z)}{k}\) degrees clockwise. Then \(q \circ q_i\) is the rotation \(r_0\) (the rotation that does nothing!). Our initial assumption is that \(q_i\circ s_{j_1}\) is the same rotation as \(q_i \circ s_{j_2}\). Composing both of these rotations with \(q\) gives that \(q\circ q_i\circ s_{j_1}\) is the same rotation as \(q \circ q_i \circ s_{j_2}\). However, \(q \circ q_i \circ s_{j_1} = r_0\circ s_{j_1} = s_{j_1}\) and similarly \(q\circ q_i \circ s_{j_2} = s_{j_2}\). Therefore \(s_{j_1}\) and \(s_{j_2}\) are the same rotation. We can conclude that the collection of rotations \(q_i \circ s_j\) where \(i\) ranges from \(0\) to \(t-1\) and \(j\) ranges from \(0\) to \(m-1\) is a collection of \(mt\) distinct rotations.
It remains to show that every rotation is of the form \(q_i \circ s_j\) for some \(i\) and \(j\). Let \(r\) be an arbitrary rotation. Then \(r(c)\) is a colouring equivalent to \(c\), and so there exists some \(i\) so that \(q_i(c) = r(c)\). As we argued above, there is some rotation \(q\) so that \(q \circ q_i = r_0\). Applying \(q\) to the colouring \(q_i(c) = r(c)\) gives \(q\circ r(c) = q \circ q_i(c) =r_0(c) = c\).
Therefore, \(q\circ r\) is equal to some rotation \(s_j\). Composing \(q\circ r\) and \(s_j\) with \(q_i\) gives \(q_i\circ s_j = q_i \circ q \circ r = r_0 \circ r = r\), completing the proof.
Let’s look more closely at the example from Question 1 to guide us in our solution. Here is a picture of all the colourings of the \(2\times 2\) grid, organised into rows of equivalent colourings. The rotations that fix each colouring appear below that colouring:
There are a few important things to notice here.
If we count the number of rotations appearing in each row, it is always four (which is the value of \(k\), the total number of rotations). This corresponds to there being four stable pairs containing the colourings in any row.
The number of rotations appearing below a colouring \(c\) is the number of stable pairs containing \(c\) in the second coordinate, which is also the value of \(S(c)\).
The number of rotations below a colouring \(c\) is equal to four divided by the number of colourings in its row. This is a reflection of the fact from 3(a) that \(E(c)S(c) = k\) (can you see why?).
The total number of stable pairs is equal to the number of rotations that appear in the entire image. Since there are \(k = 4\) rotations in each row, and \(N = 6\) rows, the number of stable pairs is \(kN = 24\).
These four points provide an outline of our solution to the general case. Here we go!
Fix some colouring \(c\). The number of stable pairs with \(c\) in the second coordinate is equal to the number of rotations \(r\) satisfying \(r(c) = c\). Therefore the number of stable pairs with \(c\) in the second coordinate is \(S(c)\). If we sum up \(S(c)\) over all colourings \(c\) we get the number of stable pairs.
Suppose that \(E(c) = t\) and \(c_1,c_2,\ldots,c_t\) are the \(t\) colourings equivalent to \(c\) (so in particular, one of the \(c_i\) is \(c\)). By \(3\)(a), for each \(i\) we have \(S(c_i) = \frac{k}{E(c_i)} = \frac{k}{t}\). Therefore, \[S(c_1) + S(c_2) + \cdots + S(c_t) = \underbrace{\frac{k}{t} + \frac{k}{t} + \cdots + \frac{k}{t}}_{t\rm\ times} = k.\] We have shown that if we sum up \(S(c)\) over all colourings that are equivalent to a particular fixed colouring, we get \(k\). Since there are \(N\) inequivalent colourings, summing up \(S(c)\) over all colourings gives \(kN\). Since the number of stable pairs is the sum over all colourings \(c\) of \(S(c)\), we conclude that the number of stable pairs is equal to \(kN\).
If we fix a rotation \(r\), the number of stable pairs with \(r\) in the first coordinate is the number of colourings \(c\) satisfying \(r(c) = c\). This is precisely \(\operatorname{fix}(r)\). Therefore, to count all stable pairs we can sum up \(\operatorname{fix}(r)\) over all possible rotations. Said another way, the number of stable pairs is equal to \(\operatorname{fix}(r_0) + \operatorname{fix}(r_1) + \cdots + \operatorname{fix}(r_{k-1})\).
The important thing to take away from Question 3 is that the quantities \(kN\) and \[\operatorname{fix}(r_0) + \operatorname{fix}(r_1) + \cdots + \operatorname{fix}(r_{k-1})\] both count the number of stable pairs, and are therefore equal!
The number of possible colourings of the grid with exactly four red squares is the binomial coefficient \(\binom{16}{4} = \frac{16!}{(12!)(4!)} = 1820\). Since all colourings are fixed by \(r_0\), \(\operatorname{fix}(r_0) = 1820\).
Observe that \(r_1\) moves the four squares in the top-left quarter of the grid to the top-right quarter. It moves the four squares in the top-right quarter to the bottom-right quarter, and it moves the four squares in the bottom-right quarter to the bottom-left quarter. Therefore, a colouring of the grid with four red squares that is fixed by \(r_1\) must have exactly one red square in each of the four quarters of the grid. In fact, the colouring is entirely determined by which of the four squares in the top-left quarter is coloured red.
There are four possibilities for which square in the top-left quarter of the grid is coloured red, and therefore \(\operatorname{fix}(r_1) = 4\). A similar argument shows \(\operatorname{fix}(r_3) = 4\). The next image shows the four colourings of the grid fixed by \(r_1\) (and \(r_3\)).
We can compute \(\operatorname{fix}(r_2)\) in a similar way, except this time a colouring fixed by \(r_2\) is determined by which two squares in the top half of the grid are coloured red. There are \(\binom{8}{2} = 28\) ways to colour two of the eight squares in the top half of the grid red, which gives \(\operatorname{fix}(r_2) = 28\).
From Question 3, we know that the number of inequivalent colourings of the grid is equal to \[\frac{1}{4}\left(\operatorname{fix}(r_0) + \operatorname{fix}(r_1) + \operatorname{fix}(r_2) + \operatorname{fix}(r_3)\right) = \frac{1820+4 + 28 + 4}{4} = 464.\]
Let \(r_0,r_1,\ldots,r_{p-1}\) be the \(p\) rotations of the windmill, where \(r_j\) is a rotation by \(\frac{360j}{p}\) degrees clockwise. From Question 3 we know that the number of inequivalent colourings of the windmill is \[\frac{1}{p}\left(\operatorname{fix}(r_0) + \operatorname{fix}(r_1) + \cdots + \operatorname{fix}(r_{p-1})\right).\] There are \(p+1\) regions (including the central circle) that can either be coloured black or white. Therefore, there are \(2^{p+1}\) possible colourings of the windmill, and \(\operatorname{fix}(r_0) = 2^{p+1}\).
Let \(r\) be any other rotation. Arrange the windmill so one of the blades is pointing straight up. Starting from the top and going clockwise, label the blades \(b_1, b_2,\ldots,b_p\). For a positive integer \(t\), denote by \(r^t\) the rotation obtained by composing \(r\) with itself \(t\) times. So, for example, \(r_1^3 = r_1 \circ r_1 \circ r_1 = r_3\).
Now, consider the sequence of blades \(b_1, r(b_1), r^2(b_1), r^3(b_1),\ldots\). Since there are only finitely many blades, there will be an appearance of at least one blade more than once. Suppose that the first time we get a repeated blade occurring in the sequence is at \(r^t(b_1)\) and \(r^{t+s}(b_1) = r^s(r^t(b_1))\). Since \(r^s\) is some rotation that fixes a blade, it must be that \(r^s(b_i) = b_i\) for all the blades \(b_i\). Furthermore, since this is the first time in the sequence a blade appears twice, we must have that for all blades \(b\), \(r^l(b) \neq b\) for any integer \(l\) satisfying \(1 \leq l < s\).
Our goal is to now show that \(s = p\). Since \(r\) is a rotation by \(\frac{360j}{p}\) degrees clockwise (for some integer \(j\)), \(r^p\) is a rotation by \(360j\) degrees clockwise. Since this is a multiple of \(360\degree\), it must be the case that \(r^p(b) = b\) for all blades \(b\). Therefore, we have \(1 < s \leq p\) (the first inequality is since \(r \neq r_0\)).
Suppose that \(s < p\). Since \(p\) is prime, there is some remainder when you divide \(p\) by \(s\). That is, there are integers \(q\) and \(m\) with \(1 \leq m < s\) such that \(p = qs + m\). For a blade \(b\) we have \[b = r^p(b) = r^{qs + m}(b) = r^m\underbrace{(r^s(r^s(r^s(\cdots r^s}_{q\rm\ times}(b))))) = r^m(b).\] This is a contradiction since \(1 \leq m < s\) and so \(r^m(b) \neq b\). We are forced to conclude that \(s = p\).
Returning to how we defined \(s\), we must have that the \(p\) blades \(r^t(b_1),r^{t+1}(b_1),\ldots, r^{t+p-1}(b_1)\) are distinct, and thus every blade appears exactly once in the list of \(p\) blades. Therefore, any colouring of the windmill that is fixed by \(r\) must have every blade be the same colour! Therefore, for any colouring fixed by \(r\), there are two choices for the colour of the central circle, and two choices for the colour of the blades. We therefore have that \(\operatorname{fix}(r) = 4\).
Finally, the number of inequivalent colourings of the windmill is \[\frac{1}{p}\left(\operatorname{fix}(r_0) + \operatorname{fix}(r_1) + \cdots + \operatorname{fix}(r_{p-1})\right) = \frac{2^{p+1} + 4(p-1)}{p}.\]