China Mathematical Competition (Complementary Test)

Given an arbitrary code-set for the lock, if two adjacent vertices have different numbers, we label the sides linking them by letter $a$; if they have different colors, we label it by $b$; if both the numbers and colors are the same, we label it by $c$. Once the number and color on vertex $A_1$ are set (there are four different sets for it), we can then set $A_2,A_3,\dots ,A_n$ one by one according to the letters labelled on each side. In order to let it return to the initial set of $A_1$ finally, the numbers of sides labelled $a$ and $b$ must be both even. So the number of code-sets for the lock is four times the number of labelled-side sequences which satisfy the condition that the numbers of sides labelled by $a$ and $b$ are both even.

Suppose there are $2i$ ($0\le i\le \lfloor \frac{n}{2}\rfloor$) sides labelled by $a$, and $2j$ ($0\le j\le \lfloor \frac{n-2i}{2}\rfloor$) sides labelled by $b$. Then there are $C_n^{2i}$ ways to label $2i$ sides by $a$ from $n$ ones, $C_{n-2i}^{2j}$ ways to label $2j$ sides by $b$ from $n-2i$ ones, and the remaining sides are labelled by $c$. Therefore, by the Multiplication Principle, there are $C_n^{2i}{C}_{n-2i}^{2j}$ ways to label all the sides. So there are totally $$4\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }\left(C_n^{2i}\sum _{j=0}^{\lfloor \frac{n-2i}{2}\rfloor }{C}_{n-2i}^{2j}\right)$$ code-sets for the lock. Here we stipulate $C_0^0=1$.

When $n$ is odd, we have $n-2i>0$, and then $$\sum _{j=0}^{\lfloor \frac{n-2i}{2}\rfloor }{C}_{n-2i}^{2j}=2^{n-2i-1}.$$ Substituting it into the previous formula, we get $$\begin{array}{rl}4\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }\left(C_n^{2i}\sum _{j=0}^{\lfloor \frac{n-2i}{2}\rfloor }{C}_{n-2i}^{2j}\right)& =4\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }(C_n^{2i}{2}^{n-2i-1})\\ & =2\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }(C_n^{2i}{2}^{n-2i})\\ & =\sum _{k=0}^n{C}_n^k{2}^{n-k}+\sum _{k=0}^n{C}_n^k{2}^{n-k}(-1{)}^k\\ & =(2+1{)}^n+(2-1{)}^n\\ & =3^n+1.\end{array}$$

When $n$ is even, if $i<\frac{n}{2}$, then the above remains true; if $i=\frac{n}{2}$, then all the sides of the polygon are labelled by $a$, and that means there is only one way to label the sides. Therefore, there are totally $$\begin{array}{rl}4\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }\left(C_n^{2i}\sum _{j=0}^{\lfloor \frac{n-2i}{2}\rfloor }{C}_{n-2i}^{2j}\right)& =4\times \left(1+\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }(C_n^{2i}{2}^{n-2i-1})\right)\\ & =2+4\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }(C_n^{2i}{2}^{n-2i-1})\\ & =3^n+3\end{array}$$ code-sets for the lock.

In summary, the number of code-sets for the lock is $$\{\begin{array}{ll}{3}^n+1& \text{when }n\text{ is odd,}\\ 3^n+3& \text{when }n\text{ is even.}\end{array}$$