SOLUTION: Cut a circle into 8 congruent parts. Use 4 colors to paint 7 parts of the circle. The adjacent sides cannot have the same colors and you must use all 4 colors. How many methods

Algebra ->  Permutations -> SOLUTION: Cut a circle into 8 congruent parts. Use 4 colors to paint 7 parts of the circle. The adjacent sides cannot have the same colors and you must use all 4 colors. How many methods      Log On


   

Question 877133: Cut a circle into 8 congruent parts.
Use 4 colors to paint 7 parts of the circle.
The adjacent sides cannot have the same colors and you must use all 4 colors. How many methods are there?
Thank you so much.
Answer by Edwin McCravy(20054) About Me  (Show Source):
You can put this solution on YOUR website!
Our approach will be this way:

%28matrix%288%2C1%2C%0D%0ANumber%2C+of%2Cways%2Cthat%2C+use%2C+ALL%2C+FOUR%2C+colors%29%29 %22%22=%22%22 %22%22-%22%22%22%22-%22%22


First we calculate the number of ways if we had no restriction
on the number of colors we must use.  That is, we calculate as
though we didn't have the restriction "you must use all 4 colors".
That is, to begin with, we calculate the number of ways using 4 
or fewer colors.

Choose the color for the 1st part 4 ways.
Choose the color for the 2nd part 3 ways.
Choose the color for the 3rd part 3 ways.
Choose the color for the 4th part 3 ways.
Choose the color for the 5th part 3 ways.
Choose the color for the 6th part 3 ways.
Choose the color for the 7th part 3 ways.

That's 4×3×3×3×3×3×3 = 4×36 = 2916 ways 
that we can use 4 or fewer colors and have no adjacent
parts with the same color.

From the 2916 we will subtract:

A. the number that use exactly 3 of the 4 colors, and
B. the number that use exactly 2 of the 4 colors.

A. We'll calculate the number of ways that use exactly  
3 of the 4 colors.

We'll calculate the number of ways that use exact 3 SPECIFIED 
colors.  (Then we'll multiply that by C(4,3) ways to choose 
the 3 specified colors.)

We begin this by first calculating the number of ways that
use 3 OR 2 colors. 

Choose the color for the 1st part 3 ways.
Choose the color for the 2nd part 2 ways.
Choose the color for the 3rd part 2 ways.
Choose the color for the 4th part 2 ways.
Choose the color for the 5th part 2 ways.
Choose the color for the 6th part 2 ways.
Choose the color for the 7th part 2 ways.

That's 3×2×2×2×2×2×2 = 3×26 = 192 ways that use
3 or fewer of 3 specified colors.

From that we must calculate and subtract the number 
of ways that use 2 of those specifed 3 colors.  There 
are only 2 such types:  ABABABA and BABABAB, where A and
B represent different colors.  But since we have 3
specified colors, we can choose the 2 colors any of 
C(3,2) or 3 ways. So that's 6 ways we must subtract 
from the 192.

So there are 192-6 = 186 ways to have exactly 3 
specified colors.

But there are C(4,3) = 4 ways to chose the 3 specified
colors.  So there are 4×186 = 744 ways that use exactly
3 of the four colors.

B. Finally we must subtract the number which have exactly
2 of the 4 colors.

We have already shown that there are only 2 types which
use exactly 2 colors, ABABABA and BABABAB.  And there
are C(4,2) = 6 ways to choose the 2 colors for them.
So that's 6×2 or 12 ways to use exactly 2 colors.     

Answer: 2916-744-12 = 2160.

Edwin