2016 AIME II Problems/Problem 12
Contents
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 colors of sections 1, 3, 5.
Case 1: the colors of the three sections are the same.
In this case, each of sections 2, 4, 6 can be one of 3 colors, so this case yields ways.
Case 2: two of sections 1, 3, 5 are the same color.
Note that there are 3 ways for which two of the three sections have the same color, and ways to determine their colors. After this, the section between the two with the same color can be one of 3 colors and the other two can be one of 2 colors. This case yields
ways.
Case 3: all three sections of 1, 3, 5 are of different colors.
Clearly, there are choices for which three colors to use, and there are 2 ways to choose the colors of each of sections 2, 4, 6. Thus, this case gives
ways.
In total, there are valid colorings.
Solution by ADMathNoob
Solution 6
We will take a recursive approach to this problem. We can start by writing out the number of colorings for a circle with and
compartments, which are
and
Now we will try to find a recursive formula,
, for a circle with an arbitrary number of compartments
We will do this by focusing on the
section in the circle. This section can either be the same color as the first compartment, or it can be a different color as the first compartment. We will focus on each case separately.
Case 1:
If they are the same color, we can say there are to fill the first
compartments. The
compartment must be different from the first and second to last compartments, which are the same color. Hence this case adds
to our recursive formula.
Case 2:
If they are different colors, we can say that there are to fill the first
compartments, and for the the
compartment, there are
ways to color it because the
and
compartments are different colors. Hence this case adds
So our recursive formula, , is
Using the initial values we calculated, we can evaluate this recursive formula up to
When
we get
valid colorings.
Solution by NeeNeeMath
Solution 7
WLOG, color the top left section and the top right section
. Then the left section can be colored
,
, or
, and the right section can be colored
,
, or
. There are
ways to color the left and right sections. We split this up into two cases.
Case 1: The left and right sections are of the same color. There are ways this can happen: either they both are
or they both are
. We have
colors to choose for the bottom left, and
remaining colors to choose for the bottom right, for a total of
cases.
Case 2: The left and right sections are of different colors. There are ways this can happen. Assume the left is
and the right is
. Then the bottom left can be
,
, or
, and the bottom right can be
,
, or
. However the bottom sections cannot both be
or both be
, so there are
ways to color the bottom sections, for a total for
colorings.
Since there were ways to color the top sections, the answer is
.
Solution 8
This is equivalent to a node coloring of a cycle with 6 nodes. After repeatedly using deletion-contraction, the solution comes out to be
Solution 9
Label the four colors and
, respectively.
Now let's imagine a circle with the four numbers
and
written clockwise. We'll say that a bug is standing on number
. It is easy to see that for the bug to move to a different number, it must walk
or
steps clockwise. (This is since adjacent numbers can't be the same, as stated in the problem). Note that the sixth number in the bug's walking sequence must not equal the first number. Thus, our total number of ways,
, given the bug's starting number
, is simply the number of ordered quintuplets of positive integers
that satisfy
for all
and
since the bug cannot land on
again on his fifth and last step.
We know that the number of ordered quintuplets of positive integers
that satisfy
without the other restriction is just
, so we aim to find the number of quintuplets such that
Note that the number of ordered quintuplets satisfying
is the same as the number of them satisfying
due to symmetry. By stars and bars, there are
ways to distribute the three "extra" units to the five variables
(since
), but ways of distribution such that one variable is equal to
are illegal, so the actual number of ways is
. Since there are four possible values of
(or the starting position for the bug), we obtain
-fidgetboss_4000
Solution 10
Let's number the regions . Suppose we color regions
. Then, how many ways are there to color
?
Note: the numbers are numbered as shown:
The colors of
are
, in that order.
Then the colors of can be
,
,
,
, or
in that order, where
is any color not equal to its surroundings. Then there are
choices for
,
choices for
(it cannot be
),
choices for
, and
for
, the last color. So, summing up, we have
colorings.
The colors of
are
, in that order.
Again, we list out the possible arrangements of :
,
,
,
,
,
,
,
, or
. (Easily simplified; listed here for clarity.) Then there are
choices for
as usual,
choices for
, and so on. Hence we have
colorings in this case.
Adding up, we have as our answer.
This solution was brought to you by LEONARD_MY_DUDE
Solution 11 (chromatic polynomial-VERY HELPFUL)
We quickly notice that this is just the cycle graph with 6 vertices. The chromatic polynomial for a cycle is where we use
colors on a cycle of
vertices. Plugging in
and
we arrive at
.
~chrisdiamond10
Solution 12 (step-by-step case analysis)
Let's label the regions as in that order. We start with region
. There are no restrictions on the color of region
so it can be any of the four colors. We know move on the region
. It can be any color but color used for region
, giving us
choices. Section
is where it gets a bit complicated; we will have to do casework based on whether the color of region
is that of region
or not.
If we have the color of region being different from that of region
(in which we color do so in
ways), then we have need for another casework at region
. If the color of region
is different from that of region
(which can be achieved in
ways), then we have yet another casework split.
If the color of region is different from that of region
(which can be done in
ways, then we would have a total of
possible colorings for region
(for it cannot be the color of regions
nor
). Moving on to the case where the color of section
is the same as that of section
(which can be done in
way), we will have
ways (region
cannot be that color of both region
and
). Thus, if the color of region
is different of that of region
, then we have
ways.
If the color of region is the same as that of region
(which can be done in one way), then the color of region
have to be different from that of sector
(
ways). That means there will be
choices for the color of region
. So if the color of region
is the same as region
, then we will have
. That means if the color of section
is different from that of region
, then there are
.
Now, moving on to the case where section has the same color of region
. That means section
will have to be a different color of that of region
(
ways). So, that means we have region
to be either the same color or different color as region
. If it is different (which can be done in
ways), then there will be
possibilities on the color of sector
. If it is same (which can be done in
way), then there are
ways to color region
. So, if section
has the same color as section
, then we have
.
Now, in overall we will have .
The full expansion without the explanation is right here:
~sml1809
Solution 13
Video Solution: https://www.youtube.com/watch?v=Yndl8HqVkJk
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.