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.
Insert figure of a smaller circle, a bigger circle, and 6 sections dividing the region between the concentric circles.
+
 
 +
<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 17: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]

Solution

Assume, WLOG, the left ring is color $1$. Now, let $f(a,b)$ be the number of ways to satisfy the conditions where there are $a$ sections ending on color $b$. We make a table on $f(a,b)$.

$\begin{tabular}{c|c|c|c|c }&1 & 2 & 3& 4 \\ \hline 1& 1 & 0 & 0 & 0\\ 2 & 0 & 1 & 1 & 1 \\ 3& 3 & 2 & 2 & 2 \\ 4 & 6 & 7 & 7 & 7 \\ 5 & 21 & 20 & 20 & 20\\ 6& 0& 61 & 61 & 61\\ \end{tabular}$

Note that $f(6, 1)=0$ because then $2$ adjacent sections are both color $1$. We also have to multiply by $4$ by symmetry for other colors in the left ring, so the desired answer is $(61+61+61) \cdot 4 = \boxed{732}$.

Solution by Shaddoll