19
$\begingroup$

I have a young group of kids ($30$) playing soccer and they need to be put into $6$ teams of $5$ players for each round of matches. All $6$ teams play at the same time on adjoining fields.

If I wanted each kid to play on a team with every other kid in the group (so they know each others names), how many team rounds would I need?

Note: I'm not after the number of rounds to get through all of the combinations of unique teams.

$\endgroup$
10
  • 3
    $\begingroup$ Nice question! Bookmarked. $\endgroup$
    – Matti P.
    Apr 13 at 7:51
  • 2
    $\begingroup$ This is related to the Social Golfer problem math.stackexchange.com/search?tab=votes&q=social%20golfer Also see en.wikipedia.org/wiki/Block_design $\endgroup$
    – PM 2Ring
    Apr 13 at 7:55
  • 2
    $\begingroup$ I haven't the time to answer this in full now and the answer seems non-trivial, but this is definitely a design theory question. In particular, the rounds of teams where each player plays means that whatever design this is will have to be resolvable. Though you don't seem to require that each pair of players plays together the same number of times, only that they do so at least once. $\endgroup$ Apr 13 at 12:40
  • 6
    $\begingroup$ You need at least 8 rounds. Here are 48 teams that cover all 435 pairs at least once, but I don't think that covering is resolvable into 8 parallel classes. It can be resolved into 15 classes though, so perhaps 15 rounds is the smallest solution to your puzzle. $\endgroup$
    – PM 2Ring
    Apr 14 at 5:49
  • 4
    $\begingroup$ FWIW, there's a perfect solution (using a finite affine plane) that splits $q^2$ players into $q$ teams of $q$, over $q+1$ rounds, when $q$ is a prime, or prime power. See here $\endgroup$
    – PM 2Ring
    Apr 28 at 19:04
7
+100
$\begingroup$

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$ :)

$\endgroup$
13
  • $\begingroup$ Your 13 class solution doesn't look too bad. FWIW, its pair coverage is (1: 205, 2: 143, 3: 67, 4: 13, 5: 6, 6: 1). That is, 205 pairs are covered once, 143 pairs are covered twice, etc. A 13 class solution that doesn't permit a pair to be covered more than twice would have coverage (1: 90, 2: 345). Also, your solution only covers 30 triplets twice, and no group of 4 (or 5) is covered more than once. $\endgroup$
    – PM 2Ring
    Jun 16 at 19:29
  • 1
    $\begingroup$ Coverage script $\endgroup$
    – PM 2Ring
    Jun 16 at 19:52
  • 1
    $\begingroup$ I saw a couple of articles on searching for resolvable coverings using simulated annealing, and yeah, they weren't very clear about the probability function. (And I have no experience using SA, which doesn't help). I guess we want to make it expensive to cover a pair more than once, and very expensive to cover a pair more than twice, or to cover a triplet more than once. $\endgroup$
    – PM 2Ring
    Jun 16 at 19:57
  • 1
    $\begingroup$ The only absolute rule for the temperature $c_i$ is that it should decrease from some large "hot" value to some small "cold" value over time. The exact values are dependent both on the range of the goodness function and the shape of the problem. I recommend trying a very large range at first, but debugging the process by looking at a plot of the goodness function over time. There's an unproductive "too hot" period where the goodness jumps around randomly, and an unproductive "too cold" period where nothing changes; pick your range to keep those short. $\endgroup$ Jun 16 at 21:30
  • 1
    $\begingroup$ All the SA code I've seen online suggests that $c_i$ should decay exponentially from its maximum to its minimum value, but I'm not sure how much that matters as long as it decays slowly enough. $\endgroup$ Jun 16 at 21:32
5
+50
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Nice work, but I agree that the repeated ABCDE team does make it a bit ugly. I also had that problem in my attempts. ;) $\endgroup$
    – PM 2Ring
    Jun 16 at 19:34
  • 1
    $\begingroup$ Now there's no more repeated ABCDE team! Still can't beat the computer search, though. Maybe that's evidence that 10 rounds is the best possible. $\endgroup$ Jun 18 at 20:29
  • $\begingroup$ BTW, The non-existence of mutually orthogonal Latin squares of order 6 is connected to a famous problem of historical significance: the 36 officers problem. $\endgroup$
    – PM 2Ring
    Jun 19 at 4:31
4
$\begingroup$

This answer is just a supplement to the answer by Yorch, but it's a bit too large to fit into a comment. ;)

The 8 round partial solution has pair coverage (0: 14, 1: 365, 2: 53, 3: 3). That is, only 14 pairs are uncovered, 365 pairs are covered once, etc. It has perfect triplet coverage: 480 triplets are covered exactly once. (Each round covers 60 triplets).

I completed the 9th round by simply assigning unused numbers to the partial and empty groups. This produced a final row of

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

which has coverage (1: 341, 2: 83, 3: 11)

By randomly shuffling the unused numbers, we can increase the number of pairs that have coverage of 1, and reduce the pairs with coverage 2, but that increases the number of pairs that are covered 3 times.

Here are typical results, found by searching through 10000 random permutations. I actually searched 500000 permutations, but I didn't find any solutions which have >346 pairs with coverage 1.

8 classes
0: 14, 1: 365, 2: 53, 3: 3, 

[[0, 2, 10, 17, 29], [1, 3, 6, 12, 28], [4, 7, 8, 21, 23], [5, 9, 14, 19, 22], [11, 13, 15, 16, 18], [20, 24, 25, 26, 27]]
1: 341, 2: 83, 3: 11, 
[[0, 2, 10, 17, 29], [1, 3, 6, 12, 28], [4, 16, 21, 23, 26], [5, 14, 19, 22, 24], [8, 9, 13, 15, 18], [7, 11, 20, 25, 27]]
1: 342, 2: 81, 3: 12, 
[[0, 2, 10, 17, 29], [1, 3, 6, 12, 28], [4, 8, 21, 23, 25], [5, 7, 14, 19, 22], [11, 15, 16, 26, 27], [9, 13, 18, 20, 24]]
1: 343, 2: 79, 3: 13, 
[[0, 2, 10, 17, 29], [1, 3, 6, 12, 28], [4, 7, 16, 21, 23], [5, 14, 19, 22, 26], [9, 13, 18, 20, 24], [8, 11, 15, 25, 27]]
1: 344, 2: 77, 3: 14, 
[[0, 2, 10, 17, 29], [1, 3, 6, 12, 28], [4, 8, 16, 21, 23], [5, 14, 19, 22, 24], [7, 11, 15, 18, 26], [9, 13, 20, 25, 27]]
1: 345, 2: 75, 3: 15, 
[[0, 2, 10, 17, 29], [1, 3, 6, 12, 28], [4, 7, 16, 21, 23], [5, 14, 19, 22, 24], [8, 13, 20, 25, 27], [9, 11, 15, 18, 26]]
1: 346, 2: 73, 3: 16, 

Going in the other direction, we reduce the number of pairs that are covered once or 3 times, but increase those with a coverage of 2. Eg,

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

which has coverage (1: 336, 2: 93, 3: 6).

You can see and run my Python code here.

FWIW, a 9 round equitable covering would have coverage (1: 330, 2: 105), and an 8 round equitable covering would have coverage (1: 390, 2: 45). 

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.