Icosahedron Coloring Problem

Problem :How many different ways can you color an icosahedron with one of three colors on each face?

Sol :

As with any mathematical problem, we must understand the problem before we can attempt to solve it. First, an icosahedron is a regular solid consisting of 20 faces, each of which is an equilateral triangle. We wish to color each face of the icosahedron with one of three colors. A sample icosahedron colored red, green, and blue is pictured at right. We will permit any face to be colored any of the three colors, regardless of the colors of adjacent faces.

An initial guess for the number of ways to color the icosahedron might go as follows: we can choose any of three colors for the first face, and no matter which color we choose, we can choose any of three colors for the second face, so there are 3 · 3 = 9 ways to color the first 2 faces. Continuing in this fasion, we see there are 3³ ways to color the first three faces, and in general, 3ⁿ ways to color the first n faces. Therefore, there are 3²⁰ = 3,486,784,401 ways to color the 20 faces of the icosahedron with three colors.

The problem with the above reasoning is that we have overcounted. If we were coloring an oriented icosahedron (one that is fixed in space), then 3²⁰ would be the correct answer. However, the question is much more interesting if we allow our icosahedron to be unoriented, that is, the icosahedron may be rotated in space. Each colored icosahedron can be positioned many different ways, so two colored icosahedrons that at first glance appear different may be the same if one can be rotated so that its coloring matches that of the other. The major task in counting the number of colorings, then, is to determine when two colorings are the same. Therefore, we will study some simpler problems to gain intuition before we answer the question, "How many ways can you color an unoriented icosahedron with three colors?"

Basic Combinatorics

First we will count the ways we can arrange n objects in a line. Clearly we can choose any of n distinct objects to go in the first position, and regardless of our choice, we can choose any of n – 1 for the second position. We can choose any of n – 2 for the third position, and so on, until we obtain the formula n(n – 1)(n – 2) ··· (2)(1) = n! ways to arrange n elements in a line.

Now suppose we wanted to arrange n distinct objects in an unoriented circle (that is, a circle that we can rotate). An equivalent question is, "How many different necklaces can we make with n beads of different colors?" Since we can rotate the necklace, we can choose one specific bead and fix it at the top. We can then choose any of n – 1 beads to be positioned to the right of the first bead, and n – 2 beads for the next position, and so on. The number of unique necklaces then becomes 1·(n – 1)(n – 2) ··· (2)(1) = (n – 1)!

The problem becomes more difficult when we have nonunique items to arrange in a circle. Consider the following two orderings of orange and blue dots arranged in a circle. They are different when fixed in space, but as necklaces made from orange and blue beads, they are the same, since we can rotate one to align it with the other. This example forces us to consider the symmetries of elements arranged in a circle.

Answer: 58,130,055

http://www.mrwright.org