Question

Define a good word as a sequence of letters that consists only of the letters $A,$ $B,$ and $C$ — some of these letters may not appear in the sequence — and in which $A$ is never immediately followed by $B,$ $B$ is never immediately followed by $C,$ and $C$ is never immediately followed by $A.$ How many seven-letter good words are there?

Answer

Solution:

Each letter rules out exactly one successor ( $A$ forbids $B,$ $B$ forbids $C,$ $C$ forbids $A$ ), so whatever letter has just been written, exactly $2$ of the $3$ letters may come next.

With $3$ choices for the first letter and $2$ for each of the remaining six positions, the number of seven-letter good words is $3 \cdot 2^6 = 192.$

2003 AIME II Problem 3

Solution:

Problem 3 in Other Years