A problem about pigeonhole principle or graph.

Question

Let $A=\{1,2,...,n\}$, where $\binom{n}{3}\geq n+1$. Let $A_1,A_2,...,A_{n+1}$ be distinct subsets of $A$ such that $\bigcup_{i=1}^{n+1}A_i=A$ and $n(A_i)=3$ for all $i$. How to prove or disprove that there exists $i,j$ such that $n(A_i\cap A_j)=1$.

I try to use formula $$n \left(\bigcup_{i=1}^{n+1}A_i\right) = \sum n(A_i) - \sum n(A_i\cap A_j)+\sum n(A_i\cap A_j\cap A_k)-...+(-1)^n n(A_1\cap A_2\cap ...\cap A_{n+1})$$, but it is unsuccessful.

I think this problem about pigeonhole principle or graph.

Thank in advances.

Answer 1

This is my approach, using the pigeonhole principle:

If $|A|=n$ and the number of subsets is exactly $n+1$, there will be $\big[\frac{n}{3}\big]$ sets with unique elements, $\big|A_i \cap A_j\big| = 0$, the rest of the sets $n+1-\big[\frac{n}{3}\big]$ will have $|A_i \cap A_j| > 0$.

Answer 2

Suppose that the result is false, and let $n$ be minimal for which a counterexample exists. Let $\mathscr{A}=\{A_1,\ldots,A_{n+1}\}$, and suppose that this is a counterexample: for any distinct $A_i,A_j\in\mathscr{A}$, either $A_i\cap A_j=\varnothing$, or $|A_i\cap A_j|=2$. Clearly it’s not possible for the family $\mathscr{A}$ to be pairwise disjoint, so without loss of generality assume, relabelling sets and points if necessary, that $A_1=\{1,2,3\}$ and $A_2=\{1,2,4\}$. Suppose that $A_i$ is another element of $\mathscr{A}$ that intersects $A_1$ in two points.

• Show that either $A_i\cap A_1=\{1,2\}$, or $A_i$ is one of the sets $\{1,3,4\}$ and $\{2,3,4\}$.

It follows that if $\mathscr{A}_1=\{A\in\mathscr{A}:A\cap A_1\ne\varnothing\}$, then either $\bigcup\mathscr{A}_1=\{1,2,3,4\}$ and $|\mathscr{A}_1|\le 4$, or $\bigcap\mathscr{A}_1=\{1,2\}$, and $\left|\bigcup\mathscr{A}_1\right|=|\mathscr{A}_1|+2$. Note that in both cases $|\mathscr{A}_1|\le\left|\bigcup\mathscr{A}_1\right|$, so $\mathscr{A}_1\subsetneqq\mathscr{A}$. Moreover, if $A\in\mathscr{A}\setminus\mathscr{A}_1$, then $A\cap\bigcup\mathscr{A}_1=\varnothing$.

Let $X=\{1,\ldots,n\}\setminus\bigcup\mathscr{A}_1$, and let $\mathscr{B}=\mathscr{A}\setminus\mathscr{A}_1$. Then $\mathscr{B}$ is a collection of $3$-element subsets of $X$, $|\mathscr{B}|\ge|X|+1$, and if $B_0$ and $B_1$ are distinct members of $\mathscr{B}$, then either $B_0\cap B_1=\varnothing$, or $|B_0\cap B_1|=2$. Let $\mathscr{B}_0$ be any subset of $\mathscr{B}$ of cardinality $|X|+1$; then $X$ and $\mathscr{B}_0$ are another counterexample, and $|X|<n$, contradicting the minimality of $n$. Thus, there cannot be a counterexample.