Difference between revisions of "2016 AIME II Problems/Problem 12"
m (→Solution 4) |
Admathnoob (talk | contribs) (Added another solution to the problem) |
||
Line 57: | Line 57: | ||
To compute the requested value <math>f(6)</math>, we repeatedly apply this formula: <cmath>\begin{align*} f(6)&=4\cdot3^5-f(5)\\&=4\cdot3^5-4\cdot3^4+f(4)\\&=4\cdot3^5-4\cdot3^4+4\cdot3^3-f(3)\\&=4\cdot3^5-4\cdot3^4+4\cdot3^3-4\cdot3^2+f(2)\\&=4(3^5-3^4+3^3-3^2+3)\\&=4\cdot3\cdot\frac{3^5+1}{3+1}\\&=\boxed{732}.\end{align*}</cmath> (Solution by MSTang.) | To compute the requested value <math>f(6)</math>, we repeatedly apply this formula: <cmath>\begin{align*} f(6)&=4\cdot3^5-f(5)\\&=4\cdot3^5-4\cdot3^4+f(4)\\&=4\cdot3^5-4\cdot3^4+4\cdot3^3-f(3)\\&=4\cdot3^5-4\cdot3^4+4\cdot3^3-4\cdot3^2+f(2)\\&=4(3^5-3^4+3^3-3^2+3)\\&=4\cdot3\cdot\frac{3^5+1}{3+1}\\&=\boxed{732}.\end{align*}</cmath> (Solution by MSTang.) | ||
+ | |||
+ | |||
+ | ==Solution 5== | ||
+ | Label the sections 1, 2, 3, 4, 5, 6 clockwise. We do casework on the colours of 1, 3, 5. | ||
+ | |||
+ | Case 1: the colours of the three sections are the same. | ||
+ | In this case, each of 2, 4, 6 can be one of three colours, so this case yields <math>4 \times 3^3 = 108</math> ways. | ||
+ | |||
+ | Case 2: two of sections 1, 3, 5 are the same colour. | ||
+ | Note that there are 3 ways for which of the three sections have the same colour, and <math>4 \times 3 = 12</math> ways to determine their colours. After this, the section between the two with the same colour can be one of 3 colours and the other two can be one of 2 colours. This case yields <math>3 \times (4 \times 3) \times (3 \times 2 \times 2) = 432</math> ways. | ||
+ | |||
+ | Case 3: all three sections of 1, 3, 5 are of different colours. | ||
+ | Clearly there are <math>4 \times 3 \times 2 = 24</math> choices for which three colours to use, and there are 2 ways to choose the colours of each of sections 2, 4, 6. Thus, this case gives <math>4 \times 3 \times 2 \times 2^3 = 192</math> ways. | ||
+ | |||
+ | In total, there are <math>108 + 432 + 192 = \boxed{732}</math> valid colourings. | ||
+ | |||
+ | Solution by ADMathNoob | ||
== See also == | == See also == | ||
{{AIME box|year=2016|n=II|num-b=11|num-a=13}} | {{AIME box|year=2016|n=II|num-b=11|num-a=13}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 21:49, 7 June 2018
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.
Solution 1
Choose a section to start coloring. Assume, WLOG, that this section is color . We proceed coloring clockwise around the ring. Let
be the number of ways to color the first
sections (proceeding clockwise) such that the last section has color
. In general (except for when we complete the coloring), we see that
i.e.,
is equal to the number of colorings of
sections that end in any color other than
. Using this, we can compute the values of
in the following table.
Note that because then
adjacent sections are both color
. We multiply this by
to account for the fact that the initial section can be any color. Thus the desired answer is
.
Solution by Shaddoll
Solution 2
We use complementary counting. There are 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
. Let
be the sets of colorings of the ring where the sections on both sides of
are the same color. We wish to determine
. Note that all of these cases are symmetric, and in general,
. There are
such sets
. Also,
, 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
such pairs
. Similarly,
, with
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,
We wish to find the complement of this, or
By the Binomial Theorem, this is
.
Solution 3
We use generating functions. Suppose that the colors are . Then as we proceed around a valid coloring of the ring in the clockwise direction, we know that between two adjacent sections with colors
and
, there exists a number
such that
. Therefore, we can represent each border between sections by the generating function
, where
correspond to increasing the color number by
, respectively. Thus the generating function that represents going through all six borders is
, where the coefficient of
represents the total number of colorings where the color numbers are increased by a total of
as we proceed around the ring. But if we go through all six borders, we must return to the original section, which is already colored. Therefore, we wish to find the sum of the coefficients of
in
with
.
Now we note that if , then
Therefore, the sum of the coefficients of
with powers congruent to
is
We multiply this by
to account for the initial choice of color, so the answer is
.
Solution 4
Let be the number of valid ways to color a ring with
sections (which we call an
-ring), so the answer is given by
. For
, we compute
. For
, we can count the number of valid colorings as follows: choose one of the sections arbitrarily, which we may color in
ways. Moving clockwise around the ring, there are
ways to color each of the
other sections. Therefore, we have
colorings of an
-ring.
However, note that the first and last sections could be the same color under this method. To count these invalid colorings, we see that by "merging" the first and last sections into one, we get a valid coloring of an -ring. That is, there are
colorings of an
-ring in which the first and last sections have the same color. Thus,
for all
.
To compute the requested value , we repeatedly apply this formula:
(Solution by MSTang.)
Solution 5
Label the sections 1, 2, 3, 4, 5, 6 clockwise. We do casework on the colours of 1, 3, 5.
Case 1: the colours of the three sections are the same.
In this case, each of 2, 4, 6 can be one of three colours, so this case yields ways.
Case 2: two of sections 1, 3, 5 are the same colour.
Note that there are 3 ways for which of the three sections have the same colour, and ways to determine their colours. After this, the section between the two with the same colour can be one of 3 colours and the other two can be one of 2 colours. This case yields
ways.
Case 3: all three sections of 1, 3, 5 are of different colours.
Clearly there are choices for which three colours to use, and there are 2 ways to choose the colours of each of sections 2, 4, 6. Thus, this case gives
ways.
In total, there are valid colourings.
Solution by ADMathNoob
See also
2016 AIME II (Problems • Answer Key • Resources) | ||
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.