Laurent asked on my blog:
Given n players, arrange a competition in which, in each match, two teams of k players play each other. We require that any two players are on the same team in a fixed number s of matches and on opposite teams in t matches, though t is not required to be the same as s. Furthermore, we want to play the minimum possible number of matches. How many matches do we need to schedule?
He put it under “About”, which probably nobody reads.
He gave the following example for n=4 and k=2, where three
matches are required:
1,2 v 3,4 |
1,3 v 2,4 |
1,4 v 2,3 |
Clearly the problem is a non-problem unless n ≥ 2k. In this post, I will address the case n = 2k.
A Hadamard matrix is a square matrix H of order n with entries +1 and −1 satisfying the equation HH^{T} = nI (or equivalently H^{T}H = nI). It is known that the order of a Hadamard matrix is 1, 2, or a multiple of 4; the Hadamard conjecture asserts that, for every number n which is divisible by 4, there is a Hadamard matrix of order n. The smallest multiple of 4 for which no Hadamard matrix is currently known is 668.
Hadamard defined these matrices in terms of a determinant problem: they maximise the determinant of a matrix all of whose entries have magnitude at most 1. They come up in many geometric and combinatorial situations. For example, if we take a cube with side length 2 and centre at the origin in Euclidean space of n dimensions, when can we select n vertices forming an orthogonal basis for the space? Such vectors must be the rows of a Hadamard matrix, and conversely. Sylvester called them anallagmatic pavements, clearly motivated by geometric ideas. (Sylvester was a genius at weird terminology; we saw his “synthematic totals” before.) For much more information see the Wikipedia article on Hadamard matrices.
Now the Hadamard conjecture would solve our problem for the case n = 2k:
- If k is even, then the number of matches is at least n−1, with equality if and only if there is a Hadamard matrix of order n.
- If k is odd and k>1, then the number of matches is at least 2(n−1); equality holds if there is a Hadamard matrix of order 2n.
Note that the second part does not say “if and only if”; I don’t know whether the converse is true. But in any case, the truth of the Hadamard conjecture would resolve the question.
I will sketch the proof of this result here. Let m be the number of matches. Since every player participates in all the matches, we have s+t = m. Fix attention on a particular player. In the m matches, he plays with each of the other n−1 players s times, so (2k−1)s = (k−1)m. Since the greatest common divisor of k−1 and 2k−1 is 1, we see that 2k−1 divides m, so clearly m ≥ n−1.
Now suppose that equality holds. Then s = k−1 and t = k. Number the players from 1 to n, and write each match as a row vector of length n with entries +1 (for one team) and −1 (for the other). Stack up these rows to form a matrix, and put a row with all entries +1 on top.
I claim that this matrix H is a Hadamard matrix. For if we take any two columns, they agree in the first row (which is all +1s) and in k−1 further rows, and disagree in k rows; so their inner product is 0. This means that all the off-diagonal entries of H^{T}H are zero, so that H^{T}H = nI.
By our remarks on Hadamard matrices, for k > 1, this is only possible if k is even.
Conversely, if we have a Hadamard matrix of order n = 2k, we can change signs of columns to make the top row consist entirely of +1s. The orthogonality of rows now says that each further row contains k +1s and k −1s, so we use these rows to describe the schedule of matches. Orthogonality of columns now shows that the conditions on pairs of players are satisfied.
Now suppose that k is odd and k > 1. Then m is a multiple of n−1, and is not n−1; so it is at least 2(n−1).
Suppose that a Hadamard matrix of order 2n exists. As before, change signs of columns to make the first row consist of +1s; then every further row has n +1s. Order the columns so that the +1s in the second row occur in positions 1,2,…,n. Now delete the last n columns and the first two rows of the matrix. What is left has k +1s and k −1s in each row, so it describes a schedule of matches; and as before, it is easy to see by looking at columns that the condition on pairs of players is true.
Appendix
Last week one of my colleagues suggested to me that the Axiom of Choice is not “discrete mathematics”. I answered that it is, and gave the following illustration. Without using AC, it is possible to show that if AC holds for any family of 2-element sets, then it holds for any family of 4-element sets.
The proof is as follows. Consider the scheme for 4 players given above. They play 2 against 2 in all possible combinations. The Axiom of Choice for 2-element sets says that we can choose a winner for each of these matches. Now it is easy to see that, whatever the results, either one player is on the winning side in every match, or one player is on the losing side in every match; this is the player chosen from the set of 4.
I showed in the post that (assuming the Hadamard conjecture) the smallest number of matches for 2k players in teams of k, such that any two players are on the same team a constant number of times, and on opposing teams a (different) constant number of times, is 2k−1 if
k = 2 or k is even, and 2(2k−1) otherwise.
Here is a nice description of the case k = 3.
Take an icosahedron, perhaps the one Carl Murray lent to Amir Foley last week. It has six diagonals, which we match up with the six players. Now the 20 ways of choosing a set of three players fall into two types. Ten consist of three diagonals which can be oriented so that each pair make an acute angle (these are easily described – take the three diagonals through the vertices on a face of the icosahedron – there are only ten such triples because oppposite faces give rise to the same triple). The other ten can be oriented so that each pair make an obtuse angle. This gives rise to ten partitions of the six players into two sets of three, that is, ten matches. (The complement of a triple of the first type is a triple of the second type; this is clear if you look at an icosahedron.)
It is easily checked that any two players are in the same team four times (twice in a triple of the first type, corresponding to the two faces sharing an edge, and twice in a triple of the second type), and on opposite teams six times.
Well, Peter, quite interesting and impressive.
In the situation I am currently dealing with, k is fixed to 4, so I will try to write a program that resolves (8, 4) using your method.
I already had this schedule for (8, 4):
(8 4 5 7) vs (3 1 6 2)
(8 5 6 1) vs (4 2 7 3)
(8 6 7 2) vs (5 3 1 4)
(8 7 1 3) vs (6 4 2 5)
(8 1 2 4) vs (7 5 3 6)
(8 2 3 5) vs (1 6 4 7)
(8 3 4 6) vs (2 7 5 1)
As kindly suggested by Ian Wakeling.
I am still searching for a semi-brute force, constructive approach for (n, 4) with 8 <= n <= 16.
It's absolutely fascinating how the problem space grows with n.
I’ll say something about the case where n is bigger than 2k sometime (when other things permit).
The solution for (8,4) comes from the Hadamard matrix of order 8, which has many descriptions: for example, it is the character table of the group of order 8 which is the direct product of three cyclic groups of order 2. As numbered above, 1, 2 and 4 are the generators of the three groups and 8 is the identity element.
Found this other resource:
http://allan-jensen.adr.dk/tournam.htm
Pingback: Team games, 3 « Peter Cameron's Blog