old chestnut: restaurant seating

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.