Suppose $X$ is a set with $|X| = 56$. Find the minimum value of $n$, so that for any 15 subsets of $X$, if the cardinality of the union of any 7 of them is greater or equal to $n$, then there exists 3 of them whose intersection is nonempty.
Problem
Source: China NMO 2006, Problem 6
Tags: combinatorics unsolved, combinatorics
29.01.2006 20:15
I think it's 41. First, let us prove $n=41$ is good. Take $A_{1},A_{2},...,A_{15} \subseteq [56]$ such that $|A_{i_{1}} \cup ... \cup A_{i_{7}}| \geq 41$. Suppose by way of contradiction that every element of $X$ occurs in at most 2 sets. If there is some $x \in X$ which belongs to a single $A_{i}$, you can add this $x$ to some other $A_{j}$ without affecting the property that the union of any 7 is at least 41, so suppose WLOG that every element of $X$ occurs in exactly 2 sets. Take a graph $G$ with vertices $1,2,...,15$ in which vertices $i$ and $j$ are connected iff $A_{i} \cap A_{j} \neq \emptyset$. It is clear that $G$ has exactly 56 edges. We know that for any 7 vertices, the number of edges which have at least one endpoint among these 7 vertices is at least 41, hence for any 8 vertices, the number of edges which have both endpoints among them is at most 56-41=15. Consider some vertice $v$ whose degree is $\deg v$. By our last observation, the number of edges among these 14 points is \[ 56-\deg v \leq 15 \frac{{14 \choose 2}}{{8 \choose 2}} = 48.75 \Rightarrow \deg v \geq 8, \forall v \in V. \] Hence $112 = 2|E| \geq 8 \times 15=120$, a contradiction. To create a counterexample for $n=40$, just select some sets $A_{i}$ such that our graph $G$ is a $K_{8,7}$. I hope it's correct.
02.02.2006 05:53
Quote: It is clear that has exactly 56 edges I don't understand.What is$K_{8,7}$?
02.02.2006 08:01
The complete bipartite graph with 8 and 7 vertices, having $8\cdot 7 = 56$ edges between them.
03.02.2006 05:57
thank you.I understood
10.02.2006 02:36
Quote: We know that for any 7 vertices, the number of edges which have at least one endpoint among these 7 vertices is at least 41 . It'll be absolutely true if $|A_{i_j}\cap A_{i_k}|\le1$. But if there are $i; k$such that $|A_{i_j}\cap A_{i_k}|\ge 2$ then the number of edges which at least one endpoint among $A_{i_1};A_{i_2};...;A_{i_7}$is not necessary $\ge 41$. Example: $A_1=\{1;2;...;8\}$ $A_2=\{9;10;...;16\}$ $A_3=\{17;18;...;24\}$ $A_4=\{25;...;32\}.$ $A_5=\{1;9;17;25;33;34;35\}$ $A_6=\{2;10;18;26;36;37;38\}$ $A_7=\{3;4;19;27;39;40;41\}$ The number of edges is 40 because $A_1$ and $A_7$ have "two" edges between them.
10.02.2006 13:36
You are right. What I wanted to say is that every element of $X$ is represented in $G$ by an edge whose endpoints are the indices of the 2 sets containing it. That means that I should have constructed $G$ as a multigraph, but obviously that doesn't change the proof.
11.02.2006 02:48
Yes, so did I. And it's nice problem and solution is nice,too.