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:

1∘∣Si∪Sj∣⩽20041^{\circ}\left|S_{i} \cup S_{j}\right| \leqslant 2004 for every two integers 1⩽i,j⩽n1 \leqslant i, j \leqslant n, and

2∘Si∪Sj∪Sk={1,2,…,2008}2^{\circ} S_{i} \cup S_{j} \cup S_{k}=\{1,2, \ldots, 2008\} for every three integers 1⩽i<j<k⩽n1 \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 1∘1^{\circ} it follows that Sj⊂SiS_{j} \subset S_{i} for all jj, contrary to condition 2∘2^{\circ}. Consider the sets
G{i,j}={1,2,…,2008}\(Si∪Sj) for 1≤i,j≤n 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 x∈G{i,j}∩G{k,l}x \in G_{\{i, j\}} \cap G_{\{k, l\}}, then x∉Si∪Sj∪Sk∪Slx \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 n⩽32n \leqslant 32.

We will construct 32 sets satisfying 1∘1^{\circ} and 2∘2^{\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 1⩽i,j⩽321 \leqslant i, j \leqslant 32, and define
Si={1,2,…,2008}\⋃j≠iG{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 1∘1^{\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 2∘2^{\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.