SK 2016 Q20
20. A barcode of the type shown in the two examples is composed of alternate strips of black and white, where the leftmost and rightmost strips are always black. Each strip (of either colour) has a width of 1 or 2. The total width of the barcode is 12. The barcodes are always read from left to right. How many distinct barcodes are possible?

Senior Kangaroo 2016, Question 20. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: 116
Any code will start with a black strip and a white strip followed by a shorter barcode. Let \(C(m)\) be the number of distinct barcodes of width \(m\).
Those codes which start with BW will be followed by a code of width \(m - 2\); so there will be \(C(m - 2)\) of these. Likewise, there will be \(C(m - 3)\) codes starting BBW, the same number starting BWW, and \(C(m - 4)\) starting BBWW; and that exhausts the possibilites. So it follows that \(C(m) = C(m - 2) + 2C(m - 3) + C(m - 4)\).
When \(m \leqslant 4\), it is simple to list all possible barcodes; namely B, BB, BWB and BBWB, BWBB, BWWB. Therefore \(C(1) = C(2) = C(3) = 1\) and \(C(4) = 3\). We can now calculate \(C(m)\) for \(m > 4\).
Thus \(C(5) = C(3) + 2C(2) + C(1) = 1 + 2 + 1 = 4\), and continuing like this, we get \(C(6) = 6\), \(C(7) = 11\), \(C(8) = 17\), \(C(9) = 27\), \(C(10) = 45\), \(C(11) = 72\), \(C(12) = 116\).
Solution © UK Mathematics Trust, from the SK 2016 solutions.