The code setting of a cipher lock is established on an n-regular-polygon with vertices A1,A2,…,An: 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 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 A1 are set (there are four different sets for it), we can then set A2,A3,…,An one by one according to the letters labelled on each side. In order to let it return to the initial set of A1 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≤i≤⌊2n⌋) sides labelled by a, and 2j (0≤j≤⌊2n−2i⌋) sides labelled by b. Then there are Cn2i ways to label 2i sides by a from n ones, Cn−2i2j 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 Cn2iCn−2i2j ways to label all the sides. So there are totally 4i=0∑⌊2n⌋Cn2ij=0∑⌊2n−2i⌋Cn−2i2j code-sets for the lock. Here we stipulate C00=1.
When n is odd, we have n−2i>0, and then j=0∑⌊2n−2i⌋Cn−2i2j=2n−2i−1. Substituting it into the previous formula, we get 4i=0∑⌊2n⌋Cn2ij=0∑⌊2n−2i⌋Cn−2i2j=4i=0∑⌊2n⌋(Cn2i2n−2i−1)=2i=0∑⌊2n⌋(Cn2i2n−2i)=k=0∑nCnk2n−k+k=0∑nCnk2n−k(−1)k=(2+1)n+(2−1)n=3n+1.
When n is even, if i<2n, then the above remains true; if i=2n, 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 4i=0∑⌊2n⌋Cn2ij=0∑⌊2n−2i⌋Cn−2i2j=4×1+i=0∑⌊2n⌋(Cn2i2n−2i−1)=2+4i=0∑⌊2n⌋(Cn2i2n−2i−1)=3n+3 code-sets for the lock.
In summary, the number of code-sets for the lock is {3n+13n+3when n is odd,when n is even.
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.