Some students from a school were divided into teams satisfying the following conditions:

i) Any 2 different teams have exactly 2 members in common.

ii) Every team has exactly 4 members.

iii) For any 2 students, there is a team of which neither is a member.

a) Explain why any pair of students can participate in at most 3 teams.

b) What is the maximum number of teams?

#
Solution

a) Suppose there are students $A$ and $B$ participating in 4 teams called $E_{1}, E_{2}$, $E_{3}$, and $E_{4}$:

$$
\begin{aligned}
E_{1} & =\{A, B, C, D\} \\
E_{2} & =\{A, B, E, F\} \\
E_{3} & =\{A, B, G, H\} \\
E_{4} & =\{A, B, I, J\}
\end{aligned}
$$

By condition (iii), there exists a team $E_{5}$ that does not simultaneously have students $A$ and $B$. By condition (i), team $E_{5}$ must have exactly two members in common with $E_{1}, E_{2}, E_{3}$, and $E_{4}$. If $E_{5}$ does not have $A$ and $B$, then it must have elements from the following 4 disjoint sets $\{C, D\},\{E, F\},\{G, H\}$, and $\{I, J\}$. This forces $E_{5}$ to have more than 4 elements. Suppose $E_{5}$ does not have student $A$ but has student $B$ (since $A$ and $B$ play the same role in this analysis, the study we will do for $A$ is the same for $B$). Thus, $E_{5}$ must have at least one student from each of the same 4 sets mentioned earlier, and again this team will be forced to have more than 4 elements. This absurdity shows that any pair of students cannot participate in 4 teams.

b) Consider a pair of students ($A, B$) that participates in more than one team, whose existence is guaranteed by item (i), and study the following possibilities based on the information from the previous item.

1) The pair ($A, B$) participates in exactly three other teams called $E_{1}$, $E_{2}$, and $E_{3}$:

$$
\begin{aligned}
& E_{1}=\{A, B, C, D\} \\
& E_{2}=\{A, B, E, F\} \\
& E_{3}=\{A, B, G, H\}
\end{aligned}
$$

We will show that in this case, there cannot be more than 4 other teams. Repeating the argument from the previous item, if a team does not have $A$ and $B$, it will have all the elements of the set $\{C, D, E, F, G, H\}$, which produces an absurdity with condition (i). Therefore, all other teams must have $A$ or $B$, and by condition (i), any other team must have exactly one element from each of the three sets: $\{C, D\},\{E, F\}$, and $\{G, H\}$. Analyzing the possible combinations of the remaining 3 elements, in principle, we would have at most $2 \cdot 2 \cdot 2=8$ choices associated with the sets mentioned earlier. However, there are some pairs of choices that cannot be present simultaneously to satisfy condition (i):

$$
\begin{array}{ccc}
\{C, E, G\} & \text { and } & \{D, F, H\} \\
\{C, E, H\} & \text { and } & \{D, F, G\} \\
\{C, F, G\} & \text { and } & \{D, E, H\} \\
\{C, F, H\} & \text { and } & \{D, E, G\}
\end{array}
$$

Thus, there can be at most 4 more teams in addition to $E_{1}, E_{2}$, and $E_{3}$.
2) The pair $(A, B)$ participates in exactly two other teams called $E_{1}$ and $E_{2}$:

$$
\begin{aligned}
& E_{1}=\{A, B, C, D\} \\
& E_{2}=\{A, B, E, F\}
\end{aligned}
$$

Due to condition (i), the only team that cannot simultaneously have $A$ and $B$ is $\{C, D, E, F\}$. Considering a team distinct from it, again by item (i), one element from each of the sets $\{A, B\},\{C, D\}$, and $\{E, F\}$ must be present. This again generates $2 \cdot 2 \cdot 2=8$ choices that can be divided into the following pairs:

$$
\begin{array}{lcc}
\{A, C, E\} & \text { and } & \{B, D, F\} \\
\{A, C, F\} & \text { and } & \{B, D, E\} \\
\{A, D, E\} & \text { and } & \{B, C, F\} \\
\{A, D, F\} & \text { and } & \{B, C, E\}
\end{array}
$$

From each pair, only one choice can be present in the teams of students, and this shows that there can be at most 4 more teams that contain $A$ or $B$. Considering the two teams that contain $\{A, B\}$, the potential team $\{C, D, E, F\}$, and the possible 4 other teams, we have a total of at most $2+1+4=7$ teams.

In both cases, the maximum number of teams is 7. To show that it is possible to satisfy all three conditions with this number, it is sufficient to consider the following example:

$$
\{A, B, C, H\},\{A, D, F, H\},\{A, E, G, H\},\{B, D, G, H\},\{B, E, F, H\},\{C, D, E, H\},\{C, F, G, H\}
$$

where each letter, as before, represents a certain student.