colouring edges of an icosahedron in a certain way

Question

Find the number of ways to colour the 30 edges of an icosahedron with three colours so that for any triangular face, two edges are the same colour and the other is a different colour.

I think the answer is $2^{20}3^{10},$ but I'm not sure how to show this. Let $v$ and $w$ be antipodal vertices on the icosahedron. Let $S_v$ be the set of edges coincident with $v$ and $T_v$ be the set of edges coincident with the opposite end of two edges in $S_v$ that form a pentagon around $v.$ Define $S_w$ and $T_w$ similarly. Let $U$ be the set of $10$ remaining edges. There are $3^{10}$ ways to colour the edges of $U.$ Also, for each possible way, there are $2^{10}$ ways to colour the edges of $T_v$ and $T_w$; given an edge in $T_v \cup T_w,$ it forms a triangle with $2$ other edges in $U.$ This triangle may have two edges of the same colour, in which case we choose one of the $2$ remaining colours, and if the two edges are different colours, we choose one of the $2$ colours. However, I'm not sure how to show that there are $2^{10}$ ways to colour the edges of $S_v\cup S_w$.

Answer 1

This is Putnam 2017 problem A6; full solutions are here. My solution (which Kedlaya quotes in a remark) is as follows.

Identify the three colors with the three elements of $\mathbb F_3 = \mathbb Z/3\mathbb Z$. Then the "two of one color, one of another" condition is equivalent to "sum $\neq 0$". This allows us to turn the question into a linear algebra problem. Consider the linear transformation $f: \mathbb F_3^{30} \to \mathbb F_3^{20}$ that takes a vector of 30 edge colors to the vector whose components are the sums of the elements of $\mathbb F_3$ surrounding each face. We want the preimage of $\{1, 2\}^{20}$ under $f$. Note that if $f$ is surjective, then $\ker f$ has dimension 10, so all fibers have cardinality $3^{10}$, and the answer is $2^{20} 3^{10} = 12^{10}$.

To prove that $f$ is surjective, it suffices to show that each standard basis vector (i.e. each vector consisting of a 1 on one face and zeroes everywhere else) is in its image. This can be achieved by coloring the five edges around one vertex $2, 1, 2, 1, 2$ in order, and everything else 0.

Answer 2

Your calculations for $U$, $T_v$ and $T_w$ are correct. To complete the solution by showing that there are $2^{10}$ ways to colour the edges of $S_v\cup S_w$, you can proceed as follows.

Consider the $5$ edges of $S_v$ as the rays of a pentagon, connecting the vertices with the center $v$, and call them $r_1$, $r_2...r_5$. The possible colours of the sides of the pentagon,which correspond to $T_v$, have already been counted in the first part of your solution.

Firstly consider $r_1$. Since no triangle is completed by colouring this first ray, we have $3$ possible choices for the colour of $r_1$.

Then consider $r_2$: colouring it, we complete a triangle. Irrespective of whether the other two (already coloured) sides of this triangle have the same colour or not, we have two choices for $r_2$. In fact, if the other two edges are equal, we can choose one of the $2$ remaining colours; if the other two edges have diffetent colours, we can choose one of these two colours also for $r_2$. By similar considerations, we also get that there are $2$ choices for $r_3$, and $2$ choices for $r_4$.

---

Now consider $r_5$. Colouring it, we no longer complete a single triangle, but two triangles. Let us call $p_1$ the pair of other two sides of the first triangle and $p_2$ that of the second triangle. By simplicity, I will assume that the three colours are blue, red, and yellow, indicating them with $B$, $R$, $Y$. Also, I will call homogeneous a pair containing one single colour (e.g., $BB$) and heterogeneous a pair containing two colours (e.g., $BR$). We have to consider three different cases.

$\textbf{First case}$: $p_1$ and $p_2$ have two colours in common (e.g., $BR$ and $RB$). In this case they both are heterogeneous and we have $2$ choices for $r_5$, because we can choose one of the two common colours.

• Note that this case accounts for $4/27$ of all $3^4$ possible combinations of colours in $p_1$ and $p_2$. In fact, there are $3$ ways to choose the common colour couple, and for each of these there are $2^2$ ways to order the colours within the pairs. This leads to a proportion of $3 \cdot 2^2\cdot 1/3^4=4/27$.

$\textbf{Second case}$: $p_1$ and $p_2$ have one colour in common. In this case we have to consider three subcases. The first one occurs when both pairs are heterogeneous (e.g., $BR$ and $RY$): we have $1$ choice for $r_5$, because we can choose only the common colour. The second one occurs when one pair is homogeneous and the other is heterogeneous (e.g., $BB$ and $BR$): we still have $1$ choice for $r_5$, because we have to avoid the common colour and the third colour. The last subcase occurs when both pairs are homogeneous (e.g., $BB$ and $BB$): here we clearly have $2$ choices for $r_5$.

• The first subcase accounts for $8/27$ of all possible combinations of colours of $p_1$ and $p_2$: in fact, there are $3$ possible choices for the common colour, and for each of these there are $2$ ways to place the other two colours in $p_1$ and $p_2$, and $2^2$ ways to order the colours within the pairs. This leads to a proportion of $3 \cdot 2^3\cdot 1/3^4=8/27$. The second subcase accounts for $8/27$ of all possible combinations as well. In fact, there are $3$ possible choices for the common colour, and for each of these there are $2$ ways to decide which is the homogeneous pair, $2$ possible choices for the other colour of the heterogeneous pair, and $2^2$ ways to order the colours within the pairs. This again leads to a proportion of $3 \cdot 2^3\cdot 1/3^4=8/27$. For the last subcase, it is not difficult to show that it accounts for $1/27$ of all possible combinations.

$\textbf{Third case}$: $p_1$ and $p_2$ have no colours in common. Since in this case the two pairs cannot be both heterogeneous, we have to consider two subcases. The first one occurs when both pairs are homogeneous (e.g., $BB$ and $RR$): we have $1$ choice for $r_5$, because we have to choose the third colour. The second one occurs when one pair is homogeneous and the other is heterogeneous (e.g., $BB$ and $RY$): here we have $2$ choices for $r_5$, because we can choose one of the two colours of the heterogeneous pair.

• The first subcase occurs with probability $2/27$: in fact, there are $3$ ways to choose the two colours of the homogeneous pairs, and $2$ ways to place them in the pairs. This leads to a proportion of $3 \cdot 2\cdot 1/3^4=2/27$. The second subcase occurs with probability $4/27$: in fact, there are $3$ ways to choose the colour of the homogeneous pair, and for each of these there are $2$ ways to decide which is the homogeneous pair, and $2^2$ ways to order the remaining two colours within the heterogeneous pair.

Basen on these considerations, $r_5$ can be coloured in $1$ way in $18/27=2/3$ of cases, and in $2$ ways in $9/27=1/3$ of cases.

---

Coming back to the initial problem, since there are $3$ ways to colour $r_1$ and $2$ ways to colour each of the rays $r_2$, $r_3$, $r_4$, taking into account the results obtained for $r_5$ we get that the total number of ways to colour the edges of $S_v$ is

$$3\cdot 2^3 \cdot \left(\frac 23+ 2\cdot \frac 13\right)=2^5$$

Since the same procedure can be symmetrically applied to $S_w$, we conclude that there are $2^5 \cdot 2^5=2^{10}$ ways to colour the edges of $S_v\cup S_w$.

Answer 3

This is not (directly) an answer to your question about your specific approach, but instead a suggestion for an alternative approach. Consider the edges of the icosahedron painted red in the following images:

You already note that for any coloring of two edges of a face, there are precisely two ways to complete the coloring. For every coloring of the 10 edges indicated in each image, there are only 2 possible colors for some of the edges. Coloring them, there are in turn only 2 possible colors for some other edges. Repeating this, in both cases above we are left with only a set of the form $S_v$ to be colored, i.e. just $5$ edges adjacent to $1$ vertex. Perhaps you can find another choice of $10$ edges so that all other edges allow only 2 possible colors?