Solution: 2018 Winter Midterm - 2

Author: Michiel Smid

Question

Consider strings consisting of 12 characters, where each character is an element of the set $\{a,b,c,d,e\}$. The positions in such strings are numbered as $1,2,3,\dots,12$.
How many such strings have the property that

each even position contains an element of $\{a, b, c\}$, or
each odd position contains an element of $\{d,e\}$?

(a)

$3^{6} \cdot 5^{6} + 2^{6} \cdot 5^{6}$

(b)

$6^{3} \cdot 6^{5} + 6^{2} \cdot 6^{5}$

(c)

$6^{3} \cdot 6^{5} + 6^{2} \cdot 6^{5} - 6^{2} \cdot 6^{3}$

(d)

$3^{6} \cdot 5^{6} + 2^{5} \cdot 5^{6} - 2^{6} \cdot 3^{6}$

Solution

Let’s break this down into 2 cases:

A = Each even position has 3 choices: $ a, b, c $

There are 6 even positions, so there are $ 3^6 $ ways to choose the characters for the even positions.

The other 6 odd positions can be any of the 5 characters: $ a, b, c, d, e $

$ |A| = 3^6 \cdot 5^6 $

B = Each odd position has 2 choices: $ d, e $

There are 6 odd positions, so there are $ 2^6 $ ways to choose the characters for the odd positions.

The other 6 even positions can be any of the 5 characters: $ a, b, c, d, e $

$ |B| = 2^6 \cdot 5^6 $

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

$ |A \cup B| = 3^6 \cdot 5^6 + 2^6 \cdot 5^6 - 3^6 \cdot 2^6 $