$S_1, \dots, S_6 \subseteq \{1,2,\dots,21\},$ prove either $|S_i \cap S_j| \ge 5$ or $|S_i^C \cap S_j^C| \ge 5$ for some $i,j.$

Question

Given subsets $S_1, \dots, S_6 \subseteq \{1,2,\dots,21\},$ I wish to prove either $|S_i \cap S_j| \ge 5$ or $|S_i^C \cap S_j^C| \ge 5$ for some $i \ne j.$

I started off by assuming $|S_i^C \cap S_j^C| \le 4$ for all $i \ne j.$ This gives us $|S_i \cup S_j| \ge 17$ for all $i \ne j,$ and we wish to find an intersection of size $\ge 5.$ I tried the probabilistic method, pigeonhole principle, and proof by contradiction, but none of these techniques worked.

So far I've gotten that if the result does not hold, we have $8 \le |S_i| \le 14$ for all $i,$ but I cannot rule out these cases. I also tried to draw segments within a $6 \times 21$ rectangle to find sets which violated the condition, and always failed by the time I got to the $5$th row, so maybe the bound isn't even that sharp. The problem with the probabilistic method is that $p(k \in S_i \, \& \, k \in S_j) \ne p(k \in S_i)p(k \in S_j)$ since the events are not independent. If you use conditional probabilities to fix this, you end up getting $\mathbb{E}(|S_i \cup S_j|) = \dots = \mathbb{E}(|S_i \cup S_j|).$ This problem is outside the realm of horseshoe combinatorics, so such an equality is not helpful. The issue with the pigeonhole principle is that while it will give you interesting bounds on numbers within $\{1,2,\dots,21\}$ appearing in at least this or that amount of sets $S_i,$ it will not produce a set of numbers appearing in two sets simultaneously; you might be drawing different numbers over and over.

Does anyone have a hint or idea about how to proceed? What would be the motivation behind a successful approach?

Answer 1

I have found a proof. Choices of $S_1, \dots, S_6$ correspond to coloring the squares of a $6 \times 21$ rectangle white or black according to whether the elements lie in $S_i$ or not. We want to find $2$ rows and $5$ columns such that the $10$ squares at the intersections of these rows and columns are all the same color. If a column has $k$ black squares and $6-k$ white pairs, it contains $\binom{6-k}{2} + \binom{k}{2} \ge 6$ monochromatic pairs. There are $2$ colors and $\binom{6}{2} = 15$ positions for a pair, so there are $30$ position-color combinations for a column pair. Since $6 \cdot 21 > 30 \cdot 4,$ some color and position combination appears at least $5$ times as desired.

Answer 2

Take the incidence matrix setup where rows correspond to $S_i$ and columns correspond to elements $j$. Place a 1 if $j \in S_i$, 0 otherwise.

We count column pairs of both types $1-1$ and $0-0$.
In each column, if there are $k$ ones, then there are $ { k \choose 2 } + { 6-k \choose 2 } \geq 6 $ column pairs.
So there are at least $ 21 \times 6 = 126 $ column pairs.

There are $ { 6 \choose 2 } = 15 $ pairs of rows, which contain these 126 column pairs.
By the PP, at least 1 pair of rows contains at least $ \lceil \frac{126}{15} \rceil = 9 $ pairs.
By the PP, at least $\lceil \frac{9}{2} \rceil = 5$ pairs are of the same type (either $1-1$ or $0-0$).
Translating back, this pair of subsets contain at least 5 elements in common ($1-1$), or not at all ($0-0$).