A password lock is set by assigning one of the two numbers 0 and 1 to each vertex of a regular $n$-sided polygon $A_{1} A_{2} \cdots A_{n}$, and coloring each vertex in one of two colors, red or blue, such that for any two adjacent vertices, at least one of the number or color is the same. How many different password settings are there for this type of password lock? ${ }^{[1]}$
(2010, National High School Mathematics Competition)
Using 2 to represent red and 3 to represent blue, the problem is equivalent to:
In an $n$-sided polygon $A_{1} A_{2} \cdots A_{n}$, label the vertices $A_{i}(i=1,2, \cdots, n)$ with ordered pairs $\left(x_{i}, y_{i}\right)\left(x_{i}=0\right.$ or $1, y_{i}=2$ or 3$)$, such that for any $i(1 \leqslant i \leqslant n)$, $\left(x_{i}, y_{i}\right)$ and $\left(x_{i+1}, y_{i+1}\right)$ have at least one component in common, where $x_{n+1}=x_{1}, y_{n+1}=y_{1}$.
Let the number of valid labeling methods be $a_{n}$, then
$a_{1}=4, a_{2}=4 \times 3=12$.
When $n \geqslant 3$, if we do not consider whether $\left(x_{1}, y_{1}\right)$ and $\left(x_{n}, y_{n}\right)$ satisfy the above requirement, then $\left(x_{1}, y_{1}\right)$ has 4 possibilities, $\left(x_{2}, y_{2}\right)$ has 3 possibilities, $\cdots \cdots \cdot\left(x_{n}, y_{n}\right)$ has 3 possibilities. Thus, there are $4 \times 3^{n-1}$ methods in total.

Consider the number of methods $t$ where $\left(x_{1}, y_{1}\right)$ and $\left(x_{n}, y_{n}\right)$ have no common components.
Assume $\left(x_{1}, y_{1}\right)=(0,2)$. Then $\left(x_{n}, y_{n}\right)=(1,3)$.
By the coloring rule, $\left(x_{2}, y_{2}\right) \neq(1,3)$.
Let $\left(x_{2}, y_{2}\right),\left(x_{3}, y_{3}\right), \cdots,\left(x_{n-1}, y_{n-1}\right)$ be the largest index not equal to $(1,3)$, i.e.,
$\left(x_{k}, y_{k}\right) \neq(1,3)$.
And $\left(x_{k+1}, y_{k+1}\right)=\left(x_{k+2}, y_{k+2}\right)=\ldots$
$=\left(x_{n}, y_{n}\right)=(1,3)(2 \leqslant k \leqslant n-1)$.
Connect $A_{1} A_{k}$.

Consider the labeling of the vertices of the polygon $A_{1} A_{2} \cdots A_{k}$. Then there are $a_{k}$ valid labeling methods. But according to the above rule, $\left(x_{k}, y_{k}\right) \neq(0,2)$, otherwise, $\left(x_{k+1}, y_{k+1}\right)=(1,3)$,
$\left(x_{k}, y_{k}\right)$ and $\left(x_{k+1}, y_{k+1}\right)$ have no common components, which is a contradiction.

Thus, the labeling of the vertices of the polygon $A_{1} A_{2} \cdots A_{k}$ does not include the case $\left(x_{k}, y_{k}\right)=(0,2)$.
When $\left(x_{k}, y_{k}\right)=(0,2)$,
$\left(x_{k}, y_{k}\right)=(0,2)=\left(x_{1}, y_{1}\right)$,

Merge $A_{1}$ and $A_{k}$ into one point, and the number of valid labeling methods for the $(k-1)$-sided polygon is $a_{k-1}$.
Therefore, the number of valid labeling methods for the vertices of the polygon $A_{1} A_{2} \cdots A_{k}$ is
$a_{k}-a_{k-1}$.
Notice that, $k=2,3, \cdots, n$.
Thus, $t=\sum_{k=2}^{n-1}\left(a_{k}-a_{k-1}\right)=a_{n-1}-a_{1}=a_{n-1}-4$.
So, $a_{n}=4 \times 3^{n-1}-t=4 \times 3^{n-1}-a_{n-1}+4$.
Iterating, we get $a_{n}=3^{n}+2+(-1)^{n}$.
2 Generalization
Using the above method, the original problem can be generalized to:
A password lock's password setting involves labeling each vertex of a regular $n$-sided polygon $A_{1} A_{2} \cdots A_{n}$ with a $k$-dimensional array $\left(p_{1}, p_{2}, \cdots, p_{k}\right)$, where $p_{i} \in\{0,1\}(i=1,2, \cdots, k)$, such that any two adjacent vertices have at least one common component in their $k$-dimensional arrays. How many different password settings are there for this lock?
Using a completely similar method, the solution is as follows.
Let the number of valid labeling methods be $a_{n}$. Then
$a_{1}=2^{k}, a_{2}=2^{k}\left(2^{k}-1\right)=4^{k}-2^{k}$.
When $n \geqslant 3$, if we do not consider the relationship between the array $\left(p_{1}, p_{2}, \cdots, p_{k}\right)$ at vertex $A_{1}$ and the array $\left(q_{1}, q_{2}, \cdots, q_{k}\right)$ at vertex $A_{n}$, then the array at $A_{1}$ has $2^{k}$ possibilities, the array at $A_{2}$ has $2^{k}-1$ possibilities, $\cdots \cdots \cdots$ the array at $A_{n}$ has $2^{k}-1$ possibilities. Thus, there are $2^{k}\left(2^{k}-1\right)^{n-1}$ methods in total.
Consider the number of methods $T$ where
$\left(p_{1}, p_{2}, \cdots, p_{k}\right)$ and $\left(q_{1}, q_{2}, \cdots, q_{k}\right)$ have no common components.
Assume $\left(p_{1}, p_{2}, \cdots, p_{k}\right)=(0,0, \cdots, 0)$. Then $\left(q_{1}, q_{2}, \cdots, q_{k}\right)=(1,1, \cdots, 1)$.
By the coloring rule, the array at $A_{2}$ is not $(1,1, \cdots, 1)$.
Let the largest index among $A_{2}, A_{3}, \cdots, A_{n-1}$ that is not $(1,1, \cdots, 1)$ be $A_{j}(2 \leqslant j \leqslant n-1)$, i.e., the array at $A_{j}$ is not $(1,1, \cdots, 1)$, but the arrays at $A_{j+1}, A_{j+2}$ are all $(1,1, \cdots, 1)$.
Connect $A_{1} A_{j}$.
Consider the labeling of the vertices of the polygon $A_{1} A_{2} \cdots A_{j}$. Then there are $a_{i}$ valid labeling methods. But according to the above rule, the array at $A_{j}$ is not $(0,0, \cdots, 0)$, otherwise, the array at $A_{j+1}$ is $(1,1, \cdots, 1), A_{j}$ and $A_{j+1}$ have no common components, which is a contradiction.

Thus, the labeling of the vertices of the polygon $A_{1} A_{2} \cdots A_{j}$ does not include the case where the array at $A_{j}$ is $(0,0, \cdots, 0)$.

When the array at $A_{j}$ is $(0,0, \cdots, 0)$, the arrays at $A_{1}$ and $A_{j}$ are identical, merge $A_{1}$ and $A_{j}$ into one point, and the number of valid labeling methods for the $(j-1)$-sided polygon is $a_{j-1}$.
Therefore, the number of valid labeling methods for the vertices of the polygon $A_{1} A_{2} \cdots A_{j}$ is $a_{j}-a_{j-1}$.
Notice that, $j=2,3, \cdots, n$. Thus,
$$
\begin{array}{l} 
T=\sum_{j=2}^{n-1}\left(a_{j}-a_{j-1}\right)=a_{n-1}-a_{1}=a_{n-1}-2^{k} . \\
\text { Hence } a_{n}=2^{k}\left(2^{k}-1\right)^{n-1}-T \\
=2^{k}\left(2^{k}-1\right)^{n-1}-a_{n-1}+2^{k} . \\
\text { Let } t=2^{k} \text {. Then } \\
a_{n}=t(t-1)^{n-1}-a_{n-1}+t \\
\Rightarrow a_{n}+a_{n-1}=t(t-1)^{n-1}+t \\
\Rightarrow a_{n}=(-1)^{n-1} a_{1}+\sum_{t=0}^{n-2}(-1)^{k}\left(a_{n-k}+a_{n-k-1}\right) \\
=t \sum_{k=0}^{n-2}(-1)^{k}(t-1)^{n-k-1}+\frac{1+(-1)^{n-1}}{2} t \\
=\left(2^{k}-1\right)^{n}+2^{k-1}+(-1)^{n}\left(2^{k-1}-1\right) .
\end{array}
$$
$$
\text { In particular, when } k=2 \text {, we have } a_{n}=3^{n}+2+(-1)^{n} \text {. }
$$