2. Gari took a 6 -item multiple choice test with 3 choices per item, labelled $A, B$, and $C$. After the test, he tried to recall his answers to the items. He only remembered that he never answered three consecutive A's, he never answered three consecutive $B$ 's, and he did not leave any item blank. How many possible sets of answers could Gari have had?
Answer: 569
Solution: The problem is equivalent to that of finding the number of ternary strings of length 6 that do not contain any 3 consecutive 0 's or 3 consecutive 1's. Using the principle of inclusion and exclusion, it suffices to count the number of ternary strings of length 6 that contain at least 3 consecutive 0 's, multiply the number by 2 (by symmetry), and then subtract the number of ternary strings of length 6 that contain at least 3 consecutive 0 s and 3 consecutive 1s.

Note that there are 60 such strings with exactly 3 consecutive 0 s, 16 with exactly 4 consecutive 0 's, 4 with exactly 5 consecutive 0 's, and 1 with exactly 60 's. This gives a total of $60+16+4+1=81$ strings of length 6 that contain at least 3 consecutive 0 's.
The total number of ternary strings of length 6 is $3^{6}$ while the number of ternary strings of length 6 that contain both 3 consecutive 0 s and 3 consecutive $1 \mathrm{~s}$ is 2 . Thus, the number of strings that satisfy the problem are $3^{6}-(2)(81)+2=569$.