Cocktail bar problem Recently I went out with friends and we asked ourselves the following question: Consider $n$ people sitting at a cocktail bar next to each other. How many rearrangements have to be made to ensure that every possible pair has sat at least once next to each other?
More precisely:
For given $n>1$, find a subset $A$ of $S_n$ with minimum cardinality such that for each $1\leq i<j\leq n$ there is a $\pi\in A$ such that $|\pi(i)-\pi(j)|=1$.

Basically, you are given a complete graph, and you need to pick the minimum number of hamiltonian paths (or cycles, if the table is circular) which cover all the edges.
When there are an even number of people, it is a well known theorem that $K_{2n}$ can be decomposed into $n$ edge disjoint hamiltonian paths. (See Modern Graph Theory, page 16, for instance, or see a previous answer which has a snapshot of the book inlined).
When $n$ is odd, you can do even better, and make $\frac{n-1}{2}$ cycles!
So, if you want paths, for $2k$ answer is $k$ and $2k+1$ answer is $k+1$.
If you want cycles, the values are switched.
I believe those are optimal.
