2
$\begingroup$

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)

  • 0
    Yes I tried on paper just moving them around and it just becomes a mess after the first move! the must be a more logical way?2012-12-07

2 Answers 2

1

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

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.

  • 1
    Gosh thanks, it's going to take me a while as I don't know Maple programming! seems really quite complex!2012-12-08
0

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