In a school, $n$ clubs must be formed, with $n \geq 3$ and each with 3 members, such that for each pair of clubs there is exactly one student who is a member of both.

a) Give an example of a distribution of 7 clubs that satisfy the mentioned conditions.

b) Verify that if a student belongs to 4 clubs, then he must belong to all the others.

c) Determine the minimum value of $n$ such that for any set of clubs that satisfy these conditions, it is mandatory for one student to be in all of them.
Solution

a) Naming the students as $A, B, C, D, E$ and $F$, the following sets represent 7 clubs that meet the conditions stated:

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

b) Suppose student $A$ belongs to the following 4 clubs:

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

Suppose there exists a club $K$ formed by students $\{M, N, P\}$ of which $A$ is not a part. Then, $K$ must have at least one element from each of the following 4 disjoint sets:

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

This is a contradiction, because for this to happen, $K$ would need to have at least 4 elements. Therefore, $A$ must belong to all clubs.

c) We claim that the minimum value is $n=8$. From the previous item, it suffices to verify that in this case some student must belong to at least 4 clubs. Suppose this does not happen, that is, that each student belongs to at most 3 clubs and consider a generic club $w$ formed by students $\{X, Y, Z\}$. Each of the elements of $w$ can be in at most 2 more clubs. Since any other club must share a student in common with $w$, counting the other clubs that contain $X, Y$ or $Z$, we conclude that there can be at most $2+2+2=6$ other distinct clubs besides $w$. Thus, the total number of clubs would be at most $6+1=7$, which is a contradiction.

Comment: It is possible to construct the example from item a) by considering the segments and the circle of the Fano diagram, as illustrated below. In it, each segment passing through 3 marked points and the central circle represent a club. Note that these segments and the central circle have a point of intersection.

![](https://cdn.mathpix.com/cropped/2024_05_01_12f29789e10e6749ebb9g-13.jpg?height=362&width=399&top_left_y=1955&top_left_x=911)