Solution: 2015 Fall Midterm - 5

Author: Michiel Smid

Question

Consider strings of length 99 consisting of the characters $a$, $b$, and $c$. How many such strings are there that start with $abc$ or end with $bbb$?

(a)

$3^{99} - 2 \cdot 3^{96}$

(b)

$2 \cdot 3^{96} - 3^{93}$

(c)

$3^{96} + 3^{96}$

(d)

None of the above.

Solution

Let A be the set of all bitstrings that start with abc.
The first 3 letters are set in stone: 1 possibility
The remaining 96 letters can be anything: $3^{96}$ possibilities
$|A| = 1 \cdot 3^{96}$
Let B be the set of all bitstrings that end with bbb.
The last 3 letters are set in stone: 1 possibility
The remaining 96 letters can be anything: $3^{96}$ possibilities
$|B| = 3^{96} \cdot 1$
Let $A \cap B$ be the set of all bitstrings that start with abc and end with bbb.
The first 3 letters and last 3 letters are set in stone: 1 possibility
The remaining 93 letters can be anything: $3^{93}$ possibilities
$|A \cap B| = 1 \cdot 3^{93}$

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

$|A \cup B| = 1 \cdot 3^{96} + 3^{96} \cdot 1 - 1 \cdot 3^{93}$

$|A \cup B| = 3^{96} + 3^{96} - 3^{93}$

$|A \cup B| = 2 \cdot 3^{96} - 3^{93}$