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

  • $\begingroup$ Counting only the number of permutations $A$ required to "cover" all the possible pairs with adjacent seats seems to make an easier problem than asking to minimize the number of swaps (transpositions) needed to accomplish the purpose. $\endgroup$
    – hardmath
    Mar 29, 2013 at 0:29
  • $\begingroup$ @hardmath: I'm not looking for the number of swaps that have to be made, I'm only interested in $A$ or its cardinality. I reformulated the question in order to make it more clear what I mean. $\endgroup$ Mar 29, 2013 at 0:42

2 Answers 2


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.

  • $\begingroup$ I don't see how those bounds can be improved, since the hamiltonian paths are disjoint. Isn't it exactly the minimum? $\endgroup$ Mar 29, 2013 at 2:15
  • $\begingroup$ @VincentTjeng: Yes, exactly :) $\endgroup$
    – Aryabhata
    Mar 29, 2013 at 2:17
  • $\begingroup$ I understand the proof for the case of $n$ being even, and it is indeed the minimum as $|A|\geq \frac{n}{2}$ which Greg Martin pointed out in his answer. But in case of $n$ being odd, we need at least $\frac{n+1}{2}$ paths, and I don't see how to construct them from the $\frac{n-1}{2}$ cycles. Am I missing something trivial? $\endgroup$ Mar 29, 2013 at 8:28
  • $\begingroup$ Ok the construction described in the book works as well for the case of $n$ being odd, for which it yields $\frac{n+1}{2}$ paths where the $\frac{n-1}{2}$ pairs $\{1,n\},\{2,n-1\},\dots$ are covered exactly twice, all others being covered exactly once. $\endgroup$ Mar 29, 2013 at 13:28
  • $\begingroup$ @zero-divisor: For odd $n$, $\frac{n-1}{2}$ paths are not sufficient (cannot cover all edges, even if all disjoint). You can now add the bartender to the list of people, and apply the even $n$ case to get $\frac{n+1}{2}$. $\endgroup$
    – Aryabhata
    Mar 29, 2013 at 15:19

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

  • $\begingroup$ very nice approach, thanks! $\endgroup$ Mar 29, 2013 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.