How many rounds would it take to get each pair on the same team at least once, not using all possible teams?

Solution 1:

We are trying to find a parallel block design with $k=5$ and $q=6$ which covers every pair of the $qk$ points in which the number $r$ of classes is minimal.

I implemented the simulated annealing technique described here: https://onlinelibrary.wiley.com/doi/epdf/10.1002/jcd.10024

In this method we select an initial parallel design and search through the space of parallel designs with $q$ blocks of size $k$ in each class, and where there are $r$ classes ( they don't need to cover all the pairs) (so each class is a partition of $\{1,\dots,qk\}$ into $q$ sets of size $k$).

We start out with a given design, and in each step modify it to get a new one. The idea is that we want our designs to get "better and better". But we don't want only let them get better because we could get caught at a local maximum.

The authors propose that we let the number of "uncovered pairs" be the function that tells us how good a design is. We would like to find a design in which there are $0$ uncovered pairs, as such a design solves our original problem.

We use the method they propose. We transpose two two random elements of the same class and different blocks of our design, and let it be the next element of the search with probability $1$ if the cost does not increase and probability $e^{(oldcost - newcost)/c_i}$ where $i$ is the current depth of the search and $c_i$ is $0.99^{10^{-4}i}$ if the cost does increase.

I didn't know which starting designs I should use so I just used designs in which the starting classes are all random (that is, formed by a random permutation of $\{1,\dots,k*q\}$ in which the blocks of the class are consecutive elements).

I let the search go on for $160,000$ iterations and selected a starting set of $200$ designs. It seems to find a design with $13$ classes every time I run it. Although I haven't been able to find one with $12$, although I really haven't tried that hard.

Here is an example of a design with $13$ classes:

Class 0:13 1 23 2 8 | 25 14 24 17 28 | 5 10 29 6 15 | 21 16 20 18 7 | 9 0 22 11 3 | 27 26 19 12 4 | 
Class 1:25 4 20 14 26 | 21 5 22 18 0 | 16 15 6 13 24 | 7 8 27 10 17 | 12 28 11 23 2 | 3 9 19 29 1 | 
Class 2:15 23 18 29 16 | 28 27 4 7 10 | 20 25 11 13 0 | 9 26 3 5 8 | 6 17 22 2 19 | 24 21 14 12 1 | 
Class 3:15 25 10 23 26 | 2 9 13 21 24 | 14 19 27 4 0 | 20 5 8 28 7 | 16 17 29 11 22 | 18 1 12 3 6 | 
Class 4:5 16 17 4 19 | 14 10 3 20 12 | 27 9 29 18 23 | 24 0 26 25 13 | 1 2 7 8 21 | 22 28 15 11 6 | 
Class 5:6 18 0 1 17 | 28 19 21 12 2 | 24 3 27 13 20 | 7 25 22 23 10 | 4 9 16 29 8 | 26 11 15 14 5 | 
Class 6:22 4 1 5 15 | 24 19 8 14 2 | 12 28 7 17 9 | 3 29 11 25 27 | 26 23 18 13 0 | 16 21 20 6 10 | 
Class 7:12 20 23 15 19 | 13 14 7 11 4 | 8 18 28 22 0 | 25 16 17 24 9 | 26 29 6 21 10 | 3 27 5 1 2 | 
Class 8:14 16 23 22 27 | 1 19 26 12 0 | 18 11 10 9 13 | 7 24 4 29 20 | 17 21 15 28 3 | 8 25 2 5 6 | 
Class 9:23 5 24 3 22 | 28 13 18 17 26 | 29 15 25 21 27 | 12 6 9 4 14 | 16 0 2 10 20 | 19 7 11 8 1 | 
Class 10:19 18 14 24 13 | 27 29 0 12 5 | 1 6 16 28 3 | 2 15 8 25 26 | 22 10 21 4 23 | 20 11 17 7 9 | 
Class 11:1 10 3 24 4 | 7 15 9 6 0 | 29 27 14 28 13 | 11 21 26 20 22 | 25 12 19 18 16 | 23 8 5 17 2 | 
Class 12:22 12 8 5 13 | 23 28 27 21 6 | 19 11 24 15 10 | 2 29 0 4 18 | 3 16 7 26 9 | 20 25 1 17 14 | 

It seems we can obtain better results by trying to get the best design with $r-1$ classes and then checking if it can be patched with an $r$'th class.

to do this we can print the unsatisfied pairs, check the sizes of the connected components of the graph formed by those pairs, and trying to split these components into groups of size $5$.

For example, with $r=9$ we run the code with the parameter $8$, and check which unsatisfied pairs exist in the "result", and find the components.

Class 0: 8 13 6 25 18 | 22 14 11 28 0 | 15 12 23 9 2 | 26 27 16 20 7 | 19 24 10 3 4 | 21 5 17 29 1 | 
Class 1: 10 26 5 14 28 | 17 11 15 16 3 | 4 13 9 20 27 | 24 0 21 8 25 | 18 12 29 2 22 | 1 19 6 23 7 | 
Class 2: 6 17 4 22 26 | 10 25 27 23 28 | 2 19 21 8 16 | 5 11 12 24 7 | 20 13 15 0 29 | 14 3 9 1 18 | 
Class 3: 16 9 24 28 29 | 25 1 2 26 17 | 21 3 22 23 20 | 13 19 11 12 6 | 15 8 14 5 27 | 7 0 4 18 10 | 
Class 4: 19 9 3 0 26 | 29 6 5 4 16 | 1 12 10 20 8 | 11 18 21 27 2 | 22 7 15 25 28 | 14 17 13 24 23 | 
Class 5: 18 20 17 28 19 | 1 0 22 24 27 | 29 11 23 26 8 | 15 9 6 21 10 | 4 12 16 14 25 | 13 7 2 5 3 | 
Class 6: 6 17 12 0 27 | 3 8 2 4 28 | 15 24 18 19 26 | 21 23 7 14 29 | 13 10 1 16 22 | 25 9 11 20 5 | 
Class 7: 7 8 9 17 22 | 27 19 25 29 3 | 16 18 5 23 0 | 20 14 2 24 6 | 15 1 10 4 11 | 12 13 28 26 21 | 
Components formed by missing edges
component : 0 2 10 17 29 
component : 1 28 6 3 12 
component : 4 21 23 
component : 5 19 22 14 

It is not hard to see we can create a final class such that each component is contained inside one of the blocks.

For $r=8$ I always get components of size larger than $5$ though, although I don't really know what I'm doing, but at least we found one for $r=9$ :)

Solution 2:

Here's a $10$-round solution with some theory behind it, although it seems like the theory hasn't helped us do better than a computer search.

Let's divide the $30$ kids into four groups: group abcdefghijkl, group 123456, group OPQRST, and group UVWXYZ. Then, begin with the following six rounds:

ab1PX   cd2QY   ef3RZ   gh4SU   ij5TV   kl6OW
ab2RU   cd3SV   ef4TW   gh5OX   ij6PY   kl1QZ
ab6SW   cd1TX   ef2OY   gh3PZ   ij4QU   kl5RV
ab3TY   cd4OZ   ef5PU   gh6QV   ij1RW   kl2SX
ab5QZ   cd6RU   ef1SV   gh2TW   ij3OX   kl4PY
ab4OV   cd5PW   ef6QX   gh1RY   ij2SZ   kl3TU

Where do these come from? I have built this out of the three mutually nearly orthogonal Latin squares of order $6$ constructed on p.24 of this paper, with one Latin square used on the group 123456, one used on OPQRST, and one on UVWXYZ.

If we took actually orthogonal Latin squares, then the result would be that all kids in different groups have met. Unfortunately, orthogonal Latin squares of order $6$ don't exist. This set has almost that property: the six triples 1OU, 2PV, 3QW, 4RX, 5SY, 6TZ are all we need.

In four more rounds, we can finish the job, and also have the three small groups meet each other; this can be done by hand easily without too much thought. Here is the partial construction of these four rounds:

2PV..   3QW..   4RX..   5SY..   .....   .....
12345   UZ6T.   OPQRS   .....   .....   .....
23456   UVWXY   OT...   .....   .....   .....
16OU    VWXYZ   PQRST   .....   .....   .....

Having everyone in the large group meet (that hasn't already) is harder; this is the bottleneck, and can't be done in $3$ rounds. For this, I gave in and did a simulated annealing run of my own, and got the following four rounds (I represent with . positions that can be filled in any way you like):

2PV..   3QW..   4RX..   5SY..   aegil   bfhjk
12345   UZ6T.   OPQRS   acfgk   bdhil   ej...
23456   UVWXY   OT...   achjl   defik   bg...
16OU.   VWXYZ   PQRST   adgjk   bcehi   fl...

These four rounds, together with the six rounds at the beginning, are a $10$-round solution to the problem.

I can't prove that there's no $9$-round solution. The Latin-square based approach can't possibly be made to work in $9$ rounds, however, and it seems very efficient (except that the six pairs ab, cd, ef, gh, ij, kl are stuck together all the time).