Generate groups for multiple match rounds while minimizing the number of times two participants are in the same match

Question

We are hosting an event with 100 participants. $20$ Participants can participate in one Match. $5$ Matches with $20$ Participants each will be called one Round. (Each participant is only playing one Match per Round) We are going to play $6$ Rounds.

We would like to minimize the number of times a participant is in the same match with another participant. (To be exact we would like to minimize the quadratic count, since it is better to have two participants seeing someone twice, than zero and four times.)

I am looking for any help, ether solutions or just keywords what a problem like this is called.

I tried the brute force approach with a small program, but it seems to converge rather quickly.

Answer 1

This might or might not be the literal minimum, but it gives a result that's significantly better than random teams. We give the participants numbers between $1$ and $100$ that change from round to round, and in each round the matches are comprised of participants $1,\dots,20$, participants $21,\dots,40$, participants $41,\dots,60$, participants $61,\dots,80$, and participants $81,\dots,100$.

• Round one: Number the participants $1,2,\dots,100$.
• Round two: Multiply each participant's number by $18$ and reduce it modulo $101$ (that is, replace each number by its remainder when divided by $101$).
• Round three: Again multiply each participant's number by $18$ and reduce it modulo $101$.
• Round four: Same thing.
• Round five: Same thing.
• Round six: Same thing.

With this scheme, $1{,}116$ pairs of participants are never in a match together, $2{,}369$ pairs of participants are in exactly one match together, $1{,}107$ are in exactly two matches together, $317$ are in three matches together, $39$ are in four matches together, and $2$ are in five matches together. The quadratic count, summed over all $4{,}950$ possible pairs of participants, is $10{,}324$.

(Random matches tends to yield quadratic counts around $11{,}000$ to $11{,}300$. By way of comparison, the best possible outcome would be if $4{,}200$ pairs of participants were in exactly one match together and $750$ pairs of participants were in exactly two matches together, giving a quadratic count of $7{,}200$.)

Answer 2

No proof of optimality, but here's a solution I obtained via integer linear programming.

Round 1
Match 1 {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
Match 2 {21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
Match 3 {41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60}
Match 4 {61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80}
Match 5 {81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100}

Round 2
Match 1 {1,5,8,14,22,29,32,39,45,47,54,57,61,63,68,79,84,86,97,98}
Match 2 {9,10,11,17,25,26,33,38,44,50,56,60,67,71,72,80,87,88,91,93}
Match 3 {12,13,18,20,21,27,28,34,41,42,46,52,64,65,69,78,81,83,85,96}
Match 4 {2,4,7,15,23,35,36,40,49,53,55,58,66,70,74,76,82,90,99,100}
Match 5 {3,6,16,19,24,30,31,37,43,48,51,59,62,73,75,77,89,92,94,95}

Round 3
Match 1 {4,11,13,14,24,27,32,35,45,49,52,59,64,67,68,72,82,91,92,95}
Match 2 {6,7,16,17,21,22,34,50,54,55,60,65,70,73,78,79,87,89,98,99}
Match 3 {2,5,12,20,25,26,29,31,36,41,44,46,53,74,75,77,84,88,94,97}
Match 4 {1,8,10,18,23,28,37,38,43,47,51,56,62,63,66,80,81,85,90,100}
Match 5 {3,9,15,19,30,33,39,40,42,48,57,58,61,69,71,76,83,86,93,96}

Round 4
Match 1 {2,7,11,15,28,31,32,38,42,48,50,57,64,66,68,79,85,88,89,94}
Match 2 {4,6,17,18,25,33,39,41,51,52,60,61,63,70,74,84,92,95,96,100}
Match 3 {3,5,12,19,23,29,35,37,46,49,54,55,65,72,73,80,81,86,91,93}
Match 4 {1,10,13,14,21,22,27,30,36,44,45,56,58,62,75,76,77,83,87,99}
Match 5 {8,9,16,20,24,26,34,40,43,47,53,59,67,69,71,78,82,90,97,98}

Round 5
Match 1 {5,9,16,20,23,33,36,38,45,46,56,59,65,68,76,79,89,95,96,100}
Match 2 {1,13,17,19,28,29,30,31,41,47,50,53,64,70,71,80,82,86,92,99}
Match 3 {4,7,8,18,26,27,34,35,43,48,54,57,63,72,74,75,83,87,93,94}
Match 4 {10,11,12,15,21,24,25,32,42,51,55,58,61,62,73,78,84,90,91,97}
Match 5 {2,3,6,14,22,37,39,40,44,49,52,60,66,67,69,77,81,85,88,98}

Round 6
Match 1 {6,11,14,16,21,26,31,39,46,53,54,58,63,64,76,80,85,90,93,95}
Match 2 {4,7,17,19,24,29,34,36,44,51,56,59,61,66,68,78,81,83,86,88}
Match 3 {1,2,9,12,22,27,32,38,41,43,48,49,70,71,73,75,91,96,98,100}
Match 4 {3,5,13,18,23,25,28,40,45,50,55,57,62,67,69,74,87,89,92,97}
Match 5 {8,10,15,20,30,33,35,37,42,47,52,60,65,72,77,79,82,84,94,99}

It has quadratic count $$1144 \cdot 0^2 + 2244 \cdot 1^2 + 1258 \cdot 2^2 + 276 \cdot 3^2 + 28 \cdot 4^2 + 0 \cdot 5^2 + 0 \cdot 6^2 = 10208.$$