Maths Olympiad Prep

Library / /88 of 520

Combinatorics Difficulty 6.1 National olympiad Find the answer

Example 3 Let S={1,2,,15}S=\{1,2, \cdots, 15\}. From SS, take nn subsets A1,A2,,AnA_{1}, A_{2}, \cdots, A_{n}, satisfying the following conditions:
(1) Ai=7(i=1,2,,n)\left|A_{i}\right|=7(i=1,2, \cdots, n);
(2) AiAj3(1i<jn)\left|A_{i} \cap A_{j}\right| \leqslant 3(1 \leqslant i<j \leqslant n);
(3) For any 3-element subset MM of SS, there exists some AkA_{k} such that MAkM \subset A_{k}.
Find the minimum value of the number of such subsets nn. (40th IMO Chinese National Team Selection Exam Question)

A number or a short expression. Spacing and $ signs are ignored.

Solution

Analysis and Solution: From condition (1) Ai=7(i=1,2,,n)\left|A_{i}\right|=7(i=1,2, \cdots, n), we think of calculating the total number of times each element appears in all subsets S1S_{1}.

On the one hand, starting from each subset, we have S1=7nS_{1}=7 n. On the other hand, starting from each element, let the number of times i(i=1,2,,15)i(i=1,2, \cdots, 15) appears be rir_{i}, then we have S1=i=115riS_{1}=\sum_{i=1}^{15} r_{i}, so 7n=S1=i=115ri7 n=S_{1}=\sum_{i=1}^{15} r_{i}. We only need to find the range of i=115ri\sum_{i=1}^{15} r_{i}, a sufficient condition is to find the range of each rir_{i}. Without loss of generality, we first find the range of r1r_{1}.

From condition (3), we think of calculating the number of all 3-element subsets containing 1, S2S_{2}.
On the one hand, starting from the whole SS, we have S2=C142=91S_{2}=\mathrm{C}_{14}^{2}=91. On the other hand, considering all r1r_{1} subsets AiA_{i} containing 1, each such subset contains C62=15\mathrm{C}_{6}^{2}=15 3-element subsets containing 1, so there are a total of 15r115 r_{1} 3-element subsets containing 1. By condition (3), we know that such a calculation of 3-element subsets containing 1 does not miss any, so 15r1S2=9115 r_{1} \geqslant S_{2}=91, so r17r_{1} \geqslant 7. Similarly, for all i=1,2,,15i=1,2, \cdots, 15, we have ri7r_{i} \geqslant 7. Thus, 7n=i=115rii=1157=15×77 n=\sum_{i=1}^{15} r_{i} \geqslant \sum_{i=1}^{15} 7=15 \times 7, so n15n \geqslant 15.

When n=15n=15, let Ai={1+i1,2+i1,4+i1,5+i1,6+i1,11+i1,13+i1}(i=1,2,,15)A_{i}=\{1+i-1,2+i-1,4+i-1,5+i-1,6+i-1, 11+i-1,13+i-1\}(i=1,2, \cdots, 15), if the number in the set is greater than 15, then take the remainder of its division by 15 to replace it. It is not difficult to verify that these 15 sets meet all the conditions of the problem.

In summary, the minimum value of nn is 15.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.