Let \[M=\{1, 2, 3, \ldots, 2022\}\]Determine the least positive integer $k$, such that for every $k$ subsets of $M$ with the cardinality of each subset equal to $3$, there are two of these subsets with exactly one common element.
Problem
Source: Cyprus 2022 TST-2 Problem 4
Tags: combinatorics, Extremal combinatorics
22.02.2022 19:07
Say that a set of triples, $V$, is "good" iff each pair of triples $u,v\in V$ is disjoint or has two elements in common. Construct a graph $\mathcal{G}$ on good $V$ by drawing an edge $u\sim v$ between each $u,v\in V$ with $|u\cap v|=2$. The relation $\sim$ is obviously reflexive and, in a good graph, it's transitive as well. What do components of this graph look like? NB: we'll illustrate paths in what follows, not all other edges in the component. Case $1$: isolated vertices. This uses up $3$ elements of $M$ for the reward of only a single vertex (triple). Say it has "efficiency" $\eta_3 = \tfrac{1}{3}$, i.e. #triples divided by #$M$-elements. Case $2$: isolated component $u\sim v$. This has efficiency $\tfrac{2}{4}=\tfrac{1}{2}$. We'll never use this case. Case $3$: $\{a,b,c\}\sim\{a,b,d\}\sim\{a,c,d\}\sim\{b,c,d\}$. Note that after $\{a,c,d\}$, no further triple involving a new element together with any of $(a,b,c,d)$ is allowed, since any of them would clash (have intersection size 1) with an existing triple: \begin{tabular}{c|c} new &existing\\ \hline a,b,x & a,c,d \\ a,c,x & a,b,d \\ a,d,x & a,b,c \\ b,c,x & a,b,d \\ b,d,x & a,b,c \\ c,d,x & a,b,c \end{tabular}where $x$ is new. However, we can add $\{b,c,d\}$ without a clash, giving $\eta_4=1$. Case $4$: $\{a,b,c\}\sim\{a,b,d\}\sim\{a,b,e\}\sim\ldots$. All subsequent terms must be of the form $\{a,b,\star\}$ in order to avoid a return to case $3$ (which would immediately lead to a contradiction). Supposing this path consists of $k-2\ge 3$ triples, its efficiency is $\eta_k=\tfrac{k-2}{k}$. The most efficient way to group triples into components is therefore case 3, with $\eta_4=1$, followed by case 4, with case 1 useless unless we find ourselves with three elements of $M$ not yet assigned. To finish: if there are $q$ "case 3" components, then there are $2022-4q=2$ (unusable) or $6,10,14,\ldots$ elements of $M$ remaining to be packed into a "case 4" component, making for $4q+(2022-4q)\eta_{2022-4q}=\boxed{2020}$ triples.