Balkan 89/4 solution

6th Balkan 1989

Problem 4

S is a collection of subsets of {1, 2, ... , n} of size 3. Any two distinct elements of S have at most one common element. Show that S cannot have more than n(n-1)/6 elements. Find a set S with n(n-4)/6 elements.

Solution

Solution by Robert Israel

Let T be the set of all pairs which are contained in an element of S. Each member of S gives rise to 3 pairs and the pairs corresponding to each member of S must be distinct (otherwise two members of S would have more than one common element). Hence T has 3S elements. But the total number of available pairs is n(n-1)/2, so S ≤ n(n-1)/6.

The next part is harder. Let S be the set of all triples {a, b, c} whose sum is divisible by n (and with a, b, c unequal). We show that S has n(n-3)/6 members.

There are n(n-1) ordered pairs (a, b) with a and b unequal. We can then require c = n - a - b mod n, so c is uniquely determined. However, in n cases we will get c = a (for each a there is a unique b such that 2a + b = n), and in n cases we will get c = b. These may overlap, but certainly there are at least n² - 3n ordered triples (a, b, c) where a, b, c are all unequal. Hence there are n(n-3)/6 unordered sets {a, b, c} with a, b, c all unequal and a + b + c = n. Obviously two such sets cannot have just two elements in common.

Note on Steiner and Kirkman Triple Systems

If |S| = n(n-1)/6, then S is called at Steiner triple system. It is well-known that such systems exist iff n = 1 or 3 mod 6. That is harder to prove. The standard approach is induction. The inductive step is to show that if a system is possible for n, then one is also possible for 2n+1 and for 2n+7. This is sufficient. For suppose we have proved the result for m < n and n = 1 mod 6. If n = 12k + 1, then n = 2(6k - 3) + 7, whilst if n = 12k + 7, then n = 2(6k + 3) + 1. Similarly if n = 12k + 3, then n = 2(6k + 1) + 1, whilst if n = 12k + 9, then n = 2(6k + 1) + 7.

n to 2n+1 is easy. Take A to be a collection of triples of {1, 2, ... , n} which form a Steiner system. Take X = {x₁, x₂, ... , x_n, y₁, y₂, ... , y_n, z}. Take as the collection of triples from X: (1) the n triples {z, x_i, y_i}, (2) the n(n-1)/6 triples {x_i, x_j, x_k}, where ijk is in A, (3) the 3n(n-1)/6 triples {x_i, y_j, y_k}, where ijk is in A. A little reflection shows that this is a Steiner triple system.

n to 2n+7 is harder and not given here. We require n > 3. As our starting values we need n = 3 (obvious), n = 7 (fairly obvious), n = 9 (fairly obvious), n = 13 (less obvious). These are exhibited below.

n = 7     n = 9           n = 13              n = 15

(unique) (unique)         1 of 2            1 of several

1 2 3     1 2 3     1  2  3   1  7 13     1  2  3   1  8 14

1 4 5     4 5 6     1  4  5   1  9 12     4  5  6   2  6  9

1 6 7     7 8 9     1  6  8   1 10 11     7  8  9   3  7 12

2 4 6               2  8 13   2  4  6    10 11 12   4 10 13

2 5 7     1 4 7     2 11 12   2  5  7    13 14 15   5 11 15

3 4 7     2 5 9     3  5 12   2  9 10

3 5 6     3 6 8     3  9 13   3  4  7     1  4  7   1  9 11

                    4  9 11   3  6 11     2  5 14   2  8 10

          1 5 8     4 10 13   3  8 10     3  6 11   3  4 15

          2 6 7     5  6 10   4  8 12     8 12 13   5  7 13

          3 4 9     6  7  9   5  8  9     9 10 15   6 12 14

                    7 10 12   5 11 13

          1 6 9     7  8 11   6 12 13     1  5 10   1 12 15

          2 4 8                           2  4 12   2 11 13

          3 5 7                           3  9 13   3  5  8

                                          6  8 15   4  9 14

                                          7  11 14  6  7 10

                                          

                                          1  6 13

                                          2  7 15

                                          3 10 14

                                          4  8 11

                                          5  9 12

Note that the systems for n = 9 and 15 are also Kirkman triple systems (meaning that the triples can be partitioned into (n-1)/2 sets each containing all the points just once). Proving that this is always possible for n=3 mod 6 is harder.

6th Balkan 1989