We are discussing the following problem:
Given n players, arrange a series of matches, each between two teams of k players, in such a way that every pair of players are on the same team in s matches and on opposite teams in t matches, and subject to this the number of matches is as small as possible.
Here I want to discuss the case where k = 2. Much of this can be modified for other values of k, but I am speaking as a mathematician, and not giving specific formulas for arranging the matches.
I am going to explain the derivation of the following result.
Suppose that k = 2. Then the number of matches is at least n(n−1)/4 if n is congruent to 0 or 1 (mod 4), and at least n(n−1)/2 if n is congruent to 2 or 3 (mod 4). These bounds are attained for all but finitely many values of n.
Before embarking on the proof, here are some examples.
- For n = 4, the three partitions of four players into two sets of two (given in the previous post) form a solution.
- For n = 5, put the players at the vertices of a regular pentagon. Now arrange five matches, in each of which the players on an edge play against those on the parallel diagonal.
- For n = 7, there is a similar solution. A regular heptagon has seven vertices, seven short diagonals and seven long diagonals, falling into seven parallel classes each containing one edge, one short diagonal, and one long diagonal. For each parallel class we schedule three matches: edge v short diagonal; edge v long diagonal; and short diagonal v long diagonal. There are 21 matches.
- For n = 6, identify the six players with the diagonals of an icosahedron. (I discussed this in a comment to the preceding post.) Now any four diagonals can be directed so that they pass through the vertices of two adjacent faces; arrange a match in which the common edge of the two faces plays against the non-edge. There are 15 matches.
First we do some counting. Each player must take part in (n−1)s matches (s paired with every other player), and opposes two players in each match; so t = 2s. Also, the total number of matches is n(n−1)s/4. Since s is at least one, there are at least n(n−1)/4 matches. If n is congruent to 2 or 3 (mod 4), then n(n−1)/4 is not an integer, so s is at least 2, and the number of matches at least n(n−1)/2.
To prove that the schedules exist for almost all admissible integers, I am going to use Richard Wilson’s powerful theory of pairwise balanced designs. First, a brief summary of this theory.
A pairwise balanced design, or PBD, consists of a set of n points, together with a collection of subsets called “lines” so that any two points belong to a unique line. If K is a set of positive integers, and all cardinalities of lines belong to K, we call the design a PBD(K). Let B(K) denote the set of all n for which a PBD(K) on n points exists.
Wilson’s first observation is that B is a closure operator on sets of natural numbers. This means that
- K ⊆ B(K);
- if K ⊆ L, then B(K) ⊆ B(L);
- B(B(K)) = B(K).
The first statement uses the fact that there is always a trivial PBD with a single line containing all points. The second is straightforward. The third uses a simple but powerful construction technique. We know that B(K) is contained in B(B(K)), and have to show the reverse inclusion. So take a number n in B(B(K)). There is a PBD X on n points, each of whose line sizes belongs to B(K). This means that there is a PBD(K) on each line of X. Now replace each line by the lines of the corresponding PBD(K), to obtain a PBD(K) on the whole set. So n belongs to B(K).
Given a non-empty set K of positive integers, let
- α(K) = gcd{k−1 : k∈K};
- β(K) = gcd{k(k−1) : k∈K}.
Easy counting arguments show that, if n is in B(K), then α(K) divides n−1, and β(K) divides n(n−1). Wilson’s Theorem is a near-converse:
Let K be a non-empty set of positive integers. Then all but finitely many positive integers n which satisfy the above divisibility conditions belong to B(K).
The proof is long and complicated, but the theorem is deceptive in its simplicity: it is extremely powerful. I will now show how the theorem stated earlier about arranging matches follows from Wilson’s Theorem.
Let T denote the set of all integers n≥4 for which we can arrange n(n−1)/4 matches satisfying our conditions (necessarily having s=1 and t=2). I claim that T = B(T). For suppose that we have a PBD(T) on n points. By assumption, there is a match schedule involving the players in each line of the PBD. Now all the resulting matches form a schedule on the entire set which satisfies our conditions.
Our earlier examples show that 4 and 5 both belong to T. Now gcd(3,4)=1 and gcd(12,20)=4; so all sufficiently large integers n for which n(n−1)/4 is an integer (that is, congruent to 0 or 1 (mod 4) belong to T.
In exactly the same way, the set U of integers n for which a match schedule with n(n−1)/2 matches exists (having s=2 and t=4) contains all sufficiently large integers. (Note that T is contained in U, since given a schedule with n(n−1)/4 matches, we can simply play each match twice. So 4,5,6,7 all belong to U, from which we conclude that α(U)=1 and β(U)=2. Also, just as before, we have U = B(U), so that U contains all sufficiently large positive integers.)
It remains to discover exactly what “sufficiently large” means in each case. Typically, questions like this require a good deal of ingenuity, and involve techniques like those used by Wilson in the proof of his Theorem.
Thanks, again, Peter.
A lot more information for me to digest.
I also appreciate the fact that you speak as a a mathematician.
It is a great feat of mathematics to be able to prove that “schedules exist for almost all admissible integers”, while inventorying those schedules may be a task beyond current computing capabilities. [although “almost” is a little suspicious :)]
What I have learned over the past few days is that any brute force approach will fail, unless k and n are relatively small.
Knowing that schedules exist is better than learning they do not. Does it mean there could be a constructive approach to generate them? Probably not. But, at least, there is hope.
Wilson’s methods are constructive; but the amount of work required to go through his argument and specialise it to the case in hand is quite daunting. Also, as I said, working out the finitely many exceptions is a real challenge, although again there is a bound (probably much too large) in Wilson’s work.
The real problem is that Wilson’s methods only work if k is fixed. If we allow k and n to grow together, we really don’t know how to proceed. (The Hadamard conjecture is still open for n=668, despite a great deal of work.)