Arranging $n$ different numbers on a circle such that difference of two adjacent ones is at most two 
In how many ways can the numbers $1, \ldots, n$ be arranged in a circle so that adjacent numbers always differ by $1$ or $2$?

There are just two possibilities for every $n$, right?
 A: Fix the location of $1$.  Then its neighbors must be $2,3$ in one order of the other.  Fix that order.  Then I claim that the rest of the numbers are locked in.  It is easy to see that that the string that starts $1,2$ must continue with $4$ while the string that starts $1,3$ must continue with $5$.  Let's show that this pattern continues.  We remark that the obvious extension of this works...that is $1,2,4,6,\cdots$ in one direction, $1,3,5,7,\cdots$ in the other, meeting at $n,n-1$ is one order or the other.  We must show that these are the only two cases.
Indeed, the numbers must go by $2's$ from the start...the two clockwise and counterclockwise strings meet at $n,n-1$ in one order or the other.  We can see this inductively.  Suppose we have shown it up to $k-1<n$.  Then the strings are $1,2,4,\cdots$ and $1,3,5,\cdots$. Depending on the parity of $k$ one of these ends in $k-2$ and the other ends in $k-1$.  What can go in the free spot next to $k-2$?  Well, the numbers less than or equal to $k-1$ are already in place, so it has to be $k$, and we are done.
A: One solution is obtained by taking first the odd numbers between $1$ and $n$ in increasing order, and then the even numbers between $1$ and $n$ in decreasing order. For instance, for $n=9$, this gives $1,3,5,7,9,8,6,4,2$. 
Then one can show that this is the only solution, up to the symmetries of the $n$-gon, i.e. the group of symmetries generated by the cyclic permutation (in the example, applying it gives $3,5,7,9,8,6,4,2,1$) and the reflection (on the example, it gives $2,4,8,9,7,5,3,1$). 
The proof goes as follows. Using rotations, I can put $1$ in the first position. Because of the rules, its neighbours are $2$ and $3$. Using the reflection freedom, I can put $3$ on the right of $1$. Then the only possible neighbour of $2$ that remains is $4$. And the only possible neighbour of $3$ is $5$. One proceeds by induction to show the unicity of the solution. 
