Dinner party combinatorics (meeting each other once)

Question

I am hosting a meet-and-greet dinner party but am having troubles with some elementary combinatorics. I got 20 people for a dinner party and they can only sit at tables in groups of 4. What is the minimum number of table arrangements required so that everyone gets to meet each other at least once?

Intuitively, the upper bound is going to be 20 choose 4 = 4845, as these are the total number of ways to choose sub-groups of 4 from a group of 20. However, this number seems too high but I don't know exactly how to work from here.

For a simpler case, if I have 5 people and have tables for 4, it seems I only need 3 different rounds of table arrangements to get my result: (1,2,3,4)5; 1(2,3,4,5); (1)2(3,4,5). Everyone has met everyone now. Clearly 5 choose 4 = 5 > 3. But I'm having troubles finding the exact principle here. The furthest I've gone is that we have 5 choices for the 1st member of a group of 4, 4 choices for the 2nd member, 3 choices for the 3rd, and 2 choices for the 4th. But I am not sure what number to divide this by to get the result we want.

Thanks in advance.

Answer 1

Here’s your party schedule in $7$ rounds:

14 16  1  0    11  5  9  8    10 12  2  7    19 17 15 13    18  3  6  4    
11  7 17 16    15 12  0  6     1 18  8 10    13  9 14  3     5  4  2 19    
 3 11  0  2    17 14 10  4    18 15  9  7     6  8 19 16    13  5  1 12    
10  9  0 19    13  4 15 16     2 11 18  1    14  7  6  5    12  8  3 17    
 3  7  1 19    11 13 10  6     9 12 16  4     5  0 18 17    14 15  2  8    
 1 17  6  9    12 11 14 19    15  5 10  3     7  8  0  4    18 13  2 16    
16 10  3  5    18 14 19 12     8  7 13  0     2  6  9 17     1 15  4 11    

Here’s the simulated annealing code I wrote to find it.

Since everyone needs to meet $19$ people and can only meet $3$ new people per round, this is optimal.

Answer 2

You must cover $\binom{20}{2}$ pairs, and each round covers $5 \binom{4}{2}$ pairs, so a lower bound is $$\left\lceil\frac{\binom{20}{2}}{5 \binom{4}{2}}\right\rceil = 7$$ rounds.

8 is an upper bound:

1
{1,2,3,4}
{5,6,7,8}
{9,10,11,12}
{13,14,15,16}
{17,18,19,20}
2
{1,7,15,20}
{3,6,16,18}
{9,12,14,17}
{4,5,10,11}
{2,8,13,19}
3
{8,9,12,20}
{4,16,17,19}
{3,11,13,15}
{1,5,7,18}
{2,6,10,14}
4
{7,10,15,19}
{3,4,8,14}
{5,6,12,16}
{2,11,17,20}
{1,9,13,18}
5
{10,14,18,20}
{1,6,11,19}
{5,8,15,17}
{3,4,12,13}
{2,7,9,16}
6
{1,12,14,19}
{4,6,9,15}
{3,7,10,17}
{2,5,13,20}
{8,11,16,18}
7
{7,11,12,14}
{1,8,10,16}
{6,13,15,17}
{3,5,9,19}
{2,4,18,20}
8
{3,6,16,20}
{1,8,17,19}
{5,9,11,14}
{2,12,15,18}
{4,7,10,13}