We have many $\text{three-element}$ subsets of a $1000\text{-element}$ set. We know that the union of every $5$ of them has at least $12$ elements. Find the most possible value for the number of these subsets.
Problem
Source: Iran MO Third Round 2022 Mid-Terms P3
Tags: combinatorics, Sets, union
19.08.2022 14:31
19.08.2022 17:08
An interesting adaptation: We have many $\text{three-element}$ subsets of a $1000\text{-element}$ set. We know that the union of every $5$ of them has at most $12$ elements. Find the most possible value for the number of these subsets.
14.09.2022 09:12
Behanorm_rifghcky wrote: Case2.1:There exists a cycle in $G$. From (1) we know that the cycle must be a triangle,say $v_1v_2v_3$. Your solution is wrong. You can see a counterexample in my solution. Note that (1) is wrong.
14.09.2022 12:17
Mehrshad wrote: Behanorm_rifghcky wrote: Case2.1:There exists a cycle in $G$. From (1) we know that the cycle must be a triangle,say $v_1v_2v_3$. Your solution is wrong. You can see a counterexample in my solution. Note that (1) is wrong. Could you explain it more specifically? I don't know where disproves (1). @below thank you for pointing out my mistake!
14.09.2022 12:54
31.12.2022 17:08
A tricky induction! $\textcolor{red}{Claim:}$ If there are $N$ elements $N>10$ we can have at most $\frac{4N}{9}$ subsets. $\textcolor{red}{Proof:}$ Just control the small cases like $N<14$ to be safe and we apply strong induction. Suppose the induction is true for $N-1,N-2...,11$ Let us assume for $N$ sets we can achieve more than $\frac{4N}{9}$ sets. $\textcolor{green}{Lemma 1:}$ We can assume union of $4$ sets is at least $10$ elements. It is clear that their union cannot be less than $9$ elements. If you take any $4$ subsets and their union has $9$ elements. This means no other set intersects those $4$, otherwise $5$ sets would include less than 12 elements. So you can remove those $9$ elements and those $4$ sets and apply strong induction to the rest. $\textcolor{green}{Lemma 2:}$ We can assume union of any $3$ sets is at least $8$ $a)$ It is clear union of any $3$ sets is more than $5$ $b)$ If union of $3$ sets is $6$ this means if we take any other two sets they do not intersect. So maximum set number would be $\frac{N-6}{3}+3$ which is less than $\frac{4N}{9}$ while $N>13$. $c)$ If union of 3 sets $7$, since we assumed union of any $4$ sets is at least $10$, this means other sets does not intersect the first $3$ sets and since $\frac{7}{3}>\frac{9}{4}$ we can remove those $3$ sets and $7$ elements and apply induction on the rest. Now we can finish. If any two sets intersect, since we assumed union of any $3$ sets is at least $8$ elements, we can say that no other set intersect the first two sets. Since $\frac{5}{2}>\frac{9}{4}$ we can remove those $2$ sets and $5$ elements and apply induction on the rest. If no any two set intersect, it is clear we can only achieve $\frac{N}{3}$ sets.