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?

enter image description here

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.

  1. 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?

  2. 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?

  • 1
    $\begingroup$ Does this help? $\endgroup$ – koder613 Nov 12 '20 at 20:54

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.

  • $\begingroup$ Oh, oops, I didn't notice, the width-1-or-2-only assumption was explicit in the OP. $\endgroup$ – Barry Cipra Nov 12 '20 at 19:40
  • $\begingroup$ Thanks. I'm not quite clear how you've answered my questions, particularly question 2. Would you mind elaborating or stating how each one is answered explicitly? $\endgroup$ – A-Level Student Nov 12 '20 at 19:55
  • $\begingroup$ @A-LevelStudent, the idea is that what comes next starts with a new $B$. So "$BW$" is shorthand for a black bar of width 1 followed by a white bar of width 1, whereas "$BWW$" is shorthand for a black bar of width 1 followed by a white bar of width 2. So $BWW$ is distinctly different from $BW$, not included as part of it. $\endgroup$ – Barry Cipra Nov 12 '20 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.