Solution: 2019 Winter Final - 8

Author: Michiel Smid

Question

A bitstring is called 00-free, if it does not contain two 0's next to each other. In class, we have seen that for any $m \geq 1$, the number of 00-free bitstrings of length $m$ is equal to the $(m + 2)$-th Fibonacci number $f_{m+2}$.
What is the number of 00-free bitstrings of length 20 that have 1 at position 11 and 0 at position 20? (The positions are numbered $1,2,...,20$.)

(a)

$f_8 \cdot f_{11}$

(b)

$f_7 \cdot f_{10}$

(c)

$f_9 \cdot f_{12}$

(d)

$f_{10} \cdot f_{12}$

Solution

Setup

So we have something that looks like XXXXXXXXXX1XXXXXXXX0

We can deduce that position 19 must be a 1, since we can’t have two 0’s next to each other, so it’d look like

XXXXXXXXXX1XXXXXXX10
Possible first 10 bits

Let’s determine the number of 00-free bitstrings of length 9 that make up the first section

m=10

$f_{10+2} = f_{12}$
Possible bitstrings from bit 12 to 18

Let’s determine the number of 00-free bitstrings of length 8 that make up the second section

m=7

$f_{7+2} = f_{9}$
Profit

$f_{12} \cdot f_{9}$