Solution: 2017 Fall Midterm - 6

Author: Michiel Smid

Question

Let $n \geq 7$ 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 $abc$ or end with $dddd$?

(a)

$2 \cdot 4^{n-3} - 4^{n-7}$

(b)

$4^{n-3} + 4^{n-4} - 4^{n-7}$

(c)

$2 \cdot 4^{n-4} - 4^{n-7}$

(d)

$4^{n-3} + 4^{n-4}$

Solution

A = strings that start with $ abc $.

A = first 3 bits are set in stone while other $ n-3 $ bits can be a, b, c, or d.

$ |A| = 1 \cdot 4^{n-3} $

B = strings that end with $ dddd $.

B = last 4 bits are set in stone while the final bit can be a, b, c, or d.

$ |B| = 1 \cdot 4^{n-4} $

$ A \cap B $ = strings that start with $ abc $ and end with $ dddd $.

Assuming the string starts with $ abc $ and ends with $ dddd $, there are $ n-7 $ bits left that can be a, b, c, or d.

$ |A \cap B| = 1 \cdot 4^{n-7} $

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

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

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