Let $A$ be a finite set, and $A_1,A_2,\cdots, A_n$ are subsets of $A$ with the following conditions: (1) $|A_1|=|A_2|=\cdots=|A_n|=k$, and $k>\frac{|A|}{2}$; (2) for any $a,b\in A$, there exist $A_r,A_s,A_t\,(1\leq r<s<t\leq n)$ such that $a,b\in A_r\cap A_s\cap A_t$; (3) for any integer $i,j\, (1\leq i<j\leq n)$, $|A_i\cap A_j|\leq 3$. Find all possible value(s) of $n$ when $k$ attains maximum among all possible systems $(A_1,A_2,\cdots, A_n,A)$.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
Sardor
30.07.2014 22:08
any solution ?
Qtaro
25.08.2020 15:58
$| A_r \cup A_s \cup A_t | = | A_r | + | A_s | + | A_t | - | A_r \cap A_s | - | A_s \cap A_t | - | A_t \cap A_r | + | A_r \cap A_s \cap A_t | $ For sets in condition 2 this gives $|A| \ge 3k - 9 + 2 \ge k + |A| + 1 - 9 + 2, k \le 6.$ if $k=6$, $|A| < 2k = 12$, also $|A| \ge 3k - 9 + 2 = 11$, $|A| = 11$. For any pair$\{ a, b \}(a \ne b)$, it is contained in at least 3 subsets. Every subset gives $\tbinom{k}{2}$ pairs, hence $n \cdot \tbinom{k}{2} \ge 3 \tbinom{|A|}{2}$ which gives $n \ge 11$. Consider pairs that contain the $i$-th element, let $a_i$ be the number of subsets containing the $i$-th element, then $ \sum a_i = nk$, $\sum_i \tbinom{a_i}{2} = \sum_{i<j} | A_i \cap A_j | \le 3 \tbinom{n}{2}$ Apply Cauchy's Inequality we get $n \le 11$. Example for $n = 11$: $A_i = \{ i, i+ 1, i + 2, i + 6, i + 8, i + 9\} (mod 11)$ element of $A$ can be viewed as point in unit circle, consider distance of two points in $A_i$, each possible distance $1,2,3,4,5$ appears exactly three times.