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.