Difference between revisions of "2011 AMC 10A Problems/Problem 22"
(→Solution 5 (constructive counting)) |
|||
| Line 60: | Line 60: | ||
Our final count is <math>30(84+20) = \boxed{3120}</math>, which is answer <math>\boxed{\textbf{(C)}}</math>. | Our final count is <math>30(84+20) = \boxed{3120}</math>, which is answer <math>\boxed{\textbf{(C)}}</math>. | ||
| + | |||
| + | ~FIREDRAGONMATH16 | ||
==Video Solution== | ==Video Solution== | ||
Revision as of 01:19, 8 August 2021
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
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. 
