Solution: 2019 Fall Final - 8

Author: Michiel Smid

Question

A string that is obtained by rearranging the letters of the word BOOGER is called awesome, if the string does not contain the substring OO. Thus, GEOROB is awesome, whereas GREOOB is not awesome. What is the number of awesome strings?

(a)

$6 \cdot {5 \choose 2} \cdot 3 \cdot 2$

(b)

$(6 \cdot {5 \choose 2} \cdot 3 \cdot 2) - 5!$

(c)

$6! - 5!$

(d)

$(6 \cdot {5 \choose 2} \cdot 3) - 5!$

Solution

I guess we can just think, “total possibilities minus possibilities where both O’s are together”

Let S be the set of all possibilities
We choose 1 position out of the 5 positions for the B: 5
We choose 2 position out of the 4 remaining positions for the O: $ \binom{4}{2} $
We choose 1 position out of the 3 remaining positions for the G: 3
We choose 1 position out of the 2 remaining positions for the E: 2
We choose 1 position out of the 1 remaining positions for the R: 1
$ |S| = 5 \cdot \binom{4}{2} \cdot 3 \cdot 2 $
Let A be the set of all possibilities where both O's are together
Let's treat the two O's as one letter
We have 5 letters: $ G, E, R, B, O $
We choose 1 position out of the 5 positions for the O's: 5
We choose 1 position out of the 4 remaining positions for the G: 4
We choose 1 position out of the 3 remaining positions for the E: 3
We choose 1 position out of the 2 remaining positions for the R: 2
We choose 1 position out of the 1 remaining positions for the B: 1
$ |A| = 5! $

Now, let's math $ |S| - |A|$ $ = 5 \cdot \binom{4}{2} \cdot 3 \cdot 2 - 5! $