Find maximum size of set family, where at least one member has at least one of any three points, but do not contains all those three points

Question

Let $n$ and $s$ be non-negative integers such that $n\geq 3$ and $2s\log2>3\log n$. Prove that there exists sets $A_1,A_2,\ldots,A_s \subseteq [n]$ such that
for every $B\in \binom {[n]} 3$ there exists $1 \leq j \leq s$ with both $A_j \cap B \neq \emptyset$ and $A_j \cap B \neq B$.
Should I start by counting the sets that do not either not intersect $B$ or contains $B$?

Answer 1

Roughly speaking: If we increase $s$ by $3$, we allow $n$ to grow by a factor of four. This suggests the following recursive procedure:

If $n=4k-r$ with $k\ge 1$ and $0\le r\le 3$, we may assume that $s-3$ sets suffice to solve that problem for three-element subsets of $[k]$ (and also for $[k-1]$). Thus let $A'_1,\ldots,A'_{s-3}\subseteq[k]$ and $A''_1,\ldots,A''_{s-3}\subseteq[k-1]$ be such sets. Let $$A_i=\begin{cases}4A'_i\cup(4A'_i+1)\cup(4A'_i+2)\cup(4A'_i+3)&\text{if }r=0,\\ 4A'_i\cup(4A'_i+1)\cup(4A'_i+2)\cup(4A''_i+3)&\text{if }r=1,\\ 4A'_i\cup(4A'_i+1)\cup(4A''_i+2)\cup(4A''_i+3)&\text{if }r=2,\\ 4A'_i\cup(4A''_i+1)\cup(4A''_i+2)\cup(4A''_i+3)&\text{if }r=3.\\ \end{cases}$$ Then the sets $A_1,\ldots, A_{s-3}$ solve the problem for all sets $B$ consisting only of numbers pairwise congruent modulo $4$. Add $A_{s-2}=4\mathbb Z\cap [n]$, $A_{s-1}=(4\mathbb Z+1)\cap [n]$, $A_{s}=(4\mathbb Z+2)\cap [n]$. Any three-element set $B$ that has elements from at least two resudue classes mod $4$, has one element in one of these three sets and another not in it.

To complete the proof, we need to verify the claim for some mall $n$. For $n\le 2$, the claim is vacuously true. From $n=3$ on, the condition implies $s\ge 3$, and hence the reduction works fine.