16 friends decided to form clubs. Each club will have 4 members, and any two clubs may have at most two member in common. What is the greatest/least possible number of clubs they can form.
Got 7 clubs (not sure if it is the maximum) I made it so every club contains members $A$ and $B$. Then there are 14 members left, so 7 clubs. How to show whether this is the maximum or not ? And minimum i think is 4 by letting exactly 4 diff members in each of the four club , all conditions are satisfied but i dont know how to show its the minimum
You can solve the problem via integer linear programming as follows. Let $n=16$. For each $4$-subset $C \subset\{1,\dots,n\}$, let binary decision variable $x_C$ indicate whether $C$ is selected. The problem is to maximize $\sum_C x_C$ subject to linear (conflict) constraints $$x_C + x_D \le 1 \quad \text{if $|C \cap D|>2$}.$$
You can also interpret this as finding a maximum independent set in a graph with one node per $4$-subset and an edge between each pair of subsets whose intersection has cardinality greater than two.
The maximum for general $n$ is given in https://oeis.org/A001843.