Given are $50$ distinct sets of positive integers, each of size $30$, such that every $30$ of them have a common element. Prove that all of them have a common element.
Problem
Source: ARO Regional stage 2023 10.3=11.3
Tags: combinatorics, Russia
08.04.2023 17:11
We'll show that we can find a set of $k$ sets with a common element , where $30 \leq k \leq 50$. To show that we can find such a set for $k=31$ , take a set $B$ , there are now $\binom{49}{29}>30$ ways to form a set of $30$ sets with $B$ in it , therfore some common element much have appeared at least twice , and the overlap of two such sets of $30$ sets will certainly have more than $31$ elements. Suppose we have a set of $n (\geq 31)$ sets with a common element, and we wish to extend it to $n+1$ sets.Take the set of $n$ sets $\{A_i\}$ with their common element $x$.Let $A$ be another set.We now form a set $S$ of sets with $n$ sets each as : take $A$ common in all those sets and take the remaining $n-1$ sets from the $\{A_i\}$, so we get exactly $\binom{n}{n-1} =n$ sets .If $x$ is a common element in any of these sets , then $x$ is a common element in $\{A_i+A\}$ and we are done.The number of sets in $S$ with $A_1$ in them is $\binom{n-1}{n-2}=n-1\geq30$.Now if $x$ is not a common element in any of them , then by PHP some $y$ among the other $29$ elements of $A_1$ must have appeared at least twice as a common element, and the union of any two sets of $S$ gives $\{A_i+A\}$ , and this is now a set of $n+1$ elements with $y$ as a common element and we are done
17.06.2023 17:01
Some steps of my solution: Let all of them don't have a common element and sets are $A_1,A_2....A_{50}$ $1.$ For all $30$ sets from $A_1,A_2....A_{50}$ define $k$ is the least number of common element. (Where $1 \leq k \leq30$) $2.$ There isn't a $29$ sets with $k$ common element. $3.$ And we can see that there is $31$ sets which use the same $31$ element. $4.$ Finally take another set different from these $31$ sets and easily to see there is a $29$ sets in these $31$ set which supplies there is no common element of these $30$ sets. contradiction
17.06.2023 17:06
Another approach is if two sets have $k$ common element where $1 \leq k \leq 28$ and let the common elements are $a_1,a_2,......a_k$ we define another set which don't have $a_i$ is $S_i$. If we choose these 2 sets and $S_1,S_2....S_k$ we can see there isn't common element. So all sets have 29 common element with all sets.