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.

  • 2
    $\begingroup$ 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? $\endgroup$ – Mike Pierce Jan 21 '15 at 18:34
  • $\begingroup$ @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.) $\endgroup$ – Brian M. Scott Jan 21 '15 at 18:35
  • $\begingroup$ For a finite set A, n(A) denote number of element of A. $\endgroup$ – kong Jan 21 '15 at 18:37
  • $\begingroup$ 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$? $\endgroup$ – Perry Elliott-Iverson Jan 21 '15 at 18:51
  • $\begingroup$ @Perry: Presumably the $A_i$ are required to be distinct. (If not, of course, you’ve found the desired disproof.) $\endgroup$ – 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.

  • $\begingroup$ @kong: You're very welcome. $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.