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$.
 A: Not a complete answer, but: when $n+1$ is prime, the answer is $n/2$.
Notice that $n/2$ is a lower bound for any $n$: each element of $A$ "checks off" at most $n-1$ new pairs, and there are $\binom n2 = n(n-1)/2$ pairs that need to be checked off in total.
To construct $n/2$ configurations that accomplish this when $n+1$ is prime: number the people from $1$ to $n$, and in the $k$th configuration, have person $i$ sit in seat $ik\pmod{n+1}$. We must prove, for any $1\le i<j\le n$, that there exists $1\le k\le n/2$ such that $ik\pmod{n+1}$ and $jk\pmod{n+1}$ differ by 1, that is, $ik-jk\equiv\pm1\pmod{n+1}$. The appropriate $k$ to choose is $k\equiv\pm(i-j)^{-1}\pmod{n+1}$, with the sign chosen so that the residue lies between $1$ and $n$ rather than between $n+1$ and $2n$.
A: 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.
