Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.