IMO 1988 SL 5

Let n be an even positive integer. Let A1, A2, . . . , An+1 be

imoshortlistmathematicsolympiad

IMO 1988 SL 5

Origin: CZS

Problem

Let n be an even positive integer. Let A1, A2, . . . , An+1 be sets having n elements each such that any two of them have exactly one element in common while every element of their union belongs to at least two of the given sets. For which n can one assign to every element of the union one of the numbers 0 and 1 in such a manner that each of the sets has exactly n/2 zeros?

Solution

Let n = 2k and let A = {A1, . . . , A2k+1} denote the family of sets with the desired properties. Since every element of their union B belongs to at least two sets of A, it follows that Aj = % i̸=j Ai \capAj holds for every 1 \leqj \leq2k+1. Since each intersection in the sum has at most one element and Aj has 2k elements, it follows that every element of Aj, i.e., in general of B, is a member of exactly two sets. We now prove that k is even, assuming that the marking described in the problem exists. We have already shown that for every two indices 1 \leqj \leq2k + 1 and i ̸= j there exists a unique element contained in both Ai and Aj. On a 2k \times 2k matrix let us mark in the ith column and jth row for i ̸= j the number that was joined to the element of B in Ai \capAj. In the ith row and column let us mark the number of the element of B in Ai \capA2k+1. In each row from the conditions of the marking there must be an even number of zeros. Hence, the total number of zeros in the matrix is even. The matrix is symmetric with respect to its main diagonal; hence it has an even number of zeros outside its main diagonal. Hence, the number of zeros on the main diagonal must also be even and this number equals the number of elements in A2k+1 that are marked with 0, which is k. Hence k must be even.

For even k we note that the dimensions of a 2k \times 2k matrix are divisible by 4. Tiling the entire matrix with the 4 \times 4 submatrix Q = ⎡ ⎢⎢⎣ 0 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 ⎤ ⎥⎥⎦, we obtain a marking that indeed satisfies all the conditions of the problem; hence we have shown that the marking is possible if and only if k is even.