I was doing a past paper for a competition and I came across this question:
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?
This is the solution given:
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\le4$, it is simple to list all possible barcodes; namely $B$, $BB$, $BWB$ and $BBWB$, $BWBB$, $BWWB$. Therefore $$C (1) = C (2) = C (3) = 1 ,~~C (4) = 3$$ We can now calculate 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$$
There's a couple of points I don't understand.
Won't the value of $C(m-3)$ be different for different starting points? More specifically, if the starting points are $BBW$ or $BWW$ why won't the value of $C(m-3)$ be different? Surely if it starts with $BWW$ then there's only one choice for the colour of the next strip?
Aren't the number of barcodes starting with $BWW$ included in those starting with $BW$? If so, haven't they been counted twice in the solution?
There are certain unstated assumptions lurking here. One is that each strip, be it black or white, is of "width" $1$ or $2$ only; that is, $BB$ and $WW$ are allowed, but not $BBB$ or $WWW$. Another is that the bar code both starts and stops with a black strip. The latter assumption explains why we have $C(1)=C(2)=1$ and the two assumptions together explain why we have $C(3)=1$ and $C(4)=3$. Finally, the no-width-$3$ assumption explains the recursion: The first pair of strips in a barcode of length greater than $4$ are either $BW$, $BBW$, $BWW$, or $BBWW$, followed by a bar code (starting with a new $B$) of the appropriate shorter length.