Maths Olympiad Prep

Library / /16 of 20

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it China

The code setting of a cipher lock is established on an nn-regular-polygon with vertices A1,A2,,AnA_1, A_2, \dots, A_n: each vertex is assigned a number (0 or 1) and a color (red or blue), such that either the numbers or the colors on each pair of adjacent vertices are the same. We ask: How many code-sets can be realized for this lock?

Solution

Given an arbitrary code-set for the lock, if two adjacent vertices have different numbers, we label the sides linking them by letter aa; if they have different colors, we label it by bb; if both the numbers and colors are the same, we label it by cc. Once the number and color on vertex A1A_1 are set (there are four different sets for it), we can then set A2,A3,,AnA_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 A1A_1 finally, the numbers of sides labelled aa and bb 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 aa and bb are both even.

Suppose there are 2i2i (0in20 \le i \le \lfloor \frac{n}{2} \rfloor) sides labelled by aa, and 2j2j (0jn2i20 \le j \le \lfloor \frac{n-2i}{2} \rfloor) sides labelled by bb. Then there are Cn2iC_n^{2i} ways to label 2i2i sides by aa from nn ones, Cn2i2jC_{n-2i}^{2j} ways to label 2j2j sides by bb from n2in-2i ones, and the remaining sides are labelled by cc. Therefore, by the Multiplication Principle, there are Cn2iCn2i2jC_n^{2i} C_{n-2i}^{2j} ways to label all the sides. So there are totally
4i=0n2(Cn2ij=0n2i2Cn2i2j) 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 C00=1C_0^0 = 1.

When nn is odd, we have n2i>0n - 2i > 0, and then
j=0n2i2Cn2i2j=2n2i1. \sum_{j=0}^{\left\lfloor \frac{n-2i}{2} \right\rfloor} C_{n-2i}^{2j} = 2^{n-2i-1}.
Substituting it into the previous formula, we get
4i=0n2(Cn2ij=0n2i2Cn2i2j)=4i=0n2(Cn2i2n2i1)=2i=0n2(Cn2i2n2i)=k=0nCnk2nk+k=0nCnk2nk(1)k=(2+1)n+(21)n=3n+1. \begin{aligned} 4 \sum_{i=0}^{\left\lfloor \frac{n}{2} \right\rfloor} \left( C_n^{2i} \sum_{j=0}^{\left\lfloor \frac{n-2i}{2} \right\rfloor} C_{n-2i}^{2j} \right) &= 4 \sum_{i=0}^{\left\lfloor \frac{n}{2} \right\rfloor} (C_n^{2i} 2^{n-2i-1}) \\ &= 2 \sum_{i=0}^{\left\lfloor \frac{n}{2} \right\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{aligned}

When nn is even, if i<n2i < \frac{n}{2}, then the above remains true; if i=n2i = \frac{n}{2}, then all the sides of the polygon are labelled by aa, and that means there is only one way to label the sides. Therefore, there are totally
4i=0n2(Cn2ij=0n2i2Cn2i2j)=4×(1+i=0n2(Cn2i2n2i1))=2+4i=0n2(Cn2i2n2i1)=3n+3 \begin{aligned} 4 \sum_{i=0}^{\left\lfloor \frac{n}{2} \right\rfloor} \left( C_n^{2i} \sum_{j=0}^{\left\lfloor \frac{n-2i}{2} \right\rfloor} C_{n-2i}^{2j} \right) &= 4 \times \left( 1 + \sum_{i=0}^{\left\lfloor \frac{n}{2} \right\rfloor} (C_n^{2i} 2^{n-2i-1}) \right) \\ &= 2 + 4 \sum_{i=0}^{\left\lfloor \frac{n}{2} \right\rfloor} (C_n^{2i} 2^{n-2i-1}) \\ &= 3^n + 3 \end{aligned}
code-sets for the lock.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.