Solution: 2017 Winter Midterm - 6

Author: Michiel Smid

Question

Let $n \geq 4$ be an integer and consider strings of length $n$ consisting of the characters $a$, $b$, $c$, and $d$. How many such strings are there that start with $ab$ or start with $abc$?

(a)

$4^{n-1}$

(b)

$4^{n}$

(c)

$4^{n-2}$

(d)

$4^{n-3}$

Solution

We can break this down into 2 cases:

A = strings that start with $ ab $

There is $ 1 $ way to arrange the first 2 bits and $ 4^{n-2} $ ways to choose the last $ n-2 $ bits: $ 1 \cdot 4^{n-2} $

B = strings that start with $ abc $

There is $ 1 $ way to arrange the first 3 bits and $ 4^{n-3} $ ways to choose the last $ n-3 $ bits: $ 1 \cdot 4^{n-3} $

$ A \cap B = $ strings that start with $ ab $ and start with $ abc $

There is $ 1 $ way to arrange the first 3 bits and $ 4^{n-3} $ ways to choose the last $ n-3 $ bits: $ 1 \cdot 4^{n-3} $

$ |A \cup B| = |A| + |B| - |A \cap B| $

$ |A \cup B| = 1 \cdot 4^{n-2} + 1 \cdot 4^{n-3} - 1 \cdot 4^{n-3} $

$ |A \cup B| = 4^{n-2} + 4^{n-3} - 4^{n-3} $

$ |A \cup B| = 4^{n-2} $