1
$\begingroup$

Let $F_1,F_2...F_{13}$ be sets such that $\forall 1\le i \le 13: F_i\subseteq [10]$ and $|F_i|=6$ when $[10]={1,2,3...10}$

prove that there are $1 \le j < k < l \le 13$ such that $|F_j \cap F_k \cap F_l| \ge 3$

It's pretty obvious I should use the Pigeonhole principle, but cluless to how should I get started?

$\endgroup$
1
$\begingroup$

I don't know if the question can be answered through the pigeonhole principle, but you can use double counting to solve this.

The way you can set this up is to make a table in which rows correspond to the $F_i$'s and the columns correspond to 3-element subsets of $[10]$. Then you can say that you will mark with a + a cell such that the 3-element set corresponding to that cell's column is a subset of the $F_i$ corresponding to that cell's row.

For example, it might look like:

$$\begin{array}{c|c c c c} & \{0,1,2\} & \{0,1,3\} & \cdots & \{8,9,10\}\\ \hline F_1&-&+&\cdots&-\\ F_2&+&+&\cdots&-\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ F_{13}&-&-&\cdots&+ \end{array}$$

What you can now proceed to do is count up the pluses both by rows and by columns. You should be able to find that when counted one way, the upper bound on the number of pluses when counted one way is smaller than the number of pluses when counted the other way.

$\endgroup$

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.