Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  hardmath Mar 29 '13 at 0:29
    
@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. –  zero-divisor Mar 29 '13 at 0:42

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
I don't see how those bounds can be improved, since the hamiltonian paths are disjoint. Isn't it exactly the minimum? –  Vincent Tjeng Mar 29 '13 at 2:15
    
@VincentTjeng: Yes, exactly :) –  Aryabhata Mar 29 '13 at 2:17
    
+1 for a very clear answer! –  Vincent Tjeng Mar 29 '13 at 2:19
    
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? –  zero-divisor Mar 29 '13 at 8:28
    
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. –  zero-divisor Mar 29 '13 at 13:28

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

share|improve this answer
    
very nice approach, thanks! –  zero-divisor Mar 29 '13 at 9:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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