2
$\begingroup$

Peter purchased a pentagonal pen for his puppy Piper. Now Peter wants to decorate the new pen for Piper, and he would like to paint each side of the pen either red, green, or blue so that each wall is a solid color.

enter image description here

Peter can only paint at night when Piper is sleeping, and unfortunately it is too dark for him to determine which color he is painting. So for each wall, Peter randomly chooses a can of paint and paints the wall in that color. In the morning, Peter observes the resulting color scheme. The vertices of the pentagon are labeled with the letters $A, B, C, D,$ and $E$, and these labels are clearly visible during the daytime. What is the probability that no two adjacent walls of the pen have the same color?


My approach was, that the total number of possible ways is $3^5$, and the number of ways to do it is, $3$ for the first side, $2$ for the next, $2$ for the next, $2$ for the next, and either $1$ or $2$ ways for the final side. These would be my two cases. However, I don't know how to do that. Can someone help, please? Thanks!


EDIT: I am open to other methods as well, but please do not make it too complicated.

$\endgroup$
4
  • 1
    $\begingroup$ This question is just an excuse to use that alliteration, isnt it ? ;) $\endgroup$ Mar 6, 2020 at 2:45
  • $\begingroup$ @Certainlynotadog They missed out on "permutation" in that alliterative sentence. :) $\endgroup$
    – Deepak
    Mar 6, 2020 at 3:14
  • 2
    $\begingroup$ You have a course message board to ask questions on. Posting here is cheating. $\endgroup$ Mar 11, 2021 at 14:35
  • $\begingroup$ This question is a special case of computing the chromatic polynomial of a cycle graph. $\endgroup$ May 2 at 17:42

4 Answers 4

5
$\begingroup$

There is no way to paint three sides the same color, with no two adjacent sides being the same color, so we must have one side of one color and two sides of each of the other two colors.

We have $3$ ways to choose the single color and $5$ ways to choose the wall to paint with it. The two adjacent walls must be painted different colors, or the two remaining walls, which are adjacent would be painted the same. There are $2$ ways to choose how to paint the two adjacent walls, and then the colors of the remaining walls are determined.

Altogether, we have $$3\cdot5\cdot2=30$$ admissible colorings.

$\endgroup$
5
$\begingroup$

In general, let $a_n$ be the number of ways to paint the walls of an $n$-gon in $3$ colors so that no two adjacent walls are the same color.

You can show that $$ a_n = 3\cdot 2^{n-1} - a_{n-1}. $$ Let us first unfold the $n$-gon into a line of $n$ walls, and count the number of colorings with no two adjacent walls the same color. There are $3$ choices for the walls at one end, then $2$ choices for its neighbor, then two for its neighbor's neighbor, and so on, leading to $3\cdot 2^{n-1}$ ways.

From these colorings of a linear sequence of walls, we can obtain the number of colorings of a circular arrangement of walls by subtracting the colorings where the walls at either end are the same color. But the number of colorings of a linear sequence of $n$ walls with the first and last walls the same is just $a_{n-1}$.

Taking the recurrence relation, and applying the same relation to $a_{n-1}$, and so on, you get $$ \begin{align} a_n &=3\cdot 2^{n-1}-a_{n-1} \\&=3\cdot 2^{n-1}-(3\cdot 2^{n-2}-a_{n-2}) \\&=3\cdot 2^{n-1}-\big(3\cdot 2^{n-2}-(3\cdot 2^{n-3}-a_{n-3})\big) \\&\vdots \\&=3\big(2^{n-1}-2^{n-2}+2^{n-3}-\dots+(-1)^{n}2\big) \\&=3\cdot \frac{2^{n-1}-(-1)^{n+1}}{1-\frac{-1}2} \\&=2^n+2(-1)^{n}. \end{align} $$ In your case, $a_5=2^5+2(-1)^5=30$. You then divide by $3^5$ to get the probability of no two adjacent walls having like colors.

$\endgroup$
3
$\begingroup$

$5$ sides is small enough for us to do some manual work.

Consider any side. You have $3$ choices for that side, and two for the adjacent ones. Now, split it into 2 cases: $(1)$ the adjacent panels to the first one we considered are of the same color and $(2)$ if they are different.

Case $(1)$ has 2 sub cases: one for each color that is not that of the first panel. In both cases, the last 2 panels cannot have the same color as each other and the same color as the one we chose for the panels adjacent to the first one, so this gives us finally 2 ways in each case: One for either of the last panels which would be painted as the original tile.

Case $(2)$ is even simpler. Again, there are 2 sub cases, the two permutations of the colors on the adjacent panels. Then, out of the last two panels, one MUST have the color of the other adjacent-to-the-first panel and the other must be the color of the first panel.

Can you finish it?

We are assuming the pencil is sharp and not symmetric about any axis perpendicular to its own.

$\endgroup$
2
$\begingroup$

Doing it your way...

Let us look at sides starting from AB and move in anti-clockwise direction. Let AB color is 'c'. We know that BC and EA can't be 'c'. For remaining 2 sides (CD and DE) we have 3 possibilities:

  1. CD color is 'c' (and DE is not 'c')

enter image description here

then as you mentioned:

AB has 3 options, BC has 2 options, CD has 1 option (since fixed to same color as AB), DE has 2 options and AE only has 1 option as shown in figure.

Thus #options = $3\cdot2\cdot1\cdot2\cdot1$ = $12$

  1. DE color is 'c' (and CD is not 'c')

enter image description here

Note that since AB and DE color are same ('c'), we are left with 2 options for EA.

Similarly as shown in figure, #options = $3\cdot2\cdot1\cdot1\cdot2$ = $12$

  1. Neither (of CD and DE) color is 'c'

enter image description here

Similarly #options = $3\cdot2\cdot1\cdot1\cdot1$ = $6$

Thus total favourable ways = $12+12+6$ = $30$

total ways = $3^5$

probability = $\dfrac{30}{3^5}$ = $\dfrac{10}{81}$ = $0.1234567$ :-)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .