1988 IMO Problems/Problem 2

Problem

Let $n$ be a positive integer and let $A_1, A_2, \cdots, 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\le i<j\le 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?

Solution

Answer: All $n$ such that $4|n$

We first make the following $2$ claims:

Claim $1$ : Each element of union belongs to exactly $2$ subsets.

Proof:

Consider a subset $A_i$ . Assume that some element $x \in\ A_i$ also $\in A_k, A_l$ . There are $n-1$ elements remaining in $A_i$ and there are $n-2$ subsets to choose from. By pigeon hole principle, at least $1$ of the remaining elements in $A_i$ must $\in A_k$ or $\in A_l$ . This contradicts the assumption that any $2$ subsets have only $1$ element in common.

Claim $2$ : $4|n$

Proof:

Now, since each element in $A_i \in$ exactly $1$ other subset, total number of elements present in the union = $n*(n+1)/2$ . If each subset must have $n/2$ elements assigned a value of $1$ , the total number of elements assigned value of $1$ = $n/2*(n+1)/2 = n*(n+1)/4$ . Thus $4$ must divide $n$ .

Now we make our final claim:

Claim $3$ : $4|n$ is a sufficient condition to assign every element of the union one of the numbers 0 and 1 in such a manner that each of the sets has exactly $\frac {n}{2}$ zeros.

Proof:

Consider a regular polygon consisting of $n+1$ vertices where each line joining two vertices $A_i, A_j$ represents the element which $\in A_i, A_j$ . Clearly there are a total of $n*(n+1)/2$ such lines representing the total number of elements of the union where each vertex is connected to $n$ vertices, meaning each of the $n$ elements of $A_i$ is part of $1$ other subset.

Starting with $i = 1$ , let us start coloring all lines joining vertices $A_i$ , $A_{i+1}$ with color Red, all lines joining $A_i$ , $A_{i+2}$ with color White, $A_i$ , $A_{i+3}$ with color Red, $A_i$ , $A_{i+4}$ with color White and so on ... $A_i$ , $A_{i+n/2}$ with color White.

Clearly each line from vertex $A_i$ alternates Red, White for first $n/2$ lines and then alternates White, Red for remaining $n/2$ lines implying that we could have exactly $n/2$ red lines emanating from each vertex $A_i$ . But these $n/2$ lines represent $n/2$ elements of each subset $A_i$ which could each be assigned a value of $0$ . This completes the proof.

- Kris17

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1988 IMO (Problems) • Resources
Preceded by Problem 1	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 3
All IMO Problems and Solutions

Page

Toolbox

Search

1988 IMO Problems/Problem 2

Problem

Solution

See Also