3. Determine the largest natural number $n$ for which there exist distinct sets $S_{1}, S_{2}, \ldots, S_{n}$ such that:

$1^{\circ}\left|S_{i} \cup S_{j}\right| \leqslant 2004$ for any two integers $1 \leqslant i, j \leqslant n$, and

$2^{\circ} S_{i} \cup S_{j} \cup S_{k}=\{1,2, \ldots, 2008\}$ for any three integers $1 \leqslant i<j<k \leqslant n$.

(Ivan Matic)

## SERBIAN MATHEMATICAL OLYMPIAD

competition of high school students in mathematics

Novi Sad, 14.04.2009.

## Second day
3. Each set $S_{i}$ has at most 2003 elements. Indeed, if $\left|S_{i}\right|=2004$, then from condition $1^{\circ}$ it follows that $S_{j} \subset S_{i}$ for all $j$, contradicting condition $2^{\circ}$. Consider the sets

$$
G_{\{i, j\}}=\{1,2, \ldots, 2008\} \backslash\left(S_{i} \cup S_{j}\right) \quad \text { for } 1 \leq i, j \leq n
$$

Then $\left|G_{\{i, j\}}\right| \geqslant 4$ and all $\binom{n}{2}$ sets $G_{\{i, j\}}$ are mutually disjoint (otherwise, if $x \in G_{\{i, j\}} \cap G_{\{k, l\}}$, then $x \notin S_{i} \cup S_{j} \cup S_{k} \cup S_{l}$, which is impossible if at least three of $i, j, k, l$ are distinct). It follows that $4\binom{n}{2} \leqslant 2008$, from which $n \leqslant 32$.

We will construct 32 sets that satisfy $1^{\circ}$ and $2^{\circ}$. Decompose the set $\{1,2, \ldots, 2008\}$ arbitrarily into $\binom{32}{2}=496$ (disjoint) sets $G_{\{i, j\}}$, where $\left|G_{\{i, j\}}\right| \geqslant 4$ for $1 \leqslant i, j \leqslant 32$, and define

$$
S_{i}=\{1,2, \ldots, 2008\} \backslash \bigcup_{j \neq i} G_{\{i, j\}} \quad \text { for } i=1, \ldots, 32
$$

Condition $1^{\circ}$ is automatically satisfied. Moreover, each $s \in\{1,2, \ldots, 2008\}$ belongs to at most one of the sets $G_{\{p, q\}}$, which means that there are at most two sets $S_{i}$ that do not contain it (these are $S_{p}$ and $S_{q}$), so condition $2^{\circ}$ is also satisfied. Therefore, the answer is $n=32$.