Combinatorics › Combinations and selections › Choosing with gaps

Minimum number of 7-subsets covering all triples

University · ●●●●○ 100 pts

Let S={1,2,…,15}S=\{1,2,\ldots,15\}. Choose nn subsets A1,A2,…,AnA_1,A_2,\ldots,A_n of SS such that: (i) ∣Ai∣=7|A_i|=7 for each ii; (ii) ∣Ai∩Aj∣≤3|A_i\cap A_j|\leq 3 for all 1≤i<j≤n1\leq i<j\leq n; (iii) for every 3-element subset MM of SS, there is some kk with M⊂AkM\subset A_k. Find the minimum possible value of nn.

Sign in to save your progress.

double countingextremal combinatoricsset systems