IMO 1988/A2 solution

IMO 1988

Problem A2

Let n be a positive integer and let A₁, A₂, ... , A_2n+1 be subsets of a set B. Suppose that:
(i) Each A_i has exactly 2n elements,
(ii) The intersection of every two distinct A_i contains exactly one element, and
(iii) Every element of B belongs to at least two of the A_i.
For which values of n can one assign to every element of B one of the numbers 0 and 1 in such a way that A_i has 0 assigned to exactly n of its elements?

Solution

Answer: n even.

Each of the 2n elements of A_i belongs to at least one other A_j because of (iii). But given another A_j it cannot contain more than one element of A_i because of (ii). There are just 2n other A_j available, so each must contain exactly one element of A_i. Hence we can strengthen (iii) to every element of B belongs to exactly two of the As.

This shows that the arrangement is essentially unique. We may call the element of B which belongs to A_i and A_j (i,j). Then A_i contains the 2n elements (i, j) with j not i.

|B| = 1/2 x no. of As x size of each A = n(2n+1). If the labeling with 0s and 1s is possible, then if we list all the elements in each A, n(2n+1) out of the 2n(2n+1) elements have value 0. But each element appears twice in this list, so n(2n+1) must be even. Hence n must be even.

Next part thanks to Stan Dolan

Label (i,j) 0 if j = i-n/2, i-(n/2 - 1), ... , i-1, i+1, i+2, ... , i+n/2 (working mod 2n+1 when necessary). This clearly has the required property.

My original solution was a pedestrian induction:

We show by induction that a labeling is always possible for n even. If n = 2, there is certainly a labeling. For example, we may assign 0 to (1,2), (1,3), (2,4), (3,5), (4,5). Now suppose we have a labeling for n. For n + 2, we label (i , j) 0 if it was labeled 0 for n or if it is:
(i, 2n+2) or (i, 2n+3) for i = 1, 2, ... , n+1
(i, 2n+4) or (i, 2n+5) for i = n+2, n+3, ... , 2n+1
(2n+2, 2n+4), (2n+3, 2n+5), (2n+4,2n+5).
For i = 1, 2, ... n+1, A_i has n elements (i, j) labeled zero with j ≤ 2n+1 and also (i, 2n+2) and (i, 2n+3), giving n+2 in all. For i = n+2, n+3, ... , 2n+1, A_i has n elements (i, j) labeled zero with j ≤ 2n+1 and also (i, 2n+4) and (i, 2n+5), giving n+2 in all. A_2n+2 has the n+1 elements (i, 2n+2) with i <= n+1 and also (2n+2, 2n+4), giving n+2 in all. A_2n+3 has the n+1 elements (i, 2n+3) for i ≤ n+1 and also (2n+3, 2n+5), giving n+2 in all. A_2n+4 has the n elements (i, 2n+4) with n+2 ≤ i ≤ 2n+1 and also (2n+2, 2n+4) and (2n+4, 2n+5), giving n+2 in all. Finally A_2n+5 has the n elements (i, 2n+5) with n+2 ≤ i ≤ 2n+1 and also (2n+3, 2n+5) and (2n+4, 2n+5), giving n+2 in all.

Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

29th IMO 1988