This problem is from Purple Comet High school contest, 2016.
Ten square tiles are placed in a row, and each can be painted with one of the four colors red (R), yellow (Y), blue (B), and white (W). Find the number of ways this can be done so that each block of five adjacent
tiles contains at least one tile of each color. That is, count the patterns RWBWYRRBWY and
WWBYRWYBWR but not RWBYYBWWRY because the five adjacent tiles colored BYYBW does not
include the color red.
It is easy to see that if a particular color to appear in any block of five tiles, there must be at least two tiles of that color and the two tiles must be at one of the following pairs of positions:
\begin{align*}
& 1,6 \\
& 2,6 \quad 2,7 \\
& 3,6 \quad 3,7 \quad 3,8 \\
& 4,6 \quad 4,7 \quad 4,8 \quad 4,9 \\
& 5,6 \quad 5,7 \quad 5,8 \quad 5,9 \quad 5,10 \\
\end{align*}
We need to choose 4 of the above pairs such that no two have the same first coordinate/second coordinate and assign the four colors one each to a pair. The remaining two tiles can be arbitrary color.
If we choose four from $(1,6), (2,7), (3,8), (4,9), (5,10)$, there are 24 ways to map the four colors and the number of colorings is
$5 \cdot 24 \cdot\left(\frac{4}{2} + \binom{4}{2} \cdot 2\right) = 1680$.
When we choose four pairs other than the above five, there are 26 ways to choose the four pairs and there are multiple countings in subtle ways:
For example, when we choose that pairs $(1,6), (3,7), (4,8), (5,9)$, the coloring $WWBRYWBRYY$ is counted 4 times: the other three occur from the pairs $((2,6), (3,7), (4,8), (5,9))$, $((2,6), (3,7), (4,8), (5,9))$, $((1,6), (3,7), (4,8), (5,10))$ and $((2,6), (3,7), (4,8), (5,10))$ and the colorings $WWBRYWBRYW, WWBRYWBRYB, WWBRYWBRYR$ are counted twice each.
I am not able to eliminate all the multiple countings. The answer is 7296.
Best Answer
There are four types of legitimate sequence of length $n$:
Type $A$: the last four colours are distinct,
Type $B$: the second from last colour is repeated later in the sequence,
Type $C$: the third from last colour is repeated later in the sequence,
Type $D$: the fourth from last colour is repeated later in the sequence.
A length $n$ sequence of type $A$ may be extended uniquely to one sequence each of type $A,B,C,D$ of length $n+1$. Sequences of the other types may be extended uniquely to just one sequence of length $n+1$ of the following types:$$B\to C\to D\to A.$$
Let $A_n,B_n,C_n,D_n$ denote the number of length $n$ sequences of type $A,B,C,D$ respectively, each divided by 24 (to keep the numbers small). From the above we have:
\begin{eqnarray*} A_{n+1}&=&A_n+D_n\\ B_{n+1}&=&A_n\\ C_{n+1}&=&A_n+B_n\\ D_{n+1}&=&A_n+C_n\\ \end{eqnarray*}
Writing $A_n,B_n,C_n,D_n$ as a column vector and starting at $n=4$ we get: $$ \left(\begin{array}{c} 1\\1\\2\\3 \end{array} \right) \to \left(\begin{array}{c} 4\\1\\2\\3 \end{array} \right) \to \left(\begin{array}{c} 7\\4\\5\\6 \end{array} \right) \to \left(\begin{array}{c} 13\\7\\11\\12 \end{array} \right) \to \left(\begin{array}{c} 25\\13\\20\\24 \end{array} \right) \to \left(\begin{array}{c} 49\\25\\38\\45 \end{array} \right) \to \left(\begin{array}{c} 94\\49\\74\\87 \end{array} \right) $$
Adding the values for $n=10$ and returning the factor of 24 we get:$$24(94+49+74+87)=24*304=7296.$$
This was quick to do by hand for $n=10$. However the general solution will be a linear combination of $n$'th powers of the roots of the polynomial $$t^4-t^3-t^2-t-1.$$