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.

Ok hi all, my first question! I would like to organize a party where everyone meets everyone, the table is organized like this:

ABCD
J  E
IHGF

So A can only meet B and J, and B can only meet A and C and so on. So I suppose it could be seen as a lot of groups of 3s + 1 or 2. (abc) (def) (ghi)+J , but there is also the groups (bcd) (efg) (hij)+a

How should I move them around?

I will not know exact numbers before they arrive! Any help much appreciated.

Seems a bit like this question but a bigger table! How to rotate n individuals at a dinner party so that every guest meets every other guests and How to derive a general formula for this problem? (pairs of people seated around a table)

share|improve this question
    
also seems a bit like this: math.stackexchange.com/questions/58922/… –  user1392166 Dec 7 '12 at 20:21
    
You give all of them a version of the Keirsey personality test. Then you kick out all of the introverts. They'll move themselves. More seriously, my intuition tells me that you want to do something like picking an individual say A to swap positions with the person on the opposite corner like F, while B, J, E, and G stay seated. Just a guess. –  Doug Spoonwood Dec 7 '12 at 20:45
    
swapping with corners would be ok but BC would stay together, which seem a little ineffective! –  user1392166 Dec 7 '12 at 20:57
    
You'd have C also swap places. –  Doug Spoonwood Dec 7 '12 at 20:59
    
I suppose the is a finite number of possible combinations, where each member of a set of 3 is less likely to pick a set with members it's already seen, that's more dealing with it from a programming point of view than mathematical. I'd quite link to understand what I am doing? –  user1392166 Dec 7 '12 at 21:18
show 1 more comment

2 Answers 2

Partial answer:

Let's start with the simple case that the number $n$ of people is an odd prime: Assign a number $0, \ldots, n-1$ to each guest and in round $k$ let guest $i$ sit on chair $ki\bmod n$. Then guest $i$ and $j$ are neighbours when $k(i-j)\equiv \pm 1\pmod n$. If we let $k$ run from $1$ to $\frac{n-1}2$, the multiplicative inverse of $i-j$ or its negative are among the $k$ values, hence $i$ and $j$ have met. Clearly, it is not possible to get away with less than $\frac{n-1}2$ rounds.

If $n$ is not prime it may be worth considereing a few more invitations until the number is prime :)

share|improve this answer
add comment

Suppose you have $n$ people, numbered $0$ to $n-1$. We might as well suppose person $0$ stays put, and the others move around. So a "configuration" corresponds to a permutation of $1$ to $n-1$. Let $a_{i,j,c} = 1$ if $i$ and $j$ are seated next to each other in configuration $c$, $0$ if not. You can think of your problem as an integer linear programming problem:

$$\eqalign{\text{minimize } & \sum_c x_c\cr \text{subject to } & \sum_c a_{i,j,c} x_c \ge 1 \ \text{for all } 0 \le i<j \le n-1 \cr x_c \in \{0,1\}\cr}$$

The trouble is that there are a huge number of configurations ($9! = 362880$ in your example).

I tried a different approach: tabu search. In the cases I've tried it didn't take long to come up with an optimal solution. Here's my Maple program:

n:= 10;  # number of guests
m:= ceil((n-1)/2); # minimal number of rounds required
scorer:= proc(L)
# count number of introductions for an m-tuple of configurations
   nops(map(op,{seq([seq({L[i,j],L[i,j+1]},j=1..n-2),
      {0,L[i,1]},{0,L[i,n-1]}],i=1..m)})) 
end proc;
move:= proc(i,j,k,L) 
# switch j'th and k'th positions in configuration i of m-tuple L
   local M; 
   M:= L; 
   M[i,j]:= L[i,k]; M[i,k]:= L[i,j]; 
   M 
end proc;
target:= n*(n-1)/2;  # necessary number of introductions
current:= [[$1..(n-1)],seq(combinat[randperm](n-1),i=2..m)];
tabu:= [seq([2,i],i=1..7)]; # these items temporarily can't be switched
currentscore:= scorer(current); 
bestyet:= current; bestscore:= scorer(bestyet);
for iter from 1 to 1000 while bestscore < target do
   bestnewscore:= 0;
   for i from 2 to m do
      for j from 1 to n-2 do 
          if member([i,j],tabu) then next fi;
          for k from j+1 to n-1 do
              if member([i,k],tabu) then next fi;
              newtry:= move(i,j,k,current);
              newscore:= scorer(newtry);
              if newscore > bestnewscore then 
                  bestnew:= newtry; bestnewscore:= newscore; 
                  ij:= [i,j]; ik:= [i,k];
              fi
   od od od:
   if bestnewscore > bestscore then 
       bestyet:= bestnew; bestscore:= bestnewscore;
       printf("Best yet at iteration %d: %d\n",iter, bestscore);
   fi;
   current:= bestnew;
   tabu:= [op(tabu[3..7]),ij,ik];
   if iter mod 20 = 0 then
       printf("iteration %d, score %d\n",iter, bestnewscore)
   fi;
od:    
if bestnewscore = target then printf("Optimal configuration ") 
else printf("Best configuration so far ") 
fi;
printf("with score %d out of %d:\n",bestscore,target);
print(bestyet);

For example, with $n=15$ it took 312 iterations to come up with an optimal solution:

[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], 
[5, 10, 3, 11, 13, 7, 9, 6, 14, 4, 12, 1, 8, 2], 
[11, 7, 10, 1, 5, 13, 2, 4, 8, 14, 9, 12, 3, 6], 
[10, 14, 3, 7, 4, 11, 2, 6, 8, 12, 5, 9, 1, 13], 
[3, 5, 7, 2, 14, 12, 6, 10, 8, 13, 4, 1, 11, 9], 
[8, 11, 14, 5, 2, 12, 10, 13, 3, 9, 4, 6, 1, 7], 
[4, 10, 2, 9, 13, 6, 11, 5, 8, 3, 1, 14, 7, 12]]

That is, there are 7 rounds; each row above lists the seating arrangement around the table starting to the right of person 0.

share|improve this answer
    
Gosh thanks, it's going to take me a while as I don't know Maple programming! seems really quite complex! –  user1392166 Dec 8 '12 at 21:24
add comment

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.