What is the maximum number of subsets of size $5$, taken from the set $A=\{1,2,3,...,20\}$ such that any $2$ of them share exactly $1$ element.
Problem
Source: Iranian Third Round 2020 Combinatorics exam Problem4
Tags: combinatorics, Sets, Subsets
19.11.2020 05:14
Redacted
19.11.2020 05:18
@Above, false. Your first and third subsets have no terms in common.
20.11.2020 17:55
Pluto1708 wrote: ... Your inequality gives $k \le 16$.
21.11.2020 16:05
The bounding for $16\geqslant k$ Is easy (prove that each $i$ comes at most $4$ times) Now for the subsets take: {1,2,3,4,5} {1,6,7,8,9} {1,10,11,12,13} {1,14,15,16,17} {2,6,10,14,18} {2,7,11,15,19} {2,8,12,16,20} {3,6,11,17,20} {3,8,13,15,18} {3,9,12,14,19} {4,6,13,16,19} {4,7,12,17,18} {4,9,10,15,20} {5,7,13,14,20} {5,9,11,16,18} {5,8,10,17,19}
21.11.2020 16:38
The sets $(4,9,10,15,20)$ and $(5,9,10,17,19)$ have two elements in common.
21.11.2020 17:36
It seems that i had made a typo, it’s fixed now
22.11.2020 03:43
as it shows that 16 is the maximum?
24.11.2020 10:39
Jjesus wrote: as it shows that 16 is the maximum? $B_{i}\subset A$ $(i=1,2,\cdots,n)$ s.t $|B_{i}|=5$, $|B_{i} \cap B_{j}|=1$ Let's double count the $good pair$ $((B_{i},B_{j}),k)$ $(1\leq i \leq n, 1 \leq k \leq 20)$ s.t $k \in B_{i},B_{j}$. We define the number of good pairs be $X$ (1) For any $(B_{i},B_{j})$, it belongs to exact one good pair considering the condition. So the Number of good pair is $X=\binom{n}{2}$ (2) For any element $k$, denote $d_{i}$ be the number of the set $B_{i}$ which it is belonged in. We can easily find the lower bound of $X=\sum_{i=1}^{20} d_{i} \geq 20 \cdot \binom{\frac{n}{4}}{2}$ by Cauchy-Schwarz Inequality. By (1),(2) It concludes $n \leq 16$
12.02.2021 17:19
$\color{red} \boxed{\textbf{claim:}}$ a number cannot be represented in $5$ or more subsets. $\color{green}\boxed{\textbf{proof:}}$ consider that a number like $1$ is appeared in more than $5$ subsets. Then it is trivial that we need at least $21$ different numbers, hence contradiction. \[\color{cyan} \rule{250mm}{2pt}\] $\color{red} \boxed{\textbf{claim:}}$ the desired number is less than $17$ $\color{green}\boxed{\textbf{proof:}}$ $\frac{4*20}{5}=16$ \[\color{cyan} \rule{250mm}{2pt}\] the rest is easy(actually the whole problem was easy), we just need to introduce a construction.$\boxed{Q.E.D}$