4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$.

$\endgroup$
  • 1
    $\begingroup$ Nice answer. Fibonacci and induction is something the student has a handle on. I'll run it by her. $\endgroup$ – dave Sep 29 '15 at 21:23
2
$\begingroup$

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!}$$

$\endgroup$
  • $\begingroup$ That's sort of what we were trying, but how do you get the number of combinations in the non-trivial cases. For example, the "2 pairs of white tiles" (allowing for adjacency and so on) noting the restrictions on math knowledge. $\endgroup$ – dave Sep 29 '15 at 5:26
  • $\begingroup$ Give me a sec. I'll edit. $\endgroup$ – Gummy bears Sep 29 '15 at 5:29
  • $\begingroup$ There, that should help. This is a slightly lengthy method, but it's the only thing that came to mind. I'm surprised that this is a question being asked to a 12 year old...... $\endgroup$ – Gummy bears Sep 29 '15 at 5:34
  • $\begingroup$ Me too! It is the advanced / extension stream, but I don't think they've done factorials (and combinations) yet. I could solve it that way, but not another way. $\endgroup$ – dave Sep 29 '15 at 6:15
  • $\begingroup$ BTW, do you have a typo in your answer? 18!/16!2! is 153 not 113? $\endgroup$ – dave Sep 29 '15 at 6:15

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.