Calculating number of tile sequences

Question

My daughter (aged 12) came to me with the problem below. I was able to help her to some extent but I could not see an age-appropriate solution. That is, I could imagine solutions involving factorials / combinations or writing a computer program. However she is in Year 7 at school and I could not see how to solve it with that level of knowledge. We settled on a brute-force solution but did not complete it as it would take too long. So can anyone solve this with a simple, logical algorithm using knowledge / techniques that a student just starting high school would be familiar with?

Say you have a set of black (B) and white (W) tiles - identical apart from colour. You arrange the tiles in various sequences, eg. B, BW, WWBW, etc. A sequence is considered to be significant if all of its sub-sequences of white tiles are even in length. Thus the following are significant: WW, BBB, WWWWBB; while the following are not: W, BWWW, BWWBBBW. Note: a sequence of length zero would appear to be deemed even.

There were a few simple questions we could solve, eg. how many significant sequences of length 1, 2, 3 and 4 are there. Enumerate them.

But the question that stumped us was: how many significant sequences of length 20 are there. We could not extrapolate easily from the earlier questions.

PS: I wasn't sure what tags to use. Please update as you see fit.

Answer 1

Let $a_n$ be the number of significant sequences of length $n$. If you count carefully, you’ll find that $a_1=1$, $a_2=2$, $a_3=3$, $a_4=5$, $a_5=8$, and $a_6=13$. You (or she) might recognize these as the Fibonacci numbers, and even if you don’t, you might notice that each is the sum of the previous two. If you extrapolate on this basis, you can guess (after a bit of arithmetic) that $a_{20}=10946$.

Of course you might wonder whether the extrapolation is legitimate. To see that it is, suppose that $\sigma$ is a significant sequence of length $n$, where $n\ge 3$. If $\sigma$ ends in B, the first $n-1$ letters of $\sigma$ are a significant sequence of length $n-1$. Conversely, if you start with any significant sequence of length $n-1$, adding a B to the end gives you a significant sequence of length $n$. Thus, there are $a_{n-1}$ significant sequences of length $n$ that end in B.

If, on the other hand, $\sigma$ ends in W, then it must actually end in WW, and the first $n-2$ letters of $\sigma$ must be a significant sequence of length $n-2$. Conversely, if you start with a significant sequence of length $n-2$ and add WW to the end, you get a significant sequence of length $n$. Thus, there are $a_{n-2}$ significant sequences of length $n$ that end in W.

Putting the two together, we see that $a_n=a_{n-1}+a_{n-2}$.

Answer 2

I'm pretty sure there's a better way to answer this than mine, but I'l post mine anyways.

Group the white tiles into pairs of 2 - this is done as we only want even sequences of the white tiles. Now, for arranging 20 tiles, we have the following ways to chose the tiles:

• 0 white tiles and 20 black tiles
• 1 pair of white tiles and 18 black tiles
• 2 pair of white tiles and 16 black tiles ........ so on until:
• 10 pair of white tiles and 0 black tiles

Consider the first case, when there are no white tiles. There's only one possible combination. In the second case, where there's 1 pair of white tiles, we have 19 possible combinations. When we have 2 pairs of white tiles, we have 153 possible combinations... and so on.

Adding all of them will give us our answer.

EDIT:

If we have $x$ items, out of which $m$ are of one kind and $n$ are of another kind, then the total number of ways to arrange them is: $$\frac{x!}{m!n!}$$ In our case, we have two types of objects, pairs of white tiles (which are considered as 1 object) and black tiles.

So, in the third case (two pairs of white tiles), we have a total of 18 objects - 16 black tiles and 2 pairs of white tiles. So, the total way or arranging them is: $$\frac{18!}{16!2!}$$