2011 AMC 10A Problems/Problem 22
Contents
Problem 22
Each vertex of convex pentagon is to be assigned a color. There are
colors to choose from, and the ends of each diagonal must have different colors. How many different colorings are possible?
Solution 1
Let vertex be any vertex, then vertex
be one of the diagonal vertices to
,
be one of the diagonal vertices to
, and so on. We consider cases for this problem.
In the case that has the same color as
,
has a different color from
and so
has a different color from
and
. In this case,
has
choices,
has
choices (any color but the color of
),
has
choice,
has
choices, and
has
choices, resulting in a possible of
combinations.
In the case that has a different color from
and
has a different color from
,
has
choices,
has
choices,
has
choices (since
and
necessarily have different colors),
has
choices, and
has
choices, resulting in a possible of
combinations.
In the case that has a different color from
and
has the same color as
,
has
choices,
has
choices,
has
choices,
has
choice, and
has
choices, resulting in a possible of
combinations.
Adding all those combinations up, we get .
Solution 2
First, notice that there can be cases. One with all vertices painted different colors, one with one pair of adjacent vertices painted the same color and the final one with two pairs of adjacent vertices painted two different colors.
Case : There are
ways of assigning each vertex a different color.
Case : There are
ways. After picking four colors, we can rotate our pentagon in
ways to get different outcomes.
Case : There are
ways of arranging the final case. We can pick
colors for our pentagon. There are
spots for the first pair of colors. Then, there are
possible ways we can put the final pair in the last
spaces. But because the two pairs are indistinguishable, we divide by
.
Adding all the possibilities up, we get
~ZericHang
Solution 3
There are ways to assign a color to
. WLOG, give vertex
a color; we can multiply by
at the end. Since vertices
and
cannot have the same color, there are
ways to assign colors to vertex
. Using this same logic, there are
ways to assign a color to vertices
,
, and
, giving a total of
ways. However, vertex
cannot be the same color as vertex
. To use complementary counting, we need to find the amount of ways for
and
to have the same color. Notice that this is equivalent to the amount of ways to arrange colors among the vertices of a square. Using the same logic as above, there are
ways, except we must subtract the number of ways for a triangle. Each time, there is
less vertex, so
times less ways to color. This process stops when there are only
vertices left; in this case there are simply
ways to color this figure.
So in conclusion, there are
ways.
Solution 4
This problem is a direct application of the chromatic polynomial of a graph, represented by , which returns a polynomial representing the number of ways to color a graph
with
colors such that no two adjacent vertices share the same color. In other words, it gives us a polynomial in terms of
where we can plug in
to get our answer.
Well, if we want to find for a graph
, we should probably first draw the graph, right? We can first draw five vertices (without any edges) in the shape of a pentagon. After connecting the diagonals, we get a star. We attempt to shift the vertices around to simplify the graph, which we quickly realize is isomorphic (can be turned into) the five-cycle, or the pentagon.
Finding on a graph with a cycle of length at most 3 is straightforward -- we first pick a vertex v. It has 0 colored (visited) neighbors, so we can color it in k ways. We then move on to the vertices adjacent to v, etc, and at the end we multiply all these together. For example, the chromatic polynomial of a triangle is
. However, cycles with length > 3 introduce ambiguity, and thus the above technique fails. Thus, we need to use the recursive formula
, where
represents removing e and
represents contracting e, or collapsing the two endpoints of e into one. When we hit a graph where the longest cycle has length 3, we can use the first technique to quickly find
.
After about four iterations of the algorithm, we get that the chromatic polynomial is . Plugging in 6 gives us
.
~Helloworld1
Solution 5 (constructive counting)
In pentagon , fix any vertex
. Now draw diagonal
. There are six choices for vertex
and
choices for vertex
Now draw diagonal . Since
cannot be the same color as vertex
, we have
choices for
. Again, we have five choices for vertex
(draw diagonal
).
Thus there are choices for vertices
and
and
combinations for
and
.
To determine the final count, we consider two cases for the final combinations of
and
, which uniquely determines
. Then, we multiply by
since the choices of
and
are independent from these two cases.
Case :
and
are the same color. There are
possible pairs, and thus we have
choices for
. There are
cases here.
Case :
and
are different. There are
possible combinations and we have
choices for
(not the color of
nor
). In this case we have
cases.
Our final count is , which is answer
.
~FIREDRAGONMATH16
Solution 6 (Casework)
WLOG, draw such that point
is at the top, and write the letters in counterclockwise order. WLOG, fill in
first. There are
ways to do so. From here we proceed with casework on the color of
:
- Case 1:
is the same color as
In this case, there isoption for
,
options for
,
options for
, and
options for
.
.
- Case 2:
and
are different colors
In this case, there areoptions for
,
options for
,
options for
, but we notice we need to do casework on the color of
.
- Case 2.1:
and
are the same color
There areoptions for
,
options for
,
option for
,
options for
, and
options for
.
.
- Case 2.2:
and
are different colors
There areoptions for
,
options for
,
options for
,
options for
, and
options for
.
.
Summing up the cases, .
~JH. L
Solution 7
Notice that a minimum of, and a maximum of
colours can be used.
- Case
:
colours used.
This is straight forward and there are ways.
- Case
:
colours used.
If and
have same colours, they have to be adjacent. Let
be directly right of
.
consecutive points from
clockwise have different colours. They can be coloured in
ways. And
can be chosen in
ways, bringing the total to
.
- Case
:
colours used.
Note that points can't have the same colour as at least
of the lines joining them will be a diagonal. Then the arrangement is
. The point with distinct colour can be chosen in
ways and can be coloured in
ways. The next two points clockwise can be coloured in
ways and the next two in
ways. The total is
.
Finally, adding all cases, the answer is .
~IamBATMAN1313
Solution 8
Name the pentagon . Then
and
have to be of different colours.
can be coloured in
ways,
in
ways (Without the one used for
),
in
ways (Without the one used for
),
in
ways (Without the one used for
).
Now we find the expected value of how many ways can be coloured.
If and
are of the same colour,
and
are always different. This happens
times and leaves
options for
.
If and
are of different colours
then there is a
chance that
and
are of same colour and
chance that they are different. The first one leaves
ways to colour
and the second one leaves
.
Calculating all these, we find the expected value for the number of ways can be coloured is
Therefore total number or ways .
~IamBATMAN1313
Video Solution
~IceMatrix
See Also
2011 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 21 |
Followed by Problem 23 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.