Maths Olympiad Prep

Library / /54 of 87

Combinatorics Difficulty 6.5 National Olympiad Prove it Serbia

Problem:

Determine the largest natural number nn for which there exist distinct sets S1,S2,,SnS_{1}, S_{2}, \ldots, S_{n} such that:

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

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

Solution

Solution:

Each set SiS_{i} has at most 2003 elements. Indeed, if Si=2004\left|S_{i}\right|=2004, then from condition 11^{\circ} it follows that SjSiS_{j} \subset S_{i} for all jj, contrary to condition 22^{\circ}. Consider the sets
G{i,j}={1,2,,2008}\(SiSj) for 1i,jn 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 G{i,j}4\left|G_{\{i, j\}}\right| \geqslant 4 and all (n2)\binom{n}{2} sets G{i,j}G_{\{i, j\}} are pairwise disjoint (otherwise, if xG{i,j}G{k,l}x \in G_{\{i, j\}} \cap G_{\{k, l\}}, then xSiSjSkSlx \notin S_{i} \cup S_{j} \cup S_{k} \cup S_{l}, which is impossible if at least three of i,j,k,li, j, k, l are distinct). It follows that 4(n2)20084\binom{n}{2} \leqslant 2008, whence n32n \leqslant 32.

We will construct 32 sets satisfying 11^{\circ} and 22^{\circ}. Let us partition the set {1,2,,2008}\{1,2, \ldots, 2008\} arbitrarily into (322)=496\binom{32}{2}=496 (disjoint) sets G{i,j}G_{\{i, j\}}, where G{i,j}4\left|G_{\{i, j\}}\right| \geqslant 4 for 1i,j321 \leqslant i, j \leqslant 32, and define
Si={1,2,,2008}\jiG{i,j} for i=1,,32 S_{i}=\{1,2, \ldots, 2008\} \backslash \bigcup_{j \neq i} G_{\{i, j\}} \quad \text{ for } i=1, \ldots, 32
Condition 11^{\circ} is automatically satisfied. Moreover, every s{1,2,,2008}s \in\{1,2, \ldots, 2008\} belongs to at most one of the sets G{p,q}G_{\{p, q\}}, which means that there exist at most two sets SiS_{i} that do not contain it (these are SpS_{p} and SqS_{q}), so condition 22^{\circ} is also satisfied. Therefore, the answer is n=32n=32.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from sr; metadata (topic, difficulty) added by this project.