1988 IMO Problems/Problem 2

Revision as of 00:28, 15 March 2020 by KRIS17 (talk | contribs) (Solution)

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-1$ vertices, meaning each element of $A_i$ is part of $n-1$ other subsets.

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.

See Also

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