Prove that at least $4$ persons are common

Question

In an assembly of $30$ persons, $300$ groups are formed. Each group contains $10$ persons each. Prove that one can find two groups having at least $4$ common members.

My approach is that first I'll take any three disjoint sets of persons and then I'll form the $4th$ set and I'll show that we need at least $4$ persons from any one of the previous groups to form the $4th$ set. Since the statement is true in the worst case, it must be true in all other cases.

---

Suppose the names of persons are $S_1,\cdots,S_{30}$ and WLOG assume that the disjoint groups we form are $S_1\to S_{10}$ and $S_{11}\to S_{20}$ and $S_{21}\to S_{30}$

Now to form the $4th$ set, select any worst case (least number of common people that are possible). One such is $S_1,S_{11},S_{21},S_2,S_{12},S_{22},S_3,S_{13},S_{23},S_4$ We see that this group and the $1st$ group have at least $4$ common members. Hence proved.

Is my approach and proof correct$?$ If not please tell the correct method. Basically I just proved the statement in the case where there were least number of common people (like in first three groups none and then in $4th$ one only $4$ people, no extra).

Answer 1

This is how the hint given in bof's comment leads to a solution.

Imagine that there are $\binom{30}4$ urns. Each urn is labeled with a subset of four people, such that each possible subset appears on exactly one urn.

Number the groups from $1$ to $300$. For each group numbered $i$, we place a token labeled with $i$ in every urn whose label is a subset of group number $i$. Since the group has $10$ people, there are $\binom{10}4$ labels which are subsets of group number $i$, so each group causes $\binom{10}4$ tokens to be placed.

There are $300\cdot \binom{10}4$ tokens placed into $\binom{30}4$ urns. Since $300\cdot \binom{10}4>\binom{30}4$, there must be some urn which has two or more tokens in it. These two tokens must have different labels, say $i$ and $j$, which implies that groups numbered $i$ and $j$ have four people in common.

Answer 2

Any solution that starts off with "This is how things must be arranged" or "This is definitely the worst case", without providing further justification, triggers alarm bells in my head.

I agree that if we're able to find 3 completely disjoint groups, then your proof works. However, this is not guaranteed, and you'd have to consider numerous other cases.
EG It might be possible that each of the 300 groups contain the first person. (This case also has an easy argument, but then you still have a lot of in-between cases to consider.)

---

Set up the standard incidence matrix where the rows correspond to the 300 groups, and the columns correspond to the 30 people. We put a 1 if that person is in the group.

Proof by contradiction. Suppose no two groups have at least 4 common members.

We count the number of column pairs ${ 1 \choose 1 }$.

Since any two groups have at most 3 members in common,

hence there are at most $ 3 \times { 300 \choose 2 } = 134550 $ column pairs.

Since each row has 10 1's, so there are 3000 1's in total.
Let person $i$ belong to $r_i$ groups with $ \sum r_i = 3000$.
The number of column pairs is $ \sum { r_i \choose 2 } $,

which is $\geq 30 \times {100 \choose 2 } = 148500$ by convexity.

Thus, we have a contradiction.
So there is some pair of groups with at least 4 common members.