Difference between revisions of "2016 AIME II Problems/Problem 12"
(Solution) |
(picture and formatting) |
||
| Line 1: | Line 1: | ||
| + | ==Problem== | ||
The figure below shows a ring made of six small sections which you are to paint on a wall. You have four paint colors available and you will paint each of the six sections a solid color. Find the number of ways you can choose to paint the sections if no two adjacent sections can be painted with the same color. | The figure below shows a ring made of six small sections which you are to paint on a wall. You have four paint colors available and you will paint each of the six sections a solid color. Find the number of ways you can choose to paint the sections if no two adjacent sections can be painted with the same color. | ||
| − | + | ||
| + | <asy> | ||
| + | draw(Circle((0,0), 4)); | ||
| + | draw(Circle((0,0), 3)); | ||
| + | draw((0,4)--(0,3)); | ||
| + | draw((0,-4)--(0,-3)); | ||
| + | draw((-2.598, 1.5)--(-3.4641, 2)); | ||
| + | draw((-2.598, -1.5)--(-3.4641, -2)); | ||
| + | draw((2.598, -1.5)--(3.4641, -2)); | ||
| + | draw((2.598, 1.5)--(3.4641, 2)); | ||
| + | </asy> | ||
==Solution== | ==Solution== | ||
Assume, WLOG, the left ring is color <math>1</math>. Now, let <math>f(a,b)</math> be the number of ways to satisfy the conditions where there are <math>a</math> sections ending on color <math>b</math>. We make a table on <math>f(a,b)</math>. | Assume, WLOG, the left ring is color <math>1</math>. Now, let <math>f(a,b)</math> be the number of ways to satisfy the conditions where there are <math>a</math> sections ending on color <math>b</math>. We make a table on <math>f(a,b)</math>. | ||
| + | |||
<math>\begin{tabular}{c|c|c|c|c }&1 & 2 & 3& 4 \\ \hline | <math>\begin{tabular}{c|c|c|c|c }&1 & 2 & 3& 4 \\ \hline | ||
1& 1 & 0 & 0 & 0\\ | 1& 1 & 0 & 0 & 0\\ | ||
| Line 12: | Line 24: | ||
6& 0& 61 & 61 & 61\\ | 6& 0& 61 & 61 & 61\\ | ||
\end{tabular}</math> | \end{tabular}</math> | ||
| + | |||
Note that <math>f(6, 1)=0</math> because then <math>2</math> adjacent sections are both color <math>1</math>. We also have to multiply by <math>4</math> by symmetry for other colors in the left ring, so the desired answer is <math>(61+61+61) \cdot 4 = \boxed{732}</math>. | Note that <math>f(6, 1)=0</math> because then <math>2</math> adjacent sections are both color <math>1</math>. We also have to multiply by <math>4</math> by symmetry for other colors in the left ring, so the desired answer is <math>(61+61+61) \cdot 4 = \boxed{732}</math>. | ||
Solution by Shaddoll | Solution by Shaddoll | ||
Revision as of 18:09, 18 March 2016
Problem
The figure below shows a ring made of six small sections which you are to paint on a wall. You have four paint colors available and you will paint each of the six sections a solid color. Find the number of ways you can choose to paint the sections if no two adjacent sections can be painted with the same color.
![[asy] draw(Circle((0,0), 4)); draw(Circle((0,0), 3)); draw((0,4)--(0,3)); draw((0,-4)--(0,-3)); draw((-2.598, 1.5)--(-3.4641, 2)); draw((-2.598, -1.5)--(-3.4641, -2)); draw((2.598, -1.5)--(3.4641, -2)); draw((2.598, 1.5)--(3.4641, 2)); [/asy]](http://latex.artofproblemsolving.com/f/b/8/fb859ada9b08ae3472e7ba1166edc94baaacc34a.png)
Solution
Assume, WLOG, the left ring is color 
. Now, let 
be the number of ways to satisfy the conditions where there are 
sections ending on color 
. We make a table on .
Note that 
because then 
adjacent sections are both color . We also have to multiply by 
by symmetry for other colors in the left ring, so the desired answer is 
.
Solution by Shaddoll
