Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2011 AMC 10A Problems/Problem 22"

(→‎Solution 3)
(→‎Solution 3)
Line 31: Line 31:
  
 
==Solution 3==
 
==Solution 3==
−
There are <math>6</math> ways to assign a color to <math>A</math>. WLOG, give vertex <math>A</math> a color; we can multiply by <math>6</math> at the end. Since vertices <math>A</math> and <math>C</math> cannot have the same color, there are <math>5</math> ways to assign colors to vertex <math>C</math>. Using this same logic, there are <math>5</math> ways to assign a color to vertices <math>E</math>, <math>B</math>, and <math>D</math>, giving a total of <math>5^4=625</math> ways. However, if vertex <math>D</math> cannot be the same color as vertex <math>A</math>. To use complementary counting, we need to find the amount of ways for <math>D</math> and <math>A</math> 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 <math>5^3=125</math> ways, except we must subtract the number of ways for a triangle. Each time, there is <math>1</math> less vertex, so <math>5</math> times less ways to color. This process stops when there are only <math>2</math> vertices left; in this case there are simply <math>5</math> ways to color this figure.  
+
There are <math>6</math> ways to assign a color to <math>A</math>. WLOG, give vertex <math>A</math> a color; we can multiply by <math>6</math> at the end. Since vertices <math>A</math> and <math>C</math> cannot have the same color, there are <math>5</math> ways to assign colors to vertex <math>C</math>. Using this same logic, there are <math>5</math> ways to assign a color to vertices <math>E</math>, <math>B</math>, and <math>D</math>, giving a total of <math>5^4=625</math> ways. However, vertex <math>D</math> cannot be the same color as vertex <math>A</math>. To use complementary counting, we need to find the amount of ways for <math>D</math> and <math>A</math> 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 <math>5^3=125</math> ways, except we must subtract the number of ways for a triangle. Each time, there is <math>1</math> less vertex, so <math>5</math> times less ways to color. This process stops when there are only <math>2</math> vertices left; in this case there are simply <math>5</math> ways to color this figure.  
 
So in conclusion, there are <math>6(5^4-(5^3-(5^2-(5))))=6(5^4-5^3+5^2-5)=\boxed{3120 \ \mathbf{(C)}}</math> ways.
 
So in conclusion, there are <math>6(5^4-(5^3-(5^2-(5))))=6(5^4-5^3+5^2-5)=\boxed{3120 \ \mathbf{(C)}}</math> ways.
  

Revision as of 17:01, 11 September 2018

Problem 22

Each vertex of convex pentagon $ABCDE$ is to be assigned a color. There are $6$ colors to choose from, and the ends of each diagonal must have different colors. How many different colorings are possible?

$\textbf{(A)}\ 2520\qquad\textbf{(B)}\ 2880\qquad\textbf{(C)}\ 3120\qquad\textbf{(D)}\ 3250\qquad\textbf{(E)}\ 3750$

Solution 1

Let vertex $A$ be any vertex, then vertex $B$ be one of the diagonal vertices to $A$, $C$ be one of the diagonal vertices to $B$, and so on. We consider cases for this problem.

In the case that $C$ has the same color as $A$, $D$ has a different color from $A$ and so $E$ has a different color from $A$ and $D$. In this case, $A$ has $6$ choices, $B$ has $5$ choices (any color but the color of $A$), $C$ has $1$ choice, $D$ has $5$ choices, and $E$ has $4$ choices, resulting in a possible of $6 \cdot 5 \cdot 1 \cdot 5 \cdot 4 = 600$ combinations.

In the case that $C$ has a different color from $A$ and $D$ has a different color from $A$, $A$ has $6$ choices, $B$ has $5$ choices, $C$ has $4$ choices (since $A$ and $B$ necessarily have different colors), $D$ has $4$ choices, and $E$ has $4$ choices, resulting in a possible of $6 \cdot 5 \cdot 4 \cdot 4 \cdot 4 = 1920$ combinations.

In the case that $C$ has a different color from $A$ and $D$ has the same color as $A$, $A$ has $6$ choices, $B$ has $5$ choices, $C$ has $4$ choices, $D$ has $1$ choice, and $E$ has $5$ choices, resulting in a possible of $6 \cdot 5 \cdot 4 \cdot 1 \cdot 5 = 600$ combinations.

Adding all those combinations up, we get $600+1920+600=\boxed{3120 \ \mathbf{(C)}}$.

Solution 2

First, notice that there can be $3$ 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 $1$: There are $6!$ ways of assigning each vertex a different color. $6! = 720$

Case $2$: There are $\frac {6!}{2!} * 5$ ways. After picking four colors, we can rotate our pentagon in $5$ ways to get different outcomes. $\frac {6!}{2} * 5 = 1800$

Case $3$: There are $\frac {\frac {6!}{3!} * 10}{2!}$ ways of arranging the final case. We can pick $3$ colors for our pentagon. There are $5$ spots for the first pair of colors. Then, there are $2$ possible ways we can put the final pair in the last $3$ spaces. But because the two pairs are indistinguishable, we divide by $2!$. $\frac {\frac {6!}{3!} * 10}{2!} = 600$

Adding all the possibilities up, we get $720+1800+600=\boxed{3120 \ \mathbf{(C)}}$

~ZericHang

Solution 3

There are $6$ ways to assign a color to $A$. WLOG, give vertex $A$ a color; we can multiply by $6$ at the end. Since vertices $A$ and $C$ cannot have the same color, there are $5$ ways to assign colors to vertex $C$. Using this same logic, there are $5$ ways to assign a color to vertices $E$, $B$, and $D$, giving a total of $5^4=625$ ways. However, vertex $D$ cannot be the same color as vertex $A$. To use complementary counting, we need to find the amount of ways for $D$ and $A$ 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 $5^3=125$ ways, except we must subtract the number of ways for a triangle. Each time, there is $1$ less vertex, so $5$ times less ways to color. This process stops when there are only $2$ vertices left; in this case there are simply $5$ ways to color this figure. So in conclusion, there are $6(5^4-(5^3-(5^2-(5))))=6(5^4-5^3+5^2-5)=\boxed{3120 \ \mathbf{(C)}}$ ways.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_10A_Problems/Problem_22&oldid=97797"