Year: 2017
Topic: Combinatorics Linear Algebra

Problem:
The 30 edges of a regular icosahedron are distinguished by labeling them $1,2,\dots,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:
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.  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,\dots,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,\dots,f_5$ being the five faces sharing a vertex of the icosahedron and $f_{16},\dots,f_{20}$ being the five faces sharing the antipodal vertex.  For $i=1,\dots,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,\dots,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,\dots,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,\dots,f_{19}$ have the same sum as the components of $f_{2},\dots,f_{20}$.   By performing a mirror reflection, we can construct a second hamiltonian path $g_1,\dots,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 \emph{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^F$ with no zero components is then the image of exactly $3^{10}$ colorings of the desired form, yielding the result. The number of such colorings is $2^{20} 3^{10} = \boxed{61917364224}$.