# Problem of the Week Problem E and Solution Red Dog

## Problem

We can take any word and rearrange all the letters to get another “word”. These new “words” may be nonsensical. For example, you can rearrange the letters in $$MATH$$ to get $$MTHA$$.

Nalan wants to rearrange all the letters in $$RED DOG$$. However, she uses the following rules:

• the letters $$R$$, $$E$$, and $$D$$ cannot be adjacent to each other and in that order, and

• the letters $$D$$, $$O$$, and $$G$$ cannot be adjacent to each other and in that order.

For example, the “words” $$DOGRED$$, $$DDOGRE$$, $$GDREDO$$, and $$DREDOG$$ are examples of unacceptable words in this problem, but $$DROEGD$$ is acceptable.

How many different arrangements of the letters in $$RED DOG$$ can Nalan make if she follows these rules?

## Solution

We will find the total number of possible “words” Nalan can make, and then exclude those “words” which don’t follow the rules (i.e. those which contain $$RED$$ or $$DOG$$ (or both)).

1. Determine the total number of “words” formed using $$2$$ $$D$$s, $$1$$ $$E$$, $$1$$ $$G$$, $$1$$ $$O$$, and $$1$$ $$R$$.

First, place the $$E$$ in $$6$$ possible positions. Then, for each of the $$6$$ possible placements of the $$E$$, there are $$5$$ ways to place the $$G$$. There are then $$6\times 5=30$$ ways to place the $$E$$ and the $$G$$. Then, for each of the $$30$$ possible placements of the $$E$$ and $$G$$, there are $$4$$ ways to place the $$O$$. There are then $$30\times 4=120$$ ways to place the $$E$$, the $$G$$, and the $$O$$. Then, for each of the $$120$$ possible placements of the $$E$$, $$G$$, and $$O$$, there are $$3$$ ways to place the $$R$$. There are then $$120\times 3=360$$ ways to place the $$E$$, the $$G$$, the $$O$$, and the $$R$$.

For each of the $$360$$ ways to place the $$E$$, $$G$$, $$O$$, and $$R$$, the $$2~D$$s must go in the remaining two empty spaces in $$1$$ way. Therefore, there are $$360\times 1=360$$ ways to place the $$E$$, the $$G$$, the $$O$$, the $$R$$, and the $$2~D$$s.

Thus, there are $$360$$ possible “words” that Nalan can make.

2. Determine how many “words” contain $$RED$$.

There are $$4$$ ways to place the word $$RED$$ in the six spaces. The word $$RED$$ could start in the first, second, third, or fourth position.

For each placement of the word $$RED$$, there are $$6$$ ways to place the letters of the word $$DOG$$ in the remaining three spaces: $$DOG$$, $$DGO$$, $$GDO$$, $$GOD$$, $$ODG$$ and $$OGD$$. So there are $$4 \times 6=24$$ “words” containing $$RED$$.

3. Determine how many “words” contain $$DOG$$.

There are $$4$$ ways to place the word $$DOG$$ in the six spaces. The word $$DOG$$ could start in the first, second, third, or fourth position.

For each placement of the word $$DOG$$, there are $$6$$ ways to place the letters of the word $$RED$$ in the remaining three spaces: $$DER$$, $$DRE$$, $$EDR$$, $$ERD$$, $$RDE$$ and $$RED$$. So there are $$4 \times 6=24$$ “words” containing $$DOG$$.

4. Determine how many “words” contain both $$RED$$ and $$DOG$$.

There are $$4$$ “words” that contain both $$RED$$ and $$DOG$$. They are as follows. $REDDOG\quad\quad DOGRED \quad\quad REDOGD\quad\quad DREDOG$ These $$4$$ “words” have been double-counted, as they would have been counted in case 2 and in case 3.

Thus in total, there are $$24+24-4=44$$ “words” that contain $$RED$$ or $$DOG$$ (or both). Since there are $$360$$ possible “words” Nalan can make, we can subtract $$44$$ from this to determine the number of these “words” that do not contain $$RED$$ or $$DOG$$ (or both).

Therefore, $$360-44=316$$ “words” can be formed in which the letters $$R$$, $$E$$ and $$D$$ are not adjacent to each other and in that order and the letters $$D$$, $$O$$ and $$G$$ are not adjacent to each other and in that order.