Solution to MP31

Even University has only 20 faculty members, while Odd University has 1000 members. Odd University tries to form as many committees as it can following its own rule, but still comes short of the number of committees at Even University. How is this possible?

We received a solution from Pierre Bornsztein (France), and a partial solution from Juan Mir Pieras (Spain). Here is Bornsztein's solution, supplemented by comments from Mir.

The number of committees at the Even University.
We let E(n) stand for the largest possible number of distinct committees that can be formed by n faculty members following the Even University's regulations. Since there is no rule against it, we include the "empty" committee as one of the possible committees (but we refrain from making jokes that compare the effectiveness of the empty committee with that of a typical university committee).

Property 1. For every n ≥ 0 we have P(n+2) ≥ 2P(n).
Suppose the Even University includes a and b among its n+2 faculty members. Without a and b one can form P(n) committees. If C is one of these committees, we form the committee C^* by adding a and b to it. In this way we can form P(n) new committees, and we easily check that these 2P(n) committees -- the old with the new -- satisfy the three regulations.

From P(0) = 1 (the empty committee) we deduce that P(2k) ≥ 2^k. In particular, P(20) ≥ 2¹⁰-1024. If you do not like the idea of having an empty committee, removing it still leaves 1023 committees that can be formed by the 20 faculty members of the Even University.

Mir comes to the same conclusion, but his approach is slightly different: We form 10 disjoint pairs from the 20 faculty members. Any combination of these pairs produces committees whose membership is even, and it insures that any two committees have an even intersection (possibly empty). Since there are 2¹⁰-1024 ways to combine 10 pairs into committees consisting of pairs, again we see that there can be as many as 1024 committees.

The number of committees at the Odd University.
We let O(n) stand for the largest possible number of distinct committees that can be formed by n faculty members following the Odd University's regulations.

Property 2. O(n) = n for n ≥ 1.
Our argument requires knowledge about the rank of a matrix. Alternatively, one can argue about the maximum dimension of a vector space. Either way, one needs here the basics of linear algebra.

We define T = M^tM, where M^t is the transpose of M. T is a k by k matrix whose general entry T(i, j) equals the number of elements common to committees C_i and C_j. Consequently, the entries where i ≠ j are all even (by rule 2), while the diagonal entries (with i = j) are all odd (by rule 1). Taking the entries modulo 2, we get the k by k identity matrix. This implies that its determinant modulo 2 is equal to 1, which means that the determinant of T is odd and, therefore, nonzero. Thus, T is invertible so its rank must be k. But then, k is also the rank of M (because, by the rank inequality, the rank of a product cannot exceed the rank of either factor, which here cannot exceed the smaller of k and n), and we have k ≤ n.

Conversely, taking each faculty member as a committee of one, we get an example with n committees that satisfy the Odd University's two rules. Thus k ≥ n, and the proof of property 2 is complete.

The solution.
We are now ready to solve this month's problem. Property 2 tells us that O(1000) = 1000. From the comment after the proof of property 1,

which shows that if they so wish, the Even University with only 20 faculty can indeed form more committees than the much larger Odd University.

Mir pointed out that there are other ways for the Odd University to achieve the maximum number of committees. One simple way is to take the complements of the singleton committees -- that is, they can have 1000 committees of 999 each, with everybody being a member of all but one of the committees (in which case any two committees would have 998 members in common).

There is a more interesting way to attain the maximum when some Odd University has n = p^2h + p^h + 2 members, where p is an odd prime and h is a positive integer. Here is an example with n = 14 (where p = 3 and h = 1). With the exception of one distinguished member, we number the faculty from 0 to 12; the exceptional member we denote by *. There are 13 committees having 5 members, of whom one is always the special person *, and there is one large committee of all thirteen numbered members. The 5-person committees are represented by the columns in the array below.

0	1	2	3	4	5	6	7	8	9	10	11	12
1	2	3	4	5	6	7	8	9	10	11	12	0
3	4	5	6	7	8	9	10	11	12	0	1	2
9	10	11	12	0	1	2	3	4	5	6	7	8
*	*	*	*	*	*	*	*	*	*	*	*	*

The quadruples of numbers in each column provide a convenient representation of the lines of the 13-point projective plane -- the points of the plane are the numbers from 0 to 12. Each pair of lines intersect in a single point while any pair of points determine a unique line. (More generally, there exists a projective plane having p^2h + p^h + 1 points and an equal number of lines, where p is an odd prime and h is a positive integer.)

This idea (of using a projective plane as the basis of an arrangement to illustrate how the Odd Universities of the world can form the maximum number of committees) came from the preliminary version of the text Linear Algebra Methods in Combinatorics by László Babai and Péter Frankl (which apparently is still a preliminary version after some 20 years). This problem serves as the first example in the text to motivate the fundamental linear-algebra-bound method, the method used by Bornsztein in his proof of Property 2 above. It was our hope that somebody might discover a way to show O(n) = n by an elementary argument that avoids linear algebra. It seems pretty unlikely that such an argument could ever be possible. Babai and Frankl got the problem from a 1969 note by E.R. Berlekamp.