Difference between revisions of "2016 AIME II Problems/Problem 12"

(picture and formatting)
Line 13: Line 13:
 
</asy>
 
</asy>
  
==Solution==
+
==Solution 1==
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>.
+
Choose a section to start coloring. Assume, WLOG, that this section is color <math>1</math>. We proceed coloring clockwise around the ring. Let <math>f(n,C)</math> be the number of ways to color the first <math>n</math> sections (proceeding clockwise) such that the last section has color <math>C</math>. In general (except for when we complete the coloring), we see that
 +
<cmath>f(n,C_i)=\sum_{j\ne i} f(n-1,C_j),</cmath>
 +
i.e., <math>f(n,C_i)</math> is equal to the number of colorings of <math>n-1</math> sections that end in any color other than <math>C_i</math>. Using this, we can compute the values of <math>f(n,C)</math> in the following table.
  
<math>\begin{tabular}{c|c|c|c|c }&1 & 2 & 3& 4 \\ \hline
+
<math>\begin{tabular}{c|c|c|c|c }
 +
\multicolumn{1}{c}{}&\multicolumn{4}{c}{\(C\)}\\
 +
\(n\)&1 & 2 & 3& 4 \\ \hline
 
1& 1 & 0 & 0 & 0\\
 
1& 1 & 0 & 0 & 0\\
 
2 & 0 & 1 & 1 & 1 \\
 
2 & 0 & 1 & 1 & 1 \\
Line 25: Line 29:
 
\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 multiply this by <math>4</math> to account for the fact that the initial section can be any color.  Thus the desired answer is <math>(61+61+61) \cdot 4 = \boxed{732}</math>.
  
 
Solution by Shaddoll
 
Solution by Shaddoll
 +
 +
==Solution 2==
 +
We use complementary counting. There are <math>4^6</math> total colorings of the ring without restriction. To count the complement, we wish to count the number of colorings in which at least one set of adjacent sections are the same color. There are six possible sets of adjacent sections that could be the same color (think of these as borders). Call these <math>B_1,B_2,\dots,B_6</math>. Let <math>\mathcal{A}_1, \mathcal{A}_2,\dots,\mathcal{A}_6</math> be the sets of colorings of the ring where the sections on both sides of <math>B_1,B_2,\dots,B_6</math> are the same color. We wish to determine <math>|\mathcal{A}_1\cup\mathcal{A}_2\cup\cdots\cup\mathcal{A}_6|</math>. Note that all of these cases are symmetric, and in general, <math>|\mathcal{A}_i|=4^5</math>. There are <math>6</math> such sets <math>\mathcal{A}_i</math>. Also, <math>|\mathcal{A}_i\cup\mathcal{A}_j|=4^4</math>, because we can only change colors at borders, so if we have two borders along which we cannot change colors, then there are four borders along which we have a choice of color. There are <math>\binom{6}{2}</math> such pairs <math>\mathcal{A}_i\cup\mathcal{A}_j</math>. Similarly, <math>|\mathcal{A}_i\cup \mathcal{A}_j\cup \mathcal{A}_k|=4^3</math>, with <math>\binom{6}{3}</math> such triples, and we see that the pattern will continue for 4-tuples and 5-tuples. For 6-tuples, however, these cases occur when there are no changes of color along the borders, i.e., each section has the same color. Clearly, there are four such possibilities.
 +
 +
Therefore, by PIE,
 +
<cmath>|\mathcal{A}_1\cup\mathcal{A}_2\cup\cdots\cup\mathcal{A}_6|=\binom{6}{1}\cdot 4^5-\binom{6}{2}\cdot 4^4+\binom{6}{3}\cdot 4^3-\binom{6}{4}\cdot 4^2+\binom{6}{5}\cdot 4^1-4.</cmath>
 +
We wish to find the complement of this, or
 +
<cmath>4^6-\left(\binom{6}{1}\cdot 6^5-\binom{6}{2}\cdot 6^4+\binom{6}{3}\cdot 6^3-\binom{6}{4}\cdot 6^2+\binom{6}{5}\cdot 6^1-4\right).</cmath>
 +
By the Binomial Theorem, this is <math>(4-1)^6+3=\boxed{732}</math>.
 +
== See also ==
 +
{{AIME box|year=2016|n=II|num-b=11|num-a=13}}
 +
{{MAA Notice}}

Revision as of 23:20, 16 May 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 1

Choose a section to start coloring. Assume, WLOG, that this section is color $1$. We proceed coloring clockwise around the ring. Let $f(n,C)$ be the number of ways to color the first $n$ sections (proceeding clockwise) such that the last section has color $C$. In general (except for when we complete the coloring), we see that \[f(n,C_i)=\sum_{j\ne i} f(n-1,C_j),\] i.e., $f(n,C_i)$ is equal to the number of colorings of $n-1$ sections that end in any color other than $C_i$. Using this, we can compute the values of $f(n,C)$ in the following table.

$\begin{tabular}{c|c|c|c|c } \multicolumn{1}{c}{}&\multicolumn{4}{c}{\(C\)}\\ \(n\)&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 multiply this by $4$ to account for the fact that the initial section can be any color. Thus the desired answer is $(61+61+61) \cdot 4 = \boxed{732}$.

Solution by Shaddoll

Solution 2

We use complementary counting. There are $4^6$ total colorings of the ring without restriction. To count the complement, we wish to count the number of colorings in which at least one set of adjacent sections are the same color. There are six possible sets of adjacent sections that could be the same color (think of these as borders). Call these $B_1,B_2,\dots,B_6$. Let $\mathcal{A}_1, \mathcal{A}_2,\dots,\mathcal{A}_6$ be the sets of colorings of the ring where the sections on both sides of $B_1,B_2,\dots,B_6$ are the same color. We wish to determine $|\mathcal{A}_1\cup\mathcal{A}_2\cup\cdots\cup\mathcal{A}_6|$. Note that all of these cases are symmetric, and in general, $|\mathcal{A}_i|=4^5$. There are $6$ such sets $\mathcal{A}_i$. Also, $|\mathcal{A}_i\cup\mathcal{A}_j|=4^4$, because we can only change colors at borders, so if we have two borders along which we cannot change colors, then there are four borders along which we have a choice of color. There are $\binom{6}{2}$ such pairs $\mathcal{A}_i\cup\mathcal{A}_j$. Similarly, $|\mathcal{A}_i\cup \mathcal{A}_j\cup \mathcal{A}_k|=4^3$, with $\binom{6}{3}$ such triples, and we see that the pattern will continue for 4-tuples and 5-tuples. For 6-tuples, however, these cases occur when there are no changes of color along the borders, i.e., each section has the same color. Clearly, there are four such possibilities.

Therefore, by PIE, \[|\mathcal{A}_1\cup\mathcal{A}_2\cup\cdots\cup\mathcal{A}_6|=\binom{6}{1}\cdot 4^5-\binom{6}{2}\cdot 4^4+\binom{6}{3}\cdot 4^3-\binom{6}{4}\cdot 4^2+\binom{6}{5}\cdot 4^1-4.\] We wish to find the complement of this, or \[4^6-\left(\binom{6}{1}\cdot 6^5-\binom{6}{2}\cdot 6^4+\binom{6}{3}\cdot 6^3-\binom{6}{4}\cdot 6^2+\binom{6}{5}\cdot 6^1-4\right).\] By the Binomial Theorem, this is $(4-1)^6+3=\boxed{732}$.

See also

2016 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 11
Followed by
Problem 13
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. AMC logo.png