Six chairs are evenly spaced around a circular table. One person is seated in each chair. Each person gets up and sits down in a chair that is not the same and is not adjacent to the chair he or she originally occupied, so that again one person is seated in each chair. In how many ways can this be done?
$\textbf{(A)}\; 14 \qquad\textbf{(B)}\; 16 \qquad\textbf{(C)}\; 18 \qquad\textbf{(D)}\; 20 \qquad\textbf{(E)}\; 24$
Consider shifting every person over three seats left after each person has gotten up and sat back down again. Now, instead of each person being seated not in the same chair and not in an adjacent chair, each person will be seated either in the same chair or an adjacent chair. The problem now becomes the number of ways in which six people can sit down in a chair that is either the same chair or an adjacent chair in a circle.
Consider the similar problem of $n$ people sitting in a chair that is either the same chair or an adjacent chair in a row. Call the number of possibilities for this $F_n$. Then if the leftmost person stays put, the problem is reduced to a row of $n-1$ chairs, and if the leftmost person shifts one seat to the right, the new person sitting in the leftmost seat must be the person originally second from the left, reducing the problem to a row of $n-2$ chairs. Thus, $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$. Clearly $F_1 = 1$ and $F_2 = 2$, so $F_3 = 3$, $F_4 = 5$, and $F_5 = 8$.
Now consider the six people in a circle and focus on one person. If that person stays put, the problem is reduced to a row of five chairs, for which there are $F_5 = 8$ possibilities. If that person moves one seat to the left, then the person who replaces him in his original seat will either be the person originally to the right of him, which will force everyone to simply shift over one seat to the left, or the person originally to the left of him, which reduces the problem to a row of four chairs, for which there are $F_4 = 5$ possibilities, giving $1 + 5 = 6$ possibilities in all. By symmetry, if that person moves one seat to the right, there are another $6$ possibilities, so we have a total of $8+6+6 = \boxed{\textbf{(D)}\; 20}$ possibilities.