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 "2017 AMC 10B Problems/Problem 18"
 
(21 intermediate revisions by 12 users not shown)
Line 1: Line 1:
−
==Problem==
+
== Problem ==
 
In the figure below, <math>3</math> of the <math>6</math> disks are to be painted blue, <math>2</math> are to be painted red, and <math>1</math> is to be painted green. Two paintings that can be obtained from one another by a rotation or a reflection of the entire figure are considered the same. How many different paintings are possible?
 
In the figure below, <math>3</math> of the <math>6</math> disks are to be painted blue, <math>2</math> are to be painted red, and <math>1</math> is to be painted green. Two paintings that can be obtained from one another by a rotation or a reflection of the entire figure are considered the same. How many different paintings are possible?
  
 
<asy>
 
<asy>
−
size(100);
+
size(110);
 
pair A, B, C, D, E, F;
 
pair A, B, C, D, E, F;
 
A = (0,0);
 
A = (0,0);
Line 21: Line 21:
 
<math>\textbf{(A)}\ 6\qquad\textbf{(B)}\ 8\qquad\textbf{(C)}\ 9\qquad\textbf{(D)}\ 12\qquad\textbf{(E)}\ 15</math>
 
<math>\textbf{(A)}\ 6\qquad\textbf{(B)}\ 8\qquad\textbf{(C)}\ 9\qquad\textbf{(D)}\ 12\qquad\textbf{(E)}\ 15</math>
  
−
==Solution==
+
== Solution 1 ==
−
 
 
−
===Solution 1===
 
 
First we figure out the number of ways to put the <math>3</math> blue disks. Denote the spots to put the disks as <math>1-6</math> from left to right, top to bottom. The cases to put the blue disks are <math>(1,2,3),(1,2,4),(1,2,5),(1,2,6),(2,3,5),(1,4,6)</math>. For each of those cases we can easily figure out the number of ways for each case, so the total amount is <math>2+2+3+3+1+1 = \boxed{\textbf{(D) } 12}</math>.
 
First we figure out the number of ways to put the <math>3</math> blue disks. Denote the spots to put the disks as <math>1-6</math> from left to right, top to bottom. The cases to put the blue disks are <math>(1,2,3),(1,2,4),(1,2,5),(1,2,6),(2,3,5),(1,4,6)</math>. For each of those cases we can easily figure out the number of ways for each case, so the total amount is <math>2+2+3+3+1+1 = \boxed{\textbf{(D) } 12}</math>.
  
−
===Solution 2===
+
== Solution 2 (similar to solution 4 but simpler)==
−
Denote the <math>6</math> discs as in the first solution. Ignoring reflections or rotations, there are <math>\binom{6}{3} * \binom{3}{2} = 60</math> colorings. Now we need to count the number of fixed points under possible transformations:
+
Denote the <math>6</math> discs as in the first solution. Ignoring reflections or rotations, there are <math>\binom{6}{3} \cdot \binom{3}{2} = 60</math> colorings. Now we need to count the number of fixed points under possible transformations:
  
−
1. The identity transformation. Since this doesn't change anything, there are <math>60</math> fixed points
+
1. The identity transformation. Since this doesn't change anything, there are <math>60</math> fixed points.
  
−
2. Reflect about a line of symmetry. There are <math>3</math> lines of reflections. Take the line of reflection going through the centers of circles <math>1</math> and <math>5</math>. Then, the colors of circles <math>2</math> and <math>3</math> must be the same, and the colors of circles <math>4</math> and <math>6</math> must be the same. This gives us <math>4</math> fixed points per line of reflection
+
2. Reflect on a line of symmetry. There are <math>3</math> lines of reflections. Take the line of reflection going through the centers of circles <math>1</math> and <math>5</math>. Then, the colors of circles <math>2</math> and <math>3</math> must be the same, and the colors of circles <math>4</math> and <math>6</math> must be the same. This gives us <math>4</math> fixed points per line of reflection.
  
−
3. Rotate by <math>120^\circ</math> counter clockwise or clockwise with respect to the center of the diagram. Take the clockwise case for example. There will be a fixed point in this case if the colors of circles <math>1</math>, <math>4</math>, and <math>6</math> will be the same. Similarly, the colors of circles <math>2</math>, <math>3</math>, and <math>5</math> will be the same. This is impossible, so this case gives us <math>0</math> fixed points per rotation.
+
3. Rotate by <math>120^\circ</math> counterclockwise or clockwise with respect to the center of the diagram. Take the clockwise case for example. There will be a fixed point in this case if the colors of circles <math>1</math>, <math>4</math>, and <math>6</math> will be the same. Similarly, the colors of circles <math>2</math>, <math>3</math>, and <math>5</math> will be the same. This is impossible, so this case gives us <math>0</math> fixed points per rotation.
  
−
By Burnside's lemma, the total number of colorings is <math>(1*60+3*4+2*0)/(1+3+2) = \boxed{\textbf{(D) } 12}</math>.
+
By [[Burnside's Lemma]], the total number of colorings is <math>(1 \cdot 60+3 \cdot 4+2 \cdot 0)/(1+3+2) = \boxed{\textbf{(D) } 12}</math>.
  
 +
== Solution 3 ==
 +
Note that the green disk has two possibilities; in a corner or on the side. WLOG, we can arrange these as
  
−
===Solution 3===
 
−
Note that the green disk has two possibilities; in a corner or on the side. WLOG, we can arrange these as
 
 
<asy>
 
<asy>
 
filldraw(circle((0,0),1),green);
 
filldraw(circle((0,0),1),green);
Line 55: Line 53:
 
draw(circle((10,2sqrt(3)),1));
 
draw(circle((10,2sqrt(3)),1));
 
</asy>
 
</asy>
−
Take the first case. Now, we must pick two of the five remaining circles to fill in the red. There are <math>\dbinom{5}{2}=10</math> of these. However, due to reflection we must divide this by two. But, in two of these cases, the reflection is itself, so we must subtract these out before dividing by 2, and add them back afterwards, giving <math>\frac{10-2}{2}+2=6</math> arrangement in this case.
+
 
 +
Take the first case. Now, we must pick two of the five remaining circles to fill in the red. There are <math>\dbinom{5}{2}=10</math> of these. However, due to reflection we must divide this by two. But, in two of these cases, the reflection is itself, so we must subtract these out before dividing by 2, and add them back afterwards, giving <math>\frac{10-2}{2}+2=6</math> arrangements in this case.
  
 
Now, look at the second case. We again must pick two of the five remaining circles, and like in the first case, two of the reflections give the same arrangement. Thus, there are also <math>6</math> arrangements in this case.  
 
Now, look at the second case. We again must pick two of the five remaining circles, and like in the first case, two of the reflections give the same arrangement. Thus, there are also <math>6</math> arrangements in this case.  
Line 61: Line 60:
 
In total, we have <math>6+6=\boxed{\text{\bf(D) }12}</math>.
 
In total, we have <math>6+6=\boxed{\text{\bf(D) }12}</math>.
  
−
Solution by tdeng
+
~tdeng
 +
 
 +
== Solution 4 (Burnside's Lemma) ==
 +
We note that the group <math>G</math> acting on the possible colorings is <math>D_3 = \{e, r, r^2, s, sr, sr^2\}</math>, where <math>r</math> is a <math>120^\circ</math> rotation and <math>s</math> is a reflection. In particular, the possible actions are the identity, the <math>120^\circ</math> and <math>240^\circ</math> rotations, and the three reflections.
 +
 
 +
We will calculate the number of colorings that are fixed under each action. Every coloring is fixed under the identity, so we count <math>\dfrac{6!}{3!2!1!} = 60</math> fixed colorings. Note that no colorings are fixed under the rotations, since then the outer three and inner three circle must be the same color, which is impossible in our situation.
 +
 
 +
Finally, consider the reflection with a line of symmetry going through the top circle. Every fixed coloring is determined by the color of the top circle (either green or blue), and the color of the middle circles (either blue or red). Hence, there are <math>2\cdot 2 = 4</math> colorings fixed under this reflection action. The other two actions are symmetric, so they also have <math>4</math> fixed colorings. Hence, by Burnside's lemma, the number of unique colorings up to reflections and rotations is
 +
<cmath> \dfrac{1}{|D_3|} (1\cdot 60 + 2\cdot 0 + 3\cdot 4) = \dfrac{1}{6}\cdot 72 = \boxed{\textbf{(D)  } 12}.</cmath>
 +
 
 +
== Solution 5 ==
 +
Call the ball in the top row A, the two balls in the 2nd row from left to right B and C, and the bottom rows balls from left to right D, E, and F. The total amount of paintings is <math>6 \cdot \dbinom{5}{2} \cdot \dbinom{3}{3} = 60</math>. If we divided this number by <math>3</math> (for rotations) and <math>2</math> (for reflections), we would not get the right answer, because the paintings that do not change when reflected are over-subtracted. So lets find the number of over subtracted paintings. To be symmetric, ball B and C must be the same color, D and F must be the same color, and A and E can be any color because they are on the line of symmetry. Pair B,C and D,F must be blue and red or red and blue, which is <math>2</math> possibilities. Then, Ball A has <math>2</math> possibilities, and Ball E has <math>1</math> possibility (the one remaining color). That means, the number of paintings that when they are reflected do not change is <math>2 \cdot 2 = 4.</math> The total amount of these paintings, after accounting for rotations, is <math>4 \cdot 3 = 12.</math> Then there are <math>60 - 12 = 48</math> paintings that when reflected, change. <math>48/(2 \cdot 3) = 8.</math> (We divided by <math>2 \cdot 3</math> since we are accounting for rotations and reflections.) Then, adding back the <math>4</math> paintings we subtracted off because they didn't change when reflected, we get <math>4 + 8 = 12.</math> □ (to look professional)
 +
 
 +
~heheman
 +
 
 +
== Solution 6 ==
 +
Notice that the green ball can be placed in 6 different positions. If the ball is placed on the top position, bottom-left position, or bottom-right position, it can be rotated to make the green ball on the top position. Meanwhile, if the green ball is placed on the middle-left, middle-right, or bottom-middle position, it can be rotated to move the green ball to the bottom-middle position. To avoid overcounting due to rotations, we can divide this problem into two cases: the green ball is at the top position, or the green ball is at the bottom-middle position.
 +
 
 +
Consider the first case. If the green ball is placed in the top position, the other five balls can be placed in <math>\tbinom{5}{2}</math> ways. (We choose 2 of the 5 positions to be occupied by the red ball.) In the following positions,
 +
  G                                  G
 +
  R R                and            B B
 +
B B B                              R B R
 +
the position is identical under reflection over a vertical line. All other 8 positions have a reflection that is different. Thus, we can count only half of these 8 positions (because otherwise we would be over counting), but we can count both of the two special cases (since they don't make a different image when reflected. Thus, this case has <math>\frac{8}{2}+2=6</math> cases.
 +
 
 +
In the second case, the green ball is placed in the bottom-middle position. Similarly, the other five balls can be placed in <math>\tbinom{5}{2}</math> ways. In the special cases,
 +
  B                                  B
 +
  R R                and            B B
 +
B G B                              R G R
 +
the position is identical under reflection over a vertical line. Proceeding just like the first case, there are <math>\frac{8}{2}+2=6</math> cases.
 +
 
 +
In total, there are <math>6+6=\boxed{\textbf{(D) }12}</math> different paintings.
  
−
==Solution: Burnsides+Guessing, for if you are running out of time but want some free points==
+
~sid2012 [https://artofproblemsolving.com/wiki/index.php/User:Sid2012]
−
By burnsides, we quickly find the set <math>G</math> of all group actions that can be applied to one coloring to obtain another. <math>G={s_1,s_2, s_3,120^\circ,240^\circ, e}</math>, where all <math>s_k</math> are lines of reflection symmetry and <math>120^\circ,240^\circ</math> are the rotations, and <math>e</math> is the identity. Note that all <math>C(6,3)*C(3,2)=60</math> colorings are fixed by the identity. Let's say there are a total of <math>K</math> other fixed points (that let's say we don't have time to calculate) from the other group actions. Using Burnsides, we have <math>(60+K)/6=10+K/6</math>. At this point, we can clearly get rid of (A), (B), and (C). We have now narrowed down to two answers, and if you're lucky, you can guess <math>\boxed{\text{\bf(D) }12}</math>
 
  
−
==See Also==
+
== See Also ==
 
{{AMC10 box|year=2017|ab=B|num-b=17|num-a=19}}
 
{{AMC10 box|year=2017|ab=B|num-b=17|num-a=19}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 14:56, 3 November 2024

Problem

In the figure below, $3$ of the $6$ disks are to be painted blue, $2$ are to be painted red, and $1$ is to be painted green. Two paintings that can be obtained from one another by a rotation or a reflection of the entire figure are considered the same. How many different paintings are possible?

[asy] size(110); pair A, B, C, D, E, F; A = (0,0); B = (1,0); C = (2,0); D = rotate(60, A)*B; E = B + D; F = rotate(60, A)*C; draw(Circle(A, 0.5)); draw(Circle(B, 0.5)); draw(Circle(C, 0.5)); draw(Circle(D, 0.5)); draw(Circle(E, 0.5)); draw(Circle(F, 0.5)); [/asy]

$\textbf{(A)}\ 6\qquad\textbf{(B)}\ 8\qquad\textbf{(C)}\ 9\qquad\textbf{(D)}\ 12\qquad\textbf{(E)}\ 15$

Solution 1

First we figure out the number of ways to put the $3$ blue disks. Denote the spots to put the disks as $1-6$ from left to right, top to bottom. The cases to put the blue disks are $(1,2,3),(1,2,4),(1,2,5),(1,2,6),(2,3,5),(1,4,6)$. For each of those cases we can easily figure out the number of ways for each case, so the total amount is $2+2+3+3+1+1 = \boxed{\textbf{(D) } 12}$.

Solution 2 (similar to solution 4 but simpler)

Denote the $6$ discs as in the first solution. Ignoring reflections or rotations, there are $\binom{6}{3} \cdot \binom{3}{2} = 60$ colorings. Now we need to count the number of fixed points under possible transformations:

1. The identity transformation. Since this doesn't change anything, there are $60$ fixed points.

2. Reflect on a line of symmetry. There are $3$ lines of reflections. Take the line of reflection going through the centers of circles $1$ and $5$. Then, the colors of circles $2$ and $3$ must be the same, and the colors of circles $4$ and $6$ must be the same. This gives us $4$ fixed points per line of reflection.

3. Rotate by $120^\circ$ counterclockwise or clockwise with respect to the center of the diagram. Take the clockwise case for example. There will be a fixed point in this case if the colors of circles $1$, $4$, and $6$ will be the same. Similarly, the colors of circles $2$, $3$, and $5$ will be the same. This is impossible, so this case gives us $0$ fixed points per rotation.

By Burnside's Lemma, the total number of colorings is $(1 \cdot 60+3 \cdot 4+2 \cdot 0)/(1+3+2) = \boxed{\textbf{(D) } 12}$.

Solution 3

Note that the green disk has two possibilities; in a corner or on the side. WLOG, we can arrange these as

[asy] filldraw(circle((0,0),1),green); draw(circle((2,0),1)); draw(circle((4,0),1)); draw(circle((1,sqrt(3)),1)); draw(circle((3,sqrt(3)),1)); draw(circle((2,2sqrt(3)),1)); draw(circle((8,0),1)); filldraw(circle((10,0),1),green); draw(circle((12,0),1)); draw(circle((9,sqrt(3)),1)); draw(circle((11,sqrt(3)),1)); draw(circle((10,2sqrt(3)),1)); [/asy]

Take the first case. Now, we must pick two of the five remaining circles to fill in the red. There are $\dbinom{5}{2}=10$ of these. However, due to reflection we must divide this by two. But, in two of these cases, the reflection is itself, so we must subtract these out before dividing by 2, and add them back afterwards, giving $\frac{10-2}{2}+2=6$ arrangements in this case.

Now, look at the second case. We again must pick two of the five remaining circles, and like in the first case, two of the reflections give the same arrangement. Thus, there are also $6$ arrangements in this case.

In total, we have $6+6=\boxed{\text{\bf(D) }12}$.

~tdeng

Solution 4 (Burnside's Lemma)

We note that the group $G$ acting on the possible colorings is $D_3 = \{e, r, r^2, s, sr, sr^2\}$, where $r$ is a $120^\circ$ rotation and $s$ is a reflection. In particular, the possible actions are the identity, the $120^\circ$ and $240^\circ$ rotations, and the three reflections.

We will calculate the number of colorings that are fixed under each action. Every coloring is fixed under the identity, so we count $\dfrac{6!}{3!2!1!} = 60$ fixed colorings. Note that no colorings are fixed under the rotations, since then the outer three and inner three circle must be the same color, which is impossible in our situation.

Finally, consider the reflection with a line of symmetry going through the top circle. Every fixed coloring is determined by the color of the top circle (either green or blue), and the color of the middle circles (either blue or red). Hence, there are $2\cdot 2 = 4$ colorings fixed under this reflection action. The other two actions are symmetric, so they also have $4$ fixed colorings. Hence, by Burnside's lemma, the number of unique colorings up to reflections and rotations is \[\dfrac{1}{|D_3|} (1\cdot 60 + 2\cdot 0 + 3\cdot 4) = \dfrac{1}{6}\cdot 72 = \boxed{\textbf{(D) } 12}.\]

Solution 5

Call the ball in the top row A, the two balls in the 2nd row from left to right B and C, and the bottom rows balls from left to right D, E, and F. The total amount of paintings is $6 \cdot \dbinom{5}{2} \cdot \dbinom{3}{3} = 60$. If we divided this number by $3$ (for rotations) and $2$ (for reflections), we would not get the right answer, because the paintings that do not change when reflected are over-subtracted. So lets find the number of over subtracted paintings. To be symmetric, ball B and C must be the same color, D and F must be the same color, and A and E can be any color because they are on the line of symmetry. Pair B,C and D,F must be blue and red or red and blue, which is $2$ possibilities. Then, Ball A has $2$ possibilities, and Ball E has $1$ possibility (the one remaining color). That means, the number of paintings that when they are reflected do not change is $2 \cdot 2 = 4.$ The total amount of these paintings, after accounting for rotations, is $4 \cdot 3 = 12.$ Then there are $60 - 12 = 48$ paintings that when reflected, change. $48/(2 \cdot 3) = 8.$ (We divided by $2 \cdot 3$ since we are accounting for rotations and reflections.) Then, adding back the $4$ paintings we subtracted off because they didn't change when reflected, we get $4 + 8 = 12.$ □ (to look professional)

~heheman

Solution 6

Notice that the green ball can be placed in 6 different positions. If the ball is placed on the top position, bottom-left position, or bottom-right position, it can be rotated to make the green ball on the top position. Meanwhile, if the green ball is placed on the middle-left, middle-right, or bottom-middle position, it can be rotated to move the green ball to the bottom-middle position. To avoid overcounting due to rotations, we can divide this problem into two cases: the green ball is at the top position, or the green ball is at the bottom-middle position.

Consider the first case. If the green ball is placed in the top position, the other five balls can be placed in $\tbinom{5}{2}$ ways. (We choose 2 of the 5 positions to be occupied by the red ball.) In the following positions, 

  G                                  G
 R R                and             B B
B B B                              R B R

the position is identical under reflection over a vertical line. All other 8 positions have a reflection that is different. Thus, we can count only half of these 8 positions (because otherwise we would be over counting), but we can count both of the two special cases (since they don't make a different image when reflected. Thus, this case has $\frac{8}{2}+2=6$ cases.

In the second case, the green ball is placed in the bottom-middle position. Similarly, the other five balls can be placed in $\tbinom{5}{2}$ ways. In the special cases, 

  B                                  B
 R R                and             B B
B G B                              R G R

the position is identical under reflection over a vertical line. Proceeding just like the first case, there are $\frac{8}{2}+2=6$ cases.

In total, there are $6+6=\boxed{\textbf{(D) }12}$ different paintings.

~sid2012 [1]

See Also

2017 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 17 		Followed by
Problem 19
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=2017_AMC_10B_Problems/Problem_18&oldid=231397"