An
old chestnut goes like this:
Fourteen friends go to a restaurant together, but the restaurant cannot
seat all of them at one table so they split into two groups of six and eight.
The next time they go there, they split up into six and eight again, but
they split differently so that different friends get a chance to eat
together (at the same table, that is).
How many times must they do this before it is possible for every pair
of friends to have eaten at the same table at least once?
What about the same question for different sizes of splits? Different
numbers of friends? Ignore the degenerate cases of 0-seat tables and
the unsolvable case of two friends split between two 1-seat tables.
Answer to old chestnut: restaurant seating:
For the original problem with 14 friends split into 6 and 8, they can all
sit with each other once within three visits, as follows:
1st night: 12345678 ABCDEF
2nd night: 1234ABCD 5678EF
3rd night: 5678ABCD 1234EF
In general, it is possible for almost all groups/splits to eat together
within three nights, but some groups require four nights.
Proof that a minimum of three nights are required for all but degenerate cases:
The easiest way to understand this is to look at any given seating arrangement
for two nights. Some people swapped tables between the two nights, while
others stayed at the same table. (If either group is empty, the same groups
sat together both nights, which is no benefit over the first night.)
The number of people who swapped from Table A to Table B must be the same
as the number who swapped from Table B to Table A, since the number of
seats at each table is constant. (See old chestnut: water and wine.)
The people in these two groups have not sat with each other yet. Likewise,
the people who sat at one table both nights have not sat with anybody who
sat at the other table both nights, but it is possible for one of these
groups to be empty.
Solutions in three nights for most cases:
Let N and M be the sizes of the two tables, N >= M.
If N >= 2M, split the friends into three groups of size M and one of size N-M.
(With the last group empty if N = 2M.) Each night, one of the groups of size M
sits at the size-M table. Each size M group sits with the other two size M
groups in their two nights at the big table, and everybody sits with the
size N-M group both those nights.
If N < 2M, and either N or M is even, then have either N/2 or M/2 people
from each table switch tables the second night (so, half of one table
moves to the other table). The third night, the other half of that table
goes to the other table in place of the first half. This is the case
shown in the example above, where 5678 eat at the small table the second
night, then 1234 swap with 5678 the third night.
If N < 2M and both N and M are odd, four nights are required.
To do it in three nights, the two groups which swapped the first night must
all eat together the third night, and the two groups (if both exist)
which sat at the same table both nights must all eat together.
However, this includes everybody, and the group which contains all the
people who swapped tables between the first and second night has an even
number of people, so we can't possibly arrange this to be the right
number for the split we have. In the case where nobody sat at the smaller
table both nights, we still need to put all the swappers together, but since
the number of swappers is twice the size of the smaller table (M), and
N < 2M, they won't all fit at one table. So at least four nights are
required.
Solution for this case in four nights:
Let (N-1)/2 people from the big table swap with sa many from the small table
the second night. Then let (N-1)/2 other people from the big table swap with
with the previous swapping group the third night. This is exactly like the
N even solution above, but one extra person sits at the big table all three
nights. The third night, that one extra person swaps to the small table
together with the ones who have been there all three nights, and the rest
of the people sit anywhere.