# A problem about pigeonhole principle or graph.

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.

• This might be just me, but I'm not familiar with the notation $n(A_i) = 3$ where it looks like you are using $n$ as a function. Previously $n$ was just the max of your set $A$. Can you explain this for me? – Mike Pierce Jan 21 '15 at 18:34
• @mapierce271: In context it’s clear that $n(A)$ is the cardinality of $A$. (This makes the use of $n$ as the largest element of $A$ mildly annoying, but it’s not really all that hard to keep them straight.) – Brian M. Scott Jan 21 '15 at 18:35
• For a finite set A, n(A) denote number of element of A. – kong Jan 21 '15 at 18:37
• Maybe I'm missing something, but doesn't $A_1 = A_2 = A_3 = A_{n+1} = \{1,2,3\}$, and $A_i = \{1,2,i\}$ for $i \in \{4,5,\dots n\}$ satisfy the properties you've specified, and for each $A_i$ and $A_j$, $|A_i \cap A_j| \neq 1$? – Perry Elliott-Iverson Jan 21 '15 at 18:51
• @Perry: Presumably the $A_i$ are required to be distinct. (If not, of course, you’ve found the desired disproof.) – Brian M. Scott Jan 21 '15 at 18:52

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.

• @kong: You're very welcome. – Brian M. Scott Jan 25 '15 at 12:26

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$.

• $n(A_i)=3$ for all $i$. Why there exist sets with unique elements?? – kong Jan 22 '15 at 2:48