2003 AIME II problem 3

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? So let's just think about this a little bit. So there's letters with just A's, B's, and C's. And then it could be all A's, all B's, all C's because some letters might not appear. And A is never immediately followed by B. So A can only be followed by another A or another C. B is never immediately followed by C, which means that B could only be followed by an A or another B. And C is never immediately followed by A. So C could only be followed by another C or a B. So how many seven letter "good words" are there? So let's just think about the places. We have seven letters, so 1, 2, 3, 4, 5, 6, 7 letters. Now, there's no constraints on this first letter since it's not following anything. So it could be an A B, or a C. So there's three possibilities for this first letter. Now, there's three possibilities for this first letter. But no matter what letter this is, how many possibilities are there for this second letter over here? Well, if this was an A, the second letter could only be an A or a C because it can't be followed by a B. If this was a B, the second letter could only be a B or an A because it can't be followed by a C. If this was a C, the second letter could only be a B, or a C. So no matter what letter this first letter is, the second letter can only have two possibilities. There could only be two possibilities. Another way to think about it is, there's one letter, no matter what letter this is, there's one letter that's being ruled out here. So it could only be two possibilities. Well, the same thing is here. We're going to stick some letter here. And no matter what letter there is over here, it's going to rule out one possibility over here. So we're going to have only two possible letters that we can put here, no matter what letter is there. And use the same logic, only two possibilities there, only two possibilities there, only two possibilities there, and then only two possibilities there. So how many total possibilities do we have? Well, 3 times 2 times 2 times 2 times 2 times 2. This is 1, 2, 3, 4, 5, 6 2's. So this is equal to 3 times 2 to the sixth power, which is 3 times 2 to the six is 32 times 2 is 64, which is equal to 180 plus 12 is equal to 192. There's 192 possible good seven letter "good words," where good words is defined above.