2 tables of 6 people: What's a schedule such that all pairs share a table for an equal amount of time?

246 Views Asked by At

The problem
There are 2 tables seating 6 people each. With 12 people, how many arrangements (with all 12 people seated) are necessary so that every pair shares a table for the same number of arrangements?

Example
Here's an example with 4 arrangements:

Arrangement 1: 1,2,3,4,5,6 and 7,8,9,10,11,12
Arrangement 2: 1,2,3,4,11,12 and 7,8,9,10,5,6
Arrangement 3: 1,2,9,10,5,6 and 7,8,3,4,11,12
Arrangement 4: 7,8,3,4,5,6 and 1,2,9,10,11,12

1 and 2 share a table 4 times.
1 and 3 share a table 2 times.
1 and 4 share a table 2 times.
...
11 and 12 share a table 4 times.

This is an invalid answer, because not all pairs share a table the same number of times.

My reasoning so far
In a single arrangement, a given person shares a table with 5 people out of 11 (other people). So, that person must sit with every other person 5 out of 11 times. So the answer must be a multiple of 11.

There are $\frac{\binom{12}{6}}{2}= 462$ unique arrangements, so that's an upper bound. (Division by two because the two tables are interchangeable).

(I'm also curious about the same problem, but with 2 tables of $n$ people)

2

There are 2 best solutions below

1
On BEST ANSWER

$1,2,3,5,8,12$
$1,3,4,6,9,2$
$1,4,5,7,10,3$
$1,5,6,8,11,4$
$1,6,7,9,12,5$
$1,7,8,10,2,6$
$1,8,9,11,3,7$
$1,9,10,12,4,8$
$1,10,11,2,5,9$
$1,11,12,3,6,10$
$1,12,2,4,7,11$.

1
On

This is an example of a block design problem. We know $v=12$ (total people) and $k=6$ (seats at each table). The following two equations must be satisfied: $$bk = vr$$ $$\lambda(v-1) = r(k-1)$$ Where $\lambda$ is the number of times each person meets each other person, $b$ is the total number of blocks (tables), and $r$ is the number of tables each person sits at. Note that all of these numbers must be positive integers. Additionally, $b \ge v$. From the above equations, we can see that: $$11 \lambda = 5r \ ; \ 12r = 6b$$ must be true. As $5$ and $11$ are conveniently prime, the smallest parameters which fit the above constraints give $b=22, \lambda=5, r=11$.

Hence there are $11$ pairs of tables ($b=22$) necessary, and each person will meet each other person $\lambda = 5$ times.

$2$-Block design (BIBD) is used for planning statistical studies on batches of samples, and also helpful in planning tournaments. When you need sets of $3$ or more together instead or pairwise planning, the math gets harder.