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$.

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$.
