How many ways are there to color the walls of a pentagonal room using five different colors, so that no two non-adjacent walls have the same color? 
How many ways are there to color the walls of a pentagonal room using five different colors, so that no two non-adjacent walls have the same color?


I tried casework, but it got very messy before long. I can't think of any other way to approach the problem. Can anyone help?
Thanks!
 A: I actually answered the question:”How many colorations of a the pentagonal room are there such that two adjacents wall never have the same colour?”, but apparently in this particular case the two problems are equivalent.
You can try "recursevely". Let's call $C_n$ the number of suitable colorations for an $n$-gon. Now let's consider your pentagon , imagine to colour only four sides. You can for sure colour them as if they were the sides of a square(imagine to remove "the excluded side" and to glue together the 2 unconnected sides):so at least in $C_4$ ways.In this scenario you can colour the last side in $3$ ways(since we coloured the other four sides as if it was a square, the adjacent sides of the "excluded side" are of different colours). This means that:
$$C_5>3C_4$$
Now we have to consider the cases in which the two "unconnected sides" are of the same colour($5 $possibilities). Than the excluded side can be coloured in $4$ ways and the remaining two sides have to be of different colours(since they are adjacent) and of different colour from the colour of the two "unconnected sides". That is to say $4*3=12$ possibilities. In total $5*4*12=240$. So:
$C_5=3C_4+240$
Now you can brute force calculate $C_4$ or apply the same reasoning:
$C_4=3C_3+80$
Notice that $C_3=5*4*3=60$ since we have to choose a different colour for each side. It follows that:
$$C_4=260$$
$$C_5=1020$$
A: A systematic answer that does not rely on terribly smart insights and can be extended to other scenarios.

Let $\Sigma$ be a set of characters, one for each color, and $w$ be the number of walls. A coloring of the $w$ walls is then isomorphic to a string in $\Sigma^w$.
Construct a DFA with character set $\Sigma$, corresponding to the strings that avoid two characters in a row. It has $|\Sigma| + 1$ states and a starting state, and upon seeing character $c$ we move to state $S_c$, unless we already are in state $S_c$ in which case we move to state $B$ (bad). $B$ is an absorbing state. All states are accepting except $B$.
However, our room wraps around, so we must also ensure that our final character does not equal the first. Copy the above DFA $|\Sigma|$ times, and keep track of what our first character was in each copy. Unmark any state $S_c$ equal to its starting character as accepting.
Now count the number of strings accepted by this DFA. We do this by constructing the transfer matrix $A$ of the above DFA. Compute $A^{w}$ and sum up all numbers in the first row corresponding to accepting states.

In this case let's implement it in Python:
import numpy as np

w = 5; sigma = 5

# Construct graph.
states = ["start", "bad"]
accepting = {"start"}
transitions = {("bad", c): "bad" for c in range(sigma)}

for start_char in range(sigma):
    for last_char in range(sigma):
        S = f"S_{start_char},{last_char}"
        states.append(S)
        if start_char != last_char:
            accepting.add(S)

        for other_char in range(sigma):
            if other_char == last_char:
                next = "bad"
            else:
                next = f"S_{start_char},{other_char}"

            transitions[(S, other_char)] = next

    transitions[("start", start_char)] = f"S_{start_char},{start_char}"

# Construct transfer matrix.
A = np.zeros((len(states), len(states)))
for i, a in enumerate(states):
    for j, b in enumerate(states):
        A[i,j] = sum(transitions[a, ch] == b for ch in range(sigma))

Aw = np.linalg.matrix_power(A, w)
print(sum(Aw[0,i] for i, s in enumerate(states) if s in accepting))

Giving answer $1020$.

With the above systematic method we find for coloring a $n$-sided room with $n$ colors:
3 6
4 84
5 1020
6 15630
7 279930
8 5764808
9 134217720

This gives us A118537, and formula
$$C(n) = (n-1)^n + (n-1)(-1)^n.$$
A: Intro: I originally misread the problem, thinking it asked for adjacent edges not to be the same color. But thanks to Mike Smith's brilliant observation, solving this solves the problem at hand! Why? Imagine drawing a graph where the vertices are the walls, and there is an edge between two walls that are adjacent. What I answered essentially is to find the number of total possible colorings$^*$ of $C_5$ (the cycle graph on $5$ vertices). But what we actually want is a coloring of $K_5 \setminus C_5 = \overline{C_5}$, because we want the edges that are not adjacent not to share the same color. Fortunately, $\overline{C_5}$ is isomorphic to $C_5$! Hence solving the problem that I did actually yields the same answer as the one asked for in the question.
Solution:
The problem is easier when rotational symmetries do not exist. Let $C(n)$ be the total number of ways we can color the walls with $n$ colors such that no two adjacent walls have the same color. Then the quantity we want is
$$\sum_{n = 1}^5 {5 \choose n} \cdot C(n)$$
(We first choose the set of colors we want, then count the number of ways those $n$ colors can be used to color the walls). We then case-bash:

*

*Clearly $C(1) = 0$, because all the walls will be the same color.

*It is also clear that $C(2) = 0$. If the five walls are $a, b, c, d, e$, then $a$'s color has to be opposite $b$'s color, $c$'s color has to be opposite $b$'s color and is therefore $a$'s color, etc. Carrying out this logic shows that $e$ will have to be the same color as $a$.

*If we have three colors, either


*

*One of the colors is used three times and the others only one time. But this is similar to the case with two colors, and you can show that this would have to imply that two adjacent walls share this color.

*Thus, the only actual possibility is that two colors are each used two times and the other one is used only once. There are $3$ ways to choose the color used once, and five ways to choose which wall will be painted that color. Once we choose that wall, we can then observe that the two walls adjacent to it must be painted different colors (why?), of which there are two possibilities (just switch the colors of the left and right wall). So here there are $3 \cdot 5 \cdot 2 = 30$ ways to paint the walls with $3$ colors.


*

*If we use four colors, then the only possibility is for one of the colors to be reused twice and the remaining colors to be used once. There are $4$ ways to choose the color that is used twice. Then, we can just choose which two of the five walls to paint that color (but remember they must not be adjacent, so there are only $5$, not $5 \choose 2$, ways to do so), and note that there will be $3! = 6$ ways to paint the remaining walls. Hence, there are $4 \cdot 5 \cdot 6 = 120$ ways to paint the wall in this way.


*Clearly $C(5) = 5! = 120$ since each color is used once and only once.
And so our final answer is
$${5 \choose 3} \cdot C(3) + {5 \choose 4} \cdot C(4) + {5 \choose 5} \cdot C(5) = 300 + 600 + 120 = 1020$$
ways to paint the walls. $\square$
Note that even though the method for calculating $C(n)$ depended on $n$, the way we counted was still pretty systematic: we first chose how many colors we wanted to use, then chose which colors we wanted to use, then chose how many times we would use each color, and then finally chose which walls would be painted which colors.
Footnote: A valid coloring of a graph assigns a color to each vertex so that no two vertices connect by an edge have the same color.
Reference: Checkout this reference, which gives the number of colorings of all cycle graphs. (Though note that it would not answer the question that was asked if we increased the number of walls. It answers the question for when we don't want adjacent walls to be the same color.)
A: Many of these answers are overcomplicated - this comes from a middle school math test (2014 MATHCOUNTS National Team #9).
Here is my solution:
Let the colors be purple, green, red, blue, and black.
Case 1: Upper left color is the same as the bottom color.
There are 5 ways to choose the lower-left color, and 4 ways to then choose the upper left and bottom color. Notice that for the other two sides, we can choose any two different colors that are not the color that we colored the bottom. There are $\binom{4}{2}=6$ ways to do this, but we have to multiply by $2$ to get $12$ because they can be switched. Therefore, the total number of ways for this case is $5*4*12=240$.
Case 2: Upper left color and bottom color are different. There are 5 ways to choose the lower left color, and again $\binom{4}{2}2=12$ ways to choose the upper left and bottom colors. For the other two colors, there are $4*4=16$ theoretical ways, but remember that they can't be the same color, so we have to subtract off $3$ ways for the three possible colors that they can be. The total number of ways for this case is $5*12*(16-3)=780$.
The answer is then $780+240=\boxed{1020}$.
No recursion or graph theory needed.
