IMO 1988 · Problem 2

Let \(n\) be a positive integer and let \(A_1, A_2, \ldots, A_{2n+1}\) be subsets of a set \(B\). Suppose that

(a) Each \(A_i\) has exactly \(2n\) elements,

(b) Each \(A_i \cap A_j\) \((1 \leq i < j \leq 2n+1)\) contains exactly one element, and

(c) 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?

Official text of the problem. Official problem paper (PDF)

Answer

Exactly the positive even integers \(n\).

Solution

We first prove that every element of \(B\) belongs to exactly two of the sets.

For \(x\in B\), let \(r(x)\) be the number of sets containing \(x\). Fix an index \(i\). Counting pairs \((x,j)\) with \(x\in A_i\cap A_j\) and \(j\ne i\), we obtain \[ \sum_{x\in A_i}\bigl(r(x)-1\bigr) =\sum_{j\ne i}|A_i\cap A_j| =2n. \] By (c), every summand on the left is at least \(1\). By (a), there are exactly \(2n\) summands. Consequently, every summand equals \(1\), so \(r(x)=2\) for every \(x\in A_i\). Since every element of \(B\) lies in some \(A_i\), the assertion follows.

For distinct indices \(i,j\), denote the unique element of \(A_i\cap A_j\) by \(b_{ij}=b_{ji}\). The preceding assertion shows that different unordered pairs of indices give different elements, and every element of \(B\) arises this way. Thus \[ A_i=\{b_{ij}:j\ne i\}. \]

Suppose a required assignment exists, and let \(Z\) be the set of elements assigned \(0\). The set \(B\) is finite because \(B=\bigcup_i A_i\). Counting incidences between elements of \(Z\) and the sets \(A_i\) gives \[ (2n+1)n=\sum_{i=1}^{2n+1}|Z\cap A_i|=2|Z|. \] Hence \((2n+1)n\) is even. Since \(2n+1\) is odd, \(n\) must be even.

Conversely, let \(n=2k\), where \(k\ge1\), and put \(m=2n+1=4k+1\). Regard the indices \(1,\ldots,m\) cyclically, modulo \(m\). Assign \(0\) to \(b_{ij}\) precisely when \[ j-i\equiv \pm1,\pm2,\ldots,\pm k\pmod m, \] and assign \(1\) otherwise. This rule is unchanged when \(i\) and \(j\) are interchanged, so it is well-defined.

For each fixed \(i\), the elements of \(A_i\) assigned \(0\) are precisely those corresponding to \[ j=i- k,\ldots,i-1,\ i+1,\ldots,i+k \pmod m. \] These \(2k\) indices are distinct and different from \(i\): their offsets are nonzero, and the difference between any two offsets has absolute value at most \(2k<m\). Thus exactly \(2k=n\) elements of every \(A_i\) receive \(0\), as required.

Therefore the assignment exists if and only if \(n\) is even.

The solution was checked against John Scholes' IMO solution archive (Kalva).