Putnam 2017, Problem A-6

The 30 edges of a regular icosahedron are distinguished by labeling them \( 1, 2, \ldots, 30 \). How many different ways are there to paint each edge red, white, or blue such that each of the 20 triangular faces of the icosahedron has two edges of the same color and a third edge of a different color? [Note: the top matter on each exam paper included the logo of the Mathematical Association of America, which is itself an icosahedron.]

Solution:
The number of such colorings is \( 2^{20} 3^{10} = 61917364224 \).  

### First solution
Identify the three colors red, white, and blue with (in some order) the elements of the field \( \mathbb{F}_3 \) of three elements (i.e., the ring of integers mod \( 3 \)). The set of colorings may then be identified with the \( \mathbb{F}_3 \)-vector space \( \mathbb{F}_3^E \) generated by the set \( E \) of edges. Let \( F \) be the set of faces, and let \( \mathbb{F}_3^F \) be the \( \mathbb{F}_3 \)-vector space on the basis \( F \); we may then define a linear transformation \( T: \mathbb{F}_3^E \to \mathbb{F}_3^F \) taking a coloring to the vector whose component corresponding to a given face equals the sum of the three edges of that face. The colorings we wish to count are the ones whose images under \( T \) consist of vectors with no zero components.  

We now show that \( T \) is surjective. (There are many possible approaches to this step; for instance, see the following remark.) Let \( \Gamma \) be the dual graph of the icosahedron, that is, \( \Gamma \) has vertex set \( F \) and two elements of \( F \) are adjacent in \( \Gamma \) if they share an edge in the icosahedron. The graph \( \Gamma \) admits a hamiltonian path, that is, there exists an ordering \( f_1, \ldots, f_{20} \) of the faces such that any two consecutive faces are adjacent in \( \Gamma \). For example, such an ordering can be constructed with \( f_1, \ldots, f_5 \) being the five faces sharing a vertex of the icosahedron and \( f_{16}, \ldots, f_{20} \) being the five faces sharing the antipodal vertex.  

For \( i = 1, \ldots, 19 \), let \( e_i \) be the common edge of \( f_i \) and \( f_{i+1} \); these are obviously all distinct. By prescribing components for \( e_1, \ldots, e_{19} \) in turn and setting the others to zero, we can construct an element of \( \mathbb{F}_3^E \) whose image under \( T \) matches any given vector of \( \mathbb{F}_3^F \) in the components of \( f_1, \ldots, f_{19} \). The vectors in \( \mathbb{F}_3^F \) obtained in this way thus form a \( 19 \)-dimensional subspace; this subspace may also be described as the vectors for which the components of \( f_1, \ldots, f_{19} \) have the same sum as the components of \( f_2, \ldots, f_{20} \).  

By performing a mirror reflection, we can construct a second hamiltonian path \( g_1, \ldots, g_{20} \) with the property that  
\[
g_1 = f_1, g_2 = f_5, g_3 = f_4, g_4 = f_3, g_5 = f_2.
\]  

Repeating the previous construction, we obtain a different \( 19 \)-dimensional subspace of \( \mathbb{F}_3^F \) which is contained in the image of \( T \). This implies that \( T \) is surjective, as asserted earlier.  

Since \( T \) is a surjective homomorphism from a \( 30 \)-dimensional vector space to a \( 20 \)-dimensional vector space, it has a \( 10 \)-dimensional kernel. Each of the \( 2^{20} \) elements of \( \mathbb{F}_3^E \) with no zero components is then the image of exactly \( 3^{10} \) colorings of the desired form, yielding the result.  

### Remark
There are many ways to check that \( T \) is surjective. One of the simplest is the following (from Art of Problem Solving, user Ravi12346): form a vector in \( \mathbb{F}_3^E \) with components \( 2, 1, 2, 1, 2 \) at the five edges around some vertex and all other components \( 0 \). This maps to a vector in \( \mathbb{F}_3^F \) with only a single nonzero component; by symmetry, every standard basis vector of \( \mathbb{F}_3^F \) arises in this way.  

### Second solution
(from Bill Huang, via Art of Problem Solving user superpi83) Let \( v \) and \( w \) be two antipodal vertices of the icosahedron. Let \( S_v \) (resp. \( S_w \)) be the set of five edges incident to \( v \) (resp. \( w \)). Let \( T_v \) (resp. \( T_w \)) be the set of five edges of the pentagon formed by the opposite endpoints of the five edges in \( S_v \) (resp. \( S_w \)). Let \( U \) be the set of the ten remaining edges of the icosahedron.  

Consider any one of the \( 3^{10} \) possible colorings of \( U \). The edges of \( T_v \cup U \) form the boundaries of five faces with no edges in common; thus each edge of \( T_v \) can be colored in one of two ways consistent with the given condition, and similarly for \( T_w \). That is, there are \( 3^{10} 2^{10} \) possible colorings of \( T_v \cup T_w \cup U \) consistent with the given condition.  

To complete the count, it suffices to check that there are exactly \( 2^5 \) ways to color \( S_v \) consistent with any given coloring of \( T_v \). Using the linear-algebraic interpretation from the first solution, this follows by observing that (by the previous remark) the map from \( \mathbb{F}_3^{S_v} \) to the \( \mathbb{F}_3 \)-vector space on the faces incident to \( v \) is surjective, and hence an isomorphism for dimensional reasons. A direct combinatorial proof is also possible.