6
$\begingroup$

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)

$\endgroup$
0

2 Answers 2

7
$\begingroup$

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

$\endgroup$
1
5
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Oh, block design, that's what I was looking for! Thanks for clearly explaining my problem in those terms. $\endgroup$ Commented Jan 21 at 7:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .