Competition problem — Combinatorics

Library / /48 of 73

Combinatorics Difficulty 8.4 Shortlist Prove it Turkey

Given some collection of subsets $A_1, A_2, \dots$ of the set $A = \{1, 2, \dots, n\}$ we say that a subset $B \subset A$ is sparse if no $A_i \not\subset B$ . Suppose that for any collection $A_1, A_2, \dots$ , with $A_i \subset A$ , $|A_i| = 3$ , and $|A_i \cap A_j| \le 1$ ( $i \neq j$ ), any sparse set containing 29 elements can be expanded to 30 element set such that after this expansion the new set remains sparse. Find the largest possible value of $n$ .

Solution

Answer: $\binom{29}{2} + 29 + 1 = 436$ .
Let $n = 436$ and $B$ is a sparse set containing at most $k \le 29$ elements. Let us consider all $\binom{k}{2}$ two element subsets of $B$ . By conditions, each of these subsets can belong to at most one subset $A_i$ . If $B$ can not be extended by adding of some element $x \in (A - B)$ then there exists a subset $A_i$ containing $x$ and some two element subset of $B$ . Therefore, if $|A - B| > k + \binom{k}{2}$ then $B$ can be expanded without losing sparse property.
Let us show that $n > 29 + \binom{29}{2} = 435$ . Evidently, $n > 29$ . Let $A = \{1, 2, \dots, 29, \dots, k\}$ and $C = \{1, 2, \dots, 29\} \subset A$ . Each $A_i$ , $i = 1, 2, \dots$ will be defined as a union of different element of $A - C$ with different two element subset of $C$ . Then for each $k \le 29 + \binom{29}{2}$ the sparse set $C$ has no sparse expansion. Done.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.