# Howto organize a party where everyone meets everyone around a big table?

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)

-
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

## 2 Answers

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 :)

-

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.

-
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