3. Determine the largest positive integer $n$ for which there exist pairwise different sets $S_{1}, S_{2}, \ldots, S_{n}$ with the following properties:

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

$2^{\circ} S_{i} \cup S_{j} \cup S_{k}=\{1,2, \ldots, 2008\}$ for any $1 \leq i<j<k \leq n . \quad$ (Ivan Matić)

Time allowed: 270 minutes.

Each problem is worth 7 points.

Novi Sad, 14.04.2009.

## Second Day
3. Each $S_{i}$ has at most 2003 elements. Indeed, if some $\left|S_{i}\right|=2004$, then $S_{j} \subset S_{i}$ for all $j$, which is impossible. Consider

$$
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 $G_{\{i, j\}} \subseteq S_{k}$ for any pairwise distinct indices $i, j, k$, and $G_{\{i, j\}} \cap G_{\{k, l\}} \subseteq S_{k} \cap G_{\{k, l\}}=\emptyset$ whenever $i \neq j, k \neq l$ and $\{i, j\} \neq\{k, l\}$. It follows that

$$
2008 \geq\left|\bigcup_{1 \leq i<j \leq n} G_{\{i, j\}}\right|=\sum_{1 \leq i<j \leq n}\left|G_{\{i, j\}}\right| \geq 4\binom{n}{2}
$$

hence $\binom{n}{2} \leq 501$, so $n \leq 32$.

Now we shall construct 32 sets satisfying $1^{\circ}$ and $2^{\circ}$.

Partition the set $\{1,2, \ldots, 1984\}$ arbitrarily into 496 (disjoint) 4-element subsets; denote these subjects $G_{\{i, j\}}, 1 \leq i<j \leq 496$ in an arbitrary manner. Define

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

Condition $1^{\circ}$ is automatically satisfied. Moreover, each $s \in\{1,2, \ldots, 2008\}$ belongs to at most one $G_{\{u, v\}}$ which is contained in $S_{r}$ for all $r \neq u, v$ (including at least one of $i, j, k$ for any distinct $i, j, k)$, so $s \in S_{i} \cup S_{j} \cup S_{k}$ for any $i<j<k$, which makes condition $2^{\circ}$ satisfied as well.

Therefore the largest $n$ satisfying the given conditions is $n=32$.