Difference between revisions of "2006 AIME II Problems/Problem 8"
m |
(→Video Solution) |
||
(12 intermediate revisions by 8 users not shown) | |||
Line 4: | Line 4: | ||
Given that there are six different colors of triangles from which to choose, how many distinguishable large equilateral triangles may be formed? | Given that there are six different colors of triangles from which to choose, how many distinguishable large equilateral triangles may be formed? | ||
− | + | <asy> | |
+ | pair A,B; | ||
+ | A=(0,0); B=(2,0); | ||
+ | pair C=rotate(60,A)*B; | ||
+ | pair D, E, F; | ||
+ | D = (1,0); | ||
+ | E=rotate(60,A)*D; | ||
+ | F=rotate(60,C)*E; | ||
+ | draw(C--A--B--cycle); draw(D--E--F--cycle); | ||
+ | </asy> | ||
− | == Solution == | + | == Solution 1== |
If two of our big equilateral triangles have the same color for their center triangle and the same [[multiset]] of colors for their outer three triangles, we can carry one onto the other by a combination of rotation and reflection. Thus, to make two triangles distinct, they must differ either in their center triangle or in the collection of colors which make up their outer three triangles. | If two of our big equilateral triangles have the same color for their center triangle and the same [[multiset]] of colors for their outer three triangles, we can carry one onto the other by a combination of rotation and reflection. Thus, to make two triangles distinct, they must differ either in their center triangle or in the collection of colors which make up their outer three triangles. | ||
Line 15: | Line 24: | ||
*There are <math>{6\choose1} = 6</math> possible choices for the three outer triangles, if all three are the same color. | *There are <math>{6\choose1} = 6</math> possible choices for the three outer triangles, if all three are the same color. | ||
− | Thus, in total we have <math>6\cdot(20 + 30 + 6) = 336</math> total possibilities. | + | Thus, in total we have <math>6\cdot(20 + 30 + 6) = \boxed{336}</math> total possibilities. |
+ | |||
+ | == Solution 2 (Easy burnsides) == | ||
+ | We apply [[Burnside's Lemma]] and consider 3 rotations of 120 degrees, 240 degrees, and 0 degrees. We also consider three reflections from the three lines of symmetry in the triangle. Thus, we have to divide by <math>3+3=6</math> for our final count. | ||
+ | |||
+ | Case 1: 0 degree rotation. This is known as the identity rotation, and there are <math>6^4=1296</math> choices because we don't have any restrictions. | ||
+ | |||
+ | Case 2: 120 degree rotation. Note that the three "outer" sides of the triangle have to be the same during this, and the middle one can be anything. We have <math>6*6=36</math> choices from this. | ||
+ | |||
+ | Case 3: 240 degree rotation. Similar to the 120 degree rotation, each must be the same except for the middle. We have <math>6*6=36</math> choices from this. | ||
+ | |||
+ | Case 4: symmetry about lines. We multiply by 3 for these because the amount of colorings fixed under symmetry are the exact same each time. Two triangles do not change under this, and they must be the same. The other two triangles (1 middle and 1 outer) can be anything because they stay the same during the reflection. We have <math>6*6*6=216</math> ways for one symmetry. There are 3 symmetries, so there are <math>216*3=648</math> combinations in all. | ||
+ | |||
+ | |||
+ | Now, we add our cases up: <math>1296+36+36+648=2016</math>. We have to divide by 6, so <math>2016/6=\boxed{336}</math> distinguishable ways to color the triangle. | ||
+ | |||
+ | == Solution 3 (stars and bars) == | ||
+ | There are <math>6</math> choices for the center triangle. Note that given any <math>3</math> colors, there is a unique way to assign them to the corner triangles. We have <math>6</math> different colors to choose from, so the number of ways to color the corner triangles is the same as the number of ways to arrange <math>6 - 1 = 5</math> dividers and <math>3</math> identical items. Therefore, our answer is <cmath>6 \binom{5 + 3}{3} = 6\binom{8}{3} = \boxed{336}.</cmath> | ||
+ | |||
+ | -MP8148 | ||
+ | |||
+ | Explanation of the bijection by WIlliamgolly: | ||
+ | Let 1,2,3,4,5,6 be the colors, and WLOG assume that the middle triangle has a color of 6. Now, the color bijection can be formed as follows: Pick the colors to the immediate right of a divider. If there is no color to the immediate right of a divider, then that color is 6. | ||
+ | |||
+ | For example, ||12345| would represent the colors 1,1,6 as the colors chosen. Note for any three colors, there is only one way to fix it on the triangle, thus forming our stars and bars bijection. | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://www.youtube.com/watch?v=dfi23WXZIug&list=PLa8j0YHOYQQIAMDRwkCILRZ5uHnIXcZiw | ||
== See also == | == See also == | ||
Line 21: | Line 57: | ||
[[Category:Intermediate Combinatorics Problems]] | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 22:34, 28 February 2021
Contents
Problem
There is an unlimited supply of congruent equilateral triangles made of colored paper. Each triangle is a solid color with the same color on both sides of the paper. A large equilateral triangle is constructed from four of these paper triangles. Two large triangles are considered distinguishable if it is not possible to place one on the other, using translations, rotations, and/or reflections, so that their corresponding small triangles are of the same color.
Given that there are six different colors of triangles from which to choose, how many distinguishable large equilateral triangles may be formed?
Solution 1
If two of our big equilateral triangles have the same color for their center triangle and the same multiset of colors for their outer three triangles, we can carry one onto the other by a combination of rotation and reflection. Thus, to make two triangles distinct, they must differ either in their center triangle or in the collection of colors which make up their outer three triangles.
There are 6 possible colors for the center triangle.
- There are possible choices for the three outer triangles, if all three have different colors.
- There are (or ) possible choices for the three outer triangles, if two are one color and the third is a different color.
- There are possible choices for the three outer triangles, if all three are the same color.
Thus, in total we have total possibilities.
Solution 2 (Easy burnsides)
We apply Burnside's Lemma and consider 3 rotations of 120 degrees, 240 degrees, and 0 degrees. We also consider three reflections from the three lines of symmetry in the triangle. Thus, we have to divide by for our final count.
Case 1: 0 degree rotation. This is known as the identity rotation, and there are choices because we don't have any restrictions.
Case 2: 120 degree rotation. Note that the three "outer" sides of the triangle have to be the same during this, and the middle one can be anything. We have choices from this.
Case 3: 240 degree rotation. Similar to the 120 degree rotation, each must be the same except for the middle. We have choices from this.
Case 4: symmetry about lines. We multiply by 3 for these because the amount of colorings fixed under symmetry are the exact same each time. Two triangles do not change under this, and they must be the same. The other two triangles (1 middle and 1 outer) can be anything because they stay the same during the reflection. We have ways for one symmetry. There are 3 symmetries, so there are combinations in all.
Now, we add our cases up: . We have to divide by 6, so distinguishable ways to color the triangle.
Solution 3 (stars and bars)
There are choices for the center triangle. Note that given any colors, there is a unique way to assign them to the corner triangles. We have different colors to choose from, so the number of ways to color the corner triangles is the same as the number of ways to arrange dividers and identical items. Therefore, our answer is
-MP8148
Explanation of the bijection by WIlliamgolly: Let 1,2,3,4,5,6 be the colors, and WLOG assume that the middle triangle has a color of 6. Now, the color bijection can be formed as follows: Pick the colors to the immediate right of a divider. If there is no color to the immediate right of a divider, then that color is 6.
For example, ||12345| would represent the colors 1,1,6 as the colors chosen. Note for any three colors, there is only one way to fix it on the triangle, thus forming our stars and bars bijection.
Video Solution
https://www.youtube.com/watch?v=dfi23WXZIug&list=PLa8j0YHOYQQIAMDRwkCILRZ5uHnIXcZiw
See also
2006 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.